Prashant Nalini Vasudevan: Average-Case Fine-Grained Hardness, and what to do with it

Speaker: Prashant Nalini Vasudevan

Date: Friday, February 10, 2017

Time: 10:30 AM to 12:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: Hewlett G882

Event Type:

Room Description:

Host: Vinod Vaikuntanathan

Contact: Deborah Goodwin, 617.324.7303, dlehto@csail.mit.edu

Relevant URL:

Speaker URL: None

Speaker Photo:
None

Reminders to: seminars@csail.mit.edu, cis-seminars@csail.mit.edu

Reminder Subject: TALK: Prashant Nalini Vasudevan: Average-Case Fine-Grained Hardness, and what to do with it

Abstract: We present functions that are hard to compute on average for algorithms running in some fixed polynomial time, assuming widely-conjectured worst-case hardness of certain problems from the study of fine-grained complexity.

We discuss the relevance of such average-case hardness to cryptography and present, as an illustration, an outline of a proof-of-work protocol constructed based on the hardness and certain structural properties of our functions.

Joint work with Marshall Ball, Alon Rosen and Manuel Sabin

Research Areas:

Impact Areas:

See other events that are part of the Cryptography and Information Seminar (CIS) 2017.

Created by Deborah Goodwin Email at Wednesday, February 01, 2017 at 11:59 AM.