Oleg Verbitsky

Publication Activity (10 Years)

Years Active: 1994-2021
Publications (10 Years): 38

Top Topics

Graph Isomorphism

Arc Consistency

Canonical Representation

Top Venues

J. Comput. Syst. Sci.

Discret. Appl. Math.

Publications

Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky
Identifiability of Graphs with Small Color Classes by the Weisfeiler-Leman Algorithm. SIAM J. Discret. Math. 35 (3) (2021)
Frank Fuhlbrück, Johannes Köbler, Ilia Ponomarenko, Oleg Verbitsky
The Weisfeiler-Leman Algorithm and Recognition of Graph Properties. CIAC (2021)
Sergei Kiselev, Andrey Kupavskii, Oleg Verbitsky, Maksim Zhukovskii
On anti-stochastic properties of unlabeled graphs. CoRR (2021)
Frank Fuhlbrück, Johannes Köbler, Ilia Ponomarenko, Oleg Verbitsky
The Weisfeiler-Leman algorithm and recognition of graph properties. Theor. Comput. Sci. 895 (2021)
Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky
Local WL invariance and hidden shades of regularity. Discret. Appl. Math. 305 (2021)
Frank Fuhlbrück, Johannes Köbler, Ilia Ponomarenko, Oleg Verbitsky
The Weisfeiler-Leman Algorithm and Recognition of Graph Properties. CoRR (2020)
Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky
Identifiability of Graphs with Small Color Classes by the Weisfeiler-Leman Algorithm. STACS (2020)
Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky
On the Weisfeiler-Leman Dimension of Fractional Packing. LATA (2020)
Steven Chaplick, Krzysztof Fleszar, Fabian Lipp, Alexander Ravsky, Oleg Verbitsky, Alexander Wolff
Drawing graphs on few lines and few planes. J. Comput. Geom. 11 (1) (2020)
Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky
Local WL Invariance and Hidden Shades of Regularity. CoRR (2020)
Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky
On Weisfeiler-Leman invariance: Subgraph counts and related graph properties. J. Comput. Syst. Sci. 113 (2020)
Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky
On Weisfeiler-Leman Invariance: Subgraph Counts and Related Graph Properties. FCT (2019)
Oleg Verbitsky, Maksim Zhukovskii
On the First-Order Complexity of Induced Subgraph Isomorphism. Log. Methods Comput. Sci. 15 (1) (2019)
Oleg Verbitsky, Maksim Zhukovskii
Tight Bounds on the Asymptotic Descriptive Complexity of Subgraph Isomorphism. ACM Trans. Comput. Log. 20 (2) (2019)
Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky
On the Weisfeiler-Leman Dimension of Fractional Packing. CoRR (2019)
Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky
Identifiability of Graphs with Small Color Classes by the Weisfeiler-Leman Algorithm. CoRR (2019)
Oleg Verbitsky, Maksim Zhukovskii
The Descriptive Complexity of Subgraph Isomorphism Without Numerics. Theory Comput. Syst. 63 (4) (2019)
Christoph Berkholz, Oleg Verbitsky
On the speed of constraint propagation and the time complexity of arc consistency testing. J. Comput. Syst. Sci. 91 (2018)
Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky
On Weisfeiler-Leman Invariance: Subgraph Counts and Related Graph Properties. CoRR (2018)
Oleg Verbitsky, Maksim Zhukovskii
Tight Bounds on the Asymptotic Descriptive Complexity of Subgraph Isomorphism. CoRR (2018)
Vikraman Arvind, Johannes Köbler, Gaurav Rattan, Oleg Verbitsky
Graph Isomorphism, Color Refinement, and Compactness. Comput. Complex. 26 (3) (2017)
Steven Chaplick, Krzysztof Fleszar, Fabian Lipp, Alexander Ravsky, Oleg Verbitsky, Alexander Wolff
The Complexity of Drawing Graphs on Few Lines and Few Planes. WADS (2017)
Oleg Verbitsky, Maksim Zhukovskii
On the First-Order Complexity of Induced Subgraph Isomorphism. CoRR (2017)
Oleg Verbitsky, Maksim Zhukovskii
On the First-Order Complexity of Induced Subgraph Isomorphism. CSL (2017)
Oleg Verbitsky, Maksim Zhukovskii
The Descriptive Complexity of Subgraph Isomorphism Without Numerics. CSR (2017)
Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky
Circular-arc hypergraphs: Rigidity via connectedness. Discret. Appl. Math. 217 (2017)
Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky
Solving the canonical representation and Star System Problems for proper circular-arc graphs in logspace. J. Discrete Algorithms (2016)
Steven Chaplick, Krzysztof Fleszar, Fabian Lipp, Alexander Ravsky, Oleg Verbitsky, Alexander Wolff
Drawing Graphs on Few Lines and Few Planes. Graph Drawing (2016)
Oleg Verbitsky, Maksim Zhukovskii
The Descriptive Complexity of Subgraph Isomorphism in the Absence of Order. CoRR (2016)
Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky
On the isomorphism problem for Helly circular-arc graphs. Inf. Comput. 247 (2016)
Steven Chaplick, Krzysztof Fleszar, Fabian Lipp, Alexander Ravsky, Oleg Verbitsky, Alexander Wolff
Drawing Graphs on Few Lines and Few Planes. CoRR (2016)
Steven Chaplick, Krzysztof Fleszar, Fabian Lipp, Alexander Ravsky, Oleg Verbitsky, Alexander Wolff
The Complexity of Drawing Graphs on Few Lines and Few Planes. CoRR (2016)
Andreas Krebs, Oleg Verbitsky
Universal Covers, Color Refinement, and Two-Variable Counting Logic: Lower Bounds for the Depth. LICS (2015)
Vikraman Arvind, Johannes Köbler, Gaurav Rattan, Oleg Verbitsky
Graph Isomorphism, Color Refinement, and Compactness. Electron. Colloquium Comput. Complex. 22 (2015)
Vikraman Arvind, Johannes Köbler, Gaurav Rattan, Oleg Verbitsky
Graph Isomorphism, Color Refinement, and Compactness. CoRR (2015)
Christoph Berkholz, Andreas Krebs, Oleg Verbitsky
Bounds for the Quantifier Depth in Finite-Variable Logics: Alternation Hierarchy. ACM Trans. Comput. Log. 16 (3) (2015)
Vikraman Arvind, Johannes Köbler, Gaurav Rattan, Oleg Verbitsky
On the Power of Color Refinement. FCT (2015)
Vikraman Arvind, Johannes Köbler, Gaurav Rattan, Oleg Verbitsky
On Tinhofer's Linear Programming Approach to Isomorphism Testing. MFCS (2) (2015)
Andreas Krebs, Oleg Verbitsky
Universal covers, color refinement, and two-variable logic with counting quantifiers: Lower bounds for the depth. CoRR (2014)
Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky
On the Isomorphism Problem for Helly Circular-Arc Graphs. CoRR (2014)
Christoph Berkholz, Oleg Verbitsky
On the speed of constraint propagation and the time complexity of arc consistency testing CoRR (2013)
Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky
Circular-arc hypergraphs: Rigidity via Connectedness. CoRR (2013)
Christoph Berkholz, Oleg Verbitsky
On the Speed of Constraint Propagation and the Time Complexity of Arc Consistency Testing. MFCS (2013)
Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky
Helly Circular-Arc Graph Isomorphism Is in Logspace. MFCS (2013)
Christoph Berkholz, Andreas Krebs, Oleg Verbitsky
Bounds for the quantifier depth in finite-variable logics: Alternation hierarchy. CSL (2013)
Oleg Verbitsky
On the dynamic width of the 3-colorability problem. CoRR (2013)
Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky
Helly Circular-Arc Graph Isomorphism is in Logspace. Electron. Colloquium Comput. Complex. 20 (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)
Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky
Solving the Canonical Representation and Star System Problems for Proper Circular-Arc Graphs in Log-Space CoRR (2012)
Christoph Berkholz, Oleg Verbitsky
Bounds for the quantifier depth in two-variable logic CoRR (2012)
Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky
Around and Beyond the Isomorphism Problem for Interval Graphs. Bull. EATCS 107 (2012)
Johannes Köbler, Sebastian Kuhnert, Bastian Laubner, Oleg Verbitsky
Interval Graphs: Canonical Representations in Logspace. SIAM J. Comput. 40 (5) (2011)
Mihyun Kang, Oleg Pikhurko, Alexander Ravsky, Mathias Schacht, Oleg Verbitsky
Untangling planar graphs from a specified vertex position - Hard cases. Discret. Appl. Math. 159 (8) (2011)
Alexander Ravsky, Oleg Verbitsky
On Collinear Sets in Straight-Line Drawings. WG (2011)
Johannes Köbler, Sebastian Kuhnert, Bastian Laubner, Oleg Verbitsky
Interval Graphs: Canonical Representation in Logspace. Electron. Colloquium Comput. Complex. 17 (2010)
Oleg Pikhurko, Oleg Verbitsky
Logical complexity of graphs: a survey CoRR (2010)
Johannes Köbler, Sebastian Kuhnert, Bastian Laubner, Oleg Verbitsky
Interval Graphs: Canonical Representation in Logspace. ICALP (1) (2010)
Taras O. Banakh, Oleg Verbitsky, Yaroslav Vorobets
Fermat's Spiral and the Line Between Yin and Yang. Am. Math. Mon. 117 (9) (2010)
Oleg Pikhurko, Oleg Verbitsky
Logical Complexity of Graphs: A Survey. AMS-ASL Joint Special Session (2009)
Oleg Verbitsky
On the Double Coset Membership Problem for Permutation Groups CoRR (2008)
Alexander Ravsky, Oleg Verbitsky
On collinear sets in straight line drawings CoRR (2008)
Oleg Verbitsky
Zero-Knowledge Proofs of the Conjugacy for Permutation Groups CoRR (2008)
Johannes Köbler, Oleg Verbitsky
From Invariants to Canonization in Parallel. CSR (2008)
Mihyun Kang, Oleg Pikhurko, Alexander Ravsky, Mathias Schacht, Oleg Verbitsky
Obfuscated Drawings of Planar Graphs CoRR (2008)
Oleg Verbitsky
On the obfuscation complexity of planar graphs. Theor. Comput. Sci. 396 (1-3) (2008)
Oleg Verbitsky
On the Obfuscation Complexity of Planar Graphs CoRR (2007)
Oleg Pikhurko, Joel Spencer, Oleg Verbitsky
Decomposable graphs and definitions with no quantifier alternation. Eur. J. Comb. 28 (8) (2007)
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. Comb. Probab. Comput. 16 (3) (2007)
Oleg Verbitsky
Planar Graphs: Logical Complexity and Parallel Isomorphism Tests. STACS (2007)
Frank Harary, Wolfgang Slany, Oleg Verbitsky
On the Computational Complexity of the Forcing Chromatic Number. SIAM J. Comput. 37 (1) (2007)
Martin Grohe, Oleg Verbitsky
Testing Graph Isomorphism in Parallel by Playing a Game. ICALP (1) (2006)
Martin Grohe, Oleg Verbitsky
Testing Graph Isomorphism in Parallel by Playing a Game CoRR (2006)
Oleg Pikhurko, Helmut Veith, Oleg Verbitsky
The first order definability of graphs: Upper bounds for quantifier depth. Discret. Appl. Math. 154 (17) (2006)
Oleg Pikhurko, Joel Spencer, Oleg Verbitsky
Succinct definitions in the first order theory of graphs. Ann. Pure Appl. Log. 139 (1-3) (2006)
Johannes Köbler, Oleg Verbitsky
From Invariants to Canonization in Parallel CoRR (2006)
Oleg Verbitsky
Planar Graphs: Logical Complexity and Parallel Isomorphism Tests CoRR (2006)
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) (2005)
Oleg Pikhurko, Oleg Verbitsky
Descriptive complexity of finite structures: Saving the quantifier rank. J. Symb. Log. 70 (2) (2005)
Frank Harary, Wolfgang Slany, Oleg Verbitsky
On the Computational Complexity of the Forcing Chromatic Number. STACS (2005)
Oleg Verbitsky
The first order definability of graphs with separators via the Ehrenfeucht game. Theor. Comput. Sci. 343 (1-2) (2005)
Frank Harary, Wolfgang Slany, Oleg Verbitsky
On the lengths of symmetry breaking-preserving games on graphs. Theor. Comput. Sci. 313 (3) (2004)
Frank Harary, Wolfgang Slany, Oleg Verbitsky
On Computational Complexity of the Forcing Chromatic Number CoRR (2004)
Uriel Feige, Oleg Verbitsky
Error Reduction by Parallel Repetition - A Negative Result. Comb. 22 (4) (2002)
Frank Harary, Wolfgang Slany, Oleg Verbitsky
A Symmetric Strategy in Graph Avoidance Games CoRR (2001)
Oleg Verbitsky
Remarks on a Query-Based Variant of the Parallel Repetition Theorem. Int. J. Found. Comput. Sci. 12 (4) (2001)
Ran Raz, Gábor Tardos, Oleg Verbitsky, Nikolai K. Vereshchagin
Arthur-Merlin Games in Boolean Decision Trees. J. Comput. Syst. Sci. 59 (2) (1999)
Ran Raz, Gábor Tardos, Oleg Verbitsky, Nikolai K. Vereshchagin
Arthur-Merlin Games in Boolean Decision Trees. Computational Complexity Conference (1998)
Ran Raz, Gábor Tardos, Oleg Verbitsky, Nikolai K. Vereshchagin
Arthur-Merlin Games in Boolean Decision Trees Electron. Colloquium Comput. Complex. 4 (54) (1997)
Oleg Verbitsky
Towards the Parallel Repetition Conjecture. Theor. Comput. Sci. 157 (2) (1996)
Uriel Feige, Oleg Verbitsky
Error Reduction by Parallel Repetition - a Negative Result. Computational Complexity Conference (1996)
Oleg Verbitsky
The Parallel Repetition Conjecture for Trees is True Electron. Colloquium Comput. Complex. 2 (13) (1995)
Oleg Verbitsky
On the Hardness of Approximating Some Optimization Problems That Are Supposedly Easier Than MAX CLIQUE. Comb. Probab. Comput. 4 (1995)
Oleg Verbitsky
Towards the Parallel Repetition Conjecture. Computational Complexity Conference (1994)