Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Nikhil Vyas and Ryan Williams. On Oracles and Algorithmic Methods for Proving Lower Bounds. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 99:1-99:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{vyas_et_al:LIPIcs.ITCS.2023.99, author = {Vyas, Nikhil and Williams, Ryan}, title = {{On Oracles and Algorithmic Methods for Proving Lower Bounds}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {99:1--99:26}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-263-1}, ISSN = {1868-8969}, year = {2023}, volume = {251}, editor = {Tauman Kalai, Yael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.99}, URN = {urn:nbn:de:0030-drops-176021}, doi = {10.4230/LIPIcs.ITCS.2023.99}, annote = {Keywords: oracles, relativization, circuit complexity, missing string, exponential hierarchy} }
Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Lijie Chen, Shuichi Hirahara, Igor C. Oliveira, Ján Pich, Ninad Rajgopal, and Rahul Santhanam. Beyond Natural Proofs: Hardness Magnification and Locality. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 70:1-70:48, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{chen_et_al:LIPIcs.ITCS.2020.70, author = {Chen, Lijie and Hirahara, Shuichi and Oliveira, Igor C. and Pich, J\'{a}n and Rajgopal, Ninad and Santhanam, Rahul}, title = {{Beyond Natural Proofs: Hardness Magnification and Locality}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {70:1--70:48}, 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.70}, URN = {urn:nbn:de:0030-drops-117550}, doi = {10.4230/LIPIcs.ITCS.2020.70}, annote = {Keywords: Hardness Magnification, Natural Proofs, Minimum Circuit Size Problem, Circuit Lower Bounds} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
Lijie Chen, Dylan M. McKay, Cody D. Murray, and R. Ryan Williams. Relations and Equivalences Between Circuit Lower Bounds and Karp-Lipton Theorems. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 30:1-30:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{chen_et_al:LIPIcs.CCC.2019.30, author = {Chen, Lijie and McKay, Dylan M. and Murray, Cody D. and Williams, R. Ryan}, title = {{Relations and Equivalences Between Circuit Lower Bounds and Karp-Lipton Theorems}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {30:1--30:21}, 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.30}, URN = {urn:nbn:de:0030-drops-108525}, doi = {10.4230/LIPIcs.CCC.2019.30}, annote = {Keywords: Karp-Lipton Theorems, Circuit Lower Bounds, Derandomization, Hardness Magnification} }
Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Dylan M. McKay and Richard Ryan Williams. Quadratic Time-Space Lower Bounds for Computing Natural Functions with a Random Oracle. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 56:1-56:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{mckay_et_al:LIPIcs.ITCS.2019.56, author = {McKay, Dylan M. and Williams, Richard Ryan}, title = {{Quadratic Time-Space Lower Bounds for Computing Natural Functions with a Random Oracle}}, booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)}, pages = {56:1--56:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-095-8}, ISSN = {1868-8969}, year = {2019}, volume = {124}, editor = {Blum, Avrim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.56}, URN = {urn:nbn:de:0030-drops-101493}, doi = {10.4230/LIPIcs.ITCS.2019.56}, annote = {Keywords: branching programs, random oracles, time-space tradeoffs, lower bounds, SAT, counting complexity} }
Feedback for Dagstuhl Publishing