All reports by Author Tal Yankovitz:

__
TR24-090
| 12th May 2024
__

Gil Cohen, Dean Doron, Tomer Manket, Edward Pyne, Yichuan Wang, Tal Yankovitz#### A Study of Error Reduction Polynomials

__
TR23-110
| 25th July 2023
__

Gil Cohen, Tal Yankovitz#### Asymptotically-Good RLCCs with $(\log{n})^{2+o(1)}$ Queries

__
TR22-045
| 4th April 2022
__

Gil Cohen, Tal Yankovitz#### Relaxed Locally Decodable and Correctable Codes: Beyond Tensoring

Revisions: 1

__
TR21-154
| 10th November 2021
__

Inbar Ben Yaacov, Gil Cohen, Tal Yankovitz#### Explicit Binary Tree Codes with Sub-Logarithmic Size Alphabet

__
TR21-136
| 13th September 2021
__

Gil Cohen, Tal Yankovitz#### LCC and LDC: Tailor-made distance amplification and a refined separation

__
TR20-084
| 31st May 2020
__

Gil Cohen, Tal Yankovitz#### Rate Amplification and Query-Efficient Distance Amplification for Locally Decodable Codes

Revisions: 1

Gil Cohen, Dean Doron, Tomer Manket, Edward Pyne, Yichuan Wang, Tal Yankovitz

Error reduction procedures play a crucial role in constructing weighted PRGs [PV'21, CDRST'21], which are central to many recent advances in space-bounded derandomization. The fundamental method driving error reduction procedures is the Richardson iteration, which is adapted from the literature on fast Laplacian solvers. In the context of space-bounded derandomization, ... more >>>

Gil Cohen, Tal Yankovitz

Recently, Kumar and Mon reached a significant milestone by constructing asymptotically good relaxed locally correctable codes (RLCCs) with poly-logarithmic query complexity. Specifically, they constructed $n$-bit RLCCs with $O(\log^{69}n)$ queries. This significant advancement relies on a clever reduction to locally testable codes (LTCs), capitalizing on recent breakthrough works in LTCs.

With ... more >>>

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 ... more >>>

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 ... more >>>

Gil Cohen, Tal Yankovitz

The Alon-Edmonds-Luby distance amplification procedure (FOCS 1995) is an algorithm that transforms a code with vanishing distance to a code with constant distance. AEL was invoked by Kopparty, Meir, Ron-Zewi, and Saraf (J. ACM 2017) for obtaining their state-of-the-art LDC, LCC and LTC. Cohen and Yankovitz (CCC 2021) devised a ... more >>>

Gil Cohen, Tal Yankovitz

In a seminal work, Kopparty et al. (J. ACM 2017) constructed asymptotically good $n$-bit locally decodable codes (LDC) with $2^{\widetilde{O}(\sqrt{\log{n}})}$ queries. A key ingredient in their construction is a distance amplification procedure by Alon et al. (FOCS 1995) which amplifies the distance $\delta$ of a code to a constant at ... more >>>