Block Rigidity: Strong Multiplayer Parallel Repetition implies Super-Linear Lower Bounds for Turing
summary
Claims that a strong multiplayer parallel-repetition theorem (conjectured decay Val(G^n) ≤ 2^{-Ω(KN)} for the independent K-player function game) yields explicit block-rigid functions (F^⊗N constructed by tensoring F column-wise) and hence super-linear lower bounds: any family FN with Ω(NK), Ω(K) block-rigidity is not computable in O(N) time by deterministic multi-tape Turing machines even with advice. Tools invoked include block-respecting TMs and the Paul–Pippenger–Szemerédi–Trotter graph combinatorics; matrix-transpose game is conjectured to have value 2^{-Ω(N^2)}.
AI-written summary · about
chapters (15)
- 0:00Block Rigidity introduction
- 1:31Turing machines lower bounds
- 2:59Multiplayer repetition basics
- 7:06Two vs multiplayer repetition
- 8:55Known results gaps
- 9:38Main conjecture parallel repetition
- 12:14What is matrix rigidity
- 14:07Rigidity definitions equivalence
- 15:10Rigidity for general functions
- 17:20Rigid matrices conjecture
- 17:42Introducing block rigidity
- 19:29Block rigidity lower bounds
- 20:12Tensored functions conjecture
- 21:16Implications open directions
- 22:17Matrix transpose future work
related talks
01h 37mMatrix Rigidity
27mSmall Value Parallel Repetition for General Games
28mCommunication Avoiding Algorithms for Linear Algebra and Beyond
35mSuperlinear Lower Bounds for Multipass Graph Processing
01h 02mConditional Hardness for Massively Parallel Computing (MPC) Via Distributed Lower Bounds
01h 07mComputational Complexity of Polynomial Time Problems: Introduction
30mA New Look at Gallager's Bounds
58mDichotomy Theorems for Counting Problems I