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


PCPs and Cryptography: New Limitations and Opportunities
event speaker icon
Liron Bronfman, M.Sc. Thesis Seminar
event date icon
Wednesday, 21.4.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.
[Back to the index of events]