| 2008 |
|---|
| 33 | EE | Johannes Köbler,
Oleg Verbitsky:
From Invariants to Canonization in Parallel.
CSR 2008: 216-227 |
| 32 | EE | Oleg Verbitsky:
On the Double Coset Membership Problem for Permutation Groups
CoRR abs/0801.4911: (2008) |
| 31 | EE | Oleg Verbitsky:
Zero-Knowledge Proofs of the Conjugacy for Permutation Groups
CoRR abs/0801.4917: (2008) |
| 30 | EE | Mihyun Kang,
Oleg Pikhurko,
Alexander Ravsky,
Mathias Schacht,
Oleg Verbitsky:
Obfuscated Drawings of Planar Graphs
CoRR abs/0803.0858: (2008) |
| 29 | EE | Alexander Ravsky,
Oleg Verbitsky:
On collinear sets in straight line drawings
CoRR abs/0806.0253: (2008) |
| 28 | EE | Oleg Verbitsky:
On the obfuscation complexity of planar graphs.
Theor. Comput. Sci. 396(1-3): 294-300 (2008) |
| 2007 |
|---|
| 27 | EE | Oleg Verbitsky:
Planar Graphs: Logical Complexity and Parallel Isomorphism Tests.
STACS 2007: 682-693 |
| 26 | EE | Oleg Verbitsky:
On the Obfuscation Complexity of Planar Graphs
CoRR abs/0705.3748: (2007) |
| 25 | EE | 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) |
| 24 | EE | Oleg Pikhurko,
Joel Spencer,
Oleg Verbitsky:
Decomposable graphs and definitions with no quantifier alternation.
Eur. J. Comb. 28(8): 2264-2283 (2007) |
| 23 | EE | Frank Harary,
Wolfgang Slany,
Oleg Verbitsky:
On the Computational Complexity of the Forcing Chromatic Number.
SIAM J. Comput. 37(1): 1-19 (2007) |
| 2006 |
|---|
| 22 | EE | Martin Grohe,
Oleg Verbitsky:
Testing Graph Isomorphism in Parallel by Playing a Game.
ICALP (1) 2006: 3-14 |
| 21 | EE | 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) |
| 20 | EE | Martin Grohe,
Oleg Verbitsky:
Testing Graph Isomorphism in Parallel by Playing a Game
CoRR abs/cs/0603054: (2006) |
| 19 | EE | Oleg Verbitsky:
Planar Graphs: Logical Complexity and Parallel Isomorphism Tests
CoRR abs/cs/0607033: (2006) |
| 18 | EE | Johannes Köbler,
Oleg Verbitsky:
From Invariants to Canonization in Parallel
CoRR abs/cs/0608074: (2006) |
| 17 | EE | 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) |
| 2005 |
|---|
| 16 | EE | Frank Harary,
Wolfgang Slany,
Oleg Verbitsky:
On the Computational Complexity of the Forcing Chromatic Number.
STACS 2005: 182-193 |
| 15 | EE | 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) |
| 14 | EE | Oleg Verbitsky:
The first order definability of graphs with separators via the Ehrenfeucht game.
Theor. Comput. Sci. 343(1-2): 158-176 (2005) |
| 2004 |
|---|
| 13 | EE | Frank Harary,
Wolfgang Slany,
Oleg Verbitsky:
On Computational Complexity of the Forcing Chromatic Number
CoRR cs.CC/0406044: (2004) |
| 12 | EE | Frank Harary,
Wolfgang Slany,
Oleg Verbitsky:
On the lengths of symmetry breaking-preserving games on graphs.
Theor. Comput. Sci. 303(3): 427-446 (2004) |
| 2002 |
|---|
| 11 | EE | Uriel Feige,
Oleg Verbitsky:
Error Reduction by Parallel Repetition - A Negative Result.
Combinatorica 22(4): 461-478 (2002) |
| 2001 |
|---|
| 10 | EE | Frank Harary,
Wolfgang Slany,
Oleg Verbitsky:
A Symmetric Strategy in Graph Avoidance Games
CoRR cs.DM/0110049: (2001) |
| 9 | | Oleg Verbitsky:
Remarks on a Query-Based Variant of the Parallel Repetition Theorem.
Int. J. Found. Comput. Sci. 12(4): 517-532 (2001) |
| 1999 |
|---|
| 8 | | 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) |
| 1998 |
|---|
| 7 | EE | 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 |
| 1997 |
|---|
| 6 | EE | 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) |
| 1996 |
|---|
| 5 | EE | Uriel Feige,
Oleg Verbitsky:
Error Reduction by Parallel Repetition - a Negative Result.
IEEE Conference on Computational Complexity 1996: 70-76 |
| 4 | EE | Oleg Verbitsky:
Towards the Parallel Repetition Conjecture.
Theor. Comput. Sci. 157(2): 277-282 (1996) |
| 1995 |
|---|
| 3 | | Oleg Verbitsky:
On the Hardness of Approximating Some Optimization Problems That Are Supposedly Easier Than MAX CLIQUE.
Combinatorics, Probability & Computing 4: 167-180 (1995) |
| 2 | EE | Oleg Verbitsky:
The Parallel Repetition Conjecture for Trees is True
Electronic Colloquium on Computational Complexity (ECCC) 2(13): (1995) |
| 1994 |
|---|
| 1 | | Oleg Verbitsky:
Towards the Parallel Repetition Conjecture.
Structure in Complexity Theory Conference 1994: 304-307 |
