Back to Events

A Biased Introduction to Average-Case Fine Grained Complexity

Speaker

Andrea Lincoln
Boston University

Host

Noah Golowich
MIT

May 08 2024

4:00P - 5:00P

Location

32-G575
https://mit.zoom.us/j/95798801182?pwd=ejR6UzdyY1JFM28rMEE1S1J1SjV5dz09
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.
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

Organizer & Contact

Noah Golowich