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).