Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > NON-COMMUTATIVE:
Reports tagged with non-commutative:
TR12-115 | 11th September 2012
Michael Forbes, Amir Shpilka

#### Quasipolynomial-time Identity Testing of Non-Commutative and Read-Once Oblivious Algebraic Branching Programs

Revisions: 1

We study the problem of obtaining efficient, deterministic, black-box polynomial identity testing (PIT) algorithms for read-once oblivious algebraic branching programs (ABPs). This class has an efficient, deterministic, white-box polynomial identity testing algorithm (due to Raz and Shpilka), but prior to this work had no known such black-box algorithm. Here we ... more >>>

TR17-077 | 30th April 2017
Guillaume Lagarde, Nutan Limaye, Srikanth Srinivasan

#### Lower Bounds and PIT for Non-Commutative Arithmetic circuits with Restricted Parse Trees

We investigate the power of Non-commutative Arithmetic Circuits, which compute polynomials over the free non-commutative polynomial ring $\mathbb{F}\langle x_1,\dots,x_N \rangle$, where variables do not commute. We consider circuits that are restricted in the ways in which they can compute monomials: this can be seen as restricting the families of parse ... more >>>

ISSN 1433-8092 | Imprint