Showing 2023Show all
2 papers · 1 filter
cs.CC2023
Black-Box Identity Testing of Noncommutative Rational Formulas in Deterministic Quasipolynomial Time
V. Arvind, Abhranil Chatterjee, Partha Mukhopadhyay
Rational Identity Testing (RIT) is the decision problem of determining whether or not a noncommutative rational formula computes zero in the free skew field. It admits a determinis…
cs.CC2023
On Lifting Lower Bounds for Noncommutative Circuits using Automata
V. Arvind, Abhranil Chatterjee
We revisit the main result of Carmosino et al \cite{CILM18} which shows that an size noncommutative arithmetic circuit size lower bound (where is the matrix mult…