Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > NONCOMMUTATIVE RATIONAL CIRCUITS:
Reports tagged with noncommutative rational circuits:
TR26-274 | 29th September 2026
Vikraman Arvind, Pushkar Joglekar

Rational Identity Testing for Noncommutative Circuits is in Polynomial Space

The rational identity testing problem, RIT, asks whether an input \emph{rational circuit}, i.e.\ a noncommutative arithmetic circuit that has inversion gates, computes the zero element of the free skew field. For rational \emph{formulas} the problem is known to be in deterministic polynomial time \cite{GGOW20}, \cite{IQS18}. For rational circuits of ... more >>>




ISSN 1433-8092 | Imprint