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-dev.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 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-dev.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 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
David P. Woodruff and Guang Yang. Separating k-Player from t-Player One-Way Communication, with Applications to Data Streams. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 97:1-97:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{woodruff_et_al:LIPIcs.ICALP.2019.97, author = {Woodruff, David P. and Yang, Guang}, title = {{Separating k-Player from t-Player One-Way Communication, with Applications to Data Streams}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {97:1--97:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-109-2}, ISSN = {1868-8969}, year = {2019}, volume = {132}, editor = {Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.97}, URN = {urn:nbn:de:0030-drops-106733}, doi = {10.4230/LIPIcs.ICALP.2019.97}, annote = {Keywords: Communication complexity, multi-player communication, one-way communication, streaming complexity} }
Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)
Benny Applebaum, Naama Haramaty-Krasne, Yuval Ishai, Eyal Kushilevitz, and Vinod Vaikuntanathan. Low-Complexity Cryptographic Hash Functions. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 7:1-7:31, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{applebaum_et_al:LIPIcs.ITCS.2017.7, author = {Applebaum, Benny and Haramaty-Krasne, Naama and Ishai, Yuval and Kushilevitz, Eyal and Vaikuntanathan, Vinod}, title = {{Low-Complexity Cryptographic Hash Functions}}, booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)}, pages = {7:1--7:31}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.7}, URN = {urn:nbn:de:0030-drops-81901}, doi = {10.4230/LIPIcs.ITCS.2017.7}, annote = {Keywords: Cryptography, hash functions, complexity theory, coding theory} }
Published in: LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017)
Itay Hazan and Eyal Kushilevitz. Two-Party Direct-Sum Questions Through the Lens of Multiparty Communication Complexity. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 26:1-26:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{hazan_et_al:LIPIcs.DISC.2017.26, author = {Hazan, Itay and Kushilevitz, Eyal}, title = {{Two-Party Direct-Sum Questions Through the Lens of Multiparty Communication Complexity}}, booktitle = {31st International Symposium on Distributed Computing (DISC 2017)}, pages = {26:1--26:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-053-8}, ISSN = {1868-8969}, year = {2017}, volume = {91}, editor = {Richa, Andr\'{e}a}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.26}, URN = {urn:nbn:de:0030-drops-79998}, doi = {10.4230/LIPIcs.DISC.2017.26}, annote = {Keywords: Communication Complexity, Direct Sum, Multiparty Communication} }
Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)
Yuval Ishai, Eyal Kushilevitz, and Omer Strulovich. Lossy Chains and Fractional Secret Sharing. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 160-171, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
@InProceedings{ishai_et_al:LIPIcs.STACS.2013.160, author = {Ishai, Yuval and Kushilevitz, Eyal and Strulovich, Omer}, title = {{Lossy Chains and Fractional Secret Sharing}}, booktitle = {30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)}, pages = {160--171}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-50-7}, ISSN = {1868-8969}, year = {2013}, volume = {20}, editor = {Portier, Natacha and Wilke, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.160}, URN = {urn:nbn:de:0030-drops-39319}, doi = {10.4230/LIPIcs.STACS.2013.160}, annote = {Keywords: Cryptography, secret sharing, Markov chains} }
Feedback for Dagstuhl Publishing