The Taub Faculty of Computer Science Events and Talks

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.