Published in: LIPIcs, Volume 288, 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024)
Moritz Lichter, Benedikt Pago, and Tim Seppelt. Limitations of Game Comonads for Invertible-Map Equivalence via Homomorphism Indistinguishability. In 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 288, pp. 36:1-36:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{lichter_et_al:LIPIcs.CSL.2024.36, author = {Lichter, Moritz and Pago, Benedikt and Seppelt, Tim}, title = {{Limitations of Game Comonads for Invertible-Map Equivalence via Homomorphism Indistinguishability}}, booktitle = {32nd EACSL Annual Conference on Computer Science Logic (CSL 2024)}, pages = {36:1--36:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-310-2}, ISSN = {1868-8969}, year = {2024}, volume = {288}, editor = {Murano, Aniello and Silva, Alexandra}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2024.36}, URN = {urn:nbn:de:0030-drops-196799}, doi = {10.4230/LIPIcs.CSL.2024.36}, annote = {Keywords: finite model theory, graph isomorphism, linear-algebraic logic, homomorphism indistinguishability, game comonads, invertible-map equivalence} }
Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)
Benedikt Pago. Lower Bounds for Choiceless Polynomial Time via Symmetric XOR-Circuits. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 73:1-73:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{pago:LIPIcs.MFCS.2023.73, author = {Pago, Benedikt}, title = {{Lower Bounds for Choiceless Polynomial Time via Symmetric XOR-Circuits}}, booktitle = {48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)}, pages = {73:1--73:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-292-1}, ISSN = {1868-8969}, year = {2023}, volume = {272}, editor = {Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.73}, URN = {urn:nbn:de:0030-drops-186077}, doi = {10.4230/LIPIcs.MFCS.2023.73}, annote = {Keywords: logic in computer science, finite model theory, descriptive complexity, symmetric computation, symmetric circuits, graph isomorphism} }
Published in: LIPIcs, Volume 252, 31st EACSL Annual Conference on Computer Science Logic (CSL 2023)
Benedikt Pago. Finite Model Theory and Proof Complexity Revisited: Distinguishing Graphs in Choiceless Polynomial Time and the Extended Polynomial Calculus. In 31st EACSL Annual Conference on Computer Science Logic (CSL 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 252, pp. 31:1-31:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{pago:LIPIcs.CSL.2023.31, author = {Pago, Benedikt}, title = {{Finite Model Theory and Proof Complexity Revisited: Distinguishing Graphs in Choiceless Polynomial Time and the Extended Polynomial Calculus}}, booktitle = {31st EACSL Annual Conference on Computer Science Logic (CSL 2023)}, pages = {31:1--31:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-264-8}, ISSN = {1868-8969}, year = {2023}, volume = {252}, editor = {Klin, Bartek and Pimentel, Elaine}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2023.31}, URN = {urn:nbn:de:0030-drops-174923}, doi = {10.4230/LIPIcs.CSL.2023.31}, annote = {Keywords: finite model theory, proof complexity, graph isomorphism} }
Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
Anuj Dawar and Danny Vagnozzi. On the Relative Power of Linear Algebraic Approximations of Graph Isomorphism. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 37:1-37:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{dawar_et_al:LIPIcs.MFCS.2021.37, author = {Dawar, Anuj and Vagnozzi, Danny}, title = {{On the Relative Power of Linear Algebraic Approximations of Graph Isomorphism}}, booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)}, pages = {37:1--37:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-201-3}, ISSN = {1868-8969}, year = {2021}, volume = {202}, editor = {Bonchi, Filippo and Puglisi, Simon J.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.37}, URN = {urn:nbn:de:0030-drops-144774}, doi = {10.4230/LIPIcs.MFCS.2021.37}, annote = {Keywords: Graph isomorphism, proof complexity, invertible map tests} }
Published in: LIPIcs, Volume 183, 29th EACSL Annual Conference on Computer Science Logic (CSL 2021)
Benedikt Pago. Choiceless Computation and Symmetry: Limitations of Definability. In 29th EACSL Annual Conference on Computer Science Logic (CSL 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 183, pp. 33:1-33:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{pago:LIPIcs.CSL.2021.33, author = {Pago, Benedikt}, title = {{Choiceless Computation and Symmetry: Limitations of Definability}}, booktitle = {29th EACSL Annual Conference on Computer Science Logic (CSL 2021)}, pages = {33:1--33:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-175-7}, ISSN = {1868-8969}, year = {2021}, volume = {183}, editor = {Baier, Christel and Goubault-Larrecq, Jean}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2021.33}, URN = {urn:nbn:de:0030-drops-134673}, doi = {10.4230/LIPIcs.CSL.2021.33}, annote = {Keywords: finite model theory, descriptive complexity, choiceless computation, symmetries of combinatorial objects} }
Published in: LIPIcs, Volume 82, 26th EACSL Annual Conference on Computer Science Logic (CSL 2017)
Erich Grädel, Benedikt Pago, and Wied Pakusa. The Model-Theoretic Expressiveness of Propositional Proof Systems. In 26th EACSL Annual Conference on Computer Science Logic (CSL 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 82, pp. 27:1-27:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{gradel_et_al:LIPIcs.CSL.2017.27, author = {Gr\"{a}del, Erich and Pago, Benedikt and Pakusa, Wied}, title = {{The Model-Theoretic Expressiveness of Propositional Proof Systems}}, booktitle = {26th EACSL Annual Conference on Computer Science Logic (CSL 2017)}, pages = {27:1--27:18}, 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.27}, URN = {urn:nbn:de:0030-drops-76897}, doi = {10.4230/LIPIcs.CSL.2017.27}, annote = {Keywords: Propositional proof systems, fixed-point logics, resolution, polynomial calculus, generalized quantifiers} }
Feedback for Dagstuhl Publishing