Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Lianna Hambardzumyan, Toniann Pitassi, Suhail Sherif, Morgan Shirley, and Adi Shraibman. An Improved Protocol for ExactlyN with More Than 3 Players. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 58:1-58:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{hambardzumyan_et_al:LIPIcs.ITCS.2024.58, author = {Hambardzumyan, Lianna and Pitassi, Toniann and Sherif, Suhail and Shirley, Morgan and Shraibman, Adi}, title = {{An Improved Protocol for ExactlyN with More Than 3 Players}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {58:1--58:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-309-6}, ISSN = {1868-8969}, year = {2024}, volume = {287}, editor = {Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.58}, URN = {urn:nbn:de:0030-drops-195868}, doi = {10.4230/LIPIcs.ITCS.2024.58}, annote = {Keywords: Corner-free sets, number-on-forehead communication} }
Published in: LIPIcs, Volume 286, 27th International Conference on Principles of Distributed Systems (OPODIS 2023)
Avinandan Das, Pierre Fraigniaud, and Adi Rosén. Distributed Partial Coloring via Gradual Rounding. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 30:1-30:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{das_et_al:LIPIcs.OPODIS.2023.30, author = {Das, Avinandan and Fraigniaud, Pierre and Ros\'{e}n, Adi}, title = {{Distributed Partial Coloring via Gradual Rounding}}, booktitle = {27th International Conference on Principles of Distributed Systems (OPODIS 2023)}, pages = {30:1--30:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-308-9}, ISSN = {1868-8969}, year = {2024}, volume = {286}, editor = {Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.30}, URN = {urn:nbn:de:0030-drops-195205}, doi = {10.4230/LIPIcs.OPODIS.2023.30}, annote = {Keywords: Distributed graph coloring, partial coloring, weak coloring} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Toniann Pitassi, Morgan Shirley, and Adi Shraibman. The Strength of Equality Oracles in Communication. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 89:1-89:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{pitassi_et_al:LIPIcs.ITCS.2023.89, author = {Pitassi, Toniann and Shirley, Morgan and Shraibman, Adi}, title = {{The Strength of Equality Oracles in Communication}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {89:1--89:19}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.89}, URN = {urn:nbn:de:0030-drops-175927}, doi = {10.4230/LIPIcs.ITCS.2023.89}, annote = {Keywords: Factorization norm, blocky rank, Merlin-Arthur} }
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-dev.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} }
Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)
Nati Linial and Adi Shraibman. An Improved Protocol for the Exactly-N Problem. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 2:1-2:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{linial_et_al:LIPIcs.CCC.2021.2, author = {Linial, Nati and Shraibman, Adi}, title = {{An Improved Protocol for the Exactly-N Problem}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {2:1--2:8}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-193-1}, ISSN = {1868-8969}, year = {2021}, volume = {200}, editor = {Kabanets, Valentine}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.2}, URN = {urn:nbn:de:0030-drops-142760}, doi = {10.4230/LIPIcs.CCC.2021.2}, annote = {Keywords: Communication complexity, Number-On-the-Forehead, Corner-free sets} }
Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)
Noga Alon, Bruno Jartoux, Chaya Keller, Shakhar Smorodinsky, and Yelena Yuditsky. The ε-t-Net Problem. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 5:1-5:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{alon_et_al:LIPIcs.SoCG.2020.5, author = {Alon, Noga and Jartoux, Bruno and Keller, Chaya and Smorodinsky, Shakhar and Yuditsky, Yelena}, title = {{The \epsilon-t-Net Problem}}, booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)}, pages = {5:1--5:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-143-6}, ISSN = {1868-8969}, year = {2020}, volume = {164}, editor = {Cabello, Sergio and Chen, Danny Z.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.5}, URN = {urn:nbn:de:0030-drops-121639}, doi = {10.4230/LIPIcs.SoCG.2020.5}, annote = {Keywords: epsilon-nets, geometric hypergraphs, VC-dimension, linear union complexity} }
Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Nati Linial, Toniann Pitassi, and Adi Shraibman. On the Communication Complexity of High-Dimensional Permutations. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 54:1-54:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{linial_et_al:LIPIcs.ITCS.2019.54, author = {Linial, Nati and Pitassi, Toniann and Shraibman, Adi}, title = {{On the Communication Complexity of High-Dimensional Permutations}}, booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)}, pages = {54:1--54:20}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.54}, URN = {urn:nbn:de:0030-drops-101470}, doi = {10.4230/LIPIcs.ITCS.2019.54}, annote = {Keywords: High dimensional permutations, Number On the Forehead model, Additive combinatorics} }
Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Adi Rosén and Florent Urrutia. A New Approach to Multi-Party Peer-to-Peer Communication Complexity. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 64:1-64:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{rosen_et_al:LIPIcs.ITCS.2019.64, author = {Ros\'{e}n, Adi and Urrutia, Florent}, title = {{A New Approach to Multi-Party Peer-to-Peer Communication Complexity}}, booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)}, pages = {64:1--64:19}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.64}, URN = {urn:nbn:de:0030-drops-101576}, doi = {10.4230/LIPIcs.ITCS.2019.64}, annote = {Keywords: communication complexity, multi-party communication complexity, peer-to-peer communication complexity, information complexity, private computation} }
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Achiya Bar-On, Itai Dinur, Orr Dunkelman, Rani Hod, Nathan Keller, Eyal Ronen, and Adi Shamir. Tight Bounds on Online Checkpointing Algorithms. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 13:1-13:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{baron_et_al:LIPIcs.ICALP.2018.13, author = {Bar-On, Achiya and Dinur, Itai and Dunkelman, Orr and Hod, Rani and Keller, Nathan and Ronen, Eyal and Shamir, Adi}, title = {{Tight Bounds on Online Checkpointing Algorithms}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {13:1--13:13}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.13}, URN = {urn:nbn:de:0030-drops-90179}, doi = {10.4230/LIPIcs.ICALP.2018.13}, annote = {Keywords: checkpoint, checkpointing algorithm, online algorithm, uniform distribution, discrepancy} }
Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Guy Even, Reut Levi, Moti Medina, and Adi Rosén. Sublinear Random Access Generators for Preferential Attachment Graphs. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 6:1-6:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{even_et_al:LIPIcs.ICALP.2017.6, author = {Even, Guy and Levi, Reut and Medina, Moti and Ros\'{e}n, Adi}, title = {{Sublinear Random Access Generators for Preferential Attachment Graphs}}, booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)}, pages = {6:1--6: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.6}, URN = {urn:nbn:de:0030-drops-74242}, doi = {10.4230/LIPIcs.ICALP.2017.6}, annote = {Keywords: local computation algorithms, preferential attachment graphs, random recursive trees, sublinear algorithms} }
Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)
Iordanis Kerenidis, Adi Rosén, and Florent Urrutia. Multi-Party Protocols, Information Complexity and Privacy. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 57:1-57:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{kerenidis_et_al:LIPIcs.MFCS.2016.57, author = {Kerenidis, Iordanis and Ros\'{e}n, Adi and Urrutia, Florent}, title = {{Multi-Party Protocols, Information Complexity and Privacy}}, booktitle = {41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)}, pages = {57:1--57:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-016-3}, ISSN = {1868-8969}, year = {2016}, volume = {58}, editor = {Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.57}, URN = {urn:nbn:de:0030-drops-64696}, doi = {10.4230/LIPIcs.MFCS.2016.57}, annote = {Keywords: multi-party protocols, information theory, communication complexity, multi-party private computation (MPC), randomness} }
Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)
Guy Even, Moti Medina, and Adi Rosén. A Constant Approximation Algorithm for Scheduling Packets on Line Networks. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 40:1-40:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{even_et_al:LIPIcs.ESA.2016.40, author = {Even, Guy and Medina, Moti and Ros\'{e}n, Adi}, title = {{A Constant Approximation Algorithm for Scheduling Packets on Line Networks}}, booktitle = {24th Annual European Symposium on Algorithms (ESA 2016)}, pages = {40:1--40:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-015-6}, ISSN = {1868-8969}, year = {2016}, volume = {57}, editor = {Sankowski, Piotr and Zaroliagis, Christos}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.40}, URN = {urn:nbn:de:0030-drops-63524}, doi = {10.4230/LIPIcs.ESA.2016.40}, annote = {Keywords: approximation algorithms, linear programming, randomized rounding, packet scheduling, admission control} }
Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)
Dror Rawitz and Adi Rosén. Online Budgeted Maximum Coverage. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 73:1-73:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{rawitz_et_al:LIPIcs.ESA.2016.73, author = {Rawitz, Dror and Ros\'{e}n, Adi}, title = {{Online Budgeted Maximum Coverage}}, booktitle = {24th Annual European Symposium on Algorithms (ESA 2016)}, pages = {73:1--73:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-015-6}, ISSN = {1868-8969}, year = {2016}, volume = {57}, editor = {Sankowski, Piotr and Zaroliagis, Christos}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.73}, URN = {urn:nbn:de:0030-drops-64146}, doi = {10.4230/LIPIcs.ESA.2016.73}, annote = {Keywords: budgeted coverage, maximum coverage, online algorithms, competitive analysis, removable online knapsack} }
Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)
Alejandro López-Ortiz, Marc P. Renault, and Adi Rosén. Paid Exchanges are Worth the Price. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 636-648, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{lopezortiz_et_al:LIPIcs.STACS.2015.636, author = {L\'{o}pez-Ortiz, Alejandro and Renault, Marc P. and Ros\'{e}n, Adi}, title = {{Paid Exchanges are Worth the Price}}, booktitle = {32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)}, pages = {636--648}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-78-1}, ISSN = {1868-8969}, year = {2015}, volume = {30}, editor = {Mayr, Ernst W. and Ollinger, Nicolas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.636}, URN = {urn:nbn:de:0030-drops-49476}, doi = {10.4230/LIPIcs.STACS.2015.636}, annote = {Keywords: list update problem, online computation, online algorithms, competitive analysis, lower bounds} }
Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)
Noga Alon, Troy Lee, and Adi Shraibman. The Cover Number of a Matrix and its Algorithmic Applications. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 34-47, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
@InProceedings{alon_et_al:LIPIcs.APPROX-RANDOM.2014.34, author = {Alon, Noga and Lee, Troy and Shraibman, Adi}, title = {{The Cover Number of a Matrix and its Algorithmic Applications}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)}, pages = {34--47}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-74-3}, ISSN = {1868-8969}, year = {2014}, volume = {28}, editor = {Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.34}, URN = {urn:nbn:de:0030-drops-46865}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2014.34}, annote = {Keywords: Approximation algorithms, Approximate Nash equilibria, Cover number, VC dimension} }
Feedback for Dagstuhl Publishing