Tata Institute of Fundamental Research
Dot-Product Proofs
STCS Seminar
Speaker:
Prahladh Harsha (TIFR)
Organiser:
Raghuvansh Saxena
Date:
Tuesday, 26 Aug 2025, 16:00 to 17:00
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
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. In this talk, 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, Yuval Ishai, Ron Rothblum, and David Wu]
| Speaker: | Prahladh Harsha (TIFR) |
| Organiser: | Raghuvansh Saxena |
| Date: | Tuesday, 26 Aug 2025, 16:00 to 17:00 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
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. In this talk, 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, Yuval Ishai, Ron Rothblum, and David Wu]