CIS/Microsoft seminar
Speaker: Benny Applebaum , Princeton U.
Date: November 7 2008
Time: 10:30AM to 12:00PM
Location: 14th flr Tea lounge, Microsoft Research
Contact: be, 3-6098, imbe
Relevant URL:
We construct a new public key encryption based on two assumptions:
- It is hard to learn parity with noise given a small number of sparse examples (e.g., n^4 vectors of weight 10).
- It is hard to distinguish between a random unbalanced bipartite graph of small degree (e.g., 10), and a similar graph with a random planted non-expanding set of vertices.
The validity and strength of the assumptions raise interesting new algorithmic and pseudorandomness questions, and we explore their relation to the current state-of-art.
Joint work with Boaz Barak and Avi Wigderson.
See other events that are part of CIS/Microsoft Seminars 2008/2009
See other events happening in November 2008
