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:

TR23-147 | 27th September 2023
Vikraman Arvind, Abhranil Chatterjee, Partha Mukhopadhyay

Black-Box Identity Testing of Noncommutative Rational Formulas in Deterministic Quasipolynomial Time

Revisions: 1

Rational Identity Testing (RIT) is the decision problem of determining whether or not a given noncommutative rational formula computes zero in the free skew field. It admits a deterministic polynomial-time white-box algorithm [Garg et al., 2016; Ivanyos et al., 2018; Hamada and Hirai, 2021], and a randomized polynomial-time black-box algorithm ... more >>>

TR18-111 | 4th June 2018
Vikraman Arvind, Abhranil Chatterjee, Rajit Datta, Partha Mukhopadhyay

Beating Brute Force for Polynomial Identity Testing of General Depth-3 Circuits

Comments: 1

Let $C$ be a depth-3 $\Sigma\Pi\Sigma$ arithmetic circuit of size $s$,
computing a polynomial $f \in \mathbb{F}[x_1,\ldots, x_n]$ (where $\mathbb{F}$ = $\mathbb{Q}$ or
$\mathbb{C}$) with fan-in of product gates bounded by $d$. We give a
deterministic time $2^d \text{poly}(n,s)$ polynomial identity testing
algorithm to check whether $f \equiv 0$ or ... more >>>

TR17-074 | 29th April 2017
Vikraman Arvind, Rajit Datta, Partha Mukhopadhyay, Raja S

Efficient Identity Testing and Polynomial Factorization over Non-associative Free Rings

Revisions: 1

In this paper we study arithmetic computations over non-associative, and non-commutative free polynomials ring $\mathbb{F}\{x_1,x_2,\ldots,x_n\}$. Prior to this work, the non-associative arithmetic model of computation was considered by Hrubes, Wigderson, and Yehudayoff [HWY10]. They were interested in completeness and explicit lower bound results.

We focus on two main problems ... more >>>

TR16-193 | 22nd November 2016
Vikraman Arvind, Pushkar Joglekar, Partha Mukhopadhyay, Raja S

Identity Testing for +-Regular Noncommutative Arithmetic Circuits

An efficient randomized polynomial identity test for noncommutative
polynomials given by noncommutative arithmetic circuits remains an
open problem. The main bottleneck to applying known techniques is that
a noncommutative circuit of size $s$ can compute a polynomial of
degree exponential in $s$ with a double-exponential number of nonzero
monomials. ... more >>>

TR11-140 | 31st October 2011
Vikraman Arvind, Partha Mukhopadhyay, Prajakta Nimbhorkar, Yadu Vasudev

Expanding Generator Sets for Solvable Permutation Groups

Revisions: 1

Let $G=\langle S\rangle$ be a solvable permutation group given as input by generating set $S$. I.e.\ $G$ is a solvable subgroup of the symmetric group $S_n$. We give a deterministic polynomial-time algorithm that computes an expanding generator set for $G$. More precisely, given a constant $\lambda <1$ we can compute ... more >>>

TR11-081 | 15th May 2011
Vikraman Arvind, Partha Mukhopadhyay, Prajakta Nimbhorkar

Erdos-Renyi Sequences and Deterministic construction of Expanding Cayley Graphs

Given a finite group $G$ by its multiplication table as input, we give a deterministic polynomial-time construction of a directed Cayley graph on $G$ with $O(\log |G|)$ generators, which has a rapid mixing property and a constant spectral expansion.\\

We prove a similar result in the undirected case, and ... more >>>

TR10-033 | 6th March 2010
Shachar Lovett, Partha Mukhopadhyay, Amir Shpilka

Pseudorandom generators for $\mathrm{CC}_0[p]$ and the Fourier spectrum of low-degree polynomials over finite fields

In this paper we give the first construction of a pseudorandom generator, with seed length $O(\log n)$, for $\mathrm{CC}_0[p]$, the class of constant-depth circuits with unbounded fan-in $\mathrm{MOD}_p$ gates, for some prime $p$. More accurately, the seed length of our generator is $O(\log n)$ for any constant error $\epsilon>0$. In ... more >>>

TR09-116 | 15th November 2009
Zohar Karnin, Partha Mukhopadhyay, Amir Shpilka, Ilya Volkovich

Deterministic identity testing of depth 4 multilinear circuits with bounded top fan-in

We give the first sub-exponential time deterministic polynomial
identity testing algorithm for depth-$4$ multilinear circuits with
a small top fan-in. More accurately, our algorithm works for
depth-$4$ circuits with a plus gate at the top (also known as
$\Spsp$ circuits) and has a running time of
$\exp(\poly(\log(n),\log(s),k))$ where $n$ is ... more >>>

TR08-086 | 9th July 2008
Vikraman Arvind, Partha Mukhopadhyay

Quantum Query Complexity of Multilinear Identity Testing

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,\cdots,r_k}$ where
$\{r_1,r_2,\cdots,r_k\}$ is an additive generating set for $R$ and a
multilinear polynomial $f(x_1,\cdots,x_m)$ over $R$ also accessed as
a ... more >>>

TR08-049 | 10th April 2008
Vikraman Arvind, Partha Mukhopadhyay

Derandomizing the Isolation Lemma and Lower Bounds for Noncommutative Circuit Size

Revisions: 3

We give a randomized polynomial-time identity test for
noncommutative circuits of polynomial degree based on the isolation
lemma. Using this result, we show that derandomizing the isolation
lemma implies noncommutative circuit size lower bounds. More
precisely, we consider two restricted versions of the isolation
lemma and show that derandomizing each ... more >>>

TR08-025 | 3rd January 2008
Vikraman Arvind, Partha Mukhopadhyay, Srikanth Srinivasan

New results on Noncommutative and Commutative Polynomial Identity Testing

Revisions: 2

Using ideas from automata theory we design a new efficient
(deterministic) identity test for the \emph{noncommutative}
polynomial identity testing problem (first introduced and studied by
Raz-Shpilka in 2005 and Bogdanov-Wee in 2005). More precisely,
given as input a noncommutative
circuit $C(x_1,\cdots,x_n)$ computing a ... more >>>

TR07-095 | 13th July 2007
Vikraman Arvind, Partha Mukhopadhyay

The Ideal Membership Problem and Polynomial Identity Testing

Revisions: 2

Given a monomial ideal $I=\angle{m_1,m_2,\cdots,m_k}$ where $m_i$
are monomials and a polynomial $f$ as an arithmetic circuit the
\emph{Ideal Membership Problem } is to test if $f\in I$. We study
this problem and show the following results.
\item[(a)] If the ideal $I=\angle{m_1,m_2,\cdots,m_k}$ for a
more >>>

ISSN 1433-8092 | Imprint