Oleg Verbitsky

112 papers A* 1A 9B 10C 2Misc 2Journal 82Unranked 6
YearRankTypeTitle / Venue / Authors
2026 J jnl
Canonization of a random circulant graph by counting walks.
Comb. Probab. Comput.
Oleg Verbitsky, Maksim Zhukovskii
2025 A conf
Canonical Labeling of Sparse Random Graphs.
STACS
Oleg Verbitsky, Maksim Zhukovskii
2025 J jnl
New Bounds for the Optimal Density of Covering Single-Insertion Codes via the Turán Density.
IEEE Trans. Inf. Theory
Oleg Pikhurko, Oleg Verbitsky, Maksim Zhukovskii
2025 J jnl
On a Hierarchy of Spectral Isomorphism Invariants.
Comput. Complex.
Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky
2025 J jnl
On the expressibility of the reconstructional color refinement.
Theor. Comput. Sci.
Vikraman Arvind, Johannes Köbler, Oleg Verbitsky
2024 J jnl
Canonical labelling of sparse random graphs.
CoRR
Oleg Verbitsky, Maksim Zhukovskii
2024 B conf
Canonization of a Random Circulant Graph by Counting Walks.
WALCOM
Oleg Verbitsky, Maksim Zhukovskii
2024 J jnl
Gathering Information about a Graph by Counting Walks from a Single Vertex.
CoRR
Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky, Maksim Zhukovskii
2024 J jnl
New bounds for the optimal density of covering single-insertion codes via the Turán density.
CoRR
Oleg Pikhurko, Oleg Verbitsky, Maksim Zhukovskii
2024 J jnl
On Isomorphism-Invariant Antistochastic Properties of Random Graphs.
SIAM J. Discret. Math.
Sergei Kiselev, Andrey Kupavskii, Oleg Verbitsky, Maksim Zhukovskii
2024 A conf
On a Hierarchy of Spectral Invariants for Graphs.
STACS
Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky
2024 J jnl
On the Expressibility of the Reconstructional Color Refinement.
CoRR
Vikraman Arvind, Johannes Köbler, Oleg Verbitsky
2023 A conf
Canonization of a Random Graph by Two Matrix-Vector Multiplications.
ESA
Oleg Verbitsky, Maksim Zhukovskii
2023 J jnl
Canonization of a random circulant graph by counting walks.
CoRR
Oleg Verbitsky, Maksim Zhukovskii
2023 J jnl
Canonization of a random graph by two matrix-vector multiplications.
CoRR
Oleg Verbitsky, Maksim Zhukovskii
2023 J jnl
On a Hierarchy of Spectral Isomorphism Invariants.
CoRR
Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky
2023 J jnl
The Complexity of Drawing Graphs on Few Lines and Few Planes.
J. Graph Algorithms Appl.
Steven Chaplick, Krzysztof Fleszar, Fabian Lipp, Alexander Ravsky, Oleg Verbitsky, Alexander Wolff
2022 B conf
On Anti-stochastic Properties of Unlabeled Graphs.
WG
Sergei Kiselev, Andrey Kupavskii, Oleg Verbitsky, Maksim Zhukovskii
2022 J jnl
On the Weisfeiler-Leman dimension of fractional packing.
Inf. Comput.
Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky
2021 J jnl
Identifiability of Graphs with Small Color Classes by the Weisfeiler-Leman Algorithm.
SIAM J. Discret. Math.
Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky
2021 J jnl
Local WL invariance and hidden shades of regularity.
Discret. Appl. Math.
Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky
2021 J jnl
On anti-stochastic properties of unlabeled graphs.
CoRR
Sergei Kiselev, Andrey Kupavskii, Oleg Verbitsky, Maksim Zhukovskii
2021 C conf
The Weisfeiler-Leman Algorithm and Recognition of Graph Properties.
CIAC
Frank Fuhlbrück, Johannes Köbler, Ilia Ponomarenko, Oleg Verbitsky
2021 J jnl
The Weisfeiler-Leman algorithm and recognition of graph properties.
Theor. Comput. Sci.
Frank Fuhlbrück, Johannes Köbler, Ilia Ponomarenko, Oleg Verbitsky
2020 J jnl
Drawing graphs on few lines and few planes.
J. Comput. Geom.
Steven Chaplick, Krzysztof Fleszar, Fabian Lipp, Alexander Ravsky, Oleg Verbitsky, Alexander Wolff
2020 A conf
Identifiability of Graphs with Small Color Classes by the Weisfeiler-Leman Algorithm.
STACS
Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky
2020 J jnl
Local WL Invariance and Hidden Shades of Regularity.
CoRR
Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky
2020 J jnl
On Weisfeiler-Leman invariance: Subgraph counts and related graph properties.
J. Comput. Syst. Sci.
Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky
2020 C conf
On the Weisfeiler-Leman Dimension of Fractional Packing.
LATA
Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky
2020 J jnl
The Weisfeiler-Leman Algorithm and Recognition of Graph Properties.
CoRR
Frank Fuhlbrück, Johannes Köbler, Ilia Ponomarenko, Oleg Verbitsky
2019 J jnl
Identifiability of Graphs with Small Color Classes by the Weisfeiler-Leman Algorithm.
CoRR
Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky
2019 B conf
On Weisfeiler-Leman Invariance: Subgraph Counts and Related Graph Properties.
FCT
Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky
2019 J jnl
On the First-Order Complexity of Induced Subgraph Isomorphism.
Log. Methods Comput. Sci.
Oleg Verbitsky, Maksim Zhukovskii
2019 J jnl
On the Weisfeiler-Leman Dimension of Fractional Packing.
CoRR
Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky
2019 J jnl
The Descriptive Complexity of Subgraph Isomorphism Without Numerics.
Theory Comput. Syst.
Oleg Verbitsky, Maksim Zhukovskii
2019 J jnl
Tight Bounds on the Asymptotic Descriptive Complexity of Subgraph Isomorphism.
ACM Trans. Comput. Log.
Oleg Verbitsky, Maksim Zhukovskii
2018 J jnl
On Weisfeiler-Leman Invariance: Subgraph Counts and Related Graph Properties.
CoRR
Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky
2018 J jnl
On the speed of constraint propagation and the time complexity of arc consistency testing.
J. Comput. Syst. Sci.
Christoph Berkholz, Oleg Verbitsky
2018 J jnl
Tight Bounds on the Asymptotic Descriptive Complexity of Subgraph Isomorphism.
CoRR
Oleg Verbitsky, Maksim Zhukovskii
2017 J jnl
Circular-arc hypergraphs: Rigidity via connectedness.
Discret. Appl. Math.
Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky
2017 J jnl
Graph Isomorphism, Color Refinement, and Compactness.
Comput. Complex.
Vikraman Arvind, Johannes Köbler, Gaurav Rattan, Oleg Verbitsky
2017 B conf
On the First-Order Complexity of Induced Subgraph Isomorphism.
CSL
Oleg Verbitsky, Maksim Zhukovskii
2017 J jnl
On the First-Order Complexity of Induced Subgraph Isomorphism.
CoRR
Oleg Verbitsky, Maksim Zhukovskii
2017 B conf
The Complexity of Drawing Graphs on Few Lines and Few Planes.
WADS
Steven Chaplick, Krzysztof Fleszar, Fabian Lipp, Alexander Ravsky, Oleg Verbitsky, Alexander Wolff
2017 Misc conf
The Descriptive Complexity of Subgraph Isomorphism Without Numerics.
CSR
Oleg Verbitsky, Maksim Zhukovskii
2016 A conf
Drawing Graphs on Few Lines and Few Planes.
GD
Steven Chaplick, Krzysztof Fleszar, Fabian Lipp, Alexander Ravsky, Oleg Verbitsky, Alexander Wolff
2016 J jnl
Drawing Graphs on Few Lines and Few Planes.
CoRR
Steven Chaplick, Krzysztof Fleszar, Fabian Lipp, Alexander Ravsky, Oleg Verbitsky, Alexander Wolff
2016 J jnl
On the isomorphism problem for Helly circular-arc graphs.
Inf. Comput.
Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky
2016 J jnl
Solving the canonical representation and Star System Problems for proper circular-arc graphs in logspace.
J. Discrete Algorithms
Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky
2016 J jnl
The Complexity of Drawing Graphs on Few Lines and Few Planes.
CoRR
Steven Chaplick, Krzysztof Fleszar, Fabian Lipp, Alexander Ravsky, Oleg Verbitsky, Alexander Wolff
2016 J jnl
The Descriptive Complexity of Subgraph Isomorphism in the Absence of Order.
CoRR
Oleg Verbitsky, Maksim Zhukovskii
2015 J jnl
Bounds for the Quantifier Depth in Finite-Variable Logics: Alternation Hierarchy.
ACM Trans. Comput. Log.
Christoph Berkholz, Andreas Krebs, Oleg Verbitsky
2015 J jnl
Graph Isomorphism, Color Refinement, and Compactness.
CoRR
Vikraman Arvind, Johannes Köbler, Gaurav Rattan, Oleg Verbitsky
2015 J jnl
Graph Isomorphism, Color Refinement, and Compactness.
Electron. Colloquium Comput. Complex.
Vikraman Arvind, Johannes Köbler, Gaurav Rattan, Oleg Verbitsky
2015 — conf
On Tinhofer's Linear Programming Approach to Isomorphism Testing.
MFCS (2)
Vikraman Arvind, Johannes Köbler, Gaurav Rattan, Oleg Verbitsky
2015 B conf
On the Power of Color Refinement.
FCT
Vikraman Arvind, Johannes Köbler, Gaurav Rattan, Oleg Verbitsky
2015 A* conf
Universal Covers, Color Refinement, and Two-Variable Counting Logic: Lower Bounds for the Depth.
LICS
Andreas Krebs, Oleg Verbitsky
2014 J jnl
On the Isomorphism Problem for Helly Circular-Arc Graphs.
CoRR
Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky
2014 J jnl
Universal covers, color refinement, and two-variable logic with counting quantifiers: Lower bounds for the depth.
CoRR
Andreas Krebs, Oleg Verbitsky
2013 B conf
Bounds for the quantifier depth in finite-variable logics: Alternation hierarchy.
CSL
Christoph Berkholz, Andreas Krebs, Oleg Verbitsky
2013 J jnl
Circular-arc hypergraphs: Rigidity via Connectedness.
CoRR
Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky
2013 B conf
Helly Circular-Arc Graph Isomorphism Is in Logspace.
MFCS
Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky
2013 J jnl
Helly Circular-Arc Graph Isomorphism is in Logspace.
Electron. Colloquium Comput. Complex.
Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky
2013 B conf
On the Speed of Constraint Propagation and the Time Complexity of Arc Consistency Testing.
MFCS
Christoph Berkholz, Oleg Verbitsky
2013 J jnl
On the dynamic width of the 3-colorability problem.
CoRR
Oleg Verbitsky
2013 J jnl
On the speed of constraint propagation and the time complexity of arc consistency testing
CoRR
Christoph Berkholz, Oleg Verbitsky
2012 J jnl
Around and Beyond the Isomorphism Problem for Interval Graphs.
Bull. EATCS
Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky
2012 J jnl
Bounds for the quantifier depth in two-variable logic
CoRR
Christoph Berkholz, Oleg Verbitsky
2012 J jnl
Solving the Canonical Representation and Star System Problems for Proper Circular-Arc Graphs in Log-Space
CoRR
Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky
2012 — conf
Solving the Canonical Representation and Star System Problems for Proper Circular-Arc Graphs in Logspace.
FSTTCS
Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky
2011 J jnl
Interval Graphs: Canonical Representations in Logspace.
SIAM J. Comput.
Johannes Köbler, Sebastian Kuhnert, Bastian Laubner, Oleg Verbitsky
2011 B conf
On Collinear Sets in Straight-Line Drawings.
WG
Alexander Ravsky, Oleg Verbitsky
2011 J jnl
Untangling planar graphs from a specified vertex position - Hard cases.
Discret. Appl. Math.
Mihyun Kang, Oleg Pikhurko, Alexander Ravsky, Mathias Schacht, Oleg Verbitsky
2010 J jnl
Fermat's Spiral and the Line Between Yin and Yang.
Am. Math. Mon.
Taras O. Banakh, Oleg Verbitsky, Yaroslav Vorobets
2010 — conf
Interval Graphs: Canonical Representation in Logspace.
ICALP (1)
Johannes Köbler, Sebastian Kuhnert, Bastian Laubner, Oleg Verbitsky
2010 J jnl
Interval Graphs: Canonical Representation in Logspace.
Electron. Colloquium Comput. Complex.
Johannes Köbler, Sebastian Kuhnert, Bastian Laubner, Oleg Verbitsky
2010 J jnl
Logical complexity of graphs: a survey
CoRR
Oleg Pikhurko, Oleg Verbitsky
2009 — conf
Logical Complexity of Graphs: A Survey.
AMS-ASL Joint Special Session
Oleg Pikhurko, Oleg Verbitsky
2008 Misc conf
From Invariants to Canonization in Parallel.
CSR
Johannes Köbler, Oleg Verbitsky
2008 J jnl
Obfuscated Drawings of Planar Graphs
CoRR
Mihyun Kang, Oleg Pikhurko, Alexander Ravsky, Mathias Schacht, Oleg Verbitsky
2008 J jnl
On collinear sets in straight line drawings
CoRR
Alexander Ravsky, Oleg Verbitsky
2008 J jnl
On the Double Coset Membership Problem for Permutation Groups
CoRR
Oleg Verbitsky
2008 J jnl
On the obfuscation complexity of planar graphs.
Theor. Comput. Sci.
Oleg Verbitsky
2008 J jnl
Zero-Knowledge Proofs of the Conjugacy for Permutation Groups
CoRR
Oleg Verbitsky
2007 J jnl
Decomposable graphs and definitions with no quantifier alternation.
Eur. J. Comb.
Oleg Pikhurko, Joel Spencer, Oleg Verbitsky
2007 J jnl
First-Order Definability of Trees and Sparse Random Graphs.
Comb. Probab. Comput.
Tom Bohman, Alan M. Frieze, Tomasz Luczak, Oleg Pikhurko, Clifford D. Smyth, Joel Spencer, Oleg Verbitsky
2007 J jnl
On the Computational Complexity of the Forcing Chromatic Number.
SIAM J. Comput.
Frank Harary, Wolfgang Slany, Oleg Verbitsky
2007 J jnl
On the Obfuscation Complexity of Planar Graphs
CoRR
Oleg Verbitsky
2007 A conf
Planar Graphs: Logical Complexity and Parallel Isomorphism Tests.
STACS
Oleg Verbitsky
2006 J jnl
From Invariants to Canonization in Parallel
CoRR
Johannes Köbler, Oleg Verbitsky
2006 J jnl
Planar Graphs: Logical Complexity and Parallel Isomorphism Tests
CoRR
Oleg Verbitsky
2006 J jnl
Succinct definitions in the first order theory of graphs.
Ann. Pure Appl. Log.
Oleg Pikhurko, Joel Spencer, Oleg Verbitsky
2006 J jnl
Testing Graph Isomorphism in Parallel by Playing a Game
CoRR
Martin Grohe, Oleg Verbitsky
2006 — conf
Testing Graph Isomorphism in Parallel by Playing a Game.
ICALP (1)
Martin Grohe, Oleg Verbitsky
2006 J jnl
The first order definability of graphs: Upper bounds for quantifier depth.
Discret. Appl. Math.
Oleg Pikhurko, Helmut Veith, Oleg Verbitsky
2005 J jnl
Descriptive complexity of finite structures: Saving the quantifier rank.
J. Symb. Log.
Oleg Pikhurko, Oleg Verbitsky
2005 J jnl
How complex are random graphs in first order logic?
Random Struct. Algorithms
Jeong Han Kim, Oleg Pikhurko, Joel H. Spencer, Oleg Verbitsky
2005 A conf
On the Computational Complexity of the Forcing Chromatic Number.
STACS
Frank Harary, Wolfgang Slany, Oleg Verbitsky
2005 J jnl
The first order definability of graphs with separators via the Ehrenfeucht game.
Theor. Comput. Sci.
Oleg Verbitsky
2004 J jnl
On Computational Complexity of the Forcing Chromatic Number
CoRR
Frank Harary, Wolfgang Slany, Oleg Verbitsky
2004 J jnl
On the lengths of symmetry breaking-preserving games on graphs.
Theor. Comput. Sci.
Frank Harary, Wolfgang Slany, Oleg Verbitsky
2002 J jnl
Error Reduction by Parallel Repetition - A Negative Result.
Comb.
Uriel Feige, Oleg Verbitsky
2001 J jnl
A Symmetric Strategy in Graph Avoidance Games
CoRR
Frank Harary, Wolfgang Slany, Oleg Verbitsky
2001 J jnl
Remarks on a Query-Based Variant of the Parallel Repetition Theorem.
Int. J. Found. Comput. Sci.
Oleg Verbitsky
1999 J jnl
Arthur-Merlin Games in Boolean Decision Trees.
J. Comput. Syst. Sci.
Ran Raz, Gábor Tardos, Oleg Verbitsky, Nikolai K. Vereshchagin
1998 A conf
Arthur-Merlin Games in Boolean Decision Trees.
CCC
Ran Raz, Gábor Tardos, Oleg Verbitsky, Nikolai K. Vereshchagin
1997 J jnl
Arthur-Merlin Games in Boolean Decision Trees
Electron. Colloquium Comput. Complex.
Ran Raz, Gábor Tardos, Oleg Verbitsky, Nikolai K. Vereshchagin
1996 A conf
Error Reduction by Parallel Repetition - a Negative Result.
CCC
Uriel Feige, Oleg Verbitsky
1996 J jnl
Towards the Parallel Repetition Conjecture.
Theor. Comput. Sci.
Oleg Verbitsky
1995 J jnl
On the Hardness of Approximating Some Optimization Problems That Are Supposedly Easier Than MAX CLIQUE.
Comb. Probab. Comput.
Oleg Verbitsky
1995 J jnl
The Parallel Repetition Conjecture for Trees is True
Electron. Colloquium Comput. Complex.
Oleg Verbitsky
1994 — conf
Towards the Parallel Repetition Conjecture.
SCT
Oleg Verbitsky