Query, Communication and Discrepancy
summary
Shows a concrete k-fold correlation problem that yields a constant vs almost linear separation between quantum and randomized query complexity (previous best was constant vs n^{2/3}), proved using discrepancy/optimization ideas that quantify dense versus sparse polynomial behavior. Proves unconditional lower bounds for approximate linear/semidefinite formulations of the matching polytope, showing one needs an exponentially large family of inequalities — matching a simple upper bound — so the construction and bounds are tight.
AI-written summary · about
chapters (7)
- 0:00Intro
- 0:12My Work
- 0:52Communication Complexity
- 2:11Query Complexity
- 3:59Quantum vs Classical Query Algorithms
- 6:01Size of Linear Programs
- 9:24Looking Forward
related talks
19mDeterministic Dynamic Matching In Worst-Case Update Time
01h 07mComputational Complexity of Polynomial Time Problems: Introduction
29mEquality, Revisited
01h 20mAn Introduction to Distributed, Massively Parallel, and Local Computation Algorithms
01h 02mConditional Hardness for Massively Parallel Computing (MPC) Via Distributed Lower Bounds
39mSketching and Randomization for Distributed Submodular and Coverage Optimization
27mOn Distributed Differential Privacy and Counting Distinct Elements
26mCounting Distinct Elements in the Message Passing Model