BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260728T120410Z
UID:Seminar-ACTO-985@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Nikhil Mande:MAILTO:Nikhil.Mande@liverpool
DTSTART:20210324T163000
DTEND:20210324T173000
SUMMARY:Algorithms, Complexity Theory and Optimisation Series
DESCRIPTION:Andrea Lincoln: New Techniques for Proving Fine-Grained Average-Case Hardness\n\nIn 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. \n\nWe will define new versions of OV, kSUM and zero-k-clique that are both worst-case and averagecase 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.\n\nTo 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.\n\nIn 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.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=985
LOCATION:
END:VEVENT
END:VCALENDAR