We initiate a study of super-perfect zero-knowledge proof systems.
Loosely speaking, these are proof systems for which the interaction can be perfectly simulated in strict probabilistic polynomial-time.
In contrast, the standard definition of perfect zero-knowledge only requires that the interaction can be perfectly simulated
by a strict probabilistic polynomial-time that ... more >>>

Given a system of linear equations $Ax=b$ over the binary field $\mathbb{F}_2$ and an integer $t\ge 1$, we study the following three algorithmic problems:
1. Does $Ax=b$ have a solution of weight at most $t$?
2. Does $Ax=b$ have a solution of weight exactly $t$?
3. Does $Ax=b$ have a ... more >>>

We prove a parallel repetition theorem for general games with value tending to 0. Previously Dinur and Steurer proved such a theorem for the special case of projection games. We use information theoretic techniques in our proof. Our proofs also extend to the high value regime (value close to 1) ... more >>>