Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)
V. Arvind, Frank Fuhlbrück, Johannes Köbler, and Oleg Verbitsky. On a Hierarchy of Spectral Invariants for Graphs. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 6:1-6:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{arvind_et_al:LIPIcs.STACS.2024.6, author = {Arvind, V. and Fuhlbr\"{u}ck, Frank and K\"{o}bler, Johannes and Verbitsky, Oleg}, title = {{On a Hierarchy of Spectral Invariants for Graphs}}, booktitle = {41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)}, pages = {6:1--6:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-311-9}, ISSN = {1868-8969}, year = {2024}, volume = {289}, editor = {Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.6}, URN = {urn:nbn:de:0030-drops-197166}, doi = {10.4230/LIPIcs.STACS.2024.6}, annote = {Keywords: Graph Isomorphism, spectra of graphs, combinatorial refinement, strongly regular graphs} }
Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)
Oleg Verbitsky and Maksim Zhukovskii. Canonization of a Random Graph by Two Matrix-Vector Multiplications. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 100:1-100:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{verbitsky_et_al:LIPIcs.ESA.2023.100, author = {Verbitsky, Oleg and Zhukovskii, Maksim}, title = {{Canonization of a Random Graph by Two Matrix-Vector Multiplications}}, booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)}, pages = {100:1--100:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-295-2}, ISSN = {1868-8969}, year = {2023}, volume = {274}, editor = {G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.100}, URN = {urn:nbn:de:0030-drops-187536}, doi = {10.4230/LIPIcs.ESA.2023.100}, annote = {Keywords: Graph Isomorphism, canonical labeling, random graphs, walk matrix, color refinement, linear time} }
Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
Frank Fuhlbrück, Johannes Köbler, and Oleg Verbitsky. Identifiability of Graphs with Small Color Classes by the Weisfeiler-Leman Algorithm. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 43:1-43:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{fuhlbruck_et_al:LIPIcs.STACS.2020.43, author = {Fuhlbr\"{u}ck, Frank and K\"{o}bler, Johannes and Verbitsky, Oleg}, title = {{Identifiability of Graphs with Small Color Classes by the Weisfeiler-Leman Algorithm}}, booktitle = {37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)}, pages = {43:1--43:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-140-5}, ISSN = {1868-8969}, year = {2020}, volume = {154}, editor = {Paul, Christophe and Bl\"{a}ser, Markus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.43}, URN = {urn:nbn:de:0030-drops-119046}, doi = {10.4230/LIPIcs.STACS.2020.43}, annote = {Keywords: Graph Isomorphism, Weisfeiler-Leman Algorithm, Cai-F\"{u}rer-Immerman Graphs, coherent Configurations} }
Published in: LIPIcs, Volume 82, 26th EACSL Annual Conference on Computer Science Logic (CSL 2017)
Oleg Verbitsky and Maksim Zhukovskii. On the First-Order Complexity of Induced Subgraph Isomorphism. In 26th EACSL Annual Conference on Computer Science Logic (CSL 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 82, pp. 40:1-40:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{verbitsky_et_al:LIPIcs.CSL.2017.40, author = {Verbitsky, Oleg and Zhukovskii, Maksim}, title = {{On the First-Order Complexity of Induced Subgraph Isomorphism}}, booktitle = {26th EACSL Annual Conference on Computer Science Logic (CSL 2017)}, pages = {40:1--40:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-045-3}, ISSN = {1868-8969}, year = {2017}, volume = {82}, editor = {Goranko, Valentin and Dam, Mads}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2017.40}, URN = {urn:nbn:de:0030-drops-76841}, doi = {10.4230/LIPIcs.CSL.2017.40}, annote = {Keywords: the induced subgraph isomorphism problem, descriptive and computational complexity, finite-variable first-order logic, quantifier depth and variable w} }
Published in: LIPIcs, Volume 23, Computer Science Logic 2013 (CSL 2013)
Christoph Berkholz, Andreas Krebs, and Oleg Verbitsky. Bounds for the quantifier depth in finite-variable logics: Alternation hierarchy. In Computer Science Logic 2013 (CSL 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 23, pp. 61-80, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
@InProceedings{berkholz_et_al:LIPIcs.CSL.2013.61, author = {Berkholz, Christoph and Krebs, Andreas and Verbitsky, Oleg}, title = {{Bounds for the quantifier depth in finite-variable logics: Alternation hierarchy}}, booktitle = {Computer Science Logic 2013 (CSL 2013)}, pages = {61--80}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-60-6}, ISSN = {1868-8969}, year = {2013}, volume = {23}, editor = {Ronchi Della Rocca, Simona}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2013.61}, URN = {urn:nbn:de:0030-drops-41907}, doi = {10.4230/LIPIcs.CSL.2013.61}, annote = {Keywords: Alternation hierarchy, finite-variable logic} }
Published in: LIPIcs, Volume 18, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)
Johannes Köbler, Sebastian Kuhnert, and Oleg Verbitsky. Solving the Canonical Representation and Star System Problems for Proper Circular-Arc Graphs in Logspace. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 18, pp. 387-399, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)
@InProceedings{kobler_et_al:LIPIcs.FSTTCS.2012.387, author = {K\"{o}bler, Johannes and Kuhnert, Sebastian and Verbitsky, Oleg}, title = {{Solving the Canonical Representation and Star System Problems for Proper Circular-Arc Graphs in Logspace}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)}, pages = {387--399}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-47-7}, ISSN = {1868-8969}, year = {2012}, volume = {18}, editor = {D'Souza, Deepak and Radhakrishnan, Jaikumar and Telikepalli, Kavitha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2012.387}, URN = {urn:nbn:de:0030-drops-38757}, doi = {10.4230/LIPIcs.FSTTCS.2012.387}, annote = {Keywords: Proper circular-arc graphs, graph isomorphism, canonization, circular ones property, logspace complexity} }