Testing Reed Muller Codes ∗ (2009)
Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, Dana Ron
A code is locally testable if there is a way to indicate with high probability that a vector is far enough from any codeword by accessing only a very small number of the vector’s bits. We show that...
Succinct Representation of Codes with Applications to Testing (2009)
Grigorescu, Elena, Kaufman, Tali, Sudan, Madhu
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...
Testing low-degree polynomials over GF(2) (2008)
Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, Dana Ron
Abstract. We describe an efficient randomized algorithm to test if a given binary function � � ����� � � ���� � is a low-degree polynomial (that is, a sum of low-degree...
The List-Decoding Size of Reed-Muller Codes (2008)
Kaufman, Tali, Lovett, Shachar
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...
Worst Case to Average Case Reductions for Polynomials (2008)
Kaufman, Tali, Lovett, Shachar
A degree-$d$ polynomial $p$ in $n$ variables over a field $\F$ is {\em equidistributed} if it takes on each of its $|\F|$ values close to equally often, and {\em biased} otherwise. We say that $p$...
Testing low-degree polynomials over GF(2), booktitle (2008)
Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, Dana Ron
We describe an efficient randomized algorithm to test if a given binary function f: {0, 1} n → {0, 1} is a low-degree polynomial (that is, a sum of low-degree monomials). For a given integer k ≥...
time has two-prover interactive protocols. Computational Complexity, 1:3–40, 1991. (2008)
Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, Dana Ron Testing, László Babai, ...
[4] Sanjeev Arora, László Babai, Jacques Stern, and Z Sweedyk. The hardness of approximate optima in lattices, codes, and systems of linear equations. Journal of
Abstract Guessing Secrets Efficiently via List Decoding (Extended Abstract) (2008)
Noga Alon, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan
We consider the guessing secrets problem defined by
Abstract Testing Triangle-Freeness in General Graphs (2008)
Noga Alon, Tali Kaufman, Michael Krivelevich, Dana Ron
In this paper we consider the problem of testing whether a graph is triangle-free, and more generally, whether it is H-free, for a fixed subgraph H. The algorithm should accept graphs that are...
Testing low-degree polynomials over (2008)
Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn
Abstract. We describe an efficient randomized algorithm to test if a given binary function is a low-degree polynomial (that is, a sum of low-degree monomials). For a ���� � given integer...
Noga Alon, Venkatesan Guruswami, Tali Kaufman
Madhu Sudan x Abstract We consider the guessing secrets problem defined by Chung, Graham, and Leighton [CGL01]. This is a variant of the standard 20 questions game where the player has a set of k? 1...
Elena Grigorescu, Tali Kaufman
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...
Ido Ben-eliezer, Tali Kaufman, Michael Krivelevich, Dana Ron
the strength of query types in property testing:
Breaking the $epsilon$-Soundness Bound of the Linearity Test over GF(2) (2008)
Kaufman, Tali, Litsyn, Simon, Xie, Ning
For Boolean functions that are $epsilon$-far from the set of linear functions, we study the lower bound on the rejection probability (denoted by $extsc{rej}(epsilon)$) of the linearity test suggested...
Noga Alon, Venkatesan Guruswami, Tali Kaufman
We consider the guessing secrets problem dened by Chung, Graham, and Leighton [CGL01]. This is a variant of the standard 20 questions game where the player has a set of k> 1 secrets from a...
Algebraic Property Testing: The Role of Invariance (2007)
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...
Sparse random linear codes are locally decodable and testable (2007)
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...
Verifying and decoding in constant depth (2007)
Shafi Goldwasser, Tali Kaufman
We develop a general approach for improving the efficiency of a computationally bounded receiver interacting with a powerful and possibly malicious sender. The key idea we use is that of delegating...
Sparse random linear codes are locally decodable and testable (2007)
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...
Verifying and decoding in constant depth (2007)
Shafi Goldwasser, Dan Gutfreund, Tali Kaufman
We develop a general approach for improving the efficiency of a computationally bounded receiver interacting with a powerful and possibly malicious sender. The key idea we use is that of delegating...
Verifying and decoding in constant depth (2007)
Shafi Goldwasser, Alexander Healy, Tali Kaufman, Dan Gutfreund, Guy N. Rothblum
We develop a general approach for improving the efficiency of a computationally bounded receiver interacting with a powerful and possibly malicious sender. The key idea we use is that of delegating...
Testing triangle-freeness in general graphs (2006)
Noga Alon, Tali Kaufman, Michael Krivelevich, Dana Ron
In this paper we consider the problem of testing whether a graph is triangle-free, and more generally, whether it is H-free, for a fixed subgraph H. The algorithm should accept graphs that are...
Testing triangle-freeness in general graphs (2006)
Noga Alon, Tali Kaufman, Michael Krivelevich, Dana Ron
In this paper we consider the problem of testing whether a graph is triangle-free, and more generally, whether it is H-free, for a fixed subgraph H. The algorithm should accept graphs that are...
Noga Alon, Ronitt Rubinfeld, Alexandr Andoni, Tali Kaufman, Ning Xie, Kevin Matulef
In this work, we consider the problems of testing whether a distribution over{0, 1} n is k-wise or (ǫ, k)-wise independent using samples drawn from that distribution. To distinguish k-wise...
1.1 History and Mission (2005)
Shakhar Smorodinsky, Dina Schneidman, Eran Leiserowitz, Eyal Molad, ...
performed at Tel-Aviv University and presented at the most prestigious international computer science conferences and workshops. The Deutsch Institute believes that enabling graduate students to...
The Raymond, Beverly Sackler, Faculty Exact Sciences, Tali Kaufman, Under Professors, Noga Alon, ...
Property Testing is nowadays one of the central fields in Theoretical Computer Science. This concept played a major role in the proof of the celebrated PCP theorem. A typical task in Property Testing...
Tight Bounds for Testing Bipartiteness in General Graphs (2004)
Tali Kaufman, Michael Krivelevich, Dana Ron
In this paper we consider the problem of testing bipartiteness of general graphs. The problem has previously been studied in two models, one most suitable for dense graphs, and one most suitable for...
Testing Reed Muller Codes \Lambda (2004)
Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, Dana Ron
Abstract A code is locally testable if there is a way to indicate with high probability that a vector is far enough from any codeword by accessing only a very small number of the vector's bits....
Tight Bounds for Testing Bipartiteness in General Graphs (2003)
Tali Kaufman, Michael Krivelevich, Dana Ron
In this paper we consider the problem of testing bipartiteness of general graphs. The problem has previously been studied in two models, one most suitable for dense graphs, and one most suitable for...
Testing Low-Degree Polynomials over GF(2) (2003)
Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, Dana Ron
We describe an efficient randomized algorithm to test if a given binary function f : f0; 1g ! f0; 1g is a low-degree polynomial (that is, a sum of low-degree monomials). For a given integer k 1 and a...
Testing Low-Degree Polynomials over GF(2) (2003)
Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, Dana Ron
We describe an efficient randomized algorithm to test if a given binary function f : f0; 1g ! f0; 1g is a low-degree polynomial (that is, a sum of low-degree monomials). For a given integer k 1 and a...
A (de)constructive approach to program checking (1989)
Shafi Goldwasser, Alexander Healy, Tali Kaufman, Dan Gutfreund, Guy N. 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,...