Document

**Published in:** LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)

In the 3-players exactly-N problem the players need to decide whether x+y+z = N for inputs x,y,z and fixed N. This is the first problem considered in the multiplayer Number On the Forehead (NOF) model. Even though this is such a basic problem, no progress has been made on it throughout the years. Only recently have explicit protocols been found for the first time, yet no improvement in complexity has been achieved to date. The present paper offers the first improved protocol for the exactly-N problem. This improved protocol has also interesting consequences in additive combinatorics. As we explain below, it yields a higher lower bound on the possible density of corner-free sets in [N]×[N].

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)

Copy BibTex To Clipboard

@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} }

Document

**Published in:** LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)

We study the multiparty communication complexity of high dimensional permutations in the Number On the Forehead (NOF) model. This model is due to Chandra, Furst and Lipton (CFL) who also gave a nontrivial protocol for the Exactly-n problem where three players receive integer inputs and need to decide if their inputs sum to a given integer n. There is a considerable body of literature dealing with the same problem, where (N,+) is replaced by some other abelian group. Our work can be viewed as a far-reaching extension of this line of research. We show that the known lower bounds for that group-theoretic problem apply to all high dimensional permutations. We introduce new proof techniques that reveal new and unexpected connections between NOF communication complexity of permutations and a variety of well-known problems in combinatorics. We also give a direct algorithmic protocol for Exactly-n. In contrast, all previous constructions relied on large sets of integers without a 3-term arithmetic progression.

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)

Copy BibTex To Clipboard

@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} }

Document

**Published in:** LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)

For many optimization problems, the instances of practical interest often occupy just a tiny part of the algorithm's space of instances.
Following (Y. Bilu and N. Linial, 2010), we apply this perspective to MAXCUT, viewed as a clustering problem. Using a variety of techniques, we investigate practically interesting instances of this problem. Specifically, we show how to solve in polynomial time distinguished, metric, expanding and dense instances of MAXCUT under mild stability assumptions. In particular, (1 + epsilon)-stability (which is optimal) suffices for metric and dense MAXCUT. We also show how to solve in polynomial time Omega(sqrt(n))-stable instances of MAXCUT, substantially improving the best previously known result.

Yonatan Bilu, Amit Daniely, Nati Linial, and Michael Saks. On the practically interesting instances of MAXCUT. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 526-537, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{bilu_et_al:LIPIcs.STACS.2013.526, author = {Bilu, Yonatan and Daniely, Amit and Linial, Nati and Saks, Michael}, title = {{On the practically interesting instances of MAXCUT}}, booktitle = {30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)}, pages = {526--537}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.526}, URN = {urn:nbn:de:0030-drops-39625}, doi = {10.4230/LIPIcs.STACS.2013.526}, annote = {Keywords: MAXCUT, Clustering, Hardness in practice, Stability, Non worst-case analysis} }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail