Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with identity testing:
TR99-018 | 8th June 1999
Manindra Agrawal, Somenath Biswas

Reducing Randomness via Chinese Remaindering

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

TR05-150 | 5th December 2005
Neeraj Kayal, Nitin Saxena

Polynomial Identity Testing for Depth 3 Circuits

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

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

TR07-124 | 23rd November 2007
Nitin Saxena

Diagonal Circuit Identity Testing and Lower Bounds

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

TR08-062 | 11th June 2008
Manindra Agrawal, V. Vinay

Arithmetic Circuits: A Chasm at Depth Four

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

TR09-026 | 17th February 2009
Vikraman Arvind, Pushkar Joglekar

Arithmetic Circuit Size, Identity Testing, and Finite Automata

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

TR09-101 | 20th October 2009
Nitin Saxena

Progress on Polynomial Identity Testing

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

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

TR10-011 | 22nd January 2010
Amir Shpilka, Ilya Volkovich

Read-Once Polynomial Identity Testing

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

TR11-021 | 13th February 2011
Chandan Saha, Ramprasad Saptharishi, Nitin Saxena

A Case of Depth-3 Identity Testing, Sparse Factorization and Duality

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

TR11-022 | 14th February 2011
Malte Beecken, Johannes Mittmann, Nitin Saxena

Algebraic Independence and Blackbox Identity Testing

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

TR11-046 | 2nd April 2011
Shubhangi Saraf, Ilya Volkovich

Black-Box Identity Testing of Depth-4 Multilinear Circuits

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

TR12-014 | 20th February 2012
Johannes Mittmann, Nitin Saxena, Peter Scheiblechner

Algebraic Independence in Positive Characteristic -- A p-Adic Calculus

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

TR13-111 | 17th August 2013
Gregory Valiant, Paul Valiant

Instance-by-instance optimal identity testing

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

TR13-186 | 27th December 2013
Nitin Saxena

Progress on Polynomial Identity Testing - II

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

TR14-130 | 17th October 2014
Ankit Gupta

Algebraic Geometric Techniques for Depth-4 PIT & Sylvester-Gallai Conjectures for Varieties

Revisions: 1

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

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

TR16-171 | 3rd November 2016
Daniel Minahan, Ilya Volkovich

Complete Derandomization of Identity Testing and Reconstruction of Read-Once Formulas

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

TR17-133 | 7th September 2017
Ilias Diakonikolas, Themis Gouleakis, John Peebles, Eric Price

Sample-Optimal Identity Testing with High Probability

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

ISSN 1433-8092 | Imprint