New Techniques for Proving Fine-Grained Average-Case Hardness

Monday, May 3, 2021 - 3:00pm to 4:00pm

Event Calendar Category

Uncategorized

Speaker Name

Andrea Lincoln

Affiliation

Berkeley

Join Zoom meeting

https://mit.zoom.us/j/97637459251

Abstract

In this talk, I will cover a new technique for worst-case to average-case reductions. There are two primary concepts introduced in this talk: "factored" problems and a framework for worst-case to average-case fine-grained (WCtoACFG) self reductions. We will define new versions of OV, kSUM, and zero-k-clique that are both worst-case and average-case fine-grained hard assuming the core hypotheses of fine-grained complexity. We then use these as a basis for fine-grained hardness and average-case hardness of other problems. Our hard-factored problems are also simple enough that we can reduce them to many other problems, e.g. to edit distance, k-LCS, and versions of Max-Flow. We further consider counting variants of the factored problems and give WCtoACFG reductions for them for a natural distribution. To show hardness for these factored problems we formalize the framework of [Boix-Adsera et al. 2019] that was used to give a WCtoACFG reduction for counting k-cliques. We define an explicit property of problems such that if a problem has that property one can use the framework on the problem to get a WCtoACFG self-reduction. In total, these factored problems and the framework together give tight fine-grained average-case hardness for various problems including the counting variant of regular expression matching.

Based on joint work with Mina Dalirrooyfard and Virginia Vassilevska Williams.

Biography

Andrea Lincoln graduated from MIT's undergraduate program with a double major in Mathematics and Electrical Engineering & Computer Science in 2014. She then received a Masters in Engineering in Electrical Engineering & Computer Science from MIT in 2015, advised by Erik Demaine. In 2016, she graduated with a Masters in Computer Science from Stanford, advised by Virginia Vassilevska Williams. Andrea Lincoln was awarded a Stanford Graduate Fellowship in 2015. She was then awarded the EECS Merrill Lynch Fellowship in 2017. She received the NSF GRFP honorable mention in 2016 and 2017. She is currently a Postdoctoral Researcher at UC Berkeley.