The Hardest Halfspace

on YouTube ↗01h 05m

" summary

Constructs an explicit hardest halfspace on {0,1}^{2n} whose degree-D polynomial (and rational) pointwise approximation error stays 1 − 2^{-Ω(n/D)}, matching prior nonconstructive bounds; proves also rational lower bound with exponent Θ(n/D) and that the intersection of two such halfspaces needs polynomial sign degree Ω(n). Key tools: build a small aperiodic integer set with tiny modular Fourier discrepancy, show the induced random walk mod M is nearly uniform, use a Gershgorin perturbation to equalize conditional expectations, and reduce any multivariate approximant to a univariate sine lower bound.

AI-written summary · about

" chapters (21)

1. 0:00Intro
2. 0:24Approximation by polynomials
3. 1:11Motivation
4. 2:50Our problem
5. 6:10Main result
6. 14:17UPP versus PP
7. 16:56The problem
8. 17:47Restricted distributions
9. 18:04Large margin
10. 18:27What about general case?
11. 19:57The polynomial method
12. 20:40Intersection of two halfspaces
13. 28:17Proof strategy
14. 33:29Discrepancy defined
15. 35:22Discrepancy pictorially
16. 37:21A nonconstructive bound
17. 38:15Explicit construction
18. 41:29A random walk on Zm
19. 46:09Fooling distributions
20. 52:40Univariatization
21. 59:58Summary