Average-case Complexity for Polynomials, and All That

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,700
Published on ● Video Link: https://www.youtube.com/watch?v=JcLhYezUubc


Duration: 59:41
393 views
7

Emanuele Viola (Northeastern University)
https://simons.berkeley.edu/talks/average-case-complexity-polynomials-all
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/papers/corr-survey.pdf).



Other Videos By Simons Institute for the Theory of Computing


2023-03-20Lower Bounds Against PC With Extension Variables
2023-03-17Strong Bounds for 3-Progressions
2023-03-15The Quantum Fourier Transform Has Small Entanglement | Quantum Colloquium
2023-03-07Writing Workshop with Science Communicator in Residence Adam Becker
2023-02-26What Do the Theory of Computing and the Movies Have in Common?
2023-02-18Unstructured Hardness to Average-Case Randomness
2023-02-18Learning with Distributional Inverters
2023-02-18What (Doesn't) Make Learning Algorithms Generalize?
2023-02-17Cryptography from Sublinear-Time Average-Case Hardness of Time-Bounded Kolmogorov Complexity
2023-02-17On Low End Obfuscation and Learning
2023-02-17Average-case Complexity for Polynomials, and All That
2023-02-17On the Average-case Complexity of the Nearest Boolean Vector to a Subspace
2023-02-17New Approaches to Heuristic Pac-learning vs. PRFs
2023-02-16Succinct Neural Networks
2023-02-16New Lower Bounds and Derandomization for ACC, and a...
2023-02-16Learning Safe Action Models
2023-02-16Quantum Meets Minimum Circuit Size Problem
2023-02-16A Duality Between One-Way Functions and Average-Case Symmetry of Information
2023-02-15Learning Versus Pseudorandom Generators in Constant Parallel Time
2023-02-15Quantum Learning Algorithms Imply Circuit Lower Bounds
2023-02-15Range Avoidance, Remote Point, and Hard Partial Truth Table via Satisfying-Pairs Algorithms


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing
Lower Bounds Learning and Average-Case Complexity
Emanuele Viola