Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Andrej Bogdanov and Alon Rosen. Nondeterministic Interactive Refutations for Nearest Boolean Vector. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 28:1-28:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{bogdanov_et_al:LIPIcs.ICALP.2023.28, author = {Bogdanov, Andrej and Rosen, Alon}, title = {{Nondeterministic Interactive Refutations for Nearest Boolean Vector}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {28:1--28:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-278-5}, ISSN = {1868-8969}, year = {2023}, volume = {261}, editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.28}, URN = {urn:nbn:de:0030-drops-180801}, doi = {10.4230/LIPIcs.ICALP.2023.28}, annote = {Keywords: average-case complexity, statistical zero-knowledge, nondeterministic refutation, Sherrington-Kirkpatrick Hamiltonian, complexity of statistical inference, lattice smoothing} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Romain Bourneuf, Lukáš Folwarczný, Pavel Hubáček, Alon Rosen, and Nikolaj I. Schwartzbach. PPP-Completeness and Extremal Combinatorics. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 22:1-22:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{bourneuf_et_al:LIPIcs.ITCS.2023.22, author = {Bourneuf, Romain and Folwarczn\'{y}, Luk\'{a}\v{s} and Hub\'{a}\v{c}ek, Pavel and Rosen, Alon and Schwartzbach, Nikolaj I.}, title = {{PPP-Completeness and Extremal Combinatorics}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {22:1--22:20}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.22}, URN = {urn:nbn:de:0030-drops-175255}, doi = {10.4230/LIPIcs.ITCS.2023.22}, annote = {Keywords: total search problems, extremal combinatorics, PPP-completeness} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Prahladh Harsha, Daniel Mitropolsky, and Alon Rosen. Downward Self-Reducibility in TFNP. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 67:1-67:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{harsha_et_al:LIPIcs.ITCS.2023.67, author = {Harsha, Prahladh and Mitropolsky, Daniel and Rosen, Alon}, title = {{Downward Self-Reducibility in TFNP}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {67:1--67:17}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.67}, URN = {urn:nbn:de:0030-drops-175700}, doi = {10.4230/LIPIcs.ITCS.2023.67}, annote = {Keywords: downward self-reducibility, TFNP, TFUP, factoring, PLS, CLS} }
Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Marshall Ball, Elette Boyle, Akshay Degwekar, Apoorvaa Deshpande, Alon Rosen, Vinod Vaikuntanathan, and Prashant Nalini Vasudevan. Cryptography from Information Loss. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 81:1-81:27, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{ball_et_al:LIPIcs.ITCS.2020.81, author = {Ball, Marshall and Boyle, Elette and Degwekar, Akshay and Deshpande, Apoorvaa and Rosen, Alon and Vaikuntanathan, Vinod and Vasudevan, Prashant Nalini}, title = {{Cryptography from Information Loss}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {81:1--81: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.81}, URN = {urn:nbn:de:0030-drops-117667}, doi = {10.4230/LIPIcs.ITCS.2020.81}, annote = {Keywords: Compression, Information Loss, One-Way Functions, Reductions, Generic Constructions} }
Published in: Dagstuhl Reports, Volume 1, Issue 7 (2011)
R. Michael Alvarez, Josh Benaloh, Alon Rosen, and Peter Y. A. Ryan. Verifiable Elections and the Public (Dagstuhl Seminar 11281). In Dagstuhl Reports, Volume 1, Issue 7, pp. 36-52, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2011)
@Article{alvarez_et_al:DagRep.1.7.36, author = {Alvarez, R. Michael and Benaloh, Josh and Rosen, Alon and Ryan, Peter Y. A.}, title = {{Verifiable Elections and the Public (Dagstuhl Seminar 11281)}}, pages = {36--52}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2011}, volume = {1}, number = {7}, editor = {Alvarez, R. Michael and Benaloh, Josh and Rosen, Alon and Ryan, Peter Y. A.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.1.7.36}, URN = {urn:nbn:de:0030-drops-33086}, doi = {10.4230/DagRep.1.7.36}, annote = {Keywords: Electronic voting, Internet voting, voter verification, verifiable elections} }
Feedback for Dagstuhl Publishing