Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)
Gal Arnon, Alessandro Chiesa, and Eylon Yogev. Hardness of Approximation for Stochastic Problems via Interactive Oracle Proofs. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 24:1-24:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{arnon_et_al:LIPIcs.CCC.2022.24, author = {Arnon, Gal and Chiesa, Alessandro and Yogev, Eylon}, title = {{Hardness of Approximation for Stochastic Problems via Interactive Oracle Proofs}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {24:1--24:16}, 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.24}, URN = {urn:nbn:de:0030-drops-165867}, doi = {10.4230/LIPIcs.CCC.2022.24}, annote = {Keywords: hardness of approximation, interactive oracle proofs, stochastic satisfaction problems} }
Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)
Sarah Bordage, Mathieu Lhotel, Jade Nardi, and Hugues Randriam. Interactive Oracle Proofs of Proximity to Algebraic Geometry Codes. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 30:1-30:45, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{bordage_et_al:LIPIcs.CCC.2022.30, author = {Bordage, Sarah and Lhotel, Mathieu and Nardi, Jade and Randriam, Hugues}, title = {{Interactive Oracle Proofs of Proximity to Algebraic Geometry Codes}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {30:1--30:45}, 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.30}, URN = {urn:nbn:de:0030-drops-165923}, doi = {10.4230/LIPIcs.CCC.2022.30}, annote = {Keywords: Algebraic geometry codes, Interactive oracle proofs of proximity, Proximity testing} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Shafi Goldwasser, Guy N. Rothblum, Jonathan Shafer, and Amir Yehudayoff. Interactive Proofs for Verifying Machine Learning. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 41:1-41:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{goldwasser_et_al:LIPIcs.ITCS.2021.41, author = {Goldwasser, Shafi and Rothblum, Guy N. and Shafer, Jonathan and Yehudayoff, Amir}, title = {{Interactive Proofs for Verifying Machine Learning}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {41:1--41:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-177-1}, ISSN = {1868-8969}, year = {2021}, volume = {185}, editor = {Lee, James R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.41}, URN = {urn:nbn:de:0030-drops-135806}, doi = {10.4230/LIPIcs.ITCS.2021.41}, annote = {Keywords: PAC learning, Fourier analysis of boolean functions, Complexity gaps, Complexity lower bounds, Goldreich-Levin algorithm, Kushilevitz-Mansour algorithm, Distribution testing} }
Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Alessandro Chiesa, Peter Manohar, and Igor Shinkar. On Local Testability in the Non-Signaling Setting. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 26:1-26:37, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{chiesa_et_al:LIPIcs.ITCS.2020.26, author = {Chiesa, Alessandro and Manohar, Peter and Shinkar, Igor}, title = {{On Local Testability in the Non-Signaling Setting}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {26:1--26: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.26}, URN = {urn:nbn:de:0030-drops-117112}, doi = {10.4230/LIPIcs.ITCS.2020.26}, annote = {Keywords: non-signaling strategies, locally testable codes, low-degree testing, Fourier analysis} }
Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Alessandro Chiesa and Siqi Liu. On the Impossibility of Probabilistic Proofs in Relativized Worlds. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 57:1-57:30, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{chiesa_et_al:LIPIcs.ITCS.2020.57, author = {Chiesa, Alessandro and Liu, Siqi}, title = {{On the Impossibility of Probabilistic Proofs in Relativized Worlds}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {57:1--57:30}, 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.57}, URN = {urn:nbn:de:0030-drops-117420}, doi = {10.4230/LIPIcs.ITCS.2020.57}, annote = {Keywords: probabilistically checkable proofs, relativization} }
Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Alessandro Chiesa, Peter Manohar, and Igor Shinkar. Probabilistic Checking Against Non-Signaling Strategies from Linearity Testing. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 25:1-25:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{chiesa_et_al:LIPIcs.ITCS.2019.25, author = {Chiesa, Alessandro and Manohar, Peter and Shinkar, Igor}, title = {{Probabilistic Checking Against Non-Signaling Strategies from Linearity Testing}}, booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)}, pages = {25:1--25:17}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.25}, URN = {urn:nbn:de:0030-drops-101188}, doi = {10.4230/LIPIcs.ITCS.2019.25}, annote = {Keywords: probabilistically checkable proofs, linearity testing, non-signaling strategies} }
Published in: LIPIcs, Volume 102, 33rd Computational Complexity Conference (CCC 2018)
Alessandro Chiesa, Peter Manohar, and Igor Shinkar. Testing Linearity against Non-Signaling Strategies. In 33rd Computational Complexity Conference (CCC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 102, pp. 17:1-17:37, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{chiesa_et_al:LIPIcs.CCC.2018.17, author = {Chiesa, Alessandro and Manohar, Peter and Shinkar, Igor}, title = {{Testing Linearity against Non-Signaling Strategies}}, booktitle = {33rd Computational Complexity Conference (CCC 2018)}, pages = {17:1--17:37}, 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.17}, URN = {urn:nbn:de:0030-drops-88731}, doi = {10.4230/LIPIcs.CCC.2018.17}, annote = {Keywords: property testing, linearity testing, non-signaling strategies, quasi-distributions} }
Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)
Alessandro Chiesa and Tom Gur. Proofs of Proximity for Distribution Testing. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 53:1-53:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{chiesa_et_al:LIPIcs.ITCS.2018.53, author = {Chiesa, Alessandro and Gur, Tom}, title = {{Proofs of Proximity for Distribution Testing}}, booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)}, pages = {53:1--53:14}, 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.53}, URN = {urn:nbn:de:0030-drops-83114}, doi = {10.4230/LIPIcs.ITCS.2018.53}, annote = {Keywords: distribution testing, proofs of proximity, property testing} }
Published in: LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)
Alessandro Chiesa, Peter Manohar, and Igor Shinkar. On Axis-Parallel Tests for Tensor Product Codes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 39:1-39:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{chiesa_et_al:LIPIcs.APPROX-RANDOM.2017.39, author = {Chiesa, Alessandro and Manohar, Peter and Shinkar, Igor}, title = {{On Axis-Parallel Tests for Tensor Product Codes}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)}, pages = {39:1--39:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-044-6}, ISSN = {1868-8969}, year = {2017}, volume = {81}, editor = {Jansen, Klaus and Rolim, Jos\'{e} D. P. and Williamson, David P. and Vempala, Santosh S.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.39}, URN = {urn:nbn:de:0030-drops-75882}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2017.39}, annote = {Keywords: tensor product codes, locally testable codes, low-degree testing, extremal graph theory} }
Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, Michael Riabzev, and Nicholas Spooner. Interactive Oracle Proofs with Constant Rate and Query Complexity. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 40:1-40:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{bensasson_et_al:LIPIcs.ICALP.2017.40, author = {Ben-Sasson, Eli and Chiesa, Alessandro and Gabizon, Ariel and Riabzev, Michael and Spooner, Nicholas}, title = {{Interactive Oracle Proofs with Constant Rate and Query Complexity}}, booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)}, pages = {40:1--40:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-041-5}, ISSN = {1868-8969}, year = {2017}, volume = {80}, editor = {Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.40}, URN = {urn:nbn:de:0030-drops-74713}, doi = {10.4230/LIPIcs.ICALP.2017.40}, annote = {Keywords: probabilistically checkable proofs, interactive proofs, proof composition, sumcheck} }
Feedback for Dagstuhl Publishing