Oleg Verbitsky
Coordinates
Humboldt-Universität zu Berlin
Unter den Linden 6
D-10099 Berlin
e-mail: [my surname (9 letters)] at informatik dot hu-berlin dot de
Expository talks and papers
My lectures on A Logical approach to Isomorphism Testing and Constraint Satisfaction at the ESSLLI 2016.
(with O.Pikhurko) Logical complexity of graphs: a survey. In: Model Theoretic Methods in Finite Combinatorics,
Contemporary Mathematics, Vol. 558, pages 129-179. American Mathematical Society (2011).
Talk on First-order complexity of individual graphs at the FMT12.
(with J.Köbler and S.Kuhnert) Around and beyond the isomorphism problem for interval graphs. Bulletin of the EATCS 107:43-71 (2012).
(with T.Banakh and Y.Vorobets) A Ramsey treatment of symmetry. The Electronic Journal of Combinatorics, vol. 7 (2000).
(with T.Banakh and Y.Vorobets) Fermat's spiral and the line between Yin and Yang. American Mathematical Monthly 117(9):786-800 (2010). Illustrative applets to this paper are provided by Tom Leathrum in Loci and by Roice Nelson in his blog. French digests of this paper are written by Serge Cantat and El Jj.
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.)
(with M.Zhukovskii) The descriptive complexity of subgraph isomorphism in the absence of order. E-print (2016).
(with V.Arvind, J.Köbler, and G.Rattan) On the power of color refinement. Proc. of FCT'15. Vol. 9210 of LNCS, pp. 339-350 (2015).
(with A.Krebs) Universal covers, color refinement, and two-variable logic with counting quantifiers: Lower bounds for the depth. Proc. of LICS'15. pp. 689-700 (2015).
(with A.Atserias and A.Dawar) On the dynamic width of the 3-colorability problem. E-print (2014).
(with C.Berkholz and A.Krebs) Bounds for the quantifier depth in finite-variable logics: Alternation hierarchy. ACM Transactions on Computational Logic 16(3):21.1--21.26 (2015).
(with C.Berkholz) On the speed of constraint propagation and the time complexity of arc consistency testing. Proc. MFCS'13. Vol. 8087 of LNCS, pp. 159-170 (2013).
(with O.Pikhurko) Logical complexity of graphs: a survey. In: Model Theoretic Methods in Finite Combinatorics, Contemporary Mathematics, Vol. 558, pages 129-179. Americal Mathematical Society (2011).
Planar graphs: logical complexity and parallel isomorphism tests. Proc. STACS'07. Vol. 4393 of LNCS, pp. 682-693 (2007).
(with T.Bohman, A.Frieze, T.Luczak, O.Pikhurko, C.Smyth, and J.Spencer) First order definability of trees and sparse random graphs. Combinatorics, Probability and Computing 16:375-400 (2007).
(with O.Pikhurko and J.Spencer) Decomposable graphs and definitions with no quantifier alternation. European Journal of Combinatorics 28:2264-2283 (2007).
(with M.Grohe) Testing graph isomorphism in parallel by playing a game. Proc. ICALP'06. Vol. 4051 of LNCS, pp. 3-14 (2006).
(with O.Pikhurko and H.Veith) The first order definability of graphs: upper bounds for quantifier depth. Discrete Applied Mathematics 154:2511-2529 (2006).
(with O.Pikhurko and J.Spencer) Succinct definitions in the first order theory of graphs. Annals of Pure and Applied Logic 139:74-109 (2006).
(with J.-H.Kim, O.Pikhurko, and J.Spencer) How complex are random graphs in first order logic? Random Structures and Algorithms 26:119-145 (2005).
(with O.Pikhurko) Descriptive complexity of finite structures: saving the quantifier rank. Journal of Symbolic Logic 70:419-450 (2005).
The first order definability of graphs with separators via the Ehrenfeucht game. Theoretical Computer Science 343:158-176 (2005).
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.
(with V.Arvind, J.Köbler, and G.Rattan) On Tinhofer's linear programming approach to isomorphism testing. Proc. of MFCS'15. Vol. 9235 of LNCS, pp. 26-37 (2015).
(with J.Köbler and S.Kuhnert) On the isomorphism problem for Helly circular-arc graphs. Information and Computation 247:266-277 (2016).
(with J.Köbler and S.Kuhnert) Helly circular-arc graph isomorphism is in Logspace. Proc. MFCS'13. Vol. 8087 of LNCS, pp. 631-642 (2013).
(with J.Köbler and S.Kuhnert) Circular-arc hypergraphs: Rigidity via connectedness. Discrete Applied Mathematics, in press (2016).
(with J.Köbler and S.Kuhnert) Solving the canonical representation and Star System problems for proper circular-arc graphs in Logspace. Journal of Discrete Algorithms, in press (2016).
Talk on the SSP at the Nordic Workshop on Complexity, Kiel, 2012.
(with J.Köbler and S.Kuhnert) Around and beyond the isomorphism problem for interval graphs. Bulletin of the EATCS 107:43-71 (2012).
(with J.Köbler, S.Kuhnert, and B.Laubner) Interval graphs: canonical representation in Logspace. SIAM Journal on Computing 40(5):1292--1315 (2011).
Talk at the CGT11.
(with J.Köbler) From invariants to canonization in parallel. Proc. CSR'08. Vol. 5010 of LNCS, pp. 216-227 (2008).
Planar graphs: logical complexity and parallel isomorphism tests. Proc. STACS'07. Vol. 4393 of LNCS, pp. 682-693 (2007).
(with M.Grohe) Testing graph isomorphism in parallel by playing a game. Proc. ICALP'06. Vol. 4051 of LNCS, pp. 3-14 (2006).
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.
(with T.Banakh and Y.Vorobets) Fermat's spiral and the line between Yin and Yang. American Mathematical Monthly 117(9):786-800 (2010).
Illustrative applets to this paper are provided by Tom Leathrum in Loci and by Roice Nelson in his blog.
French digests of this paper are written by Serge Cantat and El Jj.
(with T.Banakh and Y.Vorobets) A Ramsey treatment of symmetry. The Electronic Journal of Combinatorics, vol. 7 (2000).
Structural properties of extremal asymmetric colorings. Algebra and Discrete Mathematics 4:92-117 (2003).
(with T.Banakh and I.Kmit) On asymmetric colorings of integer grids. Ars Combinatoria 62:257-271 (2002).
Symmetric subsets of lattice paths. INTEGERS: an electronic journal of combinatorial number theory 0(A05):1-16 (2000).
(with T.Banakh and Y.Vorobets) Ramsey-type problems for spaces with symmetry. Izvestiya RAN, seriya matematicheskaya 64(6):3-40 (2000). In Russian.
English translation in: Russian Academy of Sciences. Izvestiya. Mathematics. 64:1091-1127 (2000).
Combinatorial games
The first two papers address a mirror strategy for variations of the game of Sim (implemented as Hexi by Wolfgang Slany and Bidan Zhu).
(with F.Harary and W.Slany) On the lengths of symmetry breaking-preserving games on graphs. Theoretical Computer Science 313:427-446 (2004).
Talk at the RaTLoCC09.
(with F.Harary and W.Slany) A symmetric strategy in graph avoidance games. In: More Games of No Chance , Mathematical Sciences Research Institute Publications, Vol. 42, pp. 369-381, Cambridge University Press (2002).
The next paper was motivated by the Planarity Game (a download version is available here).
On the obfuscation complexity of planar graphs. Theoretical Computer Science 396:294-300 (2008).
I also wrote a lot about the Ehrenfeucht game (I miss an implementation of this fascinating game).
Graph drawing
(with S.Chaplick, K.Fleszar, F.Lipp, A.Ravsky, and A.Wolff) Drawing graphs on few lines and few planes. Proc. of GD'16 (2016).
(with S.Chaplick, K.Fleszar, F.Lipp, A.Ravsky, and A.Wolff) The complexity of drawing graphs on few lines and few planes. E-print (2016).
(with M.Kang, O.Pikhurko, A.Ravsky, and M.Schacht) Untangling planar graphs from a specified vertex position - Hard cases. Discrete Applied Mathematics 159:789-799 (2011).
(with A.Ravsky) On collinear sets in straight line drawings. Graph-Theoretic Concepts in Computer Science. Vol. 6986 of LNCS, pp. 295-306 (2011).
On the obfuscation complexity of planar graphs. Theoretical Computer Science 396:294-300 (2008).
More papers on complexity theory
(with F.Harary and W.Slany) On the computational complexity of the forcing chromatic number. SIAM Journal on Computing 37:1-19 (2007).
Zero-knowledge proofs of the conjugacy of permutation groups. Visn. L'viv. Univ., Ser. Mekh.-Mat. (Bulletin of the Lviv University, Series in Mechanics and Mathematics) 61:195-205 (2003).
On the double coset membership problem for permutation groups. In: Algebraic structures and their applications, Institute of Mathematics, Ukrainian Academy of Sciences, Kyiv, pp. 351-363 (2002).
(with U.Feige) Error reduction by parallel repetition - a negative result. Combinatorica 22:461-478 (2002).
Remarks on a query-based variant of the parallel repetition theorem. The International Journal of Foundations of Computer Science 12:517-531 (2001).
(with R.Raz, G.Tardos, and N.Vereshchagin) Arthur-Merlin games in boolean decision trees. Journal of Computer and System Sciences 59:346-372 (1999).
Towards the parallel repetition conjecture. Theoretical Computer Science 157:277-282 (1996).
On the hardness of approximating some optimization problems that are supposedly easier than MAX CLIQUE. Combinatorics, Probability and Computing 4:167-180 (1995).
On the possibility of performing any multi-prover interactive proof in a bounded number of rounds. Izvestiya RAN, seriya matematicheskaya 57(3):152-178 (1993). In Russian.
English translation in: Russian Academy of Sciences. Izvestiya. Mathematics. 42:561-586 (1994).
Optimal algorithms for coNP-sets and the problem EXP=?NEXP. Matematicheskie Zametki 50(2):37-46 (1991). In Russian.
English translation in: Math. Notes 50:796-801 (1992).