Skip to content (access key 's')
Logo of Technion
Logo of CS Department

The Taub Faculty of Computer Science Events and Talks

PCPs and Cryptography: New Limitations and Opportunities
event speaker icon
Liron Bronfman (M.Sc. Thesis Seminar)
event date icon
Wednesday, 21.04.2021, 14:00
event location icon
Zoom Lecture: 5480679598
For password to lecture, please contact:
event speaker icon
Advisor: Dr. Ron Rothblum
The connection between information theoretic proof systems and cryptography has been extremely fruitful. In this thesis, we further explore this connection, showing both new limitations and opportunities. In the talk we will focus on the new opportunities and show constructions of computational relaxations of objects that are known to be essentially impossible to achieve information theoretically. In particular, we show cryptographic analogs of: (1) PCPs whose length is proportional to the witness size. (2) Instance compression, which allows, for example, to efficiently and generically reduce the size of a given formula on m clauses and n variables (with m >>n) to a formula of size poly(n,log(m)). We will discuss the applicability of these relaxations and raise questions for future research.