Skip to content

« All Events

Dot-Product Proofs by Prahladh Harsha

July 28 @ 11:30 am - 12:30 pm

Title: Dot-Product Proofs
Speaker: Prahladh Harsha (TIFR Mumbai)

Details: July 28 (Monday) | 11:30 AM | Bharti 501

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]

Bio: Prahladh Harsha is a Professor at the School of Technology and Computer Science at the Tata Institute of Fundamental Research (TIFR), Mumbai, India. He obtained his BTech degree in Computer Science and Engineering from IIT Madras in 1998 and his PhD in Computer Science from the Massachusetts Institute of Technology (MIT) in 2004. He has worked at Microsoft Research, TTI Chicago, and has been at TIFR since 2010.

Prahladh’s research interests are in the area of theoretical computer science, with special emphasis on computational complexity theory and algebraic coding theory. He is best known for his work in the area of probabilistically checkable proofs. Prahladh Harsha is a winner of the NASI Young Scientist Award for Mathematics and the Swarnajayanti Fellowship (Govt. of India).

Prof. Harsha has served on the editorial boards of SIAM Journal on Computing and Algorithmica. He is currently the Editor-in-Chief of the ACM Transactions on Computation Theory and a Fellow of the Indian Academy of Sciences.

Details

Date:
July 28
Time:
11:30 am - 12:30 pm

Venue

Bharti 501
IIT Campus, Hauz Khas
New Delhi, + Google Map