Strong Bounds for 3-Progressions

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


Duration: 1:04:48
504 views
12

Raghu Meka (UCLA)
https://simons.berkeley.edu/events/breakthroughs-strong-bounds-3-progressions
Breakthroughs

Abstract: Suppose you have a set S of integers from {1,2,…,N} that contains at least N/C elements. Then for large enough N, must S contain three equally spaced numbers (i.e., a 3-term arithmetic progression)?

In 1953, Roth showed that this is indeed the case when C≈(loglogN), while Behrend in 1946 showed that C can be at most 2Ω(logN√). Since then, the problem has been a cornerstone of the area of additive combinatorics. Following a series of remarkable results, a celebrated paper from 2020 due to Bloom and Sisask improved the lower bound on C to C=(logN)(1+c), for some constant c＞0.

This talk will describe a new work showing that the same holds when C≈2(logN)0.09, thus getting closer to Behrend’s construction.

Based on joint work with Zander Kelley.



Other Videos By Simons Institute for the Theory of Computing


2023-03-22Indistinguishability Obfuscation via Mathematical Proofs of Equivalence
2023-03-22Towards P≠NP from Extended Frege Lower Bounds
2023-03-22Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic
2023-03-22Unprovability of Strong Complexity Lower Bounds in Bounded Arithmetic
2023-03-21Consistency of NEXP Not in P/poly in a Strong Theory
2023-03-21Lifting to Parity Decision Trees via Stifling (with applications to proof complexity)
2023-03-21A Lower Bound for k-DNF Resolution on Random CNF Formulas via Expansion
2023-03-21The Hitting Proof System
2023-03-21Random log(n)-CNF are Hard for Cutting Planes (Again)
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


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing
Breakthroughs
Raghu Meka