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 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Sandra Kiefer and Daniel Neuen. A Study of Weisfeiler-Leman Colorings on Planar Graphs. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 81:1-81:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{kiefer_et_al:LIPIcs.ICALP.2022.81, author = {Kiefer, Sandra and Neuen, Daniel}, title = {{A Study of Weisfeiler-Leman Colorings on Planar Graphs}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {81:1--81:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.81}, URN = {urn:nbn:de:0030-drops-164228}, doi = {10.4230/LIPIcs.ICALP.2022.81}, annote = {Keywords: Weisfeiler-Leman algorithm, planar graphs, edge-transitive graphs, fixing number} }
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 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Sandra Kiefer and Daniel Neuen. The Power of the Weisfeiler-Leman Algorithm to Decompose Graphs. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 45:1-45:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{kiefer_et_al:LIPIcs.MFCS.2019.45, author = {Kiefer, Sandra and Neuen, Daniel}, title = {{The Power of the Weisfeiler-Leman Algorithm to Decompose Graphs}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {45:1--45:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-117-7}, ISSN = {1868-8969}, year = {2019}, volume = {138}, editor = {Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.45}, URN = {urn:nbn:de:0030-drops-109893}, doi = {10.4230/LIPIcs.MFCS.2019.45}, annote = {Keywords: Weisfeiler-Leman, separators, first-order logic, counting quantifiers} }
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 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)
Amey Bhangale, Ramprasad Saptharishi, Girish Varma, and Rakesh Venkat. On Fortification of Projection Games. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 497-511, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{bhangale_et_al:LIPIcs.APPROX-RANDOM.2015.497, author = {Bhangale, Amey and Saptharishi, Ramprasad and Varma, Girish and Venkat, Rakesh}, title = {{On Fortification of Projection Games}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)}, pages = {497--511}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-89-7}, ISSN = {1868-8969}, year = {2015}, volume = {40}, editor = {Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.497}, URN = {urn:nbn:de:0030-drops-53204}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2015.497}, annote = {Keywords: Parallel Repetition, Fortification} }
Published in: LIPIcs, Volume 33, 30th Conference on Computational Complexity (CCC 2015)
Kai-Min Chung, Xiaodi Wu, and Henry Yuen. Parallel Repetition for Entangled k-player Games via Fast Quantum Search. In 30th Conference on Computational Complexity (CCC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 33, pp. 512-536, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{chung_et_al:LIPIcs.CCC.2015.512, author = {Chung, Kai-Min and Wu, Xiaodi and Yuen, Henry}, title = {{Parallel Repetition for Entangled k-player Games via Fast Quantum Search}}, booktitle = {30th Conference on Computational Complexity (CCC 2015)}, pages = {512--536}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-81-1}, ISSN = {1868-8969}, year = {2015}, volume = {33}, editor = {Zuckerman, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2015.512}, URN = {urn:nbn:de:0030-drops-50727}, doi = {10.4230/LIPIcs.CCC.2015.512}, annote = {Keywords: Parallel repetition, quantum entanglement, communication complexity} }
Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)
Pascal Schweitzer. Towards an Isomorphism Dichotomy for Hereditary Graph Classes. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 689-702, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{schweitzer:LIPIcs.STACS.2015.689, author = {Schweitzer, Pascal}, title = {{Towards an Isomorphism Dichotomy for Hereditary Graph Classes}}, booktitle = {32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)}, pages = {689--702}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-78-1}, ISSN = {1868-8969}, year = {2015}, volume = {30}, editor = {Mayr, Ernst W. and Ollinger, Nicolas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.689}, URN = {urn:nbn:de:0030-drops-49513}, doi = {10.4230/LIPIcs.STACS.2015.689}, annote = {Keywords: graph isomorphism, modular decomposition, bounded color valence, reductions, forbidden induced subgraphs} }
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} }
Feedback for Dagstuhl Publishing