On the Average-case Complexity of the Nearest Boolean Vector to a Subspace
summary
Most n-dimensional subspaces of R^m are Ω(√m)-far from {-1,1}^m and there is a non-deterministic interactive algorithm that certifies a random subspace is >γ√m-far when m >> n log n and γ << 1/(m n^{1.5}), obtained by adapting Ajtai–Dwork; this yields average-case SZK interactive certificates beating spectral bounds relevant to the Sherrington–Kirkpatrick optimization while sum-of-squares fails for much smaller m (m << n^{1.5}).
AI-written summary · about
chapters (11)
- 0:00Introduction
- 4:12What is Complexity Theory
- 7:54Nearest Boolean Vector Problem
- 13:20Errorless Heuristics
- 17:34How We Came
- 18:10Proof
- 22:00Technical Claim
- 24:31Linearization
- 28:12Parallel Pipette
- 29:43Singular Value
- 34:36Open Problems
related talks
01h 05mNearest Neighbor Methods I
01h 02mTheory and Big Data
38mRed Points and Blue Points
44mConcentration Inequalites in Learning with Kernels
01h 30mAnalytic Methods for Supervised Learning IV
01h 01mNearest Neighbor Methods II
32mRandomized Numerical Linear Algebra: Overview
01h 27mPast, Present and Future of Randomized Numerical Linear Algebra I