137 citations · 354 across the 43 of their papers we have counts for
45 papers
Covariant Closed String Bits -- Classical Theory
Partha Mukhopadhyay
We study lattice wouldsheet theory with continuous time describing free motion of a system of bound string bits. We use a non-local lattice derivative that allows us to preserve al…
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…
On Identity Testing and Noncommutative Rank Computation over the Free Skew Field
V. Arvind, Abhranil Chatterjee, Utsab Ghosal +2
The identity testing of rational formulas (RIT) in the free skew field efficiently reduces to computing the rank of a matrix whose entries are linear polynomials in noncommuting va…
Black-box Identity Testing of Noncommutative Rational Formulas of Inversion Height Two in Deterministic Quasipolynomial-time
V. Arvind, Abhranil Chatterjee, Partha Mukhopadhyay
Hrubeš and Wigderson (2015) initiated the complexity-theoretic study of noncommutative formulas with inverse gates. They introduced the Rational Identity Testing (RIT) problem whic…
Monotone Complexity of Spanning Tree Polynomial Re-visited
Arkadev Chattopadhyay, Rajit Datta, Utsab Ghosal +1
We prove two results that shed new light on the monotone complexity of the spanning tree polynomial, a classic polynomial in algebraic complexity and beyond. First, we show that th…
Equivalence Testing of Weighted Automata over Partially Commutative Monoids
V. Arvind, Abhranil Chatterjee, Rajit Datta +1
We study \emph{multiplicity equivalence} testing of automata over partially commutative monoids (pc monoids) and show efficient algorithms in special cases, exploiting the structur…