Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Guy Blanc, Caleb Koch, Carmen Strassle, and Li-Yang Tan. A Strong Direct Sum Theorem for Distributional Query Complexity. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 16:1-16:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{blanc_et_al:LIPIcs.CCC.2024.16, author = {Blanc, Guy and Koch, Caleb and Strassle, Carmen and Tan, Li-Yang}, title = {{A Strong Direct Sum Theorem for Distributional Query Complexity}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {16:1--16:30}, 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.16}, URN = {urn:nbn:de:0030-drops-204123}, doi = {10.4230/LIPIcs.CCC.2024.16}, annote = {Keywords: Query complexity, direct product theorem, hardcore theorem} }
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.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 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.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 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.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 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.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 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.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} }
Published in: Dagstuhl Seminar Proceedings, Volume 8381, Computational Complexity of Discrete Problems (2008)
Troy Lee and Adi Shraibman. Approximation norms and duality for communication complexity lower bounds. In Computational Complexity of Discrete Problems. Dagstuhl Seminar Proceedings, Volume 8381, pp. 1-9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)
@InProceedings{lee_et_al:DagSemProc.08381.3, author = {Lee, Troy and Shraibman, Adi}, title = {{Approximation norms and duality for communication complexity lower bounds}}, booktitle = {Computational Complexity of Discrete Problems}, pages = {1--9}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2008}, volume = {8381}, editor = {Peter Bro Miltersen and R\"{u}diger Reischuk and Georg Schnitger and Dieter van Melkebeek}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08381.3}, URN = {urn:nbn:de:0030-drops-17768}, doi = {10.4230/DagSemProc.08381.3}, annote = {Keywords: Communication complexity, lower bounds} }