Dot-Product Proofs for Circuit Satisfiability and Cryptographic Systems

Watch a computer science seminar where Yuval Ishai from Technion explores dot-product proofs - a probabilistic proof system for verifying input vectors through linear combinations. Delve into the construction of linear-size dot-product proofs for circuit satisfiability and examine their applications in two key areas: establishing exponential-time hardness of approximating MAX-LIN based on the standard exponential-time hypothesis, and optimizing verification complexity in cryptographic proof systems. Learn about collaborative research findings developed with Nir Bitansky, Prahladh Harsha, Ron Rothblum, and David Wu during this 80-minute academic presentation at the Institute for Advanced Study's Computer Science/Discrete Mathematics Seminar series.