![Meta-complexity_logo_hi-res](/sites/default/files/styles/workshop_banner_sm_1x/public/2023-02/Meta-complexity_hi-res.png.jpg?itok=oFqprXq1)
Abstract
We survey correlation bounds (a.k.a. average-case complexity) for polynomials, and related results. In particular we discuss a number of recent results, including:
- New connection (ICALP 2021) with recent pseudorandom-generator constructions.
- Counterexample to the CHLLZ, STOC 2020 conjecture about polynomials.
- New approaches to correlation bounds, including exact bounds for mod 3 vs quadratic polynomials
- Pseudorandom generators with optimal seed length over large fields (FOCS 2022)
The speaker's survey on the topic has recently been updated (https://www.ccs.neu.edu/home/viola/papers/corr-survey.pdf).