A Biased Introduction to Average-Case Fine Grained Complexity
Boston University
Add to Calendar
2024-05-08 16:00:00
2024-05-08 17:00:00
America/New_York
A Biased Introduction to Average-Case Fine Grained Complexity
Abstract: I will introduce the techniques and approaches of fine-grained average-case complexity. I will explain the centrality of low degree polynomials. I will highlight results from many papers and different techniques that can be used. We will end with a result showing that for any constant sized subgraph H, counting the number of H in a worst-case graph and counting the number of H in an Erdős–Rényi graph take the same time up to polylog factors.
32-G575