Oleg Verbitsky

Proceedings of the WALCOM: Algorithms and Computation, 2024

On a Hierarchy of Spectral Invariants for Graphs.

[BibT_eX]

[DOI]

Proceedings of the 41st International Symposium on Theoretical Aspects of Computer Science, 2024

2023

The Complexity of Drawing Graphs on Few Lines and Few Planes.

[BibT_eX]

[DOI]

J. Graph Algorithms Appl., 2023

On a Hierarchy of Spectral Isomorphism Invariants.

[BibT_eX]

[DOI]

CoRR, 2023

Canonization of a Random Graph by Two Matrix-Vector Multiplications.

[BibT_eX]

[DOI]

Proceedings of the 31st Annual European Symposium on Algorithms, 2023

2022

On the Weisfeiler-Leman dimension of fractional packing.

[BibT_eX]

[DOI]

Inf. Comput., 2022

On Anti-stochastic Properties of Unlabeled Graphs.

[BibT_eX]

[DOI]

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2022

2021

The Weisfeiler-Leman algorithm and recognition of graph properties.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2021

Identifiability of Graphs with Small Color Classes by the Weisfeiler-Leman Algorithm.

[BibT_eX]

[DOI]

Frank Fuhlbrück

SIAM J. Discret. Math., 2021

Local WL invariance and hidden shades of regularity.

[BibT_eX]

[DOI]

Frank Fuhlbrück

Discret. Appl. Math., 2021

2020

Drawing graphs on few lines and few planes.

[BibT_eX]

[DOI]

J. Comput. Geom., 2020

On Weisfeiler-Leman invariance: Subgraph counts and related graph properties.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2020

2019

Tight Bounds on the Asymptotic Descriptive Complexity of Subgraph Isomorphism.

[BibT_eX]

[DOI]

ACM Trans. Comput. Log., 2019

The Descriptive Complexity of Subgraph Isomorphism Without Numerics.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2019

On the First-Order Complexity of Induced Subgraph Isomorphism.

[BibT_eX]

[DOI]

Log. Methods Comput. Sci., 2019

2018

On the speed of constraint propagation and the time complexity of arc consistency testing.

[BibT_eX]

[DOI]

Christoph Berkholz

J. Comput. Syst. Sci., 2018

2017

Circular-arc hypergraphs: Rigidity via connectedness.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2017

Graph Isomorphism, Color Refinement, and Compactness.

[BibT_eX]

[DOI]

Comput. Complex., 2017

2016

Solving the canonical representation and Star System Problems for proper circular-arc graphs in logspace.

[BibT_eX]

[DOI]

J. Discrete Algorithms, 2016

On the isomorphism problem for Helly circular-arc graphs.

[BibT_eX]

[DOI]

Inf. Comput., 2016

The Descriptive Complexity of Subgraph Isomorphism in the Absence of Order.

[BibT_eX]

[DOI]

CoRR, 2016

2015

Bounds for the Quantifier Depth in Finite-Variable Logics: Alternation Hierarchy.

[BibT_eX]

[DOI]

Christoph Berkholz

Andreas Krebs

ACM Trans. Comput. Log., 2015

On Tinhofer's Linear Programming Approach to Isomorphism Testing.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2015, 2015

Universal Covers, Color Refinement, and Two-Variable Counting Logic: Lower Bounds for the Depth.

[BibT_eX]

[DOI]

Andreas Krebs

Proceedings of the 30th Annual ACM/IEEE Symposium on Logic in Computer Science, 2015

On the Power of Color Refinement.

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory - 20th International Symposium, 2015

2014

Universal covers, color refinement, and two-variable logic with counting quantifiers: Lower bounds for the depth.

[BibT_eX]

[DOI]

Andreas Krebs

CoRR, 2014

2013

Helly Circular-Arc Graph Isomorphism is in Logspace.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

On the dynamic width of the 3-colorability problem.

[BibT_eX]

[DOI]

CoRR, 2013

2012

Around and Beyond the Isomorphism Problem for Interval Graphs.

[BibT_eX]

[DOI]

Bull. EATCS, 2012

Bounds for the quantifier depth in two-variable logic

[BibT_eX]

[DOI]

Christoph Berkholz

CoRR, 2012

Solving the Canonical Representation and Star System Problems for Proper Circular-Arc Graphs in Log-Space

[BibT_eX]

[DOI]

CoRR, 2012

2011

Interval Graphs: Canonical Representations in Logspace.

[BibT_eX]

[DOI]

SIAM J. Comput., 2011

Untangling planar graphs from a specified vertex position - Hard cases.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2011

On Collinear Sets in Straight-Line Drawings.

[BibT_eX]

[DOI]

Alexander Ravsky

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2011

2010

Fermat's Spiral and the Line Between Yin and Yang.

[BibT_eX]

[DOI]

Taras O. Banakh

Yaroslav Vorobets

Am. Math. Mon., 2010

Interval Graphs: Canonical Representation in Logspace.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2010

2009

Logical Complexity of Graphs: A Survey.

[BibT_eX]

Proceedings of the Model Theoretic Methods in Finite Combinatorics, 2009

2008

On the obfuscation complexity of planar graphs.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2008

Obfuscated Drawings of Planar Graphs

[BibT_eX]

[DOI]

CoRR, 2008

Zero-Knowledge Proofs of the Conjugacy for Permutation Groups

[BibT_eX]

[DOI]

CoRR, 2008

On the Double Coset Membership Problem for Permutation Groups

[BibT_eX]

[DOI]

CoRR, 2008

From Invariants to Canonization in Parallel.

[BibT_eX]

[DOI]

Proceedings of the Computer Science, 2008

2007

On the Computational Complexity of the Forcing Chromatic Number.

[BibT_eX]

[DOI]

Frank Harary

Wolfgang Slany

SIAM J. Comput., 2007

Decomposable graphs and definitions with no quantifier alternation.

[BibT_eX]

[DOI]

Joel Spencer

Eur. J. Comb., 2007

First-Order Definability of Trees and Sparse Random Graphs.

[BibT_eX]

[DOI]

Comb. Probab. Comput., 2007

Planar Graphs: Logical Complexity and Parallel Isomorphism Tests.

[BibT_eX]

[DOI]

Proceedings of the STACS 2007, 2007

2006

The first order definability of graphs: Upper bounds for quantifier depth.

[BibT_eX]

[DOI]

Helmut Veith

Discret. Appl. Math., 2006

Succinct definitions in the first order theory of graphs.

[BibT_eX]

[DOI]

Joel Spencer

Ann. Pure Appl. Log., 2006

Testing Graph Isomorphism in Parallel by Playing a Game.

[BibT_eX]

[DOI]

Martin Grohe

Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006

2005

The first order definability of graphs with separators via the Ehrenfeucht game.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2005

How complex are random graphs in first order logic?

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2005

Descriptive complexity of finite structures: Saving the quantifier rank.

[BibT_eX]

[DOI]

J. Symb. Log., 2005

2004

On the lengths of symmetry breaking-preserving games on graphs.

[BibT_eX]

[DOI]

Frank Harary

Wolfgang Slany

Theor. Comput. Sci., 2004

2002

Error Reduction by Parallel Repetition - A Negative Result.

[BibT_eX]

[DOI]

Uriel Feige

Comb., 2002

On Asymmetric Colorings of Integer Grids.

[BibT_eX]

Taras O. Banakh

Ya. Kmit

Oleg V. Verbitsky

Ars Comb., 2002

2001

Remarks on a Query-Based Variant of the Parallel Repetition Theorem.

[BibT_eX]

[DOI]

Int. J. Found. Comput. Sci., 2001

A Symmetric Strategy in Graph Avoidance Games

[BibT_eX]

[DOI]

Frank Harary

Wolfgang Slany

CoRR, 2001

2000

A Ramsey Treatment of Symmetry.

[BibT_eX]

[DOI]

Taras O. Banakh

Oleg V. Verbitsky

Yaroslav Vorobets

Electron. J. Comb., 2000

1999

Arthur-Merlin Games in Boolean Decision Trees.

[BibT_eX]

[DOI]

Ran Raz

Gábor Tardos

Nikolai K. Vereshchagin

J. Comput. Syst. Sci., 1999

1996

Towards the Parallel Repetition Conjecture.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1996

1995

The Parallel Repetition Conjecture for Trees is True

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1995

On the Hardness of Approximating Some Optimization Problems That Are Supposedly Easier Than MAX CLIQUE.

[BibT_eX]

[DOI]