All reports by Author Noga Ron-Zewi:

__
TR23-160
| 29th October 2023
__

Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf#### Simple Constructions of Unique Neighbor Expanders from Error-correcting Codes

Revisions: 1

__
TR21-180
| 21st December 2021
__

Noga Ron-Zewi, Ron Rothblum#### Proving as Fast as Computing: Succinct Arguments with Constant Prover Overhead

__
TR20-013
| 17th February 2020
__

Noga Ron-Zewi, Mary Wootters, Gilles Z\'{e}mor#### Linear-time Erasure List-decoding of Expander Codes

Revisions: 1

__
TR19-080
| 1st June 2019
__

Swastik Kopparty, Nicolas Resch, Noga Ron-Zewi, Shubhangi Saraf, Shashwat Silas#### On List Recovery of High-Rate Tensor Codes

__
TR18-198
| 22nd November 2018
__

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

Revisions: 2

__
TR18-091
| 4th May 2018
__

Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf, Mary Wootters#### Improved decoding of Folded Reed-Solomon and Multiplicity Codes

Revisions: 2

__
TR17-104
| 13th June 2017
__

Brett Hemenway, Noga Ron-Zewi, Mary Wootters#### Local List Recovery of High-rate Tensor Codes & Applications

Revisions: 1

__
TR16-122
| 11th August 2016
__

Sivakanth Gopi, Swastik Kopparty, Rafael Mendes de Oliveira, Noga Ron-Zewi, Shubhangi Saraf#### Locally testable and Locally correctable Codes Approaching the Gilbert-Varshamov Bound

__
TR15-165
| 14th October 2015
__

Ran Gelles, Bernhard Haeupler, Gillat Kol, Noga Ron-Zewi, Avi Wigderson#### Towards Optimal Deterministic Coding for Interactive Communication

Revisions: 1

__
TR15-110
| 8th July 2015
__

Swastik Kopparty, Or Meir, Noga Ron-Zewi, Shubhangi Saraf#### High-rate Locally-testable Codes with Quasi-polylogarithmic Query Complexity

Revisions: 1

__
TR15-094
| 10th June 2015
__

Eli Ben-Sasson, iddo Ben-Tov, Ivan Bjerre Damgard, Yuval Ishai, Noga Ron-Zewi#### On Public Key Encryption from Noisy Codewords

__
TR15-068
| 21st April 2015
__

Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf#### High rate locally-correctable and locally-testable codes with sub-polynomial query complexity

Revisions: 3

__
TR13-030
| 20th February 2013
__

Elad Haramaty, Noga Ron-Zewi, Madhu Sudan#### Absolutely Sound Testing of Lifted Codes

__
TR12-135
| 26th October 2012
__

Eli Ben-Sasson, Noga Ron-Zewi, Madhur Tulsiani, Julia Wolf#### Sampling-based proofs of almost-periodicity results and algorithmic applications

Revisions: 2

__
TR12-132
| 21st October 2012
__

Yuval Filmus, Massimo Lauria, Jakob NordstrÃ¶m, Noga Ron-Zewi, Neil Thapen#### Space Complexity in Polynomial Calculus

__
TR12-049
| 27th April 2012
__

Eli Ben-Sasson, Noga Ron-Zewi, Madhu Sudan#### Sparse affine-invariant linear codes are locally testable

__
TR12-046
| 24th April 2012
__

Madhu Sudan, Noga Ron-Zewi#### A new upper bound on the query complexity for testing generalized Reed-Muller codes

Revisions: 1

__
TR11-157
| 25th November 2011
__

Eli Ben-Sasson, Shachar Lovett, Noga Ron-Zewi#### An additive combinatorics approach to the log-rank conjecture in communication complexity

Revisions: 1

__
TR10-144
| 20th September 2010
__

Eli Ben-Sasson, Noga Ron-Zewi#### From Affine to Two-Source Extractors via Approximate Duality

Revisions: 1

Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf

In this note, we give very simple constructions of unique neighbor expander graphs starting from spectral or combinatorial expander graphs of mild expansion. These constructions and their analysis are simple variants of the constructions of LDPC error-correcting codes from expanders, given by

Sipser-Spielman~\cite{SS96} (and Tanner~\cite{Tanner81}), and their analysis. We also ...
more >>>

Noga Ron-Zewi, Ron Rothblum

Succinct arguments are proof systems that allow a powerful, but untrusted, prover to convince a weak verifier that an input $x$ belongs to a language $L \in NP$, with communication that is much shorter than the $NP$ witness. Such arguments, which grew out of the theory literature, are now drawing ... more >>>

Noga Ron-Zewi, Mary Wootters, Gilles Z\'{e}mor

We give a linear-time erasure list-decoding algorithm for expander codes. More precisely, let $r > 0$ be any integer. Given an inner code $\cC_0$ of length $d$, and a $d$-regular bipartite expander graph $G$ with $n$ vertices on each side, we give an algorithm to list-decode the expander code $\cC ... more >>>

Swastik Kopparty, Nicolas Resch, Noga Ron-Zewi, Shubhangi Saraf, Shashwat Silas

We continue the study of list recovery properties of high-rate tensor codes, initiated by Hemenway, Ron-Zewi, and Wootters (FOCS'17). In that work it was shown that the tensor product of an efficient (poly-time) high-rate globally list recoverable code is {\em approximately} locally list recoverable, as well as globally list recoverable ... 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 >>>

Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf, Mary Wootters

In this work, we show new and improved error-correcting properties of folded Reed-Solomon codes and multiplicity codes. Both of these families of codes are based on polynomials over finite fields, and both have been the sources of recent advances in coding theory. Folded Reed-Solomon codes were the first explicit constructions ... more >>>

Brett Hemenway, Noga Ron-Zewi, Mary Wootters

In this work, we give the first construction of {\em high-rate} locally list-recoverable codes. List-recovery has been an extremely useful building block in coding theory, and our motivation is to use these codes as such a building block.

In particular, our construction gives the first {\em capacity-achieving} locally list-decodable ...
more >>>

Sivakanth Gopi, Swastik Kopparty, Rafael Mendes de Oliveira, Noga Ron-Zewi, Shubhangi Saraf

One of the most important open problems in the theory

of error-correcting codes is to determine the

tradeoff between the rate $R$ and minimum distance $\delta$ of a binary

code. The best known tradeoff is the Gilbert-Varshamov bound,

and says that for every $\delta \in (0, 1/2)$, there are ...
more >>>

Ran Gelles, Bernhard Haeupler, Gillat Kol, Noga Ron-Zewi, Avi Wigderson

We study \emph{efficient, deterministic} interactive coding schemes that simulate any interactive protocol both under random and adversarial errors, and can achieve a constant communication rate independent of the protocol length.

For channels that flip bits independently with probability~$\epsilon<1/2$, our coding scheme achieves a communication rate of $1 - O(\sqrt{H({\epsilon})})$ and ... more >>>

Swastik Kopparty, Or Meir, Noga Ron-Zewi, Shubhangi Saraf

An error correcting code is said to be \emph{locally testable} if

there is a test that checks whether a given string is a codeword,

or rather far from the code, by reading only a small number of symbols

of the string. Locally testable codes (LTCs) are both interesting

in their ...
more >>>

Eli Ben-Sasson, iddo Ben-Tov, Ivan Bjerre Damgard, Yuval Ishai, Noga Ron-Zewi

Several well-known public key encryption schemes, including those of Alekhnovich (FOCS 2003), Regev (STOC 2005), and Gentry, Peikert and Vaikuntanathan (STOC 2008), rely on the conjectured intractability of inverting noisy linear encodings. These schemes are limited in that they either require the underlying field to grow with the security parameter, ... more >>>

Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf

In this work, we construct the first locally-correctable codes (LCCs), and locally-testable codes (LTCs) with constant rate, constant relative distance, and sub-polynomial query complexity. Specifically, we show that there exist binary LCCs and LTCs with block length $n$, constant rate (which can even be taken arbitrarily close to 1), constant ... more >>>

Elad Haramaty, Noga Ron-Zewi, Madhu Sudan

In this work we present a strong analysis of the testability of a broad, and to date the most interesting known, class of "affine-invariant'' codes. Affine-invariant codes are codes whose coordinates are associated with a vector space and are invariant under affine transformations of the coordinate space. Affine-invariant linear codes ... more >>>

Eli Ben-Sasson, Noga Ron-Zewi, Madhur Tulsiani, Julia Wolf

We give new combinatorial proofs of known almost-periodicity results for sumsets of sets with small doubling in the spirit of Croot and Sisask [Geom. Funct. Anal. 2010], whose almost-periodicity lemma has had far-reaching implications in additive combinatorics. We provide an alternative (and $L^p$-norm free) point of view, which allows for ... more >>>

Yuval Filmus, Massimo Lauria, Jakob NordstrÃ¶m, Noga Ron-Zewi, Neil Thapen

During the last decade, an active line of research in proof complexity has been to study space complexity and time-space trade-offs for proofs. Besides being a natural complexity measure of intrinsic interest, space is also an important issue in SAT solving, and so research has mostly focused on weak systems ... more >>>

Eli Ben-Sasson, Noga Ron-Zewi, Madhu Sudan

We show that sparse affine-invariant linear properties over arbitrary finite fields are locally testable with a constant number of queries. Given a finite field ${\mathbb{F}}_q$ and an extension field ${\mathbb{F}}_{q^n}$, a property is a set of functions mapping ${\mathbb{F}}_{q^n}$ to ${\mathbb{F}}_q$. The property is said to be affine-invariant if it ... more >>>

Madhu Sudan, Noga Ron-Zewi

Over a finite field $\F_q$ the $(n,d,q)$-Reed-Muller code is the code given by evaluations of $n$-variate polynomials of total degree at most $d$ on all points (of $\F_q^n$). The task of testing if a function $f:\F_q^n \to \F_q$ is close to a codeword of an $(n,d,q)$-Reed-Muller code has been of ... more >>>

Eli Ben-Sasson, Shachar Lovett, Noga Ron-Zewi

For a {0,1}-valued matrix $M$ let CC($M$) denote the deterministic communication complexity of the boolean function associated with $M$. The log-rank conjecture of Lovasz and Saks [FOCS 1988] states that CC($M$) is at most $\log^c({\mbox{rank}}(M))$ for some absolute constant $c$ where rank($M$) denotes the rank of $M$ over the field ... more >>>

Eli Ben-Sasson, Noga Ron-Zewi

Two-source and affine extractors and dispersers are fundamental objects studied in the context of derandomization. This paper shows how to construct two-source extractors and dispersers for arbitrarily small min-entropy rate in a black-box manner from affine extractors with sufficiently good parameters. Our analysis relies on the study of approximate duality, ... more >>>