# Computer Science/Discrete Mathematics Seminar I

## Dot-Product Proofs

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.

## Date & Time

November 25, 2024 | 10:30am – 11:30am

### Location

Simonyi 101 and Remote Access### Speakers

Yuval Ishai, Technion