Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Yuval Filmus, Edward A. Hirsch, Artur Riazanov, Alexander Smal, and Marc Vinyals. Proving Unsatisfiability with Hitting Formulas. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 48:1-48:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{filmus_et_al:LIPIcs.ITCS.2024.48, author = {Filmus, Yuval and Hirsch, Edward A. and Riazanov, Artur and Smal, Alexander and Vinyals, Marc}, title = {{Proving Unsatisfiability with Hitting Formulas}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {48:1--48:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-309-6}, ISSN = {1868-8969}, year = {2024}, volume = {287}, editor = {Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.48}, URN = {urn:nbn:de:0030-drops-195762}, doi = {10.4230/LIPIcs.ITCS.2024.48}, annote = {Keywords: hitting formulas, polynomial identity testing, query complexity} }
Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)
Erfan Khaniki. Nisan-Wigderson Generators in Proof Complexity: New Lower Bounds. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 17:1-17:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{khaniki:LIPIcs.CCC.2022.17, author = {Khaniki, Erfan}, title = {{Nisan-Wigderson Generators in Proof Complexity: New Lower Bounds}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {17:1--17:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-241-9}, ISSN = {1868-8969}, year = {2022}, volume = {234}, editor = {Lovett, Shachar}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.17}, URN = {urn:nbn:de:0030-drops-165799}, doi = {10.4230/LIPIcs.CCC.2022.17}, annote = {Keywords: Proof complexity, Bounded arithmetic, Bounded depth Frege, Nisan-Wigderson generators, Meta-complexity, Lower bounds} }
Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)
Susanna F. de Rezende, Massimo Lauria, Jakob Nordström, and Dmitry Sokolov. The Power of Negative Reasoning. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 40:1-40:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{derezende_et_al:LIPIcs.CCC.2021.40, author = {de Rezende, Susanna F. and Lauria, Massimo and Nordstr\"{o}m, Jakob and Sokolov, Dmitry}, title = {{The Power of Negative Reasoning}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {40:1--40:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-193-1}, ISSN = {1868-8969}, year = {2021}, volume = {200}, editor = {Kabanets, Valentine}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.40}, URN = {urn:nbn:de:0030-drops-143140}, doi = {10.4230/LIPIcs.CCC.2021.40}, annote = {Keywords: Proof complexity, Polynomial calculus, Nullstellensatz, Sums-of-squares, Sherali-Adams} }
Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)
Susanna F. de Rezende, Jakob Nordström, Kilian Risse, and Dmitry Sokolov. Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 28:1-28:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{derezende_et_al:LIPIcs.CCC.2020.28, author = {de Rezende, Susanna F. and Nordstr\"{o}m, Jakob and Risse, Kilian and Sokolov, Dmitry}, title = {{Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs}}, booktitle = {35th Computational Complexity Conference (CCC 2020)}, pages = {28:1--28:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-156-6}, ISSN = {1868-8969}, year = {2020}, volume = {169}, editor = {Saraf, Shubhangi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.28}, URN = {urn:nbn:de:0030-drops-125804}, doi = {10.4230/LIPIcs.CCC.2020.28}, annote = {Keywords: proof complexity, resolution, weak pigeonhole principle, perfect matching, sparse graphs} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
Susanna F. de Rezende, Jakob Nordström, Or Meir, and Robert Robere. Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 18:1-18:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{derezende_et_al:LIPIcs.CCC.2019.18, author = {de Rezende, Susanna F. and Nordstr\"{o}m, Jakob and Meir, Or and Robere, Robert}, title = {{Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {18:1--18:16}, 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.18}, URN = {urn:nbn:de:0030-drops-108403}, doi = {10.4230/LIPIcs.CCC.2019.18}, annote = {Keywords: proof complexity, Nullstellensatz, pebble games, trade-offs, size, degree} }
Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
Bruno Loff and Sagnik Mukhopadhyay. Lifting Theorems for Equality. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 50:1-50:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{loff_et_al:LIPIcs.STACS.2019.50, author = {Loff, Bruno and Mukhopadhyay, Sagnik}, title = {{Lifting Theorems for Equality}}, booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)}, pages = {50:1--50:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-100-9}, ISSN = {1868-8969}, year = {2019}, volume = {126}, editor = {Niedermeier, Rolf and Paul, Christophe}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.50}, URN = {urn:nbn:de:0030-drops-102892}, doi = {10.4230/LIPIcs.STACS.2019.50}, annote = {Keywords: Communication complexity, Query complexity, Simulation theorem, Equality function} }
Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)
Joël Alwen, Susanna F. de Rezende, Jakob Nordström, and Marc Vinyals. Cumulative Space in Black-White Pebbling and Resolution. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 38:1-38:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{alwen_et_al:LIPIcs.ITCS.2017.38, author = {Alwen, Jo\"{e}l and de Rezende, Susanna F. and Nordstr\"{o}m, Jakob and Vinyals, Marc}, title = {{Cumulative Space in Black-White Pebbling and Resolution}}, booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)}, pages = {38:1--38:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-029-3}, ISSN = {1868-8969}, year = {2017}, volume = {67}, editor = {Papadimitriou, Christos H.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.38}, URN = {urn:nbn:de:0030-drops-81918}, doi = {10.4230/LIPIcs.ITCS.2017.38}, annote = {Keywords: pebble game, pebbling, proof complexity, space, cumulative space, clause space, resolution, parallel resolution} }
Feedback for Dagstuhl Publishing