Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-173 | 10th September 2026 11:59

Matrix identities are hard: Fast blackbox PIT for noncommutative exponential-size constant-depth homogeneous circuits

RSS-Feed

Abstract:

In this work we give a randomized blackbox polynomial identity testing (PIT) algorithm for constant-depth homogeneous noncommutative circuits, with poly-logarithmic time complexity in the circuit size. In fact, we show that the polynomial computable by such a depth-$(\Delta-1)$ circuit of size $s$ cannot be a polynomial identity for the $O(\log ^{\Delta}s)$-dimension matrix algebra $\mathcal{M}_{O(\log ^{\Delta}s)}(\mathbb{F})$, for a sufficiently large field $\mathbb{F}$.

This represents progress toward answering the question raised by Arvind, Joglekar, Mukhopadhyay, and Raja (2019), and Bogdanov and Wee (2005) to find efficient randomized blackbox PIT algorithm for circuits that output polynomials with $doubly$ exponential sparsity. Arvind, Joglekar, Mukhopadhyay, and Raja (2019) and Bharadwaj and S. Raja (2025) defined constant-depth $+$-regular circuit and gave a PIT for it. Their model of size $S$ is simulated by our model of size $\exp(S)$; hence, we recover their result. Because of the regularity condition their model is highly restrictive than ours.

We decompose a depth-$\Delta$ formula into its constituent depth-$(\Delta - 1)$ subformulas and analyze them concurrently using Hadamard algebra, subsequently translating these findings back to the depth-$\Delta$ setting. We reduce the multivariate case to the bivariate case involving the noncommuting variables $x$ and $y$. Finally, we apply a transformation to $x$ and $y$ to ensure that the nonzero witness coefficient is associated with a monomial of exponentially-lower $y$-degree. We call this the phenomenon of $noncommutative\ low-degree\ concentration$.



ISSN 1433-8092 | Imprint