Talks
Spring 2023
Average-case Complexity for Polynomials, and All That
Thursday, February 16th, 2023, 2:15 pm–3:15 pm
Speaker:
Emanuele Viola (Northeastern University)
Location:
Calvin Lab Auditorium
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).