Published in: LIPIcs, Volume 307, 30th International Conference on Principles and Practice of Constraint Programming (CP 2024)
Markus Anders, Sofia Brenner, and Gaurav Rattan. The Complexity of Symmetry Breaking Beyond Lex-Leader. In 30th International Conference on Principles and Practice of Constraint Programming (CP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 307, pp. 3:1-3:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{anders_et_al:LIPIcs.CP.2024.3, author = {Anders, Markus and Brenner, Sofia and Rattan, Gaurav}, title = {{The Complexity of Symmetry Breaking Beyond Lex-Leader}}, booktitle = {30th International Conference on Principles and Practice of Constraint Programming (CP 2024)}, pages = {3:1--3:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-336-2}, ISSN = {1868-8969}, year = {2024}, volume = {307}, editor = {Shaw, Paul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2024.3}, URN = {urn:nbn:de:0030-drops-206881}, doi = {10.4230/LIPIcs.CP.2024.3}, annote = {Keywords: symmetry breaking, boolean satisfiability, matrix models, graph isomorphism} }
Published in: LIPIcs, Volume 305, 27th International Conference on Theory and Applications of Satisfiability Testing (SAT 2024)
Markus Anders, Sofia Brenner, and Gaurav Rattan. Satsuma: Structure-Based Symmetry Breaking in SAT. In 27th International Conference on Theory and Applications of Satisfiability Testing (SAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 305, pp. 4:1-4:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{anders_et_al:LIPIcs.SAT.2024.4, author = {Anders, Markus and Brenner, Sofia and Rattan, Gaurav}, title = {{Satsuma: Structure-Based Symmetry Breaking in SAT}}, booktitle = {27th International Conference on Theory and Applications of Satisfiability Testing (SAT 2024)}, pages = {4:1--4:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-334-8}, ISSN = {1868-8969}, year = {2024}, volume = {305}, editor = {Chakraborty, Supratik and Jiang, Jie-Hong Roland}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAT.2024.4}, URN = {urn:nbn:de:0030-drops-205269}, doi = {10.4230/LIPIcs.SAT.2024.4}, annote = {Keywords: symmetry breaking, boolean satisfiability, graph isomorphism} }
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 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Eric Allender, Shuichi Hirahara, and Harsha Tirumala. Kolmogorov Complexity Characterizes Statistical Zero Knowledge. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 3:1-3:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{allender_et_al:LIPIcs.ITCS.2023.3, author = {Allender, Eric and Hirahara, Shuichi and Tirumala, Harsha}, title = {{Kolmogorov Complexity Characterizes Statistical Zero Knowledge}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {3:1--3:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-263-1}, ISSN = {1868-8969}, year = {2023}, volume = {251}, editor = {Tauman Kalai, Yael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.3}, URN = {urn:nbn:de:0030-drops-175063}, doi = {10.4230/LIPIcs.ITCS.2023.3}, annote = {Keywords: Kolmogorov Complexity, Interactive Proofs} }
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 89, 12th International Symposium on Parameterized and Exact Computation (IPEC 2017)
Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, and Jacobo Torán. Finding Small Weight Isomorphisms with Additional Constraints is Fixed-Parameter Tractable. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 2:1-2:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{arvind_et_al:LIPIcs.IPEC.2017.2, author = {Arvind, Vikraman and K\"{o}bler, Johannes and Kuhnert, Sebastian and Tor\'{a}n, Jacobo}, title = {{Finding Small Weight Isomorphisms with Additional Constraints is Fixed-Parameter Tractable}}, booktitle = {12th International Symposium on Parameterized and Exact Computation (IPEC 2017)}, pages = {2:1--2:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-051-4}, ISSN = {1868-8969}, year = {2018}, volume = {89}, editor = {Lokshtanov, Daniel and Nishimura, Naomi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.2}, URN = {urn:nbn:de:0030-drops-85690}, doi = {10.4230/LIPIcs.IPEC.2017.2}, annote = {Keywords: parameterized algorithms, hypergraph isomorphism, mislabeled graphs} }
Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)
Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, and Jacobo Torán. Parameterized Complexity of Small Weight Automorphisms. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 7:1-7:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{arvind_et_al:LIPIcs.STACS.2017.7, author = {Arvind, Vikraman and K\"{o}bler, Johannes and Kuhnert, Sebastian and Tor\'{a}n, Jacobo}, title = {{Parameterized Complexity of Small Weight Automorphisms}}, booktitle = {34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)}, pages = {7:1--7:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-028-6}, ISSN = {1868-8969}, year = {2017}, volume = {66}, editor = {Vollmer, Heribert and Vall\'{e}e, Brigitte}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.7}, URN = {urn:nbn:de:0030-drops-70278}, doi = {10.4230/LIPIcs.STACS.2017.7}, annote = {Keywords: Parameterized algorithms, hypergraph isomorphism.} }
Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)
Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, Sebastian Kuhnert, and Gaurav Rattan. The Parameterized Complexity of Fixing Number and Vertex Individualization in Graphs. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 13:1-13:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{arvind_et_al:LIPIcs.MFCS.2016.13, author = {Arvind, Vikraman and Fuhlbr\"{u}ck, Frank and K\"{o}bler, Johannes and Kuhnert, Sebastian and Rattan, Gaurav}, title = {{The Parameterized Complexity of Fixing Number and Vertex Individualization in Graphs}}, booktitle = {41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)}, pages = {13:1--13:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-016-3}, ISSN = {1868-8969}, year = {2016}, volume = {58}, editor = {Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.13}, URN = {urn:nbn:de:0030-drops-64294}, doi = {10.4230/LIPIcs.MFCS.2016.13}, annote = {Keywords: parameterized complexity, graph automorphism, fixing number, base size, individualization} }
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} }
Published in: LIPIcs, Volume 8, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)
V. Arvind, Bireswar Das, Johannes Köbler, and Seinosuke Toda. Colored Hypergraph Isomorphism is Fixed Parameter Tractable. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Leibniz International Proceedings in Informatics (LIPIcs), Volume 8, pp. 327-337, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
@InProceedings{arvind_et_al:LIPIcs.FSTTCS.2010.327, author = {Arvind, V. and Das, Bireswar and K\"{o}bler, Johannes and Toda, Seinosuke}, title = {{Colored Hypergraph Isomorphism is Fixed Parameter Tractable}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)}, pages = {327--337}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-23-1}, ISSN = {1868-8969}, year = {2010}, volume = {8}, editor = {Lodaya, Kamal and Mahajan, Meena}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2010.327}, URN = {urn:nbn:de:0030-drops-28751}, doi = {10.4230/LIPIcs.FSTTCS.2010.327}, annote = {Keywords: Fixed parameter tractability, fpt algorithms, graph isomorphism, computational complexity} }
Feedback for Dagstuhl Publishing