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

__
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

__
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

__
TR16-193
| 22nd November 2016
__

Vikraman Arvind, Pushkar Joglekar, Partha Mukhopadhyay, Raja S#### Identity Testing for +-Regular Noncommutative Arithmetic Circuits

__
TR11-140
| 31st October 2011
__

Vikraman Arvind, Partha Mukhopadhyay, Prajakta Nimbhorkar, Yadu Vasudev#### Expanding Generator Sets for Solvable Permutation Groups

Revisions: 1

__
TR11-081
| 15th May 2011
__

Vikraman Arvind, Partha Mukhopadhyay, Prajakta Nimbhorkar#### Erdos-Renyi Sequences and Deterministic construction of Expanding Cayley Graphs

__
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

__
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

__
TR08-086
| 9th July 2008
__

Vikraman Arvind, Partha Mukhopadhyay#### Quantum Query Complexity of Multilinear Identity Testing

__
TR08-049
| 10th April 2008
__

Vikraman Arvind, Partha Mukhopadhyay#### Derandomizing the Isolation Lemma and Lower Bounds for Noncommutative Circuit Size

Revisions: 3

__
TR08-025
| 3rd January 2008
__

Vikraman Arvind, Partha Mukhopadhyay, Srikanth Srinivasan#### New results on Noncommutative and Commutative Polynomial Identity Testing

Revisions: 2

__
TR07-095
| 13th July 2007
__

Vikraman Arvind, Partha Mukhopadhyay#### The Ideal Membership Problem and Polynomial Identity Testing

Revisions: 2

Vikraman Arvind, Abhranil Chatterjee, Partha Mukhopadhyay

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

Vikraman Arvind, Abhranil Chatterjee, Rajit Datta, Partha Mukhopadhyay

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

Vikraman Arvind, Rajit Datta, Partha Mukhopadhyay, Raja S

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

Vikraman Arvind, Pushkar Joglekar, Partha Mukhopadhyay, Raja S

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

Vikraman Arvind, Partha Mukhopadhyay, Prajakta Nimbhorkar, Yadu Vasudev

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

Vikraman Arvind, Partha Mukhopadhyay, Prajakta Nimbhorkar

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

Shachar Lovett, Partha Mukhopadhyay, Amir Shpilka

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

Zohar Karnin, Partha Mukhopadhyay, Amir Shpilka, Ilya Volkovich

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

Vikraman 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,\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 >>>

Vikraman Arvind, Partha Mukhopadhyay

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

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

Vikraman Arvind, Partha Mukhopadhyay

\begin{abstract}

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.

\begin{itemize}

\item[(a)] If the ideal $I=\angle{m_1,m_2,\cdots,m_k}$ for a

more >>>