On the Hardness of Approximating Some Optimization Problems That Are Supposedly Easier Than MAX CLIQUE. - Oleg Verbitsky 001 (Comb. Probab. Comput., 1995)

The Parallel Repetition Conjecture for Trees is True - Oleg Verbitsky 001 (Electron. Colloquium Comput. Complex., 1995)

Towards the Parallel Repetition Conjecture. - Oleg Verbitsky 001 (Theor. Comput. Sci., 1996)

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

A Ramsey Treatment of Symmetry. - Taras O. Banakh; Oleg V. Verbitsky 001; Yaroslav Vorobets (Electron. J. Comb., 2000)

A Symmetric Strategy in Graph Avoidance Games - Frank Harary; Wolfgang Slany; Oleg Verbitsky 001 (CoRR, 2001)

Remarks on a Query-Based Variant of the Parallel Repetition Theorem. - Oleg Verbitsky 001 (Int. J. Found. Comput. Sci., 2001)

On Asymmetric Colorings of Integer Grids. - Taras O. Banakh; Ya. Kmit; Oleg V. Verbitsky 001 (Ars Comb., 2002)

Error Reduction by Parallel Repetition - A Negative Result. - Uriel Feige; Oleg Verbitsky 001 (Comb., 2002)

On the lengths of symmetry breaking-preserving games on graphs. - Frank Harary; Wolfgang Slany; Oleg Verbitsky 001 (Theor. Comput. Sci., 2004)

Descriptive complexity of finite structures: Saving the quantifier rank. - Oleg Pikhurko; Oleg Verbitsky 001 (J. Symb. Log., 2005)

How complex are random graphs in first order logic? - Jeong Han Kim; Oleg Pikhurko; Joel H. Spencer; Oleg Verbitsky 001 (Random Struct. Algorithms, 2005)

The first order definability of graphs with separators via the Ehrenfeucht game. - Oleg Verbitsky 001 (Theor. Comput. Sci., 2005)

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

Succinct definitions in the first order theory of graphs. - Oleg Pikhurko; Joel Spencer; Oleg Verbitsky 001 (Ann. Pure Appl. Log., 2006)

The first order definability of graphs: Upper bounds for quantifier depth. - Oleg Pikhurko; Helmut Veith; Oleg Verbitsky 001 (Discret. Appl. Math., 2006)

Planar Graphs: Logical Complexity and Parallel Isomorphism Tests. - Oleg Verbitsky 001 (STACS, 2007)

First-Order Definability of Trees and Sparse Random Graphs. - Tom Bohman; Alan M. Frieze; Tomasz Luczak 001; Oleg Pikhurko; Clifford D. Smyth; Joel Spencer; Oleg Verbitsky 001 (Comb. Probab. Comput., 2007)

Decomposable graphs and definitions with no quantifier alternation. - Oleg Pikhurko; Joel Spencer; Oleg Verbitsky 001 (Eur. J. Comb., 2007)

On the Computational Complexity of the Forcing Chromatic Number. - Frank Harary; Wolfgang Slany; Oleg Verbitsky 001 (SIAM J. Comput., 2007)

From Invariants to Canonization in Parallel. - Johannes Köbler; Oleg Verbitsky 001 (CSR, 2008)

On the Double Coset Membership Problem for Permutation Groups - Oleg Verbitsky 001 (CoRR, 2008)

Zero-Knowledge Proofs of the Conjugacy for Permutation Groups - Oleg Verbitsky 001 (CoRR, 2008)

Obfuscated Drawings of Planar Graphs - Mihyun Kang; Oleg Pikhurko; Alexander Ravsky; Mathias Schacht; Oleg Verbitsky 001 (CoRR, 2008)

On the obfuscation complexity of planar graphs. - Oleg Verbitsky 001 (Theor. Comput. Sci., 2008)

Logical Complexity of Graphs: A Survey. - Oleg Pikhurko; Oleg Verbitsky 001 (AMS-ASL Joint Special Session, 2009)

Interval Graphs: Canonical Representation in Logspace. - Johannes Köbler; Sebastian Kuhnert; Bastian Laubner; Oleg Verbitsky 001 (Electron. Colloquium Comput. Complex., 2010)

Fermat's Spiral and the Line Between Yin and Yang. - Taras O. Banakh; Oleg Verbitsky 001; Yaroslav Vorobets (Am. Math. Mon., 2010)

On Collinear Sets in Straight-Line Drawings. - Alexander Ravsky; Oleg Verbitsky 001 (WG, 2011)

Untangling planar graphs from a specified vertex position - Hard cases. - Mihyun Kang; Oleg Pikhurko; Alexander Ravsky; Mathias Schacht; Oleg Verbitsky 001 (Discret. Appl. Math., 2011)

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

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

Bounds for the quantifier depth in two-variable logic - Christoph Berkholz; Oleg Verbitsky 001 (CoRR, 2012)

Around and Beyond the Isomorphism Problem for Interval Graphs. - Johannes Köbler; Sebastian Kuhnert; Oleg Verbitsky 001 (Bull. EATCS, 2012)

On the dynamic width of the 3-colorability problem. - Oleg Verbitsky 001 (CoRR, 2013)

Helly Circular-Arc Graph Isomorphism is in Logspace. - Johannes Köbler; Sebastian Kuhnert; Oleg Verbitsky 001 (Electron. Colloquium Comput. Complex., 2013)

Universal covers, color refinement, and two-variable logic with counting quantifiers: Lower bounds for the depth. - Andreas Krebs; Oleg Verbitsky 001 (CoRR, 2014)

On the Power of Color Refinement. - Vikraman Arvind; Johannes Köbler; Gaurav Rattan; Oleg Verbitsky 001 (FCT, 2015)

Universal Covers, Color Refinement, and Two-Variable Counting Logic: Lower Bounds for the Depth. - Andreas Krebs; Oleg Verbitsky 001 (LICS, 2015)

On Tinhofer's Linear Programming Approach to Isomorphism Testing. - Vikraman Arvind; Johannes Köbler; Gaurav Rattan; Oleg Verbitsky 001 (MFCS (2), 2015)

Bounds for the Quantifier Depth in Finite-Variable Logics: Alternation Hierarchy. - Christoph Berkholz; Andreas Krebs; Oleg Verbitsky 001 (ACM Trans. Comput. Log., 2015)

The Descriptive Complexity of Subgraph Isomorphism in the Absence of Order. - Oleg Verbitsky 001; Maksim Zhukovskii (CoRR, 2016)

On the isomorphism problem for Helly circular-arc graphs. - Johannes Köbler; Sebastian Kuhnert; Oleg Verbitsky 001 (Inf. Comput., 2016)

Solving the canonical representation and Star System Problems for proper circular-arc graphs in logspace. - Johannes Köbler; Sebastian Kuhnert; Oleg Verbitsky 001 (J. Discrete Algorithms, 2016)

Graph Isomorphism, Color Refinement, and Compactness. - Vikraman Arvind; Johannes Köbler; Gaurav Rattan; Oleg Verbitsky 001 (Comput. Complex., 2017)

Circular-arc hypergraphs: Rigidity via connectedness. - Johannes Köbler; Sebastian Kuhnert; Oleg Verbitsky 001 (Discret. Appl. Math., 2017)

On the speed of constraint propagation and the time complexity of arc consistency testing. - Christoph Berkholz; Oleg Verbitsky 001 (J. Comput. Syst. Sci., 2018)

On the First-Order Complexity of Induced Subgraph Isomorphism. - Oleg Verbitsky 001; Maksim Zhukovskii (Log. Methods Comput. Sci., 2019)

The Descriptive Complexity of Subgraph Isomorphism Without Numerics. - Oleg Verbitsky 001; Maksim Zhukovskii (Theory Comput. Syst., 2019)

Tight Bounds on the Asymptotic Descriptive Complexity of Subgraph Isomorphism. - Oleg Verbitsky 001; Maksim Zhukovskii (ACM Trans. Comput. Log., 2019)

On Weisfeiler-Leman invariance: Subgraph counts and related graph properties. - Vikraman Arvind; Frank Fuhlbrück; Johannes Köbler; Oleg Verbitsky 001 (J. Comput. Syst. Sci., 2020)

Drawing graphs on few lines and few planes. - Steven Chaplick; Krzysztof Fleszar 001; Fabian Lipp; Alexander Ravsky; Oleg Verbitsky 001; Alexander Wolff 001 (J. Comput. Geom., 2020)

Local WL invariance and hidden shades of regularity. - Frank Fuhlbrück; Johannes Köbler; Oleg Verbitsky 001 (Discret. Appl. Math., 2021)

Identifiability of Graphs with Small Color Classes by the Weisfeiler-Leman Algorithm. - Frank Fuhlbrück; Johannes Köbler; Oleg Verbitsky 001 (SIAM J. Discret. Math., 2021)

The Weisfeiler-Leman algorithm and recognition of graph properties. - Frank Fuhlbrück; Johannes Köbler; Ilia Ponomarenko; Oleg Verbitsky 001 (Theor. Comput. Sci., 2021)

On Anti-stochastic Properties of Unlabeled Graphs. - Sergei Kiselev; Andrey Kupavskii; Oleg Verbitsky 001; Maksim Zhukovskii (WG, 2022)

On the Weisfeiler-Leman dimension of fractional packing. - Vikraman Arvind; Frank Fuhlbrück; Johannes Köbler; Oleg Verbitsky 001 (Inf. Comput., 2022)

Canonization of a Random Graph by Two Matrix-Vector Multiplications. - Oleg Verbitsky 001; Maksim Zhukovskii (ESA, 2023)

On a Hierarchy of Spectral Isomorphism Invariants. - Vikraman Arvind; Frank Fuhlbrück; Johannes Köbler; Oleg Verbitsky 001 (CoRR, 2023)

The Complexity of Drawing Graphs on Few Lines and Few Planes. - Steven Chaplick; Krzysztof Fleszar 001; Fabian Lipp; Alexander Ravsky; Oleg Verbitsky 001; Alexander Wolff 001 (J. Graph Algorithms Appl., 2023)

On a Hierarchy of Spectral Invariants for Graphs. - Vikraman Arvind; Frank Fuhlbrück; Johannes Köbler; Oleg Verbitsky 001 (STACS, 2024)

Canonization of a Random Circulant Graph by Counting Walks. - Oleg Verbitsky 001; Maksim Zhukovskii (WALCOM, 2024)

Gathering Information about a Graph by Counting Walks from a Single Vertex. - Frank Fuhlbrück; Johannes Köbler; Oleg Verbitsky 001; Maksim Zhukovskii (CoRR, 2024)

Canonical labelling of sparse random graphs. - Oleg Verbitsky 001; Maksim Zhukovskii (CoRR, 2024)

On Isomorphism-Invariant Antistochastic Properties of Random Graphs. - Sergei Kiselev; Andrey Kupavskii; Oleg Verbitsky 001; Maksim Zhukovskii (SIAM J. Discret. Math., 2024)

Canonical Labeling of Sparse Random Graphs. - Oleg Verbitsky 001; Maksim Zhukovskii (STACS, 2025)

On the expressibility of the reconstructional color refinement. - Vikraman Arvind; Johannes Köbler; Oleg Verbitsky 001 (Theor. Comput. Sci., 2025)

New Bounds for the Optimal Density of Covering Single-Insertion Codes via the Turán Density. - Oleg Pikhurko; Oleg Verbitsky 001; Maksim Zhukovskii (IEEE Trans. Inf. Theory, 2025)