All reports by Author Partha Mukhopadhyay:

__
TR20-191
| 27th December 2020
__

Arkadev Chattopadhyay, Rajit Datta, Partha Mukhopadhyay#### Negations Provide Strongly Exponential Savings

__
TR20-166
| 9th November 2020
__

Arkadev Chattopadhyay, Rajit Datta, Partha Mukhopadhyay#### Lower Bounds for Monotone Arithmetic Circuits Via Communication Complexity

Revisions: 1

__
TR19-063
| 28th April 2019
__

Vikraman Arvind, Abhranil Chatterjee, Rajit Datta, Partha Mukhopadhyay#### Efficient Black-Box Identity Testing for Free Group Algebra

__
TR16-089
| 2nd June 2016
__

Vikraman Arvind, Partha Mukhopadhyay, Raja S#### Randomized Polynomial Time Identity Testing for Noncommutative Circuits

Revisions: 2

__
TR15-052
| 6th April 2015
__

Partha Mukhopadhyay#### Depth-4 Identity Testing and Noether's Normalization Lemma

Revisions: 1

Arkadev Chattopadhyay, Rajit Datta, Partha Mukhopadhyay

We show that there is a family of monotone multilinear polynomials over $n$ variables in VP, such that any monotone arithmetic circuit for it would be of size $2^{\Omega(n)}$. Before our result, strongly exponential lower bounds on the size of monotone circuits were known only for computing explicit polynomials in ... more >>>

Arkadev Chattopadhyay, Rajit Datta, Partha Mukhopadhyay

Valiant (1980) showed that general arithmetic circuits with negation can be exponentially more powerful than monotone ones. We give the first qualitative improvement to this classical result: we construct a family of polynomials $P_n$ in $n$ variables, each of its monomials has positive coefficient, such that $P_n$ can be computed ... more >>>

Vikraman Arvind, Abhranil Chatterjee, Rajit Datta, Partha Mukhopadhyay

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 the question of rational identity testing. It is now known

that the problem can be solved in deterministic polynomial time in

more >>>

Vikraman Arvind, Partha Mukhopadhyay, Raja S

In this paper we show that polynomial identity testing for

noncommutative circuits of size $s$, computing a polynomial in

$\mathbb{F}\langle z_1,z_2,\cdots,z_n \rangle$, can be done by a randomized algorithm

with running time polynomial in $s$ and $n$. This answers a question

that has been open for over ten years.

The ... more >>>

Partha Mukhopadhyay

We consider the \emph{black-box} polynomial identity testing problem for a sub-class of

depth-4 circuits. Such circuits compute polynomials of the following type:

$

C(x) = \sum_{i=1}^k \prod_{j=1}^{d_i} Q_{i,j},

$

where $k$ is the fan-in of the top $\Sigma$ gate and $r$ is the maximum degree of the ...
more >>>