Guo and Wang gave a deterministic polynomial-time black-box identity test for $\Sigma^{[3]}\Pi\Sigma\Pi^{[\delta]}$ circuits over fields of arbitrary characteristic, for constant $\delta$, assuming that one product gate is squarefree. This note communicates an observation suggested by a large language model: the squarefreeness assumption can be removed by combining the normalization argument ... more >>>

Kane and Williams proved average-case wire lower bounds at the $n^{5/2}/\mathrm{polylog}, n$ scale for an explicit function against depth-two linear-threshold circuits. We prove an almost-everywhere near-cubic wire lower bound for a language in $\mathrm{E}^{\mathrm{NP}}$. For every fixed $c>0$, there is one language $F_c$ and positive constants $b_{S,c}$ and $b_{T,c}$ such ... more >>>

Grochow and Pitassi (2018) introduced the algebraic proof system, the Ideal Proof System (IPS), which connects algebraic circuit complexity to propositional proof complexity. They showed that propositional proof systems such as Extended Frege (Frege) are equivalent to circuit IPS (formula IPS) if the correctness of PIT for circuits (formulas) can ... more >>>