×

zbMATH — the first resource for mathematics

Verbitsky, Oleg

Compute Distance To:
Author ID: verbitsky.oleg Recent zbMATH articles by "Verbitsky, Oleg"
Published as: Verbitsky, Oleg; Verbitsky, O.
External Links: MGP
Documents Indexed: 60 Publications since 1995

Publications by Year

Citations contained in zbMATH Open

44 Publications have been cited 144 times in 84 Documents Cited by Year
How complex are random graphs in first order logic? Zbl 1060.05085
Kim, Jeong Han; Pikhurko, Oleg; Spencer, Joel H.; Verbitsky, Oleg
14
2005
Succinct definitions in the first order theory of graphs. Zbl 1089.03023
Pikhurko, Oleg; Spencer, Joel; Verbitsky, Oleg
11
2006
On collinear sets in straight-line drawings. Zbl 1341.05045
Ravsky, Alexander; Verbitsky, Oleg
9
2011
Interval graphs: canonical representations in logspace. Zbl 1235.05140
Köbler, Johannes; Kuhnert, Sebastian; Laubner, Bastian; Verbitsky, Oleg
8
2011
On the obfuscation complexity of planar graphs. Zbl 1155.68059
Verbitsky, Oleg
7
2008
Solving the canonical representation and star system problems for proper circular-arc graphs in logspace. Zbl 1355.68124
Köbler, Johannes; Kuhnert, Sebastian; Verbitsky, Oleg
6
2016
Error reduction by parallel repetition - a negative result. Zbl 1017.68052
Feige, Uriel; Verbitsky, Oleg
6
2002
Testing graph isomorphism in parallel by playing a game. Zbl 1223.68056
Grohe, Martin; Verbitsky, Oleg
6
2006
The complexity of drawing graphs on few lines and few planes. Zbl 1457.68207
Chaplick, Steven; Fleszar, Krzysztof; Lipp, Fabian; Ravsky, Alexander; Verbitsky, Oleg; Wolff, Alexander
5
2017
From invariants to canonization in parallel. Zbl 1142.68354
Köbler, Johannes; Verbitsky, Oleg
5
2008
Untangling planar graphs from a specified vertex position-Hard cases. Zbl 1219.05046
Kang, M.; Pikhurko, O.; Ravsky, A.; Schacht, M.; Verbitsky, O.
5
2011
The descriptive complexity of subgraph isomorphism without numerics. Zbl 1435.68113
Verbitsky, Oleg; Zhukovskii, Maksim
4
2017
Logical complexity of graphs: a survey. Zbl 1261.03117
Pikhurko, Oleg; Verbitsky, Oleg
4
2011
The first order definability of graphs: Upper bounds for quantifier depth. Zbl 1109.03023
Pikhurko, Oleg; Veith, Helmut; Verbitsky, Oleg
4
2006
Universal covers, color refinement, and two-variable counting logic: lower bounds for the depth. Zbl 1395.05134
Krebs, Andreas; Verbitsky, Oleg
3
2015
Drawing graphs on few lines and few planes. Zbl 1457.68206
Chaplick, Steven; Fleszar, Krzysztof; Lipp, Fabian; Ravsky, Alexander; Verbitsky, Oleg; Wolff, Alexander
3
2016
Descriptive complexity of finite structures: saving the quantifier rank. Zbl 1105.03029
Pikhurko, Oleg; Verbitsky, Oleg
3
2005
Helly circular-arc graph isomorphism is in logspace. Zbl 1388.68126
Köbler, Johannes; Kuhnert, Sebastian; Verbitsky, Oleg
3
2013
Planar graphs: logical complexity and parallel isomorphism tests. Zbl 1186.68215
Verbitsky, Oleg
3
2007
Graph isomorphism, color refinement, and compactness. Zbl 1379.05080
Arvind, V.; Köbler, Johannes; Rattan, Gaurav; Verbitsky, Oleg
2
2017
Solving the canonical representation and star system problems for proper circular-arc graphs in logspace. Zbl 1354.68125
Köbler, Johannes; Kuhnert, Sebastian; Verbitsky, Oleg
2
2012
A Ramsey treatment of symmetry. Zbl 0960.05101
Banakh, T.; Verbitsky, O.; Vorobets, Ya.
2
2000
Towards the parallel repetition conjecture. Zbl 0871.68008
Verbitsky, Oleg
2
1996
A symmetric strategy in graph avoidance games. Zbl 1046.91013
Harary, Frank; Slany, Wolfgang; Verbitsky, Oleg
2
2002
The first order definability of graphs with separators via the Ehrenfeucht game. Zbl 1083.03039
Verbitsky, Oleg
2
2005
The descriptive complexity of subgraph isomorphism without numerics. Zbl 1435.68114
Verbitsky, Oleg; Zhukovskii, Maksim
2
2019
On the speed of constraint propagation and the time complexity of arc consistency testing. Zbl 1378.68058
Berkholz, Christoph; Verbitsky, Oleg
2
2013
First-order definability of trees and sparse random graphs. Zbl 1119.03025
Bohman, Tom; Frieze, Alan; Łuczak, Tomasz; Pikhurko, Oleg; Smyth, Clifford; Spencer, Joel; Verbitsky, Oleg
2
2007
Interval graphs: canonical representation in logspace. Zbl 1288.05281
Köbler, Johannes; Kuhnert, Sebastian; Laubner, Bastian; Verbitsky, Oleg
2
2010
On the first-order complexity of induced subgraph isomorphism. Zbl 1434.03092
Verbitsky, Oleg; Zhukovskii, Maksim
1
2017
On Weisfeiler-Leman invariance: subgraph counts and related graph properties. Zbl 1450.05056
Arvind, V.; Fuhlbrück, Frank; Köbler, Johannes; Verbitsky, Oleg
1
2020
Bounds for the quantifier depth in finite-variable logics: alternation hierarchy. Zbl 1356.03077
Berkholz, Christoph; Krebs, Andreas; Verbitsky, Oleg
1
2013
Ramseyan variations on symmetric subsequences. Zbl 1164.05463
Verbitsky, Oleg
1
2003
Symmetric subsets of lattice paths. Zbl 0955.11004
Verbitsky, Oleg
1
2000
Arthur-Merlin games in Boolean decision trees. Zbl 0948.68166
Raz, Ran; Tardos, Gábor; Verbitsky, Oleg; Vereshchagin, Nikolai
1
1999
On the computational complexity of the forcing chromatic number. Zbl 1118.68508
Harary, Frank; Slany, Wolfgang; Verbitsky, Oleg
1
2005
On the lengths of symmetry breaking-preserving games on graphs. Zbl 1105.91009
Harary, F.; Slany, W.; Verbitsky, O.
1
2004
Around and beyond the isomorphism problem for interval graphs. Zbl 1394.68187
Köbler, Johannes; Kuhnert, Sebastian; Verbitsky, Oleg
1
2012
Bounds for the quantifier depth in finite-variable logics: alternation hierarchy. Zbl 1354.03038
Berkholz, Christoph; Krebs, Andreas; Verbitsky, Oleg
1
2015
On the power of color refinement. Zbl 1436.05101
Arvind, V.; Köbler, Johannes; Rattan, Gaurav; Verbitsky, Oleg
1
2015
On the first-order complexity of induced subgraph isomorphism. Zbl 1432.03049
Verbitsky, Oleg; Zhukovskii, Maksim
1
2019
Structural properties of extremal asymmetric colourings. Zbl 1061.05096
Verbitsky, Oleg
1
2003
Arthur-Merlin games in Boolean decision trees. Zbl 0946.68055
Raz, Ran; Tardos, Gábor; Verbitsky, Oleg; Vereshagin, Nikolai
1
1998
Decomposable graphs and definitions with no quantifier alternation. Zbl 1124.03011
Pikhurko, Oleg; Spencer, Joel; Verbitsky, Oleg
1
2007
On Weisfeiler-Leman invariance: subgraph counts and related graph properties. Zbl 1450.05056
Arvind, V.; Fuhlbrück, Frank; Köbler, Johannes; Verbitsky, Oleg
1
2020
The descriptive complexity of subgraph isomorphism without numerics. Zbl 1435.68114
Verbitsky, Oleg; Zhukovskii, Maksim
2
2019
On the first-order complexity of induced subgraph isomorphism. Zbl 1432.03049
Verbitsky, Oleg; Zhukovskii, Maksim
1
2019
The complexity of drawing graphs on few lines and few planes. Zbl 1457.68207
Chaplick, Steven; Fleszar, Krzysztof; Lipp, Fabian; Ravsky, Alexander; Verbitsky, Oleg; Wolff, Alexander
5
2017
The descriptive complexity of subgraph isomorphism without numerics. Zbl 1435.68113
Verbitsky, Oleg; Zhukovskii, Maksim
4
2017
Graph isomorphism, color refinement, and compactness. Zbl 1379.05080
Arvind, V.; Köbler, Johannes; Rattan, Gaurav; Verbitsky, Oleg
2
2017
On the first-order complexity of induced subgraph isomorphism. Zbl 1434.03092
Verbitsky, Oleg; Zhukovskii, Maksim
1
2017
Solving the canonical representation and star system problems for proper circular-arc graphs in logspace. Zbl 1355.68124
Köbler, Johannes; Kuhnert, Sebastian; Verbitsky, Oleg
6
2016
Drawing graphs on few lines and few planes. Zbl 1457.68206
Chaplick, Steven; Fleszar, Krzysztof; Lipp, Fabian; Ravsky, Alexander; Verbitsky, Oleg; Wolff, Alexander
3
2016
Universal covers, color refinement, and two-variable counting logic: lower bounds for the depth. Zbl 1395.05134
Krebs, Andreas; Verbitsky, Oleg
3
2015
Bounds for the quantifier depth in finite-variable logics: alternation hierarchy. Zbl 1354.03038
Berkholz, Christoph; Krebs, Andreas; Verbitsky, Oleg
1
2015
On the power of color refinement. Zbl 1436.05101
Arvind, V.; Köbler, Johannes; Rattan, Gaurav; Verbitsky, Oleg
1
2015
Helly circular-arc graph isomorphism is in logspace. Zbl 1388.68126
Köbler, Johannes; Kuhnert, Sebastian; Verbitsky, Oleg
3
2013
On the speed of constraint propagation and the time complexity of arc consistency testing. Zbl 1378.68058
Berkholz, Christoph; Verbitsky, Oleg
2
2013
Bounds for the quantifier depth in finite-variable logics: alternation hierarchy. Zbl 1356.03077
Berkholz, Christoph; Krebs, Andreas; Verbitsky, Oleg
1
2013
Solving the canonical representation and star system problems for proper circular-arc graphs in logspace. Zbl 1354.68125
Köbler, Johannes; Kuhnert, Sebastian; Verbitsky, Oleg
2
2012
Around and beyond the isomorphism problem for interval graphs. Zbl 1394.68187
Köbler, Johannes; Kuhnert, Sebastian; Verbitsky, Oleg
1
2012
On collinear sets in straight-line drawings. Zbl 1341.05045
Ravsky, Alexander; Verbitsky, Oleg
9
2011
Interval graphs: canonical representations in logspace. Zbl 1235.05140
Köbler, Johannes; Kuhnert, Sebastian; Laubner, Bastian; Verbitsky, Oleg
8
2011
Untangling planar graphs from a specified vertex position-Hard cases. Zbl 1219.05046
Kang, M.; Pikhurko, O.; Ravsky, A.; Schacht, M.; Verbitsky, O.
5
2011
Logical complexity of graphs: a survey. Zbl 1261.03117
Pikhurko, Oleg; Verbitsky, Oleg
4
2011
Interval graphs: canonical representation in logspace. Zbl 1288.05281
Köbler, Johannes; Kuhnert, Sebastian; Laubner, Bastian; Verbitsky, Oleg
2
2010
On the obfuscation complexity of planar graphs. Zbl 1155.68059
Verbitsky, Oleg
7
2008
From invariants to canonization in parallel. Zbl 1142.68354
Köbler, Johannes; Verbitsky, Oleg
5
2008
Planar graphs: logical complexity and parallel isomorphism tests. Zbl 1186.68215
Verbitsky, Oleg
3
2007
First-order definability of trees and sparse random graphs. Zbl 1119.03025
Bohman, Tom; Frieze, Alan; Łuczak, Tomasz; Pikhurko, Oleg; Smyth, Clifford; Spencer, Joel; Verbitsky, Oleg
2
2007
Decomposable graphs and definitions with no quantifier alternation. Zbl 1124.03011
Pikhurko, Oleg; Spencer, Joel; Verbitsky, Oleg
1
2007
Succinct definitions in the first order theory of graphs. Zbl 1089.03023
Pikhurko, Oleg; Spencer, Joel; Verbitsky, Oleg
11
2006
Testing graph isomorphism in parallel by playing a game. Zbl 1223.68056
Grohe, Martin; Verbitsky, Oleg
6
2006
The first order definability of graphs: Upper bounds for quantifier depth. Zbl 1109.03023
Pikhurko, Oleg; Veith, Helmut; Verbitsky, Oleg
4
2006
How complex are random graphs in first order logic? Zbl 1060.05085
Kim, Jeong Han; Pikhurko, Oleg; Spencer, Joel H.; Verbitsky, Oleg
14
2005
Descriptive complexity of finite structures: saving the quantifier rank. Zbl 1105.03029
Pikhurko, Oleg; Verbitsky, Oleg
3
2005
The first order definability of graphs with separators via the Ehrenfeucht game. Zbl 1083.03039
Verbitsky, Oleg
2
2005
On the computational complexity of the forcing chromatic number. Zbl 1118.68508
Harary, Frank; Slany, Wolfgang; Verbitsky, Oleg
1
2005
On the lengths of symmetry breaking-preserving games on graphs. Zbl 1105.91009
Harary, F.; Slany, W.; Verbitsky, O.
1
2004
Ramseyan variations on symmetric subsequences. Zbl 1164.05463
Verbitsky, Oleg
1
2003
Structural properties of extremal asymmetric colourings. Zbl 1061.05096
Verbitsky, Oleg
1
2003
Error reduction by parallel repetition - a negative result. Zbl 1017.68052
Feige, Uriel; Verbitsky, Oleg
6
2002
A symmetric strategy in graph avoidance games. Zbl 1046.91013
Harary, Frank; Slany, Wolfgang; Verbitsky, Oleg
2
2002
A Ramsey treatment of symmetry. Zbl 0960.05101
Banakh, T.; Verbitsky, O.; Vorobets, Ya.
2
2000
Symmetric subsets of lattice paths. Zbl 0955.11004
Verbitsky, Oleg
1
2000
Arthur-Merlin games in Boolean decision trees. Zbl 0948.68166
Raz, Ran; Tardos, Gábor; Verbitsky, Oleg; Vereshchagin, Nikolai
1
1999
Arthur-Merlin games in Boolean decision trees. Zbl 0946.68055
Raz, Ran; Tardos, Gábor; Verbitsky, Oleg; Vereshagin, Nikolai
1
1998
Towards the parallel repetition conjecture. Zbl 0871.68008
Verbitsky, Oleg
2
1996
all top 5

Cited by 144 Authors

19 Verbitsky, Oleg
10 Zhukovskiĭ, Maksim Evgen’evich
7 Köbler, Johannes
5 Kuhnert, Sebastian
5 Pikhurko, Oleg
4 Foucaud, Florent
4 Ravsky, Alex
3 Arvind, Vikraman
3 Dujmović, Vida
3 Mertzios, George B.
3 Naserasr, Reza
3 Ostrovskii, Lev B.
3 Parreau, Aline
3 Spencer, Joel H.
3 Valicov, Petru
3 Wagner, Fabian
3 Wolff, Alexander
2 Bellitto, Thomas
2 Berkholz, Christoph
2 Das, Bireswar
2 Dinur, Irit
2 Frati, Fabrizio
2 Mchedlidze, Tamara
2 Meulemans, Wouter
2 Morin, Pat
2 Schweitzer, Pascal
2 Soulignac, Francisco Juan
2 Vidick, Thomas
2 Yuen, Henry C.
1 Aaronson, Scott
1 Alcón, Liliana
1 Atserias, Albert
1 Auddy, Arnab
1 Aurora, Pawan Kumar
1 Baignères, Thomas
1 Bald, Samuel
1 Barbero, Florian
1 Bavarian, Mohammad
1 Blumensath, Achim
1 Bose, Prosenjit K.
1 Bova, Simone
1 Brešar, Boštjan
1 Cano, Javier
1 Chandoo, Maurice
1 Chaplick, Steven
1 Chiaselotti, Giampiero
1 Cibulka, Josef
1 Da Lozzo, Giordano
1 Dergachev, E. A.
1 Disser, Yann
1 Dravec, Tanja
1 Durocher, Stephane
1 Fleszar, Krzysztof
1 Fuhlbrück, Frank
1 Ganardi, Moses
1 Geerts, Floris
1 Gentile, Tommaso
1 Goaoc, Xavier
1 Göller, Stefan
1 Gonçalves, Daniel
1 Grohe, Martin
1 Gur, Tom
1 Gutierrez, Marisa
1 Gyarmati, Katalin
1 Harary, Frank
1 Harsha, Prahladh
1 Hatami, Hamed
1 Hültenschmidt, Gregor
1 Hurtado, Ferran
1 Infusino, Federico G.
1 Isenmann, Lucas
1 Johnson, Matthew P.
1 Kang, Mihyun
1 KhudaBukhsh, Wasiur R.
1 Kiefer, Sandra
1 Kindermann, Philipp
1 Klasing, Ralf
1 Klavík, Pavel
1 Knop, Dušan
1 Koeppl, Heinz
1 Kosowski, Adrian
1 Kraaijer, Rutger
1 Kratochvíl, Jan
1 Krebs, Andreas
1 Kryven, Myroslav
1 Kudryavtsev, Eremei D.
1 Kupavskii, Andrey
1 Langerman, Stefan
1 Lipp, Fabian
1 Liu, Ou
1 Lohrey, Markus
1 Makarov, Mikhail V.
1 Maserrat, Hossein
1 Matushkin, A. D.
1 Mauduit, Christian
1 Mehta, Nishali
1 Mehta, Shashank K.
1 Mondal, Debajyoti
1 Neopryatnaya, A. M.
1 Okamoto, Yoshio
...and 44 more Authors

Citations by Year