Search Results

Documents authored by Linial, Nati

Document
DOI: 10.4230/LIPIcs.ITCS.2026.44
Higher-Order Delsarte Dual LPs: Lifting, Constructions and Completeness

Authors: Leonardo Nagami Coregliano, Fernando Granha Jeronimo, Chris Jones, Nati Linial, and Elyassaf Loyfer

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
A central and longstanding open problem in coding theory is the rate-versus-distance trade-off for binary error-correcting codes. In a seminal work, Delsarte introduced a family of linear programs establishing relaxations on the size of optimum codes. To date, the state-of-the-art upper bounds for binary codes come from dual feasible solutions to these LPs. Still, these bounds are exponentially far from the best-known existential constructions. Recently, hierarchies of linear programs extending and strengthening Delsarte’s original LPs were introduced for linear codes, which we refer to as higher-order Delsarte LPs. These new hierarchies were shown to provably converge to the actual value of optimum codes, namely, they are complete hierarchies. Therefore, understanding them and their dual formulations becomes a valuable line of investigation. Nonetheless, their higher-order structure poses challenges. In fact, analysis of all known convex programming hierarchies strengthening Delsarte’s original LPs has turned out to be exceedingly difficult and essentially nothing is known, stalling progress in the area since the 1970s. Our main result is an analysis of the higher-order Delsarte LPs via their dual formulation. Although quantitatively, our current analysis only matches the best-known upper bounds, it shows, for the first time, how to tame the complexity of analyzing a hierarchy strengthening Delsarte’s original LPs. In doing so, we reach a better understanding of the structure of the hierarchy, which may serve as the foundation for further quantitative improvements. We provide two additional structural results for this hierarchy. First, we show how to explicitly lift any feasible dual solution from level k to a (suitable) larger level 𝓁 while retaining the objective value. Second, we give a novel proof of completeness using the dual formulation.
Cite as

Leonardo Nagami Coregliano, Fernando Granha Jeronimo, Chris Jones, Nati Linial, and Elyassaf Loyfer. Higher-Order Delsarte Dual LPs: Lifting, Constructions and Completeness. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 44:1-44:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{coregliano_et_al:LIPIcs.ITCS.2026.44,
  author =	{Coregliano, Leonardo Nagami and Jeronimo, Fernando Granha and Jones, Chris and Linial, Nati and Loyfer, Elyassaf},
  title =	{{Higher-Order Delsarte Dual LPs: Lifting, Constructions and Completeness}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{44:1--44:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.44},
  URN =		{urn:nbn:de:0030-drops-253315},
  doi =		{10.4230/LIPIcs.ITCS.2026.44},
  annote =	{Keywords: Coding theory, code bounds, convex optimization, linear progamming hierarchy}
}
Document
DOI: 10.4230/LIPIcs.CCC.2021.2
An Improved Protocol for the Exactly-N Problem

Authors: Nati Linial and Adi Shraibman

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

Abstract
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].
Cite as

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
DOI: 10.4230/LIPIcs.ITCS.2019.54
On the Communication Complexity of High-Dimensional Permutations

Authors: Nati Linial, Toniann Pitassi, and Adi Shraibman

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

Abstract
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.
Cite as

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
DOI: 10.4230/LIPIcs.STACS.2013.526
On the practically interesting instances of MAXCUT

Authors: Yonatan Bilu, Amit Daniely, Nati Linial, and Michael Saks

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

Abstract
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.
Cite as

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}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact