An Algebraic Rigidity Framework for Order-Oblivious Deterministic Black-Box PIT of ROABPs
Deterministic black-box polynomial identity testing (PIT) for read-once oblivious algebraic branching programs (ROABPs) is a central open problem in algebraic complexity, particularly in the absence of variable ordering. Prior deterministic algorithms either rely on order information or incur significant overhead through combinatorial isolation techniques. In this paper, we introduce an algebraic rigidity framework for ROABPs based on the internal structure of their associated matrix word algebras. We show that nonzero width-$w$ ROABPs induce word algebras whose effective algebraic degrees…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2602.13449
curl -X POST /api/v1/records/arxiv/2602.13449/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2602.13449/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'