DROPS

Document

DOI: 10.4230/LIPIcs.CCC.2026.10

The Rate-Immediacy Barrier in Explicit Tree Code Constructions

Authors: Gil Cohen, Leonard J. Schulman, and Piyush Srivastava

Published in: LIPIcs, Volume 383, 41st Computational Complexity Conference (CCC 2026)

Abstract

Since the introduction of tree codes by Schulman (STOC 1993), explicit construction of asymptotically good tree codes has remained a notorious challenge. A work by Cohen, Haeupler and Schulman (STOC 2018), as well as the state-of-the-art construction by Ben Yaacov, Cohen, and Yankovitz (STOC 2022) have achieved codes with rate Ω(1/log log n), exponentially improving upon the original rate Ω(1/log n) construction of Evans, Klugerman and Schulman from 1994. All of these constructions rely, at least in part, on increasingly sophisticated methods of combining (block) error-correcting codes. In this work, we identify a fundamental barrier to constructing tree codes using known techniques. We introduce a key property which we call immediacy, that, while not required by the original definition of tree codes, is shared by all known constructions and inherently arises in recursive combinations of error-correcting codes. Our main technical contribution is the proof of a rate–immediacy trade-off, which, in particular, implies that any tree code with constant distance and non-trivial immediacy must necessarily have vanishing rate. By applying our rate-immediacy trade-off to existing constructions, we establish that their known rate analyses are essentially optimal given their actual error-correction properties. More broadly, our work highlights the need for fundamentally new ideas - beyond the recursive use of error-correcting codes - to achieve substantial progress in explicitly constructing asymptotically good tree codes.

Cite as

Gil Cohen, Leonard J. Schulman, and Piyush Srivastava. The Rate-Immediacy Barrier in Explicit Tree Code Constructions. In 41st Computational Complexity Conference (CCC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 383, pp. 10:1-10:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{cohen_et_al:LIPIcs.CCC.2026.10,
  author =	{Cohen, Gil and Schulman, Leonard J. and Srivastava, Piyush},
  title =	{{The Rate-Immediacy Barrier in Explicit Tree Code Constructions}},
  booktitle =	{41st Computational Complexity Conference (CCC 2026)},
  pages =	{10:1--10:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-437-6},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{383},
  editor =	{Moshkovitz, Dana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2026.10},
  URN =		{urn:nbn:de:0030-drops-270522},
  doi =		{10.4230/LIPIcs.CCC.2026.10},
  annote =	{Keywords: Tree codes, Information Theory}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2019.55

Fisher Zeros and Correlation Decay in the Ising Model

Authors: Jingcheng Liu, Alistair Sinclair, and Piyush Srivastava

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

Abstract

The Ising model originated in statistical physics as a means of studying phase transitions in magnets, and has been the object of intensive study for almost a century. Combinatorially, it can be viewed as a natural distribution over cuts in a graph, and it has also been widely studied in computer science, especially in the context of approximate counting and sampling. In this paper, we study the complex zeros of the partition function of the Ising model, viewed as a polynomial in the "interaction parameter"; these are known as Fisher zeros in light of their introduction by Fisher in 1965. While the zeros of the partition function as a polynomial in the "field" parameter have been extensively studied since the classical work of Lee and Yang, comparatively little is known about Fisher zeros. Our main result shows that the zero-field Ising model has no Fisher zeros in a complex neighborhood of the entire region of parameters where the model exhibits correlation decay. In addition to shedding light on Fisher zeros themselves, this result also establishes a formal connection between two distinct notions of phase transition for the Ising model: the absence of complex zeros (analyticity of the free energy, or the logarithm of the partition function) and decay of correlations with distance. We also discuss the consequences of our result for efficient deterministic approximation of the partition function. Our proof relies heavily on algorithmic techniques, notably Weitz's self-avoiding walk tree, and as such belongs to a growing body of work that uses algorithmic methods to resolve classical questions in statistical physics.

Cite as

Jingcheng Liu, Alistair Sinclair, and Piyush Srivastava. Fisher Zeros and Correlation Decay in the Ising Model. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 55:1-55:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{liu_et_al:LIPIcs.ITCS.2019.55,
  author =	{Liu, Jingcheng and Sinclair, Alistair and Srivastava, Piyush},
  title =	{{Fisher Zeros and Correlation Decay in the Ising Model}},
  booktitle =	{10th Innovations in Theoretical Computer Science Conference (ITCS 2019)},
  pages =	{55:1--55:8},
  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.55},
  URN =		{urn:nbn:de:0030-drops-101483},
  doi =		{10.4230/LIPIcs.ITCS.2019.55},
  annote =	{Keywords: Ising model, zeros of polynomials, partition functions, approximate counting, phase transitions}
}

Search Results

Documents authored by Srivastava, Piyush

The Rate-Immediacy Barrier in Explicit Tree Code Constructions

Abstract

Cite as

Fisher Zeros and Correlation Decay in the Ising Model

Abstract

Cite as

Thanks for your feedback!

Could not send message