Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Noga Ron-Zewi:

TR17-104 | 13th June 2017
Brett Hemenway, Noga Ron-Zewi, Mary Wootters

Local List Recovery of High-rate Tensor Codes & Applications

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

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

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

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

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

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

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

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

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

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

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

TR13-030 | 20th February 2013
Elad Haramaty, Noga Ron-Zewi, Madhu Sudan

Absolutely Sound Testing of Lifted Codes

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

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

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

TR12-132 | 21st October 2012
Yuval Filmus, Massimo Lauria, Jakob Nordström, Noga Ron-Zewi, Neil Thapen

Space Complexity in Polynomial Calculus

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

TR12-049 | 27th April 2012
Eli Ben-Sasson, Noga Ron-Zewi, Madhu Sudan

Sparse affine-invariant linear codes are locally testable

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

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

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

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

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

TR10-144 | 20th September 2010
Eli Ben-Sasson, Noga Ron-Zewi

From Affine to Two-Source Extractors via Approximate Duality

Revisions: 1

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

ISSN 1433-8092 | Imprint