BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Andrea Lincoln (UC Berkeley) DTSTART:20210414T170000Z DTEND:20210414T180000Z DTSTAMP:20260423T021009Z UID:TCSPlus/25 DESCRIPTION:Title: New Techniques for Proving Fine-Grained Average-Case Hardness\nby And rea Lincoln (UC Berkeley) as part of TCS+\n\n\nAbstract\nIn this talk I wi ll 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 re ductions.\n\nWe will define new versions of OV\, kSUM and zero-k-clique th at are both worst-case and average-case fine-grained hard assuming the cor e hypotheses of fine-grained complexity. We then use these as a basis for fine-grained hardness and average-case hardness of other problems. Our har d 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 WC toACFG 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-cliq ues. 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.\nIn total these factored problems and the framework togeth er give tight fine-grained average-case hardness for various problems incl uding the counting variant of regular expression matching.\n\nBased on joi nt work with Mina Dalirrooyfard and Virginia Vassilevska Williams.\n LOCATION:https://researchseminars.org/talk/TCSPlus/25/ END:VEVENT END:VCALENDAR