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

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

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

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

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

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

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

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

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

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

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

Random linear codes (RLCs) are well known to have nice combinatorial properties and near-optimal parameters in many different settings. However, getting explicit constructions matching the parameters of RLCs is challenging, and RLCs are hard to decode efficiently. This motivated several previous works to study the problem of partially derandomizing RLCs, ... more >>>