{"id":"arxiv/2610.37677","url":"https://arxiv.org/abs/2610.37677","tags":["math.RA","cs.CC","math.CO"],"score":0,"title":"Explicit matrix hitting points for noncommutative algebraic branching programs","domain":"math.RA","source":"arxiv","authors":["Zhipeng Lu"],"reviews":0,"subject":"math.RA","summary":"We give a deterministic polynomial-resource black-box identity test for noncommutative algebraic branching programs (ABPs), using ordinary matrix evaluations of the output polynomial. Given an alphabet of size $m\\ge1$ and an ABP vertex bound $S\\ge1$, we construct one fixed tuple of integer matrices of order $R=(m+2)d(d+1)/2$, where $d=(m+2)S$, with entry bit length $O(d\\log(d+1))$. Every nonzero polynomial computed by an ABP with at most $S$ vertices has a nonzero evaluation at this tuple. The construction accesses neither the hidden ABP nor its intermediate gates. A rectangular variant…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-11","reactions":{}}