Manindra Agrawal, Somenath Biswas

We give new randomized algorithms for testing multivariate polynomial

identities over finite fields and rationals. The algorithms use

\lceil \sum_{i=1}^n \log(d_i+1)\rceil (plus \lceil\log\log C\rceil

in case of rationals where C is the largest coefficient)

random bits to test if a

polynomial P(x_1, ..., x_n) is zero where d_i is ...
more >>>

Neeraj Kayal, Nitin Saxena

We study the identity testing problem for depth $3$ arithmetic circuits ($\Sigma\Pi\Sigma$ circuits). We give the first deterministic polynomial time identity test for $\Sigma\Pi\Sigma$ circuits with bounded top fanin. We also show that the {\em rank} of a minimal and simple $\Sigma\Pi\Sigma$ circuit with bounded top fanin, computing zero, can ... 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 >>>

Nitin Saxena

In this paper we give the first deterministic polynomial time algorithm for testing whether a {\em diagonal} depth-$3$ circuit $C(\arg{x}{n})$ (i.e. $C$ is a sum of powers of linear functions) is zero. We also prove an exponential lower bound showing that such a circuit will compute determinant or permanent only ... more >>>

Manindra Agrawal, V Vinay

We show that proving exponential lower bounds on depth four arithmetic

circuits imply exponential lower bounds for unrestricted depth arithmetic

circuits. In other words, for exponential sized circuits additional depth

beyond four does not help.

We then show that a complete black-box derandomization of Identity Testing problem for depth four ... more >>>

Vikraman Arvind, Pushkar Joglekar

Let $\F\{x_1,x_2,\cdots,x_n\}$ be the noncommutative polynomial

ring over a field $\F$, where the $x_i$'s are free noncommuting

formal variables. Given a finite automaton $\A$ with the $x_i$'s as

alphabet, we can define polynomials $\f( mod A)$ and $\f(div A)$

obtained by natural operations that we ...
more >>>

Nitin Saxena

Polynomial identity testing (PIT) is the problem of checking whether a given

arithmetic circuit is the zero circuit. PIT ranks as one of the most important

open problems in the intersection of algebra and computational complexity. In the last

few years, there has been an impressive progress on this ...
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 >>>

Amir Shpilka, Ilya Volkovich

An \emph{arithmetic read-once formula} (ROF for short) is a

formula (a circuit whose underlying graph is a tree) in which the

operations are $\{+,\times\}$ and such that every input variable

labels at most one leaf. A \emph{preprocessed ROF} (PROF for

short) is a ROF in which we are allowed to ...
more >>>

Chandan Saha, Ramprasad Saptharishi, Nitin Saxena

Finding an efficient solution to the general problem of polynomial identity testing (PIT) is a challenging task. In this work, we study the complexity of two special but natural cases of identity testing - first is a case of depth-$3$ PIT, the other of depth-$4$ PIT.

Our first problem is ... more >>>

Malte Beecken, Johannes Mittmann, Nitin Saxena

Algebraic independence is an advanced notion in commutative algebra that generalizes independence of linear polynomials to higher degree. Polynomials $\{f_1,\ldots, f_m\} \subset \mathbb{F}[x_1,\ldots, x_n]$ are called algebraically independent if there is no non-zero polynomial $F$ such that $F(f_1, \ldots, f_m) = 0$. The transcendence degree, $\mbox{trdeg}\{f_1,\ldots, f_m\}$, is the maximal ... more >>>

Shubhangi Saraf, Ilya Volkovich

We study the problem of identity testing for multilinear $\Spsp(k)$ circuits, i.e. multilinear depth-$4$ circuits with fan-in $k$ at the top $+$ gate. We give the first polynomial-time deterministic

identity testing algorithm for such circuits. Our results also hold in the black-box setting.

The running time of our algorithm is ... more >>>

Johannes Mittmann, Nitin Saxena, Peter Scheiblechner

A set of multivariate polynomials, over a field of zero or large characteristic, can be tested for algebraic independence by the well-known Jacobian criterion. For fields of other characteristic $p>0$, there is no analogous characterization known. In this paper we give the first such criterion. Essentially, it boils down to ... more >>>

Gregory Valiant, Paul Valiant

We consider the problem of verifying the identity of a distribution: Given the description of a distribution over a discrete support $p=(p_1,p_2,\ldots,p_n)$, how many samples (independent draws) must one obtain from an unknown distribution, $q$, to distinguish, with high probability, the case that $p=q$ from the case that the total ... more >>>

Nitin Saxena

We survey the area of algebraic complexity theory; with the focus being on the problem of polynomial identity testing (PIT). We discuss the key ideas that have gone into the results of the last few years.

more >>>Ankit Gupta

We present an algebraic-geometric approach for devising a deterministic polynomial time blackbox identity testing (PIT) algorithm for depth-4 circuits with bounded top fanin. Using our approach, we devise such an algorithm for the case when such circuits have bounded bottom fanin and satisfy a certain non-degeneracy condition. In particular, we ... 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 >>>

Daniel Minahan, Ilya Volkovich

In this paper we study the identity testing problem of \emph{arithmetic read-once formulas} (ROF) and some related models. A read-once formula is formula (a circuit whose underlying graph is a tree) in which the

operations are $\set{+,\times}$ and such that every input variable labels at most one leaf. We obtain ...
more >>>

Ilias Diakonikolas, Themis Gouleakis, John Peebles, Eric Price

We study the problem of testing identity against a given distribution (a.k.a. goodness-of-fit) with a focus on the high confidence regime. More precisely, given samples from an unknown distribution $p$ over $n$ elements, an explicitly given distribution $q$, and parameters $0< \epsilon, \delta < 1$, we wish to distinguish, {\em ... more >>>

Prerona Chatterjee, Ramprasad Saptharishi

We study the question of algebraic rank or transcendence degree preserving homomorphisms over finite fields. This concept was first introduced by Beecken, Mittmann and Saxena (Information and Computing, 2013), and exploited by them, and Agrawal, Saha, Saptharishi and Saxena (Journal of Computing, 2016) to design algebraic independence based identity tests ... 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 >>>

Pranav Bisht, Nitin Saxena

Blackbox polynomial identity testing (PIT) affords 'extreme variable-bootstrapping' (Agrawal et al, STOC'18; PNAS'19; Guo et al, FOCS'19). This motivates us to study log-variate read-once oblivious algebraic branching programs (ROABP). We restrict width of ROABP to a constant and study the more general sum-of-ROABPs model. We give the first poly($s$)-time blackbox ... more >>>

Clement Canonne, Karl Wimmer

Motivated by the question of data quantization and "binning," we revisit the problem of identity testing of discrete probability distributions. Identity testing (a.k.a. one-sample testing), a fundamental and by now well-understood problem in distribution testing, asks, given a reference distribution (model) $\mathbf{q}$ and samples from an unknown distribution $\mathbf{p}$, both ... more >>>

Pranav Bisht, Ilya Volkovich

In a recent result of Bhargava, Saraf and Volkovich [FOCS’18; JACM’20], the first sparsity bound for constant individual degree polynomials was shown. In particular, it was shown that any factor of a polynomial with at most $s$ terms and individual degree bounded by $d$ can itself have at most $s^{O(d^2\log ... more >>>

Pranav Bisht, Nikhil Gupta, Ilya Volkovich

An arithmetic formula is an arithmetic circuit where each gate has fan-out one. An \emph{arithmetic read-once formula} (ROF in short) is an arithmetic formula where each input variable labels at most one leaf. In this paper we present several efficient blackbox \emph{polynomial identity testing} (PIT) algorithms for some classes of ... more >>>