Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)
Nicola Galesi, Joshua A. Grochow, Toniann Pitassi, and Adrian She. On the Algebraic Proof Complexity of Tensor Isomorphism. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 4:1-4:40, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{galesi_et_al:LIPIcs.CCC.2023.4, author = {Galesi, Nicola and Grochow, Joshua A. and Pitassi, Toniann and She, Adrian}, title = {{On the Algebraic Proof Complexity of Tensor Isomorphism}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {4:1--4:40}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-282-2}, ISSN = {1868-8969}, year = {2023}, volume = {264}, editor = {Ta-Shma, Amnon}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.4}, URN = {urn:nbn:de:0030-drops-182748}, doi = {10.4230/LIPIcs.CCC.2023.4}, annote = {Keywords: Algebraic proof complexity, Tensor Isomorphism, Graph Isomorphism, Polynomial Calculus, Sum-of-Squares, reductions, lower bounds, proof complexity of linear algebra} }
Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)
Ilario Bonacina, Nicola Galesi, and Massimo Lauria. On Vanishing Sums of Roots of Unity in Polynomial Calculus and Sum-Of-Squares. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 23:1-23:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{bonacina_et_al:LIPIcs.MFCS.2022.23, author = {Bonacina, Ilario and Galesi, Nicola and Lauria, Massimo}, title = {{On Vanishing Sums of Roots of Unity in Polynomial Calculus and Sum-Of-Squares}}, booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)}, pages = {23:1--23:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-256-3}, ISSN = {1868-8969}, year = {2022}, volume = {241}, editor = {Szeider, Stefan and Ganian, Robert 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.MFCS.2022.23}, URN = {urn:nbn:de:0030-drops-168211}, doi = {10.4230/LIPIcs.MFCS.2022.23}, annote = {Keywords: polynomial calculus, sum-of-squares, roots of unity, knapsack} }
Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)
Stefan Dantchev, Nicola Galesi, Abdul Ghani, and Barnaby Martin. Depth Lower Bounds in Stabbing Planes for Combinatorial Principles. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 24:1-24:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{dantchev_et_al:LIPIcs.STACS.2022.24, author = {Dantchev, Stefan and Galesi, Nicola and Ghani, Abdul and Martin, Barnaby}, title = {{Depth Lower Bounds in Stabbing Planes for Combinatorial Principles}}, booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)}, pages = {24:1--24:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-222-8}, ISSN = {1868-8969}, year = {2022}, volume = {219}, editor = {Berenbrink, Petra and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.24}, URN = {urn:nbn:de:0030-drops-158349}, doi = {10.4230/LIPIcs.STACS.2022.24}, annote = {Keywords: proof complexity, computational complexity, lower bounds, cutting planes, stabbing planes} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Nicola Galesi, Dmitry Itsykson, Artur Riazanov, and Anastasia Sofronova. Bounded-Depth Frege Complexity of Tseitin Formulas for All Graphs. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 49:1-49:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{galesi_et_al:LIPIcs.MFCS.2019.49, author = {Galesi, Nicola and Itsykson, Dmitry and Riazanov, Artur and Sofronova, Anastasia}, title = {{Bounded-Depth Frege Complexity of Tseitin Formulas for All Graphs}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {49:1--49: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.49}, URN = {urn:nbn:de:0030-drops-109932}, doi = {10.4230/LIPIcs.MFCS.2019.49}, annote = {Keywords: Tseitin formula, treewidth, AC0-Frege} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
Stefan Dantchev, Nicola Galesi, and Barnaby Martin. Resolution and the Binary Encoding of Combinatorial Principles. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 6:1-6:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{dantchev_et_al:LIPIcs.CCC.2019.6, author = {Dantchev, Stefan and Galesi, Nicola and Martin, Barnaby}, title = {{Resolution and the Binary Encoding of Combinatorial Principles}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {6:1--6:25}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-116-0}, ISSN = {1868-8969}, year = {2019}, volume = {137}, editor = {Shpilka, Amir}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.6}, URN = {urn:nbn:de:0030-drops-108287}, doi = {10.4230/LIPIcs.CCC.2019.6}, annote = {Keywords: Proof complexity, k-DNF resolution, binary encodings, Clique and Pigeonhole principle} }
Published in: LIPIcs, Volume 33, 30th Conference on Computational Complexity (CCC 2015)
Nicola Galesi, Pavel Pudlák, and Neil Thapen. The Space Complexity of Cutting Planes Refutations. In 30th Conference on Computational Complexity (CCC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 33, pp. 433-447, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{galesi_et_al:LIPIcs.CCC.2015.433, author = {Galesi, Nicola and Pudl\'{a}k, Pavel and Thapen, Neil}, title = {{The Space Complexity of Cutting Planes Refutations}}, booktitle = {30th Conference on Computational Complexity (CCC 2015)}, pages = {433--447}, 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.433}, URN = {urn:nbn:de:0030-drops-50551}, doi = {10.4230/LIPIcs.CCC.2015.433}, annote = {Keywords: Proof Complexity, Cutting Planes, Space Complexity} }
Published in: Dagstuhl Reports, Volume 2, Issue 11 (2013)
Nadia Creignou, Nicola Galesi, Oliver Kullmann, and Heribert Vollmer. SAT Interactions (Dagstuhl Seminar 12471). In Dagstuhl Reports, Volume 2, Issue 11, pp. 87-101, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
@Article{creignou_et_al:DagRep.2.11.87, author = {Creignou, Nadia and Galesi, Nicola and Kullmann, Oliver and Vollmer, Heribert}, title = {{SAT Interactions (Dagstuhl Seminar 12471)}}, pages = {87--101}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2013}, volume = {2}, number = {11}, editor = {Creignou, Nadia and Galesi, Nicola and Kullmann, Oliver and Vollmer, Heribert}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.2.11.87}, URN = {urn:nbn:de:0030-drops-39786}, doi = {10.4230/DagRep.2.11.87}, annote = {Keywords: satisfiability problem, computational complexity, P-NP question, proof complexity, combinatorics, SAT-solvers, quantified Boolean formulas} }
Published in: Dagstuhl Seminar Proceedings, Volume 10061, Circuits, Logic, and Games (2010)
Olaf Beyersdorff, Nicola Galesi, and Massimo Lauria. Hardness of Parameterized Resolution. In Circuits, Logic, and Games. Dagstuhl Seminar Proceedings, Volume 10061, pp. 1-28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
@InProceedings{beyersdorff_et_al:DagSemProc.10061.4, author = {Beyersdorff, Olaf and Galesi, Nicola and Lauria, Massimo}, title = {{Hardness of Parameterized Resolution}}, booktitle = {Circuits, Logic, and Games}, pages = {1--28}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2010}, volume = {10061}, editor = {Benjamin Rossman and 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.dagstuhl.de/entities/document/10.4230/DagSemProc.10061.4}, URN = {urn:nbn:de:0030-drops-25254}, doi = {10.4230/DagSemProc.10061.4}, annote = {Keywords: Proof complexity, parameterized complexity, Resolution, Prover-Delayer Games} }
Feedback for Dagstuhl Publishing