137 citations · 354 across the 43 of their papers we have counts for
16 papers · 1 filter
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…
On Explicit Branching Programs for the Rectangular Determinant and Permanent Polynomials
V. Arvind, Abhranil Chatterjee, Rajit Datta +1
We study the arithmetic circuit complexity of some well-known family of polynomials through the lens of parameterized complexity. Our main focus is on the construction of explicit…
Efficient Black-Box Identity Testing over Free Group Algebra
V. Arvind, Abhranil Chatterjee, Rajit Datta +1
Hrubeš and Wigderson [HW14] initiated the study of noncommutative arithmetic circuits with division computing a noncommutative rational function in the free skew field, and raised…
A Note on Polynomial Identity Testing for Depth-3 Circuits
V. Arvind, Abhranil Chatterjee, Rajit Datta +1
Let be a depth-3 arithmetic circuit of size at most , computing a polynomial (where = or ) and th…
Efficient Identity Testing and Polynomial Factorization over Non-associative Free Rings
V. Arvind, Rajit Datta, Partha Mukhopadhyay +1
In this paper we study arithmetic computations in the nonassociative, and noncommutative free polynomial ring . Prior to this work, nonassociative…
Identity Testing for +-Regular Noncommutative Arithmetic Circuits
Vikraman Arvind, Pushkar Joglekar, Partha Mukhopadhyay +1
An efficient randomized polynomial identity test for noncommutative polynomials given by noncommutative arithmetic circuits remains an open problem. The main bottleneck to applying…
Randomized Polynomial Time Identity Testing for Noncommutative Circuits
V. Arvind, Partha Mukhopadhyay, S. Raja
In this paper we show that the black-box polynomial identity testing for noncommutative polynomials of degree and sparsity $t…
On the Limits of Depth Reduction at Depth 3 Over Small Finite Fields
Suryajith Chillara, Partha Mukhopadhyay
Recently, Gupta et.al. [GKKS2013] proved that over Q any -variate and -degree polynomial in VP can also be computed by a depth three circuit of size $2^{O(\sqrt{…
Depth-4 Lower Bounds, Determinantal Complexity : A Unified Approach
Suryajith Chillara, Partha Mukhopadhyay
Tavenas has recently proved that any n^{O(1)}-variate and degree n polynomial in VP can be computed by a depth-4 circuit of size 2^{O(\sqrt{n}\log n)}. So to prove VP not equal to…
Near-Optimal Expanding Generating Sets for Solvable Permutation Groups
V. Arvind, Partha Mukhopadhyay, Prajakta Nimbhorkar +1
Let be a solvable permutation group of the symmetric group given as input by the generating set . We give a deterministic polynomial-time algorithm that computes…
Quantum Query Complexity of Multilinear Identity Testing
V. Arvind, Partha Mukhopadhyay
Motivated by the quantum algorithm in \cite{MN05} for testing commutativity of black-box groups, we study the following problem: Given a black-box finite ring $R=\angle{r_1,...,r_k…
Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size
V. Arvind, Partha Mukhopadhyay
The isolation lemma of Mulmuley et al \cite{MVV87} is an important tool in the design of randomized algorithms and has played an important role in several nontrivial complexity upp…
New results on Noncommutative and Commutative Polynomial Identity Testing
V. Arvind, Partha Mukhopadhyay, Srikanth Srinivasan
Using ideas from automata theory we design a new efficient (deterministic) identity test for the \emph{noncommutative} polynomial identity testing problem (first introduced and stu…