Lune

FOCS2020Top-tier venue

Deterministic and Efficient Interactive Coding from Hard-to-Decode Tree Codes

Zvika Brakerski, Yael Tauman Kalai, Raghuvansh R. Saxena

Abstract

The field of Interactive Coding studies how an interactive protocol can be made resilient to channel errors. Even though this field has received abundant attention since Schulman's seminal paper (FOCS 92), constructing interactive coding schemes that are both deterministic and efficient, and at the same time resilient to adversarial errors (with constant information and error rates), remains an elusive open problem. An appealing approach towards resolving this problem is to construct an efficiently encodable and decodable combinatorial object called a tree code (Schulman, STOC 93). After a lot of effort in this direction, the current state of the art has deterministic constructions of tree codes that are efficiently encodable but require an alphabet of size logarithmic (instead of constant) in the depth of the tree code (Cohen, Haeupler, and Schulman, STOC 18). We emphasize that we still lack (even heuristic) candidate constructions that are efficiently decodable. In this work, we show that tree codes that are efficiently encodable, but not efficiently decodable, also imply deterministic and efficient interactive coding schemes that are resilient to adversarial errors. Our result immediately implies a deterministic and efficient interactive coding scheme with a logarithmic alphabet (i.e., 1/ log log rate). We show this result using a novel implementation of hashing through deterministic tree codes that is powerful enough to yield interactive coding schemes.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Lineage

Builds onCited byLeft to right by year; the more cited, the higher.

Builds on1

  1. On Decoding Cohen-Haeupler-Schulman Tree CodesAnand Kumar Narayanan, Matthew WeidnerSODA 2020 · 2 citations

Related papers

  1. Efficient Interactive Coding Achieving Optimal Error Resilience over the Binary ChannelMeghal Gupta, Rachel Yun ZhangSTOC 2023 · 1 citation
  2. Binary Interactive Error Resilience Beyond 1 ⁣/ ⁣8{{}^{1}}\!/\!_{8} (or why (1 ⁣/ ⁣2)3>1 ⁣/ ⁣8)({{}^{1}}\!/\!_{2})^{3} > {{}^{1}}\!/\!_{8})Klim Efremenko, Gillat Kol, Raghuvansh R. SaxenaFOCS 2020 · 4 citations
  3. Interactive Coding with Small MemoryKlim Efremenko, Bernhard Haeupler, Yael Tauman Kalai, Gillat Kol et al.SODA 2023
  4. Locally Testable Tree CodesTamer Mour, Alon Rosen, Ron RothblumSODA 2025
  5. The optimal error resilience of interactive communication over binary channelsMeghal Gupta, Rachel Yun ZhangSTOC 2022 · 2 citations
Dusk over the sea between two cliffs drawn in fine vertical lines