Talks
Spring 2023

Average-case Complexity for Polynomials, and All That

Thursday, February 16th, 2023, 2:15 pm3:15 pm

Add to Calendar

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