Oleg Verbitsky

Christoph Berkholz, Oleg Verbitsky: On the speed of constraint propagation and the time complexity of arc consistency testing. CoRR abs/1303.7077 (2013)

Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky: Solving the Canonical Representation and Star System Problems for Proper Circular-Arc Graphs in Logspace. FSTTCS 2012: 387-399

Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky: Solving the Canonical Representation and Star System Problems for Proper Circular-Arc Graphs in Log-Space. CoRR abs/1202.4406 (2012)

Christoph Berkholz, Oleg Verbitsky: Bounds for the quantifier depth in two-variable logic. CoRR abs/1212.2747 (2012)

Mihyun Kang, Oleg Pikhurko, Alexander Ravsky, Mathias Schacht, Oleg Verbitsky: Untangling planar graphs from a specified vertex position - Hard cases. Discrete Applied Mathematics 159(8): 789-799 (2011)

Johannes Köbler, Sebastian Kuhnert, Bastian Laubner, Oleg Verbitsky: Interval Graphs: Canonical Representations in Logspace. SIAM J. Comput. 40(5): 1292-1315 (2011)

Alexander Ravsky, Oleg Verbitsky: On Collinear Sets in Straight-Line Drawings. WG 2011: 295-306

Taras O. Banakh, Oleg Verbitsky, Yaroslav Vorobets: Fermat's Spiral and the Line Between Yin and Yang. The American Mathematical Monthly 117(9): 786-800 (2010)

Johannes Köbler, Sebastian Kuhnert, Bastian Laubner, Oleg Verbitsky: Interval Graphs: Canonical Representation in Logspace. ICALP (1) 2010: 384-395

Oleg Pikhurko, Oleg Verbitsky: Logical complexity of graphs: a survey. CoRR abs/1003.4865 (2010)

Johannes Köbler, Sebastian Kuhnert, Bastian Laubner, Oleg Verbitsky: Interval Graphs: Canonical Representation in Logspace. Electronic Colloquium on Computational Complexity (ECCC) 17: 43 (2010)

Oleg Verbitsky: On the obfuscation complexity of planar graphs. Theor. Comput. Sci. 396(1-3): 294-300 (2008)

Johannes Köbler, Oleg Verbitsky: From Invariants to Canonization in Parallel. CSR 2008: 216-227

Oleg Verbitsky: On the Double Coset Membership Problem for Permutation Groups. CoRR abs/0801.4911 (2008)

Oleg Verbitsky: Zero-Knowledge Proofs of the Conjugacy for Permutation Groups. CoRR abs/0801.4917 (2008)

Mihyun Kang, Oleg Pikhurko, Alexander Ravsky, Mathias Schacht, Oleg Verbitsky: Obfuscated Drawings of Planar Graphs. CoRR abs/0803.0858 (2008)

Alexander Ravsky, Oleg Verbitsky: On collinear sets in straight line drawings. CoRR abs/0806.0253 (2008)

Tom Bohman, Alan M. Frieze, Tomasz Luczak, Oleg Pikhurko, Clifford D. Smyth, Joel Spencer, Oleg Verbitsky: First-Order Definability of Trees and Sparse Random Graphs. Combinatorics, Probability & Computing 16(3): 375-400 (2007)

Oleg Pikhurko, Joel Spencer, Oleg Verbitsky: Decomposable graphs and definitions with no quantifier alternation. Eur. J. Comb. 28(8): 2264-2283 (2007)

Frank Harary, Wolfgang Slany, Oleg Verbitsky: On the Computational Complexity of the Forcing Chromatic Number. SIAM J. Comput. 37(1): 1-19 (2007)

Oleg Verbitsky: Planar Graphs: Logical Complexity and Parallel Isomorphism Tests. STACS 2007: 682-693

Oleg Verbitsky: On the Obfuscation Complexity of Planar Graphs. CoRR abs/0705.3748 (2007)

Oleg Pikhurko, Joel Spencer, Oleg Verbitsky: Succinct definitions in the first order theory of graphs. Ann. Pure Appl. Logic 139(1-3): 74-109 (2006)

Oleg Pikhurko, Helmut Veith, Oleg Verbitsky: The first order definability of graphs: Upper bounds for quantifier depth. Discrete Applied Mathematics 154(17): 2511-2529 (2006)

Martin Grohe, Oleg Verbitsky: Testing Graph Isomorphism in Parallel by Playing a Game. ICALP (1) 2006: 3-14

Martin Grohe, Oleg Verbitsky: Testing Graph Isomorphism in Parallel by Playing a Game. CoRR abs/cs/0603054 (2006)

Oleg Verbitsky: Planar Graphs: Logical Complexity and Parallel Isomorphism Tests. CoRR abs/cs/0607033 (2006)

Johannes Köbler, Oleg Verbitsky: From Invariants to Canonization in Parallel. CoRR abs/cs/0608074 (2006)

Oleg Pikhurko, Oleg Verbitsky: Descriptive complexity of finite structures: Saving the quantifier rank. J. Symb. Log. 70(2): 419-450 (2005)

Jeong Han Kim, Oleg Pikhurko, Joel H. Spencer, Oleg Verbitsky: How complex are random graphs in first order logic? Random Struct. Algorithms 26(1-2): 119-145 (2005)

Oleg Verbitsky: The first order definability of graphs with separators via the Ehrenfeucht game. Theor. Comput. Sci. 343(1-2): 158-176 (2005)

Frank Harary, Wolfgang Slany, Oleg Verbitsky: On the Computational Complexity of the Forcing Chromatic Number. STACS 2005: 182-193

Frank Harary, Wolfgang Slany, Oleg Verbitsky: On the lengths of symmetry breaking-preserving games on graphs. Theor. Comput. Sci. 303(3): 427-446 (2004)

Frank Harary, Wolfgang Slany, Oleg Verbitsky: On Computational Complexity of the Forcing Chromatic Number. CoRR cs.CC/0406044 (2004)

Taras O. Banakh, Ya. Kmit, O. V. Verbitsky: On Asymmetric Colorings of Integer Grids. Ars Comb. 62 (2002)

Uriel Feige, Oleg Verbitsky: Error Reduction by Parallel Repetition - A Negative Result. Combinatorica 22(4): 461-478 (2002)

Oleg Verbitsky: Remarks on a Query-Based Variant of the Parallel Repetition Theorem. Int. J. Found. Comput. Sci. 12(4): 517-532 (2001)

Frank Harary, Wolfgang Slany, Oleg Verbitsky: A Symmetric Strategy in Graph Avoidance Games. CoRR cs.DM/0110049 (2001)

Taras O. Banakh, O. V. Verbitsky, Yaroslav Vorobets: A Ramsey Treatment of Symmetry. Electr. J. Comb. 7 (2000)

Ran Raz, Gábor Tardos, Oleg Verbitsky, Nikolai K. Vereshchagin: Arthur-Merlin Games in Boolean Decision Trees. J. Comput. Syst. Sci. 59(2): 346-372 (1999)

Ran Raz, Gábor Tardos, Oleg Verbitsky, Nikolai K. Vereshchagin: Arthur-Merlin Games in Boolean Decision Trees. IEEE Conference on Computational Complexity 1998: 58-67

Ran Raz, Gábor Tardos, Oleg Verbitsky, Nikolai K. Vereshchagin: Arthur-Merlin Games in Boolean Decision Trees. Electronic Colloquium on Computational Complexity (ECCC) 4(54) (1997)

Oleg Verbitsky: Towards the Parallel Repetition Conjecture. Theor. Comput. Sci. 157(2): 277-282 (1996)

Uriel Feige, Oleg Verbitsky: Error Reduction by Parallel Repetition - a Negative Result. IEEE Conference on Computational Complexity 1996: 70-76

Oleg Verbitsky: On the Hardness of Approximating Some Optimization Problems That Are Supposedly Easier Than MAX CLIQUE. Combinatorics, Probability & Computing 4: 167-180 (1995)

Oleg Verbitsky: The Parallel Repetition Conjecture for Trees is True. Electronic Colloquium on Computational Complexity (ECCC) 2(13) (1995)

Oleg Verbitsky: Towards the Parallel Repetition Conjecture. Structure in Complexity Theory Conference 1994: 304-307