All reports by Author Tali Kaufman:

__
TR23-178
| 16th November 2023
__

Louis Golowich, Tali Kaufman#### NLTS Hamiltonians and Strongly-Explicit SoS Lower Bounds from Low-Rate Quantum LDPC Codes

__
TR21-169
| 24th November 2021
__

Mitali Bafna, Max Hopkins, Tali Kaufman, Shachar Lovett#### Hypercontractivity on High Dimensional Expanders: a Local-to-Global Approach for Higher Moments

__
TR20-170
| 9th November 2020
__

Max Hopkins, Tali Kaufman, Shachar Lovett#### High Dimensional Expanders: Random Walks, Pseudorandomness, and Unique Games

Revisions: 1

__
TR19-124
| 28th August 2019
__

Roy Gotlib, Tali Kaufman#### Testing Odd Direct Sums Using High Dimensional Expanders

__
TR18-198
| 22nd November 2018
__

Irit Dinur, Tali Kaufman, Noga Ron-Zewi#### From Local to Robust Testing via Agreement Testing

Revisions: 2

__
TR18-136
| 1st August 2018
__

Irit Dinur, Prahladh Harsha, Tali Kaufman, Inbal Livni Navon, Amnon Ta-Shma#### List Decoding with Double Samplers

Revisions: 1

__
TR18-134
| 24th July 2018
__

Tali Kaufman, David Mass#### Cosystolic Expanders over any Abelian Group

__
TR17-089
| 11th May 2017
__

Irit Dinur, Tali Kaufman#### High dimensional expanders imply agreement expanders

__
TR11-055
| 14th April 2011
__

Irit Dinur, Tali Kaufman#### Dense locally testable codes cannot have constant rate and distance

__
TR10-130
| 18th August 2010
__

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

Revisions: 1

__
TR10-065
| 13th April 2010
__

Tali Kaufman, Shachar Lovett#### Testing of exponentially large codes, by a new extension to Weil bound for character sums

Revisions: 1

__
TR10-058
| 7th April 2010
__

Oded Goldreich, Tali Kaufman#### Proximity Oblivious Testing and the Role of Invariances

Revisions: 1

__
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

Louis Golowich, Tali Kaufman

Recent constructions of the first asymptotically good quantum LDPC (qLDPC) codes led to two breakthroughs in complexity theory: the NLTS (No Low-Energy Trivial States) theorem (Anshu, Breuckmann, and Nirkhe, STOC'23), and explicit lower bounds against a linear number of levels of the Sum-of-Squares (SoS) hierarchy (Hopkins and Lin, FOCS'22).

In ... more >>>

Mitali Bafna, Max Hopkins, Tali Kaufman, Shachar Lovett

Hypercontractivity is one of the most powerful tools in Boolean function analysis. Originally studied over the discrete hypercube, recent years have seen increasing interest in extensions to settings like the $p$-biased cube, slice, or Grassmannian, where variants of hypercontractivity have found a number of breakthrough applications including the resolution of ... more >>>

Max Hopkins, Tali Kaufman, Shachar Lovett

Higher order random walks (HD-walks) on high dimensional expanders have played a crucial role in a number of recent breakthroughs in theoretical computer science, perhaps most famously in the recent resolution of the Mihail-Vazirani conjecture (Anari et al. STOC 2019), which focuses on HD-walks on one-sided local-spectral expanders. In this ... more >>>

Roy Gotlib, Tali Kaufman

In this work, using methods from high dimensional expansion, we show that the property of $k$-direct-sum is testable for odd values of $k$ . Previous work of Kaufman and Lubotzky could inherently deal only with the case that $k$ is even, using a reduction to linearity testing.

Interestingly, our work ...
more >>>

Irit Dinur, Tali Kaufman, Noga Ron-Zewi

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

Irit Dinur, Prahladh Harsha, Tali Kaufman, Inbal Livni Navon, Amnon Ta-Shma

We develop the notion of double samplers, first introduced by Dinur and Kaufman [Proc. 58th FOCS, 2017], which are samplers with additional combinatorial properties, and whose existence we prove using high dimensional expanders.

We show how double samplers give a generic way of amplifying distance in a way that enables ... more >>>

Tali Kaufman, David Mass

In this work we show a general reduction from high dimensional complexes to their links based on the spectral properties of the links. We use this reduction to show that if a certain property is testable in the links, then it is also testable in the complex. In particular, we ... more >>>

Irit Dinur, Tali Kaufman

We show that high dimensional expanders imply derandomized direct product tests, with a number of subsets that is *linear* in the size of the universe.

Direct product tests belong to a family of tests called agreement tests that are important components in PCP constructions and include, for example, low degree ... more >>>

Irit Dinur, Tali Kaufman

A q-query locally testable code (LTC) is an error correcting code that can be tested by a randomized algorithm that reads at most q symbols from the given word.

An important question is whether there exist LTCs that have the ccc property: {c}onstant relative rate, {c}onstant relative distance, and that ...
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 >>>

Tali Kaufman, Shachar Lovett

In this work we consider linear codes which are locally testable

in a sublinear number of queries. We give the first general family

of locally testable codes of exponential size. Previous results of

this form were known only for codes of quasi-polynomial size (e.g.

Reed-Muller codes). We accomplish this by ...
more >>>

Oded Goldreich, Tali Kaufman

We present a general notion of properties that

are characterized by local conditions that are invariant

under a sufficiently rich class of symmetries.

Our framework generalizes two popular models of

testing graph properties as well as the algebraic

invariances studied by Kaufman and Sudan (STOC'08).

We show that, in the ... 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 >>>

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