Computer Science/Discrete Mathematics Seminar I

A dot-product proof is a simple probabilistic proof system in which the verifier decides whether to accept an input vector based on a single linear combination of the entries of the input and a proof vector. I will present constructions of linear-size dot-product proofs for circuit satisfiability and discuss two kinds of applications: basing the exponential-time hardness of approximating MAX-LIN (maximal number of linear equations that can be simultaneously satisfied) on the standard exponential-time hypothesis, and minimizing the verification complexity of cryptographic proof systems.

Joint work with Nir Bitansky, Prahladh Harsha, Ron Rothblum, and David Wu.