2.00 pm, Seminar Hall
Average-Case Fine-Grained Hardness, and what to do with it
Prashant Nalini Vasudevan
Univ. of California Berkeley.
10-04-19

---

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.