All reports by Author Michael Viderman:

__
TR15-020
| 31st January 2015
__

Michael Viderman#### Explicit Strong LTCs with inverse poly-log rate and constant soundness

Revisions: 3

__
TR13-022
| 5th February 2013
__

Michael Viderman#### Strong LTCs with inverse poly-log rate and constant soundness

Revisions: 1
An error-correcting code $C \subseteq \F^n$ is called $(q,\epsilon)$-strong locally testable code (LTC) if there exists a tester that makes at most $q$ queries to the input word. This tester accepts all codewords with probability 1 and rejects all non-codewords $x\notin C$ with probability at least $\epsilon \cdot \delta(x,C)$, where ... more >>>

__
TR12-168
| 26th November 2012
__

Michael Viderman#### Strong LTCs with inverse polylogarithmic rate and soundness

__
TR12-159
| 20th November 2012
__

Eli Ben-Sasson, Michael Viderman#### A Combinatorial Characterization of smooth LTCs and Applications

__
TR11-087
| 3rd June 2011
__

Michael Viderman#### A Combination of Testability and Decodability by Tensor Products

Revisions: 3

__
TR11-070
| 1st May 2011
__

Eli Ben-Sasson, Michael Viderman#### Composition of semi-LTCs by two-wise Tensor Products

__
TR11-058
| 15th April 2011
__

Michael Viderman#### Linear time decoding of regular expander codes

Revisions: 1

__
TR10-200
| 14th December 2010
__

Eli Ben-Sasson, Michael Viderman#### Towards lower bounds on locally testable codes via density arguments

__
TR10-171
| 11th November 2010
__

Michael Viderman#### A Note on high-rate Locally Testable Codes with sublinear query complexity

__
TR10-130
| 18th August 2010
__

Tali Kaufman, Michael Viderman#### Locally Testable vs. Locally Decodable Codes

Revisions: 1

__
TR10-004
| 6th January 2010
__

Eli Ben-Sasson, Michael Viderman#### Low Rate Is Insufficient for Local Testability

Revisions: 3

__
TR09-126
| 26th November 2009
__

Eli Ben-Sasson, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan, Michael Viderman#### Locally Testable Codes Require Redundant Testers

Revisions: 3

__
TR09-007
| 9th January 2009
__

Eli Ben-Sasson, Michael Viderman#### Tensor Products of Weakly Smooth Codes are Robust

Michael Viderman

An error-correcting code $C \subseteq \F^n$ is called $(q,\epsilon)$-strong locally testable code (LTC) if there exists a tester that makes at most $q$ queries to the input word. This tester accepts all codewords with probability 1 and rejects all non-codewords $x\notin C$ with probability at least $\epsilon \cdot \delta(x,C)$, where ... more >>>

Michael Viderman

Michael Viderman

An error-correcting code $C \subseteq \F^n$ is called $(q,\epsilon)$-strong locally testable code (LTC) if there exists a randomized algorithm (tester) that makes at most $q$ queries to the input word. This algorithm accepts all codewords with probability 1 and rejects all non-codewords $x\notin C$ with probability at least $\epsilon \cdot ... more >>>

Eli Ben-Sasson, Michael Viderman

The study of locally testable codes (LTCs) has benefited from a number of nontrivial constructions discovered in recent years. Yet we still lack a good understanding of what makes a linear error correcting code locally testable and as a result we do not know what is the rate-limit of LTCs ... more >>>

Michael Viderman

Ben-Sasson and Sudan (RSA 2006) showed that repeated tensor products of linear codes with a very large distance are locally testable. Due to the requirement of a very large distance the associated tensor products could be applied only over sufficiently large fields. Then Meir (SICOMP 2009) used this result (as ... more >>>

Eli Ben-Sasson, Michael Viderman

In this paper we obtain a composition theorem that allows us to construct locally testable codes (LTCs) by repeated two-wise tensor products. This is the First composition theorem showing that repeating the two-wise tensor operation any constant number of times still results in a locally testable code, improving upon previous ... more >>>

Michael Viderman

Sipser and Spielman (IEEE IT, 1996) showed that any $(c,d)$-regular expander code with expansion parameter $> \frac{3}{4}$ is decodable in \emph{linear time} from a constant fraction of errors. Feldman et al. (IEEE IT, 2007)

proved that expansion parameter $> \frac{2}{3} + \frac{1}{3c}$ is sufficient to correct a constant fraction of ...
more >>>

Eli Ben-Sasson, Michael Viderman

The main open problem in the area of locally testable codes (LTCs) is whether there exists an asymptotically good family of LTCs and to resolve this question it suffices to consider the case of query complexity $3$. We argue that to refute the existence of such an asymptotically good family ... more >>>

Michael Viderman

Inspired by recent construction of high-rate locally correctable codes with sublinear query complexity due to

Kopparty, Saraf and Yekhanin (2010) we address the similar question for locally testable codes (LTCs).

In this note we show a construction of high-rate LTCs with sublinear query complexity.

More formally, we show that for ...
more >>>

Tali Kaufman, Michael Viderman

We study the relation between locally testable and locally decodable codes.

Locally testable codes (LTCs) are error-correcting codes for which membership of a given word in the code can be tested probabilistically by examining it in very few locations. Locally decodable codes (LDCs) allow to recover each message entry with ...
more >>>

Eli Ben-Sasson, Michael Viderman

Locally testable codes (LTCs) are error-correcting codes for which membership of a given word in the code can be tested probabilistically by examining it in very few locations.

Kaufman and Sudan \cite{KS07} proved that sparse, low-bias linear codes are locally testable (in particular sparse random codes are locally testable).

Kopparty ...
more >>>

Eli Ben-Sasson, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan, Michael Viderman

Locally testable codes (LTCs) are error-correcting codes for which membership, in the code, of a given word can be tested by examining it in very few locations. Most known constructions of locally testable codes are linear codes, and give error-correcting codes

whose duals have (superlinearly) {\em many} small weight ...
more >>>

Eli Ben-Sasson, Michael Viderman

We continue the study of {\em robust} tensor codes and expand the

class of base codes that can be used as a starting point for the

construction of locally testable codes via robust two-wise tensor

products. In particular, we show that all unique-neighbor expander

codes and all locally correctable codes, ...
more >>>