All reports by Author Tali Kaufman:

__
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-043
| 18th May 2009
__

Elena Grigorescu, Tali Kaufman, Madhu Sudan#### Succinct Representation of Codes with Applications to Testing

__
TR08-111
| 14th November 2008
__

Shachar Lovett, Tali Kaufman#### The List-Decoding Size of Reed-Muller Codes

Revisions: 2

__
TR08-072
| 11th August 2008
__

Shachar Lovett, Tali Kaufman#### Worst case to Average case reductions for polynomials

__
TR08-033
| 21st March 2008
__

Elena Grigorescu, Tali Kaufman, Madhu Sudan#### 2-Transitivity is Insufficient for Local Testability

__
TR07-111
| 1st November 2007
__

Tali Kaufman, Madhu Sudan#### Algebraic Property Testing: The Role of Invariance

__
TR07-098
| 2nd October 2007
__

Tali Kaufman, Simon Litsyn, Ning Xie#### Breaking the $\epsilon$-Soundness Bound of the Linearity Test over GF(2)

__
TR07-060
| 11th July 2007
__

Tali Kaufman, Madhu Sudan#### Sparse Random Linear Codes are Locally Decodable and Testable

__
TR07-047
| 15th May 2007
__

Dan Gutfreund, Alexander Healy, Tali Kaufman, Guy Rothblum#### A (De)constructive Approach to Program Checking

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

Elena Grigorescu, Tali Kaufman, Madhu Sudan

Motivated by questions in property testing, we search for linear

error-correcting codes that have the ``single local orbit'' property:

i.e., they are specified by a single local

constraint and its translations under the symmetry group of the

code. We show that the dual of every ``sparse'' binary code

whose coordinates

more >>>

Shachar Lovett, Tali Kaufman

In this work we study the list-decoding size of Reed-Muller codes. Given a received word and a distance parameter, we are interested in bounding the size of the list of Reed-Muller codewords that are within that distance from the received word. Previous bounds of Gopalan, Klivans and Zuckerman~\cite{GKZ08} on the ... more >>>

Shachar Lovett, Tali Kaufman

A degree-d polynomial p in n variables over a field F is equidistributed if it takes on each of its |F| values close to equally often, and biased otherwise. We say that p has low rank if it can be expressed as a function of a small number of lower ... more >>>

Elena Grigorescu, Tali Kaufman, Madhu Sudan

A basic goal in Property Testing is to identify a

minimal set of features that make a property testable.

For the case when the property to be tested is membership

in a binary linear error-correcting code, Alon et al.~\cite{AKKLR}

had conjectured that the presence of a {\em single} low weight

more >>>

Tali Kaufman, Madhu Sudan

We argue that the symmetries of a property being tested play a

central role in property testing. We support this assertion in the

context of algebraic functions, by examining properties of functions

mapping a vector space $\K^n$ over a field $\K$ to a subfield $\F$.

We consider $\F$-linear properties that ...
more >>>

Tali Kaufman, Simon Litsyn, Ning Xie

For Boolean functions that are $\epsilon$-far from the set of linear functions, we study the lower bound on the rejection probability (denoted $\textsc{rej}(\epsilon)$) of the linearity test suggested by Blum, Luby and Rubinfeld. The interest in this problem is partly due to its relation to PCP constructions and hardness of ... more >>>

Tali Kaufman, Madhu Sudan

We show that random sparse binary linear codes are locally testable and locally decodable (under any linear encoding) with constant queries (with probability tending to one). By sparse, we mean that the code should have only polynomially many codewords. Our results are the first to show that local decodability and ... more >>>

Dan Gutfreund, Alexander Healy, Tali Kaufman, Guy Rothblum

Program checking, program self-correcting and program self-testing

were pioneered by [Blum and Kannan] and [Blum, Luby and Rubinfeld] in

the mid eighties as a new way to gain confidence in software, by

considering program correctness on an input by input basis rather than

full program verification. Work in ...
more >>>