Computer Science/Discrete Mathematics Seminar I

Two central results in modern complexity theory can be summed up as follows:

1. Everything provable is provable in zero knowledge (NP ⊆ CZK); and
2. Everything provable is locally checkable (NP = PCP[log n, 1]).

In a pair of recent works, we show how to achieve these two properties simultaneously: Everything provable is locally checkable in zero knowledge.

That is, we demonstrate that for every polynomial Q, every NP language has a polynomial-size proof which can be verified by querying O(1) positions, but where querying any Q(n) positions reveals no information about the witness.

Based on joint work with Tom Gur and Jack O'Connor.