3 papers
quant-ph2026
Robust subspace designs and the power of a unique small quantum witness
Simon Apers, Roman Edenhofer, Benjamin Mathieu-Bloise +1
The concept of subspace designs was introduced by Guruswami and Xing (STOC'13), and explicit constructions were given by Guruswami and Kopparty (FOCS'13). These are families of sub…
cs.CC2024
Trading Determinism for Noncommutativity in Edmonds' Problem
V. Arvind, Abhranil Chatterjee, Partha Mukhopadhyay
Let be a partitioned set of variables such that the variables in each part are noncommuting but for any , the variables $x\in…
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…