New Techniques for Proving Fine-Grained Average-Case Hardness

New Techniques for Proving Fine-Grained Average-Case Hardness (via Zoom)

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.

Bio: 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.