Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Amit Chakrabarti and Manuel Stoeckl. Finding Missing Items Requires Strong Forms of Randomness. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 28:1-28:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{chakrabarti_et_al:LIPIcs.CCC.2024.28, author = {Chakrabarti, Amit and Stoeckl, Manuel}, title = {{Finding Missing Items Requires Strong Forms of Randomness}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {28:1--28:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-331-7}, ISSN = {1868-8969}, year = {2024}, volume = {300}, editor = {Santhanam, Rahul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.28}, URN = {urn:nbn:de:0030-drops-204242}, doi = {10.4230/LIPIcs.CCC.2024.28}, annote = {Keywords: Data streaming, lower bounds, space complexity, adversarial robustness, derandomization, sketching, sampling} }
Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)
Roey Magen and Moni Naor. Mirror Games Against an Open Book Player. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 20:1-20:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{magen_et_al:LIPIcs.FUN.2022.20, author = {Magen, Roey and Naor, Moni}, title = {{Mirror Games Against an Open Book Player}}, booktitle = {11th International Conference on Fun with Algorithms (FUN 2022)}, pages = {20:1--20:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-232-7}, ISSN = {1868-8969}, year = {2022}, volume = {226}, editor = {Fraigniaud, Pierre and Uno, Yushi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.20}, URN = {urn:nbn:de:0030-drops-159900}, doi = {10.4230/LIPIcs.FUN.2022.20}, annote = {Keywords: Mirror Games, Space Complexity, Eventown-Oddtown} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Boaz Menuhin and Moni Naor. Keep That Card in Mind: Card Guessing with Limited Memory. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 107:1-107:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{menuhin_et_al:LIPIcs.ITCS.2022.107, author = {Menuhin, Boaz and Naor, Moni}, title = {{Keep That Card in Mind: Card Guessing with Limited Memory}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {107:1--107:28}, 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.107}, URN = {urn:nbn:de:0030-drops-157039}, doi = {10.4230/LIPIcs.ITCS.2022.107}, annote = {Keywords: Adaptivity vs Non-adaptivity, Adversarial Robustness, Card Guessing, Compression Argument, Information Theory, Streaming Algorithms, Two Player Game} }