Metraipolis › archive › dc_bc0677736bda
Explicit matrix hitting points for noncommutative algebraic branching programs — arXiv:2610.37677
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.37677
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-01T02:38:10.836Z
- SHA-256 of the archived text
170ab3e7a8f47c152d71f80d77520879d9c54d25e87b3c2a905bc14192d40849- Stable URL of this page
https://metraipolis.com/documento/dc_bc0677736bda
How to cite
Explicit matrix hitting points for noncommutative algebraic branching programs — arXiv:2610.37677 — arXiv (en), https://arxiv.org/abs/2610.37677 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_bc0677736bda (Metraipolis archive dc_bc0677736bda, sha256 170ab3e7a8f47c152d71f80d77520879d9c54d25e87b3c2a905bc14192d40849)
BibTeX
@misc{dcbc0677736bda,
title = {Explicit matrix hitting points for noncommutative algebraic branching programs — arXiv:2610.37677},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.37677},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_bc0677736bda; sha256 170ab3e7a8f47c152d71f80d77520879d9c54d25e87b3c2a905bc14192d40849},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.37677. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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 improves the order to $O(m^{3/2}S^2)$. Matrix order, description length, and all returned entries are counted; the total resources are polynomial. The result holds in characteristic zero and in characteristic $p>\binom d2$. The main ingredient is a fixed polynomial frame spanning the joint cyclic module of every matrix tuple from every prescribed vector. A compensating block makes a tagged encoding nilpotent of index at most three, while preserving the original cyclic module. A differential exterior-vector argument then gives a single triangular recurrence with polynomially many outputs. Its shared left-linear circuit is converted into actual integer query matrices by coefficient duality. Two-sided pairing further gives deterministic nonadaptive reconstruction of an equivalent ABP from polynomially many output-only matrix queries. The same frame gives polynomial-cardinality explicit trace separators for simultaneous-conjugation orbit closures, and a fixed nilpotent substitution for bounded-dimensional recognizable series. The latter also tests rational formulas whose given syntax is defined at the scalar origin. We provide complete proofs, construction costs, and exact implementation checks.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno).
Categorie arXiv: Rings and Algebras (math.RA) ; Computational Complexity (cs.CC); Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2610.37677 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-01T02:15:28.301Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).