Author name cluster

Tal Yankovitz

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

1 author row

FOCS Conference 2024 Conference Paper

A Stronger Bound for Linear 3-LCC

Tal Yankovitz

A q-locally correctable code (LCC) $C: \{0, 1\}^{k}\rightarrow \{0, 1\}^{n}$ is a code in which it is possible to correct every bit of a (not too) corrupted codeword by making at most $q$ queries to the word. The cases in which $q$ is constant are of special interest, and so are the cases that $C$ is linear. In a breakthrough result Kothari and Manohar (STOC 2024) showed that for linear 3-LCC $n=2^{\Omega(k^{1/8})}$. In this work we prove that $n=2^{\Omega(k^{1/4})}$. As Reed-Muller codes yield 3-LCC with $n=2^{O(k^{1/2})}$, this brings us closer to closing the gap. Moreover, in the special case of design-LCC (into which Reed-Muller fall) the bound we get is $n=2^{\Omega(k^{1/3})}$.

Details

STOC Conference 2022 Conference Paper

Explicit binary tree codes with sub-logarithmic size alphabet

Inbar Ben Yaacov
Gil Cohen
Tal Yankovitz

Since they were first introduced by Schulman (STOC 1993), the construction of tree codes remained an elusive open problem. The state-of-the-art construction by Cohen, Haeupler and Schulman (STOC 2018) has constant distance and (log n ) e colors for some constant e > 1 that depends on the distance, where n is the depth of the tree. Insisting on a constant number of colors at the expense of having vanishing distance, Gelles, Haeupler, Kol, Ron-Zewi, and Wigderson (SODA 2016) constructed a distance Ω(1/log n ) tree code. In this work we improve upon these prior works and construct a distance-δ tree code with (log n ) O (√δ) colors. This is the first construction of a constant distance tree code with sub-logarithmic number of colors. Moreover, as a direct corollary we obtain a tree code with a constant number of colors and distance Ω(1/(loglog n ) 2 ), exponentially improving upon the above-mentioned work by Gelles et al.

Details

FOCS Conference 2022 Conference Paper

Relaxed Locally Decodable and Correctable Codes: Beyond Tensoring

Gil Cohen
Tal Yankovitz

In their highly influential paper, Ben-Sasson, Goldreich, Harsha, Sudan, and Vadhan (STOC 2004) introduced the notion of a relaxed locally decodable code (RLDC). Similarly to a locally decodable code (Katz-Trevisan; STOC 2000), the former admits access to any desired message symbol with only a few queries to a possibly corrupted codeword. An RLDC, however, is allowed to abort when identifying corruption. The natural analog to locally correctable codes, dubbed relaxed locally correctable codes (RLCC), was introduced by Gur, Ramnarayan and Rothblum (ITCS 2018) who constructed asymptotically-good length-nRLCC and RLDC with $(\log n)^{O(\log\log n)}$ queries. In this work we construct asymptotically-good RLDC and RLCC with an improved query complexity of $(\log n)^{O(\log\log\log n)}$. To achieve this, we devise a mechanism-an alternative to the tensor product-that squares the length of a given code. Compared to the tensor product that was used by Gur et al. and by many other constructions, our mechanism is significantly more efficient in terms of rate deterioration, allowing us to obtain our improved construction.

Details