Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with locally testable codes:
TR18-198 | 22nd November 2018
Irit Dinur, Tali Kaufman, Noga Ron-Zewi

From Local to Robust Testing via Agreement Testing

Revisions: 2

A local tester for an error-correcting code is a probabilistic procedure that queries a small subset of coordinates, accepts codewords with probability one, and rejects non-codewords with probability proportional to their distance from the code. The local tester is {\em robust} if for non-codewords it satisfies the stronger property that ... more >>>

TR21-151 | 8th November 2021
Irit Dinur, Shai Evra, Ron Livne, Alexander Lubotzky, Shahar Mozes

Locally Testable Codes with constant rate, distance, and locality

Revisions: 1

A locally testable code (LTC) is an error correcting code that has a property-tester. The tester reads $q$ bits that are randomly chosen, and rejects words with probability proportional to their distance from the code. The parameter $q$ is called the locality of the tester.

LTCs were initially studied as ... more >>>

TR21-175 | 6th December 2021
Oded Goldreich

On the Locally Testable Code of Dinur et al. (2021)

Revisions: 1

This text provides a high-level description of the locally testable code constructed by Dinur, Evra, Livne, Lubotzky, and Mozes (ECCC, TR21-151).
In particular, the group theoretic aspects are abstracted as much as possible.

more >>>

TR23-043 | 9th April 2023
Yotam Dikstein, Irit Dinur

Coboundary and cosystolic expansion without dependence on dimension or degree

We give new bounds on the cosystolic expansion constants of several families of high dimensional expanders, and the known coboundary expansion constants of order complexes of homogeneous geometric lattices, including the spherical building of $SL_n(F_q)$. The improvement applies to the high dimensional expanders constructed by Lubotzky, Samuels and Vishne, and ... more >>>

TR24-088 | 29th April 2024
Tamer Mour, Alon Rosen, Ron Rothblum

Locally Testable Tree Codes

Tree codes, introduced in the seminal works of Schulman (STOC 93', IEEE Transactions on Information Theory 96') are codes designed for interactive communication. Encoding in a tree code is done in an online manner: the $i$-th codeword symbol depends only on the first $i$ message symbols. Codewords should have good ... more >>>

ISSN 1433-8092 | Imprint