Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Joshua Cook and Ron D. Rothblum. Efficient Interactive Proofs for Non-Deterministic Bounded Space. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 47:1-47:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{cook_et_al:LIPIcs.APPROX/RANDOM.2023.47, author = {Cook, Joshua and Rothblum, Ron D.}, title = {{Efficient Interactive Proofs for Non-Deterministic Bounded Space}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {47:1--47:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-296-9}, ISSN = {1868-8969}, year = {2023}, volume = {275}, editor = {Megow, Nicole and Smith, Adam}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.47}, URN = {urn:nbn:de:0030-drops-188727}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.47}, annote = {Keywords: Interactive Proofs, Alternating Algorithms, AC0\lbrack2\rbrack, Doubly Efficient Proofs} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Justin Holmgren, Andrea Lincoln, and Ron D. Rothblum. Delegation for Search Problems. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 73:1-73:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{holmgren_et_al:LIPIcs.ICALP.2022.73, author = {Holmgren, Justin and Lincoln, Andrea and Rothblum, Ron D.}, title = {{Delegation for Search Problems}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {73:1--73:18}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.73}, URN = {urn:nbn:de:0030-drops-164146}, doi = {10.4230/LIPIcs.ICALP.2022.73}, annote = {Keywords: Interactive Proofs, Fine-Grained Complexity, Delegation} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Liron Bronfman and Ron D. Rothblum. PCPs and Instance Compression from a Cryptographic Lens. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 30:1-30:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{bronfman_et_al:LIPIcs.ITCS.2022.30, author = {Bronfman, Liron and Rothblum, Ron D.}, title = {{PCPs and Instance Compression from a Cryptographic Lens}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {30:1--30:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-217-4}, ISSN = {1868-8969}, year = {2022}, volume = {215}, editor = {Braverman, Mark}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.30}, URN = {urn:nbn:de:0030-drops-156269}, doi = {10.4230/LIPIcs.ITCS.2022.30}, annote = {Keywords: PCP, Succinct Arguments, Instance Compression} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Michael Ezra and Ron D. Rothblum. Small Circuits Imply Efficient Arthur-Merlin Protocols. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 67:1-67:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{ezra_et_al:LIPIcs.ITCS.2022.67, author = {Ezra, Michael and Rothblum, Ron D.}, title = {{Small Circuits Imply Efficient Arthur-Merlin Protocols}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {67:1--67:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-217-4}, ISSN = {1868-8969}, year = {2022}, volume = {215}, editor = {Braverman, Mark}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.67}, URN = {urn:nbn:de:0030-drops-156635}, doi = {10.4230/LIPIcs.ITCS.2022.67}, annote = {Keywords: Circuits Complexity, Circuit Lower Bounds, Communication Complexity, Data Streaming, Arthur-Merlin games, Interactive Proofs} }
Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Omri Ben-Eliezer, Eldar Fischer, Amit Levi, and Ron D. Rothblum. Hard Properties with (Very) Short PCPPs and Their Applications. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 9:1-9:27, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{beneliezer_et_al:LIPIcs.ITCS.2020.9, author = {Ben-Eliezer, Omri and Fischer, Eldar and Levi, Amit and Rothblum, Ron D.}, title = {{Hard Properties with (Very) Short PCPPs and Their Applications}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {9:1--9:27}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.9}, URN = {urn:nbn:de:0030-drops-116949}, doi = {10.4230/LIPIcs.ITCS.2020.9}, annote = {Keywords: PCPP, Property testing, Tolerant testing, Erasure resilient testing, Randomized encoding, Coding theory} }
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Tom Gur, Yang P. Liu, and Ron D. Rothblum. An Exponential Separation Between MA and AM Proofs of Proximity. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 73:1-73:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{gur_et_al:LIPIcs.ICALP.2018.73, author = {Gur, Tom and Liu, Yang P. and Rothblum, Ron D.}, title = {{An Exponential Separation Between MA and AM Proofs of Proximity}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {73:1--73:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-076-7}, ISSN = {1868-8969}, year = {2018}, volume = {107}, editor = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.73}, URN = {urn:nbn:de:0030-drops-90772}, doi = {10.4230/LIPIcs.ICALP.2018.73}, annote = {Keywords: Property testing, Probabilistic proof systems, Proofs of proximity} }
Published in: LIPIcs, Volume 102, 33rd Computational Complexity Conference (CCC 2018)
Omer Reingold, Guy N. Rothblum, and Ron D. Rothblum. Efficient Batch Verification for UP. In 33rd Computational Complexity Conference (CCC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 102, pp. 22:1-22:23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{reingold_et_al:LIPIcs.CCC.2018.22, author = {Reingold, Omer and Rothblum, Guy N. and Rothblum, Ron D.}, title = {{Efficient Batch Verification for UP}}, booktitle = {33rd Computational Complexity Conference (CCC 2018)}, pages = {22:1--22:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-069-9}, ISSN = {1868-8969}, year = {2018}, volume = {102}, editor = {Servedio, Rocco A.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2018.22}, URN = {urn:nbn:de:0030-drops-88681}, doi = {10.4230/LIPIcs.CCC.2018.22}, annote = {Keywords: Interactive Proof, Batch Verification, Unique Solution} }
Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)
Itay Berman, Ron D. Rothblum, and Vinod Vaikuntanathan. Zero-Knowledge Proofs of Proximity. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 19:1-19:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{berman_et_al:LIPIcs.ITCS.2018.19, author = {Berman, Itay and Rothblum, Ron D. and Vaikuntanathan, Vinod}, title = {{Zero-Knowledge Proofs of Proximity}}, booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)}, pages = {19:1--19:20}, 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.19}, URN = {urn:nbn:de:0030-drops-83575}, doi = {10.4230/LIPIcs.ITCS.2018.19}, annote = {Keywords: Property Testing, Interactive Proofs, Zero-Knowledge} }
Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)
Tom Gur, Govind Ramnarayan, and Ron D. Rothblum. Relaxed Locally Correctable Codes. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 27:1-27:11, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{gur_et_al:LIPIcs.ITCS.2018.27, author = {Gur, Tom and Ramnarayan, Govind and Rothblum, Ron D.}, title = {{Relaxed Locally Correctable Codes}}, booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)}, pages = {27:1--27:11}, 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.27}, URN = {urn:nbn:de:0030-drops-83154}, doi = {10.4230/LIPIcs.ITCS.2018.27}, annote = {Keywords: Keywords and phrases Coding Theory, Locally Correctable Codes, Probabilistically Checkable Proofs} }
Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)
Tom Gur and Ron D. Rothblum. A Hierarchy Theorem for Interactive Proofs of Proximity. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 39:1-39:43, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{gur_et_al:LIPIcs.ITCS.2017.39, author = {Gur, Tom and Rothblum, Ron D.}, title = {{A Hierarchy Theorem for Interactive Proofs of Proximity}}, booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)}, pages = {39:1--39:43}, 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.39}, URN = {urn:nbn:de:0030-drops-81536}, doi = {10.4230/LIPIcs.ITCS.2017.39}, annote = {Keywords: Complexity Theory, Property Testing, Interactive Proofs} }
Feedback for Dagstuhl Publishing