default search action
Oleg Verbitsky 0001
Oleg V. Verbitsky 0001
Person information
- affiliation: Humboldt University of Berlin, Department of Computer Science, Germany
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2024
- [c29]Vikraman Arvind, Frank Fuhlbrück
, Johannes Köbler, Oleg Verbitsky:
On a Hierarchy of Spectral Invariants for Graphs. STACS 2024: 6:1-6:18 - [c28]Oleg Verbitsky, Maksim Zhukovskii:
Canonization of a Random Circulant Graph by Counting Walks. WALCOM 2024: 319-334 - [i42]Vikraman Arvind, Johannes Köbler, Oleg Verbitsky:
On the Expressibility of the Reconstructional Color Refinement. CoRR abs/2406.09351 (2024) - [i41]Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky, Maksim Zhukovskii:
Gathering Information about a Graph by Counting Walks from a Single Vertex. CoRR abs/2409.03690 (2024) - [i40]Oleg Pikhurko, Oleg Verbitsky, Maksim Zhukovskii:
New bounds for the optimal density of covering single-insertion codes via the Turán density. CoRR abs/2409.06425 (2024) - [i39]Oleg Verbitsky, Maksim Zhukovskii:
Canonical labelling of sparse random graphs. CoRR abs/2409.18109 (2024) - 2023
- [j37]Steven Chaplick
The Complexity of Drawing Graphs on Few Lines and Few Planes. J. Graph Algorithms Appl. 27(6): 459-488 (2023) - [c27]Oleg Verbitsky, Maksim Zhukovskii:
Canonization of a Random Graph by Two Matrix-Vector Multiplications. ESA 2023: 100:1-100:13 - [i38]Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky:
On a Hierarchy of Spectral Isomorphism Invariants. CoRR abs/2310.04391 (2023) - [i37]Oleg Verbitsky, Maksim Zhukovskii:
Canonization of a random circulant graph by counting walks. CoRR abs/2310.05788 (2023) - [i36]Oleg Verbitsky, Maksim Zhukovskii:
Canonization of a random graph by two matrix-vector multiplications. CoRR abs/2312.03686 (2023) - 2022
- [j36]Vikraman Arvind, Frank Fuhlbrück
On the Weisfeiler-Leman dimension of fractional packing. Inf. Comput. 288: 104803 (2022) - [c26]Sergei Kiselev
On Anti-stochastic Properties of Unlabeled Graphs. WG 2022: 300-312 - 2021
- [j35]Frank Fuhlbrück
Local WL invariance and hidden shades of regularity. Discret. Appl. Math. 305: 191-198 (2021) - [j34]Frank Fuhlbrück
Identifiability of Graphs with Small Color Classes by the Weisfeiler-Leman Algorithm. SIAM J. Discret. Math. 35(3): 1792-1853 (2021) - [j33]Frank Fuhlbrück
The Weisfeiler-Leman algorithm and recognition of graph properties. Theor. Comput. Sci. 895: 96-114 (2021) - [c25]Frank Fuhlbrück, Johannes Köbler, Ilia Ponomarenko, Oleg Verbitsky:
The Weisfeiler-Leman Algorithm and Recognition of Graph Properties. CIAC 2021: 245-257 - [i35]Sergei Kiselev, Andrey Kupavskii, Oleg Verbitsky, Maksim Zhukovskii:
On anti-stochastic properties of unlabeled graphs. CoRR abs/2112.04395 (2021) - 2020
- [j32]Vikraman Arvind, Frank Fuhlbrück
On Weisfeiler-Leman invariance: Subgraph counts and related graph properties. J. Comput. Syst. Sci. 113: 42-59 (2020) - [j31]Steven Chaplick
Drawing graphs on few lines and few planes. J. Comput. Geom. 11(1): 433-475 (2020) - [c24]Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky:
On the Weisfeiler-Leman Dimension of Fractional Packing. LATA 2020: 357-368 - [c23]Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky:
Identifiability of Graphs with Small Color Classes by the Weisfeiler-Leman Algorithm. STACS 2020: 43:1-43:18 - [i34]Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky:
Local WL Invariance and Hidden Shades of Regularity. CoRR abs/2002.04590 (2020) - [i33]Frank Fuhlbrück
The Weisfeiler-Leman Algorithm and Recognition of Graph Properties. CoRR abs/2005.08887 (2020)
2010 – 2019
- 2019
- [j30]Oleg Verbitsky, Maksim Zhukovskii:
On the First-Order Complexity of Induced Subgraph Isomorphism. Log. Methods Comput. Sci. 15(1) (2019) - [j29]Oleg Verbitsky
The Descriptive Complexity of Subgraph Isomorphism Without Numerics. Theory Comput. Syst. 63(4): 902-921 (2019) - [j28]Oleg Verbitsky, Maksim Zhukovskii:
Tight Bounds on the Asymptotic Descriptive Complexity of Subgraph Isomorphism. ACM Trans. Comput. Log. 20(2): 9:1-9:18 (2019) - [c22]Vikraman Arvind, Frank Fuhlbrück
On Weisfeiler-Leman Invariance: Subgraph Counts and Related Graph Properties. FCT 2019: 111-125 - [i32]Frank Fuhlbrück
Identifiability of Graphs with Small Color Classes by the Weisfeiler-Leman Algorithm. CoRR abs/1907.02892 (2019) - [i31]Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky:
On the Weisfeiler-Leman Dimension of Fractional Packing. CoRR abs/1910.11325 (2019) - 2018
- [j27]Christoph Berkholz, Oleg Verbitsky
On the speed of constraint propagation and the time complexity of arc consistency testing. J. Comput. Syst. Sci. 91: 104-114 (2018) - [i30]Oleg Verbitsky, Maksim Zhukovskii:
Tight Bounds on the Asymptotic Descriptive Complexity of Subgraph Isomorphism. CoRR abs/1802.02143 (2018) - [i29]Vikraman Arvind, Frank Fuhlbrück
On Weisfeiler-Leman Invariance: Subgraph Counts and Related Graph Properties. CoRR abs/1811.04801 (2018) - 2017
- [j26]Vikraman Arvind, Johannes Köbler, Gaurav Rattan
Graph Isomorphism, Color Refinement, and Compactness. Comput. Complex. 26(3): 627-685 (2017) - [j25]Johannes Köbler
Circular-arc hypergraphs: Rigidity via connectedness. Discret. Appl. Math. 217: 220-228 (2017) - [c21]Oleg Verbitsky, Maksim Zhukovskii:
On the First-Order Complexity of Induced Subgraph Isomorphism. CSL 2017: 40:1-40:16 - [c20]Oleg Verbitsky, Maksim Zhukovskii:
The Descriptive Complexity of Subgraph Isomorphism Without Numerics. CSR 2017: 308-322 - [c19]Steven Chaplick
The Complexity of Drawing Graphs on Few Lines and Few Planes. WADS 2017: 265-276 - [i28]Oleg Verbitsky, Maksim Zhukovskii:
On the First-Order Complexity of Induced Subgraph Isomorphism. CoRR abs/1704.02237 (2017) - 2016
- [j24]Johannes Köbler, Sebastian Kuhnert
On the isomorphism problem for Helly circular-arc graphs. Inf. Comput. 247: 266-277 (2016) - [j23]Johannes Köbler, Sebastian Kuhnert
Solving the canonical representation and Star System Problems for proper circular-arc graphs in logspace. J. Discrete Algorithms 38-41: 38-49 (2016) - [c18]Steven Chaplick
Drawing Graphs on Few Lines and Few Planes. GD 2016: 166-180 - [i27]Steven Chaplick, Krzysztof Fleszar, Fabian Lipp, Alexander Ravsky, Oleg Verbitsky, Alexander Wolff:
Drawing Graphs on Few Lines and Few Planes. CoRR abs/1607.01196 (2016) - [i26]Steven Chaplick, Krzysztof Fleszar, Fabian Lipp, Alexander Ravsky, Oleg Verbitsky, Alexander Wolff:
The Complexity of Drawing Graphs on Few Lines and Few Planes. CoRR abs/1607.06444 (2016) - [i25]Oleg Verbitsky, Maksim Zhukovskii:
The Descriptive Complexity of Subgraph Isomorphism in the Absence of Order. CoRR abs/1607.08067 (2016) - 2015
- [j22]Christoph Berkholz, Andreas Krebs, Oleg Verbitsky:
Bounds for the Quantifier Depth in Finite-Variable Logics: Alternation Hierarchy. ACM Trans. Comput. Log. 16(3): 21:1-21:26 (2015) - [c17]Vikraman Arvind, Johannes Köbler, Gaurav Rattan, Oleg Verbitsky:
On the Power of Color Refinement. FCT 2015: 339-350 - [c16]Andreas Krebs, Oleg Verbitsky:
Universal Covers, Color Refinement, and Two-Variable Counting Logic: Lower Bounds for the Depth. LICS 2015: 689-700 - [c15]Vikraman Arvind, Johannes Köbler, Gaurav Rattan, Oleg Verbitsky:
On Tinhofer's Linear Programming Approach to Isomorphism Testing. MFCS (2) 2015: 26-37 - [i24]Vikraman Arvind, Johannes Köbler, Gaurav Rattan, Oleg Verbitsky:
Graph Isomorphism, Color Refinement, and Compactness. CoRR abs/1502.01255 (2015) - [i23]Vikraman Arvind, Johannes Köbler, Gaurav Rattan
Graph Isomorphism, Color Refinement, and Compactness. Electron. Colloquium Comput. Complex. TR15 (2015) - 2014
- [i22]Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky:
On the Isomorphism Problem for Helly Circular-Arc Graphs. CoRR abs/1402.4642 (2014) - [i21]Andreas Krebs, Oleg Verbitsky:
Universal covers, color refinement, and two-variable logic with counting quantifiers: Lower bounds for the depth. CoRR abs/1407.3175 (2014) - 2013
- [c14]Christoph Berkholz, Andreas Krebs, Oleg Verbitsky:
Bounds for the quantifier depth in finite-variable logics: Alternation hierarchy. CSL 2013: 61-80 - [c13]Christoph Berkholz, Oleg Verbitsky
On the Speed of Constraint Propagation and the Time Complexity of Arc Consistency Testing. MFCS 2013: 159-170 - [c12]Johannes Köbler, Sebastian Kuhnert
Helly Circular-Arc Graph Isomorphism Is in Logspace. MFCS 2013: 631-642 - [i20]Christoph Berkholz, Oleg Verbitsky:
On the speed of constraint propagation and the time complexity of arc consistency testing. CoRR abs/1303.7077 (2013) - [i19]Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky:
Circular-arc hypergraphs: Rigidity via Connectedness. CoRR abs/1312.1172 (2013) - [i18]Oleg Verbitsky:
On the dynamic width of the 3-colorability problem. CoRR abs/1312.5937 (2013) - [i17]Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky:
Helly Circular-Arc Graph Isomorphism is in Logspace. Electron. Colloquium Comput. Complex. TR13 (2013) - 2012
- [j21]Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky:
Around and Beyond the Isomorphism Problem for Interval Graphs. Bull. EATCS 107: 43-71 (2012) - [c11]Johannes Köbler, Sebastian Kuhnert
Solving the Canonical Representation and Star System Problems for Proper Circular-Arc Graphs in Logspace. FSTTCS 2012: 387-399 - [i16]Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky:
Solving the Canonical Representation and Star System Problems for Proper Circular-Arc Graphs in Log-Space. CoRR abs/1202.4406 (2012) - [i15]Christoph Berkholz, Oleg Verbitsky:
Bounds for the quantifier depth in two-variable logic. CoRR abs/1212.2747 (2012) - 2011
- [j20]Mihyun Kang
Untangling planar graphs from a specified vertex position - Hard cases. Discret. Appl. Math. 159(8): 789-799 (2011) - [j19]Johannes Köbler, Sebastian Kuhnert
Interval Graphs: Canonical Representations in Logspace. SIAM J. Comput. 40(5): 1292-1315 (2011) - [c10]Alexander Ravsky, Oleg Verbitsky
On Collinear Sets in Straight-Line Drawings. WG 2011: 295-306 - 2010
- [j18]Taras O. Banakh
Fermat's Spiral and the Line Between Yin and Yang. Am. Math. Mon. 117(9): 786-800 (2010) - [c9]Johannes Köbler, Sebastian Kuhnert
Interval Graphs: Canonical Representation in Logspace. ICALP (1) 2010: 384-395 - [i14]Oleg Pikhurko, Oleg Verbitsky:
Logical complexity of graphs: a survey. CoRR abs/1003.4865 (2010) - [i13]Johannes Köbler, Sebastian Kuhnert, Bastian Laubner, Oleg Verbitsky:
Interval Graphs: Canonical Representation in Logspace. Electron. Colloquium Comput. Complex. TR10 (2010)
2000 – 2009
- 2009
- [c8]Oleg Pikhurko, Oleg Verbitsky:
Logical Complexity of Graphs: A Survey. AMS-ASL Joint Special Session 2009: 129-180 - 2008
- [j17]Oleg Verbitsky
On the obfuscation complexity of planar graphs. Theor. Comput. Sci. 396(1-3): 294-300 (2008) - [c7]Johannes Köbler, Oleg Verbitsky
From Invariants to Canonization in Parallel. CSR 2008: 216-227 - [i12]Oleg Verbitsky:
On the Double Coset Membership Problem for Permutation Groups. CoRR abs/0801.4911 (2008) - [i11]Oleg Verbitsky:
Zero-Knowledge Proofs of the Conjugacy for Permutation Groups. CoRR abs/0801.4917 (2008) - [i10]Mihyun Kang, Oleg Pikhurko, Alexander Ravsky, Mathias Schacht, Oleg Verbitsky:
Obfuscated Drawings of Planar Graphs. CoRR abs/0803.0858 (2008) - [i9]Alexander Ravsky, Oleg Verbitsky:
On collinear sets in straight line drawings. CoRR abs/0806.0253 (2008) - 2007
- [j16]Tom Bohman
First-Order Definability of Trees and Sparse Random Graphs. Comb. Probab. Comput. 16(3): 375-400 (2007) - [j15]Oleg Pikhurko, Joel Spencer, Oleg Verbitsky
Decomposable graphs and definitions with no quantifier alternation. Eur. J. Comb. 28(8): 2264-2283 (2007) - [j14]Frank Harary, Wolfgang Slany, Oleg Verbitsky
On the Computational Complexity of the Forcing Chromatic Number. SIAM J. Comput. 37(1): 1-19 (2007) - [c6]Oleg Verbitsky:
Planar Graphs: Logical Complexity and Parallel Isomorphism Tests. STACS 2007: 682-693 - [i8]Oleg Verbitsky:
On the Obfuscation Complexity of Planar Graphs. CoRR abs/0705.3748 (2007) - 2006
- [j13]Oleg Pikhurko, Joel Spencer, Oleg Verbitsky
Succinct definitions in the first order theory of graphs. Ann. Pure Appl. Log. 139(1-3): 74-109 (2006) - [j12]Oleg Pikhurko, Helmut Veith, Oleg Verbitsky
The first order definability of graphs: Upper bounds for quantifier depth. Discret. Appl. Math. 154(17): 2511-2529 (2006) - [c5]Martin Grohe
Testing Graph Isomorphism in Parallel by Playing a Game. ICALP (1) 2006: 3-14 - [i7]Martin Grohe, Oleg Verbitsky:
Testing Graph Isomorphism in Parallel by Playing a Game. CoRR abs/cs/0603054 (2006) - [i6]Oleg Verbitsky:
Planar Graphs: Logical Complexity and Parallel Isomorphism Tests. CoRR abs/cs/0607033 (2006) - [i5]Johannes Köbler, Oleg Verbitsky:
From Invariants to Canonization in Parallel. CoRR abs/cs/0608074 (2006) - 2005
- [j11]Oleg Pikhurko, Oleg Verbitsky
Descriptive complexity of finite structures: Saving the quantifier rank. J. Symb. Log. 70(2): 419-450 (2005) - [j10]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) - [j9]Oleg Verbitsky
The first order definability of graphs with separators via the Ehrenfeucht game. Theor. Comput. Sci. 343(1-2): 158-176 (2005) - [c4]Frank Harary, Wolfgang Slany, Oleg Verbitsky:
On the Computational Complexity of the Forcing Chromatic Number. STACS 2005: 182-193 - 2004
- [j8]Frank Harary, Wolfgang Slany, Oleg Verbitsky
On the lengths of symmetry breaking-preserving games on graphs. Theor. Comput. Sci. 313(3): 427-446 (2004) - [i4]Frank Harary, Wolfgang Slany, Oleg Verbitsky:
On Computational Complexity of the Forcing Chromatic Number. CoRR cs.CC/0406044 (2004) - 2002
- [j7]Taras O. Banakh, Ya. Kmit, Oleg V. Verbitsky:
On Asymmetric Colorings of Integer Grids. Ars Comb. 62 (2002) - [j6]Uriel Feige, Oleg Verbitsky
Error Reduction by Parallel Repetition - A Negative Result. Comb. 22(4): 461-478 (2002) - 2001
- [j5]Oleg Verbitsky
Remarks on a Query-Based Variant of the Parallel Repetition Theorem. Int. J. Found. Comput. Sci. 12(4): 517-532 (2001) - [i3]Frank Harary, Wolfgang Slany, Oleg Verbitsky:
A Symmetric Strategy in Graph Avoidance Games. CoRR cs.DM/0110049 (2001) - 2000
- [j4]Taras O. Banakh, Oleg V. Verbitsky, Yaroslav Vorobets:
A Ramsey Treatment of Symmetry. Electron. J. Comb. 7 (2000)
1990 – 1999
- 1999
- [j3]Ran Raz
Arthur-Merlin Games in Boolean Decision Trees. J. Comput. Syst. Sci. 59(2): 346-372 (1999) - 1998
- [c3]Ran Raz
Arthur-Merlin Games in Boolean Decision Trees. CCC 1998: 58-67 - 1997
- [i2]Ran Raz, Gábor Tardos, Oleg Verbitsky, Nikolai K. Vereshchagin:
Arthur-Merlin Games in Boolean Decision Trees. Electron. Colloquium Comput. Complex. TR97 (1997) - 1996
- [j2]Oleg Verbitsky
Towards the Parallel Repetition Conjecture. Theor. Comput. Sci. 157(2): 277-282 (1996) - [c2]Uriel Feige, Oleg Verbitsky:
Error Reduction by Parallel Repetition - a Negative Result. CCC 1996: 70-76 - 1995
- [j1]Oleg Verbitsky:
On the Hardness of Approximating Some Optimization Problems That Are Supposedly Easier Than MAX CLIQUE. Comb. Probab. Comput. 4: 167-180 (1995) - [i1]Oleg Verbitsky:
The Parallel Repetition Conjecture for Trees is True. Electron. Colloquium Comput. Complex. TR95 (1995) - 1994
- [c1]Oleg Verbitsky:
Towards the Parallel Repetition Conjecture. SCT 1994: 304-307
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-10-22 20:17 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: