1 citations · 1 across the 10 of their papers we have counts for
6 papers · 1 filter
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…
Recursive Error Reduction for Regular Branching Programs
Eshan Chattopadhyay, Jyun-Jie Liao
In a recent work, Chen, Hoza, Lyu, Tal and Wu (FOCS 2023) showed an improved error reduction framework for the derandomization of regular read-once branching programs (ROBPs). Thei…
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…
Determinants vs. Algebraic Branching Programs
Abhranil Chatterjee, Mrinal Kumar, Ben Lee Volk
We show that for every homogeneous polynomial of degree , if it has determinantal complexity at most , then it can be computed by a homogeneous algebraic branching program (A…
The Noncommutative Edmonds' Problem Re-visited
Abhranil Chatterjee, Partha Mukhopadhyay
Let be a matrix whose entries are linear forms over the noncommutative variables . The noncommutative Edmonds' problem (NSINGULAR) aims to determine whet…
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 where the size of each is polynom…