Published in: LIPIcs, Volume 271, 26th International Conference on Theory and Applications of Satisfiability Testing (SAT 2023)
Jacobo Torán and Florian Wörz. Cutting Planes Width and the Complexity of Graph Isomorphism Refutations. In 26th International Conference on Theory and Applications of Satisfiability Testing (SAT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 271, pp. 26:1-26:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{toran_et_al:LIPIcs.SAT.2023.26, author = {Tor\'{a}n, Jacobo and W\"{o}rz, Florian}, title = {{Cutting Planes Width and the Complexity of Graph Isomorphism Refutations}}, booktitle = {26th International Conference on Theory and Applications of Satisfiability Testing (SAT 2023)}, pages = {26:1--26:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-286-0}, ISSN = {1868-8969}, year = {2023}, volume = {271}, editor = {Mahajan, Meena and Slivovsky, Friedrich}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SAT.2023.26}, URN = {urn:nbn:de:0030-drops-184884}, doi = {10.4230/LIPIcs.SAT.2023.26}, annote = {Keywords: Cutting Planes, Proof Complexity, Linear Programming, Combinatorial Optimization, Weisfeiler-Leman Algorithm, Graph Isomorphism} }
Published in: Dagstuhl Reports, Volume 12, Issue 9 (2023)
Markus Bläser, Valentine Kabanets, Ronen Shaltiel, and Jacobo Torán. Algebraic and Analytic Methods in Computational Complexity (Dagstuhl Seminar 22371). In Dagstuhl Reports, Volume 12, Issue 9, pp. 41-59, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@Article{blaser_et_al:DagRep.12.9.41, author = {Bl\"{a}ser, Markus and Kabanets, Valentine and Shaltiel, Ronen and Tor\'{a}n, Jacobo}, title = {{Algebraic and Analytic Methods in Computational Complexity (Dagstuhl Seminar 22371)}}, pages = {41--59}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2023}, volume = {12}, number = {9}, editor = {Bl\"{a}ser, Markus and Kabanets, Valentine and Shaltiel, Ronen and Tor\'{a}n, Jacobo}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.12.9.41}, URN = {urn:nbn:de:0030-drops-178092}, doi = {10.4230/DagRep.12.9.41}, annote = {Keywords: (de-)randomization, algebra, circuits, coding, computational complexity} }
Published in: LIPIcs, Volume 216, 30th EACSL Annual Conference on Computer Science Logic (CSL 2022)
Jacobo Torán and Florian Wörz. Number of Variables for Graph Differentiation and the Resolution of GI Formulas. In 30th EACSL Annual Conference on Computer Science Logic (CSL 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 216, pp. 36:1-36:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{toran_et_al:LIPIcs.CSL.2022.36, author = {Tor\'{a}n, Jacobo and W\"{o}rz, Florian}, title = {{Number of Variables for Graph Differentiation and the Resolution of GI Formulas}}, booktitle = {30th EACSL Annual Conference on Computer Science Logic (CSL 2022)}, pages = {36:1--36:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-218-1}, ISSN = {1868-8969}, year = {2022}, volume = {216}, editor = {Manea, Florin and Simpson, Alex}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2022.36}, URN = {urn:nbn:de:0030-drops-157564}, doi = {10.4230/LIPIcs.CSL.2022.36}, annote = {Keywords: Proof Complexity, Resolution, Narrow Width, Graph Isomorphism, k-variable fragment first-order logic 𝔏\underlinek, Immerman’s Pebble Game, Symmetry Rule, SRC-1} }
Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
Jacobo Torán and Florian Wörz. Reversible Pebble Games and the Relation Between Tree-Like and General Resolution Space. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 60:1-60:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{toran_et_al:LIPIcs.STACS.2020.60, author = {Tor\'{a}n, Jacobo and W\"{o}rz, Florian}, title = {{Reversible Pebble Games and the Relation Between Tree-Like and General Resolution Space}}, booktitle = {37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)}, pages = {60:1--60: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.60}, URN = {urn:nbn:de:0030-drops-119213}, doi = {10.4230/LIPIcs.STACS.2020.60}, annote = {Keywords: Proof Complexity, Resolution, Tree-like Resolution, Pebble Game, Reversible Pebbling, Prover-Delayer Game, Raz - McKenzie Game, Clause Space, Variable Space} }
Published in: Dagstuhl Reports, Volume 8, Issue 9 (2019)
Markus Bläser, Valentine Kabanets, Jacobo Torán, and Christopher Umans. Algebraic Methods in Computational Complexity (Dagstuhl Seminar 18391). In Dagstuhl Reports, Volume 8, Issue 9, pp. 133-153, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@Article{blaser_et_al:DagRep.8.9.133, author = {Bl\"{a}ser, Markus and Kabanets, Valentine and Tor\'{a}n, Jacobo and Umans, Christopher}, title = {{Algebraic Methods in Computational Complexity (Dagstuhl Seminar 18391)}}, pages = {133--153}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2019}, volume = {8}, number = {9}, editor = {Bl\"{a}ser, Markus and Kabanets, Valentine and Tor\'{a}n, Jacobo and Umans, Christopher}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.8.9.133}, URN = {urn:nbn:de:0030-drops-103438}, doi = {10.4230/DagRep.8.9.133}, annote = {Keywords: computational complexity, algebra, (de-) randomization, circuits, coding, lower bounds} }
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-dev.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-dev.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: Dagstuhl Reports, Volume 6, Issue 10 (2017)
Valentine Kabanets, Thomas Thierauf, Jacobo Tóran, and Christopher Umans. Algebraic Methods in Computational Complexity (Dagstuhl Seminar 16411). In Dagstuhl Reports, Volume 6, Issue 10, pp. 13-32, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@Article{kabanets_et_al:DagRep.6.10.13, author = {Kabanets, Valentine and Thierauf, Thomas and T\'{o}ran, Jacobo and Umans, Christopher}, title = {{Algebraic Methods in Computational Complexity (Dagstuhl Seminar 16411)}}, pages = {13--32}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2017}, volume = {6}, number = {10}, editor = {Kabanets, Valentine and Thierauf, Thomas and T\'{o}ran, Jacobo and Umans, Christopher}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.6.10.13}, URN = {urn:nbn:de:0030-drops-69504}, doi = {10.4230/DagRep.6.10.13}, annote = {Keywords: Computational Complexity, lower bounds, approximation, pseudo-randomness, derandomization, circuits} }
Published in: Dagstuhl Reports, Volume 5, Issue 12 (2016)
László Babai, Anuj Dawar, Pascal Schweitzer, and Jacobo Torán. The Graph Isomorphism Problem (Dagstuhl Seminar 15511). In Dagstuhl Reports, Volume 5, Issue 12, pp. 1-17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@Article{babai_et_al:DagRep.5.12.1, author = {Babai, L\'{a}szl\'{o} and Dawar, Anuj and Schweitzer, Pascal and Tor\'{a}n, Jacobo}, title = {{The Graph Isomorphism Problem (Dagstuhl Seminar 15511)}}, pages = {1--17}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2016}, volume = {5}, number = {12}, editor = {Babai, L\'{a}szl\'{o} and Dawar, Anuj and Schweitzer, Pascal and Tor\'{a}n, Jacobo}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.5.12.1}, URN = {urn:nbn:de:0030-drops-58028}, doi = {10.4230/DagRep.5.12.1}, annote = {Keywords: canonical forms, complexity, computational group theory, graph isomorphism} }
Published in: LIPIcs, Volume 8, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)
Arkadev Chattopadhyay, Jacobo Torán, and Fabian Wagner. Graph Isomorphism is not AC^0 reducible to Group Isomorphism. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Leibniz International Proceedings in Informatics (LIPIcs), Volume 8, pp. 317-326, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
@InProceedings{chattopadhyay_et_al:LIPIcs.FSTTCS.2010.317, author = {Chattopadhyay, Arkadev and Tor\'{a}n, Jacobo and Wagner, Fabian}, title = {{Graph Isomorphism is not AC^0 reducible to Group Isomorphism}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)}, pages = {317--326}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2010.317}, URN = {urn:nbn:de:0030-drops-28748}, doi = {10.4230/LIPIcs.FSTTCS.2010.317}, annote = {Keywords: Complexity, Algorithms, Group Isomorphism Problem, Circuit Com plexity} }
Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)
Bireswar Das, Jacobo Torán, and Fabian Wagner. Restricted Space Algorithms for Isomorphism on Bounded Treewidth Graphs. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 227-238, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
@InProceedings{das_et_al:LIPIcs.STACS.2010.2457, author = {Das, Bireswar and Tor\'{a}n, Jacobo and Wagner, Fabian}, title = {{Restricted Space Algorithms for Isomorphism on Bounded Treewidth Graphs}}, booktitle = {27th International Symposium on Theoretical Aspects of Computer Science}, pages = {227--238}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-16-3}, ISSN = {1868-8969}, year = {2010}, volume = {5}, editor = {Marion, Jean-Yves and Schwentick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2457}, URN = {urn:nbn:de:0030-drops-24570}, doi = {10.4230/LIPIcs.STACS.2010.2457}, annote = {Keywords: Complexity, Algorithms, Graph Isomorphism Problem, Treewidth, LogCFL} }
Published in: Dagstuhl Seminar Proceedings, Volume 6451, Circuits, Logic, and Games (2007)
Uwe Schöning and Jacobo Torán. A note on the size of Craig Interpolants. In Circuits, Logic, and Games. Dagstuhl Seminar Proceedings, Volume 6451, pp. 1-9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)
@InProceedings{schoning_et_al:DagSemProc.06451.3, author = {Sch\"{o}ning, Uwe and Tor\'{a}n, Jacobo}, title = {{A note on the size of Craig Interpolants}}, booktitle = {Circuits, Logic, and Games}, pages = {1--9}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2007}, volume = {6451}, editor = {Thomas Schwentick and Denis Th\'{e}rien and Heribert Vollmer}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06451.3}, URN = {urn:nbn:de:0030-drops-9735}, doi = {10.4230/DagSemProc.06451.3}, annote = {Keywords: Interpolant, non-uniform complexity} }
Feedback for Dagstuhl Publishing