New Algebrization Barriers to Circuit Lower Bounds via Communication Complexity of Missing-String

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₁, …, xₘ ∈ 0, 1ⁿ, Bob gets a list of m strings y₁, …, yₘ ∈ 0, 1ⁿ, and the goal is to output a string s ∈ 0, 1ⁿ that is not equal to xᵢ⊕ yⱼ for any i, j ∈ m. 1) We construct an oracle A₁ and its multilinear extension A₁̃ such that PostBPE^A₁̃ has linear-size A₁-oracle circuits on infinitely many input lengths. That is, proving PostBPE ̸ ⊆ i. o. - SIZEO (n) requires non-algebrizing techniques. This barrier follows from a PostBPP communication lower bound for XOR-Missing-String. This is in contrast to the well-known algebrizing lower bound MAE (⊆ PostBPE) ̸ ⊆ P/ₚoly. 2) We construct an oracle A₂ and its multilinear extension A₂̃ such that BPE^A₂̃ has linear-size A₂-oracle circuits on all input lengths. Previously, a similar barrier was demonstrated by Aaronson and Wigderson, but in their result, A₂̃ is only a multiquadratic extension of A₂. Our results show that communication complexity is more useful than previously thought for proving algebrization barriers, as Aaronson and Wigderson wrote that communication-based barriers were "more contrived". This serves as an example of how XOR-Missing-String forms new connections between communication lower bounds and algebrization barriers. 3) Finally, we study algebrization barriers to circuit lower bounds for MAE. Buhrman, Fortnow, and Thierauf proved a sub-half-exponential circuit lower bound for MAE via algebrizing techniques. Toward understanding whether the half-exponential bound can be improved, we define a natural subclass of MAE that includes their hard MAE language, and prove the following result: For every super-half-exponential function h (n), we construct an oracle A₃ and its multilinear extension A₃̃ such that this natural subclass of MAE^A₃̃ has h (n) -size A₃-oracle circuits on all input lengths. This suggests that half-exponential might be the correct barrier for MAE circuit lower bounds w. r. t. algebrizing techniques.