Ran Raz, GĂˇbor Tardos, Oleg Verbitsky, Nikolay Vereshchagin

It is well known that probabilistic boolean decision trees

cannot be much more powerful than deterministic ones (N.~Nisan, SIAM

Journal on Computing, 20(6):999--1007, 1991). Motivated by a question

if randomization can significantly speed up a nondeterministic

computation via a boolean decision tree, we address structural

properties of Arthur-Merlin games ...
more >>>

Oded Goldreich, Howard Karloff, Leonard Schulman, Luca Trevisan

We prove that if a linear error correcting code

$\C:\{0,1\}^n\to\{0,1\}^m$ is such that a bit of the message can

be probabilistically reconstructed by looking at two entries of a

corrupted codeword, then $m = 2^{\Omega(n)}$. We also present

several extensions of this result.

We show a reduction from the ... more >>>

Eli Ben-Sasson, Oded Goldreich, Madhu Sudan

We present upper bounds on the size of codes that are locally

testable by querying only two input symbols. For linear codes, we

show that any $2$-locally testable code with minimal distance

$\delta n$ over a finite field $F$ cannot have more than

$|F|^{3/\delta}$ codewords. This result holds even ...
more >>>

Ramamohan Paturi, Pavel Pudlak

In 1977 Valiant proposed a graph theoretical method for proving lower

bounds on algebraic circuits with gates computing linear functions.

He used this method to reduce the problem of proving

lower bounds on circuits with linear gates to to proving lower bounds

on the rigidity of a matrix, a ...
more >>>

Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil Vadhan

We continue the study of the trade-off between the length of PCPs

and their query complexity, establishing the following main results

(which refer to proofs of satisfiability of circuits of size $n$):

We present PCPs of length $\exp(\tildeO(\log\log n)^2)\cdot n$

that can be verified by making $o(\log\log n)$ Boolean queries.

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

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

Venkatesan Guruswami, Patrick Xia

We prove that, for all binary-input symmetric memoryless channels, polar codes enable reliable communication at rates within $\epsilon > 0$ of the Shannon capacity with a block length, construction complexity, and decoding complexity all bounded by a *polynomial* in $1/\epsilon$. Polar coding gives the *first known explicit construction* with rigorous ... more >>>

Roei Tell

A few years ago, Blais, Brody, and Matulef (2012) presented a methodology for proving lower bounds for property testing problems by reducing them from problems in communication complexity. Recently, Bhrushundi, Chakraborty, and Kulkarni (2014) showed that some reductions of this type can be deconstructed to two separate reductions, from communication ... more >>>

Shachar Lovett

Network coding studies the capacity of networks to carry information, when internal nodes are allowed to actively encode information. It is known that for multi-cast networks, the network coding capacity can be achieved by linear codes. It is also known not to be true for general networks. The best separation ... more >>>

Alex Samorodnitsky, Ilya Shkredov, Sergey Yekhanin

A square matrix $V$ is called rigid if every matrix $V^\prime$ obtained by altering a small number of entries of $V$ has sufficiently high rank. While random matrices are rigid with high probability, no explicit constructions of rigid matrices are known to date. Obtaining such explicit matrices would have major ... more >>>