New Algebrization Barriers to Circuit Lower Bounds via Communication Complexity of Missing-String
Preprint
Abstract
The *algebrization barrier*, proposed by Aaronson and Wigderson (STOC '08, ToCT '09), captures the limitations of many complexity-theoretic techniques based on arithmetization. Notably, several circuit lower bounds that overcome the relativization barrier (Buhrman--Fortnow--Thierauf, CCC '98; Vinodchandran, TCS '05; Santhanam, STOC '07, SICOMP '09) remain subject to the algebrization barrier. In this work, we establish several new algebrization barriers to circuit lower bounds by studying the communication complexity of the following problem, called XOR-Missing-String: For $m < 2^{n/2}$, Alice gets a list of $m$ strings $x_1, \dots, x_m\in\{0, 1\}^n$, Bob gets a list of $m$ strings $y_1, \dots, y_m\in\{0, 1\}^n$, and the goal is to output a string $s\in\{0, 1\}^n$ that is not equal to $x_i\oplus y_j$ for any $i, j\in [m]$. 1. We construct an oracle $A_1$ and its multilinear extension $\widetilde{A_1}$ such that ${\sf PostBPE}^{\widetilde{A_1}}$ has linear-size $A_1$-oracle circuits on infinitely many input lengths. 2. We construct an oracle $A_2$ and its multilinear extension $\widetilde{A_2}$ such that ${\sf BPE}^{\widetilde{A_2}}$ has linear-size $A_2$-oracle circuits on all input lengths. 3. Finally, we study algebrization barriers to circuit lower bounds for $\sf MA_E$. Buhrman, Fortnow, and Thierauf proved a *sub-half-exponential* circuit lower bound for $\sf MA_E$ via algebrizing techniques. Toward understanding whether the half-exponential bound can be improved, we define a natural subclass of $\sf MA_E$ that includes their hard $\sf MA_E$ language, and prove the following result: For every *super-half-exponential* function $h(n)$, we construct an oracle $A_3$ and its multilinear extension $\widetilde{A_3}$ such that this natural subclass of ${\sf MA}_{\sf E}^{\widetilde{A_3}}$ has $h(n)$-size $A_3$-oracle circuits on all input lengths.
Keywords
All Related Versions
This publication has 37 references indexed in Scilit:
- The Landscape of Communication Complexity Classescomputational complexity, 2018
- Short PCPPs verifiable in polylogarithmic time with O(1) queriesAnnals of Mathematics and Artificial Intelligence, 2009
- Journal of Computer and System Sciences, 2006
- Competing provers yield improved Karp–Lipton collapse resultsInformation and Computation, 2005
- Super-Polynomial Versus Half-Exponential Circuit Size in the Exponential HierarchyLecture Notes in Computer Science, 1999
- Natural ProofsJournal of Computer and System Sciences, 1997
- Oracles and Queries That Are Sufficient for Exact LearningJournal of Computer and System Sciences, 1996
- BPP has subexponential time simulations unlessEXPTIME has publishable proofscomputational complexity, 1993
- Non-deterministic exponential time has two-prover interactive protocolscomputational complexity, 1991
- Relativized circuit complexityJournal of Computer and System Sciences, 1985