Abhranil Chatterjee

collaborators

Showing cs.CCShow all

5 papers · 1 filter

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

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.CC2023

Determinants vs. Algebraic Branching Programs

Abhranil Chatterjee, Mrinal Kumar, Ben Lee Volk

We show that for every homogeneous polynomial of degree $d$ , if it has determinantal complexity at most $s$ , then it can be computed by a homogeneous algebraic branching program (A…

cs.CC2023

The Noncommutative Edmonds' Problem Re-visited

Abhranil Chatterjee, Partha Mukhopadhyay

Let $T$ be a matrix whose entries are linear forms over the noncommutative variables $x_{1}, x_{2}, \dots, x_{n}$ . The noncommutative Edmonds' problem (NSINGULAR) aims to determine whet…

cs.CC2023

Border Complexity of Symbolic Determinant under Rank One Restriction

Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar +1

VBP is the class of polynomial families that can be computed by the determinant of a symbolic matrix of the form $A_{0} + \sum_{i = 1}^{n} A_{i} x_{i}$ where the size of each $A_{i}$ is polynom…