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-dev.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 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Ján Pich and Rahul Santhanam. Learning Algorithms Versus Automatability of Frege Systems. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 101:1-101:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{pich_et_al:LIPIcs.ICALP.2022.101, author = {Pich, J\'{a}n and Santhanam, Rahul}, title = {{Learning Algorithms Versus Automatability of Frege Systems}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {101:1--101:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.101}, URN = {urn:nbn:de:0030-drops-164427}, doi = {10.4230/LIPIcs.ICALP.2022.101}, annote = {Keywords: learning algorithms, automatability, proof complexity} }
Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Fedor Part and Iddo Tzameret. Resolution with Counting: Dag-Like Lower Bounds and Different Moduli. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 19:1-19:37, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{part_et_al:LIPIcs.ITCS.2020.19, author = {Part, Fedor and Tzameret, Iddo}, title = {{Resolution with Counting: Dag-Like Lower Bounds and Different Moduli}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {19:1--19:37}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-134-4}, ISSN = {1868-8969}, year = {2020}, volume = {151}, editor = {Vidick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.19}, URN = {urn:nbn:de:0030-drops-117041}, doi = {10.4230/LIPIcs.ITCS.2020.19}, annote = {Keywords: Proof complexity, concrete lower bounds, resolution, satisfiability, combinatorics} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
Igor Carboni Oliveira, Ján Pich, and Rahul Santhanam. Hardness Magnification near State-Of-The-Art Lower Bounds. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 27:1-27:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{oliveira_et_al:LIPIcs.CCC.2019.27, author = {Oliveira, Igor Carboni and Pich, J\'{a}n and Santhanam, Rahul}, title = {{Hardness Magnification near State-Of-The-Art Lower Bounds}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {27:1--27:29}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.27}, URN = {urn:nbn:de:0030-drops-108494}, doi = {10.4230/LIPIcs.CCC.2019.27}, annote = {Keywords: Circuit Complexity, Minimum Circuit Size Problem, Kolmogorov Complexity} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Igor Carboni Oliveira. Randomness and Intractability in Kolmogorov Complexity. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 32:1-32:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{oliveira:LIPIcs.ICALP.2019.32, author = {Oliveira, Igor Carboni}, title = {{Randomness and Intractability in Kolmogorov Complexity}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {32:1--32:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-109-2}, ISSN = {1868-8969}, year = {2019}, volume = {132}, editor = {Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.32}, URN = {urn:nbn:de:0030-drops-106087}, doi = {10.4230/LIPIcs.ICALP.2019.32}, annote = {Keywords: computational complexity, randomness, circuit lower bounds, Kolmogorov complexity} }
Published in: Dagstuhl Reports, Volume 4, Issue 10 (2015)
Olaf Beyersdorff, Edward A. Hirsch, Jan Krajicek, and Rahul Santhanam. Optimal algorithms and proofs (Dagstuhl Seminar 14421). In Dagstuhl Reports, Volume 4, Issue 10, pp. 51-68, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@Article{beyersdorff_et_al:DagRep.4.10.51, author = {Beyersdorff, Olaf and Hirsch, Edward A. and Krajicek, Jan and Santhanam, Rahul}, title = {{Optimal algorithms and proofs (Dagstuhl Seminar 14421)}}, pages = {51--68}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2015}, volume = {4}, number = {10}, editor = {Beyersdorff, Olaf and Hirsch, Edward A. and Krajicek, Jan and Santhanam, Rahul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.4.10.51}, URN = {urn:nbn:de:0030-drops-48923}, doi = {10.4230/DagRep.4.10.51}, annote = {Keywords: computational complexity, proof complexity, approximation algorithms, optimal algorithms, optimal proof systems, speedup theorems} }
Feedback for Dagstuhl Publishing