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 $\mathrm{PostBPE}^{\widetilde{A_1}}$ has linear-size $A_1$-oracle circuits on infinitely many input lengths. That is, proving $\mathrm{PostBPE}\not\subseteq \text{i.o.-}\mathrm{SIZE}[O(n)]$ requires non-algebrizing techniques. This barrier follows from a $\mathrm{PostBPP}$ communication lower bound for XOR-Missing-String. This is in contrast to the well-known algebrizing lower bound $\mathrm{MA_E}$ $(\subseteq \mathrm{PostBPE}) \not\subseteq \mathrm{P/_{poly}}$.

2. We construct an oracle $A_2$ and its multilinear extension $\widetilde{A_2}$ such that $\mathrm{BPE}^{\widetilde{A_2}}$ has linear-size $A_2$-oracle circuits on all input lengths. Previously, a similar barrier was demonstrated by Aaronson and Wigderson, but in their result, $\widetilde{A_2}$ is only a *multiquadratic* extension of $A_2$. 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 $\mathrm{MA_E}$. Buhrman, Fortnow, and Thierauf proved a *sub-half-exponential* circuit lower bound for $\mathrm{MA_E}$ via algebrizing techniques. Toward understanding whether the half-exponential bound can be improved, we define a natural subclass of $\mathrm{MA_E}$ that includes their hard $\mathrm{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 $\mathrm{MA}_\mathrm{E}^{\widetilde{A_3}}$ has $h(n)$-size $A_3$-oracle circuits on all input lengths. This suggests that half-exponential might be the correct barrier for $\mathrm{MA_E}$ circuit lower bounds w.r.t. algebrizing techniques.