All reports by Author Partha Mukhopadhyay:

__
TR20-166
| 9th November 2020
__

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

__
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

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