Average-case Complexity for Polynomials, and All That

Emanuele Viola (Northeastern University)
https://simons.berkeley.edu/talks/ave...
Lower Bounds, Learning, and Average-Case Complexity

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/pa....

• #education
• #simons_institute
• #theoretical_computer_science
• #uc_berkeley
• #computer_science
• #theory_of_computation
• #theory_of_computing
• #lower_bounds_learning_and_average_case_complexity
• #emanuele_viola