Oleg Verbitsky


Humboldt-Universität zu Berlin

Institut für Informatik

Unter den Linden 6

D-10099 Berlin

e-mail: [my surname (9 letters)] at informatik dot hu-berlin dot de

Expository talks and papers

Papers sorted by topics

Descriptive complexity

A warm-up: Suppose you have to describe a difference between two non-isomorphic graphs on n vertices each. You are allowed to apply existential and universal quantification over vertices and refer to adjacency and equality relations. You can easily write a statement of quantifier depth n that is true on one of the graphs and false on the other. Can you do it with a smaller quantifier depth? (The quantifier depth is the maximum number of nested quantifiers in your sentence. It is equal to the length of the Ehrenfeucht game on the graphs if the players play optimally.)

The graph isomorphism problem

If restricted to a particular class of graphs, the graph isomorphism problem can stay as hard as in general or can become solvable in polynomial time. In the latter case we want to know how efficiently we can actually solve it. Note that there is no complexity-theoretic obstacle for doing it in polylogarithmic parallel time: All what is known about the hardness of the graph isomorphism problem is that it is at least as hard as computing the determinant of an integer matrix (Jacobo Torán). Somewhat surprisingly, for some classes of graphs we can test isomorphism even in logarithmic space.

Ramsey problems (disclosing a hidden symmetry)

Hermann Weyl wrote "But seldom is asymmetry merely the absence of symmetry" (Symmetry, Princeton University Press, 1952). We made a few theorems from this truth.

Combinatorial games

Graph drawing

More papers on complexity theory