דלג לתוכן (מקש קיצור 's')
Logo of Technion
Logo of CS Department
אירועים

אירועים

PCPs and Cryptography: New Limitations and Opportunities
event speaker icon
לירון ברונפמן, הרצאה סמינריונית למגיסטר
event date icon
יום רביעי, 21.4.2021, 14:00
event location icon
Zoom Lecture: 5480679598
For password to lecture, please contact: br@cs.technion.ac.il
event speaker icon
מנחה:  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.
[בחזרה לאינדקס האירועים]