Expository talks and papers
Papers sorted by topics
Descriptive complexity
A warmup:
Suppose you have to describe a difference between two nonisomorphic 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.
Eprint (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. 339350 (2015).
 (with A.Krebs) Universal covers, color refinement, and twovariable logic with counting quantifiers: Lower bounds for the depth.
Proc. of LICS'15. pp. 689700 (2015).
 (with A.Atserias and A.Dawar) On the dynamic width of the 3colorability problem.
Eprint (2014).
 (with C.Berkholz and A.Krebs) Bounds for the quantifier depth in finitevariable logics: Alternation hierarchy. ACM Transactions on Computational Logic 16(3):21.121.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. 159170 (2013).
 (with O.Pikhurko)
Logical complexity of graphs: a survey. In:
Model Theoretic Methods in Finite Combinatorics,
Contemporary Mathematics, Vol. 558, pages 129179.
Americal Mathematical Society (2011).

Planar graphs: logical complexity and parallel isomorphism tests.
Proc. STACS'07. Vol. 4393 of LNCS, pp. 682693 (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:375400 (2007).
 (with O.Pikhurko and J.Spencer)
Decomposable graphs and definitions with no quantifier alternation.
European Journal of Combinatorics 28:22642283 (2007).
 (with M.Grohe)
Testing graph isomorphism in parallel by playing a game.
Proc. ICALP'06. Vol. 4051 of LNCS, pp. 314 (2006).
 (with O.Pikhurko and H.Veith)
The first order definability of graphs: upper bounds for quantifier depth.
Discrete Applied Mathematics 154:25112529 (2006).
 (with O.Pikhurko and J.Spencer)
Succinct definitions in the first order theory of graphs.
Annals of Pure and Applied Logic 139:74109 (2006).
 (with J.H.Kim, O.Pikhurko, and J.Spencer)
How complex are random graphs in first order logic?
Random Structures and Algorithms 26:119145 (2005).
 (with O.Pikhurko)
Descriptive complexity of finite structures: saving the quantifier rank.
Journal of Symbolic Logic 70:419450 (2005).

The first order definability of graphs with separators via the Ehrenfeucht game.
Theoretical Computer Science 343:158176 (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 complexitytheoretic 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. 2637 (2015).
 (with J.Köbler and S.Kuhnert)
On the isomorphism problem for Helly circulararc graphs. Information and Computation 247:266277 (2016).
 (with J.Köbler and S.Kuhnert)
Helly circulararc graph isomorphism is in Logspace.
Proc. MFCS'13. Vol. 8087 of LNCS, pp. 631642 (2013).
 (with J.Köbler and S.Kuhnert)
Circulararc 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 circulararc 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:4371 (2012).
 (with J.Köbler, S.Kuhnert, and B.Laubner)
Interval graphs: canonical representation in Logspace.
SIAM Journal on Computing 40(5):12921315 (2011).
Talk
at the CGT11.
 (with J.Köbler)
From invariants to canonization in parallel.
Proc. CSR'08. Vol. 5010 of LNCS, pp. 216227 (2008).

Planar graphs: logical complexity and parallel isomorphism tests.
Proc. STACS'07. Vol. 4393 of LNCS, pp. 682693 (2007).
 (with M.Grohe)
Testing graph isomorphism in parallel by playing a game.
Proc. ICALP'06. Vol. 4051 of LNCS, pp. 314 (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.
Combinatorial games
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. Eprint (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:789799 (2011).
 (with A.Ravsky)
On collinear sets in straight line drawings.
GraphTheoretic Concepts in Computer Science. Vol. 6986 of LNCS, pp. 295306 (2011).

On the obfuscation complexity of planar graphs.
Theoretical Computer Science 396:294300 (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:119 (2007).

Zeroknowledge 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:195205 (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. 351363 (2002).
 (with U.Feige)
Error reduction by parallel repetition  a negative result.
Combinatorica 22:461478 (2002).
 Remarks on a querybased variant of the parallel repetition theorem.
The International Journal of Foundations of Computer Science
12:517531 (2001).
 (with R.Raz, G.Tardos, and N.Vereshchagin)
ArthurMerlin games in boolean decision trees.
Journal of Computer and System Sciences 59:346372 (1999).
 Towards the parallel repetition conjecture.
Theoretical Computer Science 157:277282 (1996).
 On the hardness of approximating some optimization problems that are
supposedly easier than MAX CLIQUE.
Combinatorics, Probability and Computing 4:167180 (1995).
 On the possibility of performing any multiprover interactive
proof in a bounded number of rounds.
Izvestiya RAN, seriya matematicheskaya 57(3):152178 (1993).
In Russian.
English translation in:
Russian Academy of Sciences. Izvestiya. Mathematics. 42:561586 (1994).
 Optimal algorithms for coNPsets and the problem EXP=?NEXP.
Matematicheskie Zametki 50(2):3746 (1991).
In Russian.
English translation in: Math. Notes 50:796801 (1992).

