Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Partha Mukhopadhyay:

TR22-071 | 13th May 2022
Arkadev Chattopadhyay, Utsab Ghosal, Partha Mukhopadhyay

Robustly Separating the Arithmetic Monotone Hierarchy Via Graph Inner-Product

We establish an $\epsilon$-sensitive hierarchy separation for monotone arithmetic computations. The notion of $\epsilon$-sensitive monotone lower bounds was recently introduced by Hrubes [Computational Complexity'20]. We show the following:

(1) There exists a monotone polynomial over $n$ variables in VNP that cannot be computed by $2^{o(n)}$ size monotone ... more >>>

TR22-067 | 4th May 2022
Vikraman Arvind, Abhranil Chatterjee, Partha Mukhopadhyay

Black-box Identity Testing of Noncommutative Rational Formulas of Inversion Height Two in Deterministic Quasipolynomial-time

Hrube\v{s} and Wigderson (2015) initiated the complexity-theoretic study of noncommutative formulas with inverse gates. They introduced the Rational Identity Testing (RIT) problem which is to decide whether a noncommutative rational formula computes zero in the free skew field. In the white-box setting, deterministic polynomial-time algorithms are known for this problem ... more >>>

TR20-191 | 27th December 2020
Arkadev Chattopadhyay, Rajit Datta, Partha Mukhopadhyay

Negations Provide Strongly Exponential Savings

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

TR20-166 | 9th November 2020
Arkadev Chattopadhyay, Rajit Datta, Partha Mukhopadhyay

Lower Bounds for Monotone Arithmetic Circuits Via Communication Complexity

Revisions: 1

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

TR19-063 | 28th April 2019
Vikraman Arvind, Abhranil Chatterjee, Rajit Datta, Partha Mukhopadhyay

Efficient Black-Box Identity Testing for Free Group Algebra

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

TR16-089 | 2nd June 2016
Vikraman Arvind, Partha Mukhopadhyay, Raja S

Randomized Polynomial Time Identity Testing for Noncommutative Circuits

Revisions: 2

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

TR15-052 | 6th April 2015
Partha Mukhopadhyay

Depth-4 Identity Testing and Noether's Normalization Lemma

Revisions: 1

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

ISSN 1433-8092 | Imprint