Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)
Shafi Goldwasser, Ofer Grossman, and Dhiraj Holden. Pseudo-Deterministic Proofs. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 17:1-17:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{goldwasser_et_al:LIPIcs.ITCS.2018.17, author = {Goldwasser, Shafi and Grossman, Ofer and Holden, Dhiraj}, title = {{Pseudo-Deterministic Proofs}}, booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)}, pages = {17:1--17:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-060-6}, ISSN = {1868-8969}, year = {2018}, volume = {94}, editor = {Karlin, Anna R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.17}, URN = {urn:nbn:de:0030-drops-83669}, doi = {10.4230/LIPIcs.ITCS.2018.17}, annote = {Keywords: Pseudo-Deterministic, Interactive Proofs} }
Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)
Shafi Goldwasser and Dhiraj Holden. The Complexity of Problems in P Given Correlated Instances. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 13:1-13:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{goldwasser_et_al:LIPIcs.ITCS.2017.13, author = {Goldwasser, Shafi and Holden, Dhiraj}, title = {{The Complexity of Problems in P Given Correlated Instances}}, booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)}, pages = {13:1--13:19}, 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.13}, URN = {urn:nbn:de:0030-drops-81753}, doi = {10.4230/LIPIcs.ITCS.2017.13}, annote = {Keywords: Correlated instances, Longest Common Subsequence, Fine-grained complexity} }
Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)
Eric Allender, Dhiraj Holden, and Valentine Kabanets. The Minimum Oracle Circuit Size Problem. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 21-33, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{allender_et_al:LIPIcs.STACS.2015.21, author = {Allender, Eric and Holden, Dhiraj and Kabanets, Valentine}, title = {{The Minimum Oracle Circuit Size Problem}}, booktitle = {32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)}, pages = {21--33}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-78-1}, ISSN = {1868-8969}, year = {2015}, volume = {30}, editor = {Mayr, Ernst W. and Ollinger, Nicolas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.21}, URN = {urn:nbn:de:0030-drops-49013}, doi = {10.4230/LIPIcs.STACS.2015.21}, annote = {Keywords: Kolmogorov complexity, minimum circuit size problem, PSPACE, NP-intermediate sets} }