Abstract

Traditional complexity and cryptography are primarily concerned with the difference between polynomial and super-polynomial time. A recent branch of complexity called Fine-Grained Complexity (FGC) has focused on polynomial differences in running time. Traditional complexity explains the hardness of problems like the Traveling Salesman Problem (NP-hard problems), showing that there is no polynomial-time algorithm if P != NP. However, it offers no answer to whether there exist faster algorithms for problems with existing, but slow, polynomial-time algorithms. FGC has provided us with an explanatory toolbox for why some problems have seen no improvement in their polynomial-time algorithm speed for over 50 years (e.g. [BI15, LWW18]).

The long-term goal of my research agenda is to apply the new tools of fine-grained complexity to the design of cryptographic protocols. A long-standing open problem in cryptography is to design public-key encryption which is secure solely under the assumption P!=NP. However, there are barriers to building encryption from P!=NP (e.g. discussion in survey of Boaz Barak in 2017). The hypothesis P!=NP is equivalent to the fact that there is no polynomial-time algorithm for satisfiability (SAT). There is a stronger hypothesis, the exponential time hypothesis (ETH), which states that 3-SAT requires exponential time [IP01]. The ambition of my research agenda is to design public-key cryptography secure from ETH.

Biography

Andrea Lincoln is a postdoctoral scholar at UC Berkeley. She was formerly an NTT Research Fellow at Simons. She completed her PhD at MIT advised by Virginia Vassilevska Williams. Andrea's thesis was on fine-grained complexity and its applications. She continues to study fine-grained complexity more broadly, but now primarily focuses on average-case fine-grained complexity.