Vikraman Arvind

activity

20182024

collaborators

4 papers

cs.CC2024

Trading Determinism for Noncommutativity in Edmonds' Problem

V. Arvind, Abhranil Chatterjee, Partha Mukhopadhyay

Let $X = X_{1} ⊔ X_{2} ⊔ \dots ⊔ X_{k}$ be a partitioned set of variables such that the variables in each part $X_{i}$ are noncommuting but for any $i \neq = j$ , 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…

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 $Ω (n^{ω /2 + ε})$ size noncommutative arithmetic circuit size lower bound (where $ω$ is the matrix mult…

cs.DS2018

Fast Exact Algorithms Using Hadamard Product of Polynomials

V. Arvind, Abhranil Chatterjee, Rajit Datta +1

Let $C$ be an arithmetic circuit of $p o l y (n)$ size given as input that computes a polynomial $f \in F [X]$ , where $X = {x_{1}, x_{2}, \dots, x_{n}}$ and $F$ is any field whe…