Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with polynomial identity testing:
TR05-044 | 6th April 2005
Zeev Dvir, Amir Shpilka

Locally Decodable Codes with 2 queries and Polynomial Identity Testing for depth 3 circuits

In this work we study two seemingly unrelated notions. Locally Decodable Codes(LDCs) are codes that allow the recovery of each message bit from a constant number of entries of the codeword. Polynomial Identity Testing (PIT) is one of the fundamental problems of algebraic complexity: we are given a circuit computing ... more >>>

TR07-121 | 21st November 2007
Zeev Dvir, Amir Shpilka, Amir Yehudayoff

Hardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits

In this paper we show that lower bounds for bounded depth arithmetic circuits imply derandomization of polynomial identity testing for bounded depth arithmetic circuits. More formally, if there exists an explicit polynomial f(x_1,...,x_m) that cannot be computed by a depth d arithmetic circuit of small size then there exists ... 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 >>>

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

TR09-032 | 16th April 2009
Neeraj Kayal, Shubhangi Saraf

Blackbox Polynomial Identity Testing for Depth 3 Circuits

We study depth three arithmetic circuits with bounded top fanin. We give the first deterministic polynomial time blackbox identity test for depth three circuits with bounded top fanin over the field of rational numbers, thus resolving a question posed by Klivans and Spielman (STOC 2001).

Our main technical result is ... more >>>

TR09-036 | 14th April 2009
Chandan Saha, Ramprasad Saptharishi, Nitin Saxena

The Power of Depth 2 Circuits over Algebras

We study the problem of polynomial identity testing (PIT) for depth
2 arithmetic circuits over matrix algebra. We show that identity
testing of depth 3 (Sigma-Pi-Sigma) arithmetic circuits over a field
F is polynomial time equivalent to identity testing of depth 2
(Pi-Sigma) arithmetic circuits over U_2(F), the ... more >>>

TR09-039 | 6th April 2009
Matei David, Periklis Papakonstantinou, Anastasios Sidiropoulos

Polynomial Time with Restricted Use of Randomness

We define a hierarchy of complexity classes that lie between P and RP, yielding a new way of quantifying partial progress towards the derandomization of RP. A standard approach in derandomization is to reduce the number of random bits an algorithm uses. We instead focus on a model of computation ... more >>>

TR10-015 | 8th February 2010
Maurice Jansen, Youming Qiao, Jayalal Sarma

Deterministic Black-Box Identity Testing $\pi$-Ordered Algebraic Branching Programs

In this paper we study algebraic branching programs (ABPs) with restrictions on the order and the number of reads of variables in the program. Given a permutation $\pi$ of $n$ variables, for a $\pi$-ordered ABP ($\pi$-OABP), for any directed path $p$ from source to sink, a variable can appear at ... more >>>

TR10-036 | 8th March 2010
Amir Shpilka, Ilya Volkovich

On the Relation between Polynomial Identity Testing and Finding Variable Disjoint Factors

We say that a polynomial $f(x_1,\ldots,x_n)$ is {\em indecomposable} if it cannot be written as a product of two polynomials that are defined over disjoint sets of variables. The {\em polynomial decomposition} problem is defined to be the task of finding the indecomposable factors of a given polynomial. Note that ... more >>>

TR10-084 | 14th May 2010
Maurice Jansen, Youming Qiao, Jayalal Sarma

Deterministic Identity Testing of Read-Once Algebraic Branching Programs

An algebraic branching program (ABP) is given by a directed acyclic graph with source and sink vertices $s$ and $t$, respectively, and where edges are labeled by variables or field constants. An ABP computes the sum of weights of all directed paths from $s$ to $t$, where the weight of ... more >>>

TR10-105 | 29th June 2010
Scott Aaronson, Dieter van Melkebeek

A note on circuit lower bounds from derandomization

We present an alternate proof of the result by Kabanets and Impagliazzo that derandomizing polynomial identity testing implies circuit lower bounds. Our proof is simpler, scales better, and yields a somewhat stronger result than the original argument.

more >>>

TR10-188 | 8th December 2010
Matthew Anderson, Dieter van Melkebeek, Ilya Volkovich

Derandomizing Polynomial Identity Testing for Multilinear Constant-Read Formulae

Revisions: 1

We present a polynomial-time deterministic algorithm for testing whether constant-read multilinear arithmetic formulae are identically zero. In such a formula each variable occurs only a constant number of times and each subformula computes a multilinear polynomial. Our algorithm runs in time $s^{O(1)}\cdot n^{k^{O(k)}}$, where $s$ denotes the size of the ... more >>>

TR11-135 | 9th October 2011
Maurice Jansen, Rahul Santhanam

Stronger Lower Bounds and Randomness-Hardness Tradeoffs using Associated Algebraic Complexity Classes

We associate to each Boolean language complexity class $\mathcal{C}$ the algebraic class $a\cdot\mathcal{C}$ consisting of families of polynomials $\{f_n\}$ for which the evaluation problem over the integers is in $\mathcal{C}$. We prove the following lower bound and randomness-to-hardness results:

1. If polynomial identity testing (PIT) is in $NSUBEXP$ then $a\cdot ... more >>>

TR11-147 | 2nd November 2011
Michael Forbes, Amir Shpilka

On Identity Testing of Tensors, Low-rank Recovery and Compressed Sensing

We study the problem of obtaining efficient, deterministic, black-box polynomial identity testing algorithms for depth-3 set-multilinear circuits (over arbitrary fields). This class of circuits has an efficient, deterministic, white-box polynomial identity testing algorithm (due to Raz and Shpilka), but has no known such black-box algorithm. We recast this problem as ... more >>>

TR12-113 | 7th September 2012
Manindra Agrawal, Chandan Saha, Nitin Saxena

Quasi-polynomial Hitting-set for Set-depth-$\Delta$ Formulas

We call a depth-$4$ formula $C$ $\textit{ set-depth-4}$ if there exists a (unknown) partition $X_1\sqcup\cdots\sqcup X_d$ of the variable indices $[n]$ that the top product layer respects, i.e. $C(\mathbf{x})=\sum_{i=1}^k {\prod_{j=1}^{d} {f_{i,j}(\mathbf{x}_{X_j})}}$ $ ,$ where $f_{i,j}$ is a $\textit{sparse}$ polynomial in $\mathbb{F}[\mathbf{x}_{X_j}]$. Extending this definition to any depth - we call ... more >>>

TR12-115 | 11th September 2012
Michael Forbes, Amir Shpilka

Quasipolynomial-time Identity Testing of Non-Commutative and Read-Once Oblivious Algebraic Branching Programs

Revisions: 1

We study the problem of obtaining efficient, deterministic, black-box polynomial identity testing (PIT) algorithms for read-once oblivious algebraic branching programs (ABPs). This class has an efficient, deterministic, white-box polynomial identity testing algorithm (due to Raz and Shpilka), but prior to this work had no known such black-box algorithm. Here we ... more >>>

TR13-033 | 1st March 2013
Michael Forbes, Amir Shpilka

Explicit Noether Normalization for Simultaneous Conjugation via Polynomial Identity Testing

Revisions: 1

Mulmuley recently gave an explicit version of Noether's Normalization lemma for ring of invariants of matrices under simultaneous conjugation, under the conjecture that there are deterministic black-box algorithms for polynomial identity testing (PIT). He argued that this gives evidence that constructing such algorithms for PIT is beyond current techniques. In ... more >>>

TR13-068 | 3rd May 2013
Mrinal Kumar, Shubhangi Saraf

Lower Bounds for Depth 4 Homogenous Circuits with Bounded Top Fanin

We study the class of homogenous $\Sigma\Pi\Sigma\Pi(r)$ circuits, which are depth 4 homogenous circuits with top fanin bounded by $r$. We show that any homogenous $\Sigma\Pi\Sigma\Pi(r)$ circuit computing the permanent of an $n\times n$ matrix must have size at least $\exp\left(n^{\Omega(1/r)}\right)$.

In a recent result, Gupta, Kamath, Kayal and ... more >>>

TR13-132 | 23rd September 2013
Michael Forbes, Ramprasad Saptharishi, Amir Shpilka

Pseudorandomness for Multilinear Read-Once Algebraic Branching Programs, in any Order

We give deterministic black-box polynomial identity testing algorithms for multilinear read-once oblivious algebraic branching programs (ROABPs), in n^(lg^2 n) time. Further, our algorithm is oblivious to the order of the variables. This is the first sub-exponential time algorithm for this model. Furthermore, our result has no known analogue in the ... more >>>

TR13-157 | 11th November 2013
Bin Fu

Derandomizing Polynomial Identity over Finite Fields Implies Super-Polynomial Circuit Lower Bounds for NEXP

Revisions: 1 , Comments: 1

We show that
derandomizing polynomial identity testing over an arbitrary finite
field implies that NEXP does not have polynomial size boolean
circuits. In other words, for any finite field F(q) of size q,
$PIT_q\in NSUBEXP\Rightarrow NEXP\not\subseteq P/poly$, where
$PIT_q$ is the polynomial identity testing problem over F(q), and
NSUBEXP is ... more >>>

TR13-175 | 6th December 2013
Venkatesan Guruswami, Chaoping Xing

Hitting Sets for Low-Degree Polynomials with Optimal Density

Revisions: 1

We give a length-efficient puncturing of Reed-Muller codes which preserves its distance properties. Formally, for the Reed-Muller code encoding $n$-variate degree-$d$ polynomials over ${\mathbb F}_q$ with $q \ge \Omega(d/\delta)$, we present an explicit (multi)-set $S \subseteq {\mathbb F}_q^n$ of size $N=\mathrm{poly}(n^d/\delta)$ such that every nonzero polynomial vanishes on at most ... more >>>

TR14-001 | 4th January 2014
Swastik Kopparty, Shubhangi Saraf, Amir Shpilka

Equivalence of Polynomial Identity Testing and Deterministic Multivariate Polynomial Factorization

In this paper we show that the problem of deterministically factoring multivariate polynomials reduces to the problem of deterministic polynomial identity testing. Specifically, we show that given an arithmetic circuit (either explicitly or via black-box access) that computes a polynomial $f(X_1,\ldots,X_n)$, the task of computing arithmetic circuits for the factors ... more >>>

TR14-003 | 10th January 2014
Zeev Dvir, Rafael Mendes de Oliveira, Amir Shpilka

Testing Equivalence of Polynomials under Shifts

Revisions: 2 , Comments: 1

Two polynomials $f, g \in F[x_1, \ldots, x_n]$ are called shift-equivalent if there exists a vector $(a_1, \ldots, a_n) \in {F}^n$ such that the polynomial identity $f(x_1+a_1, \ldots, x_n+a_n) \equiv g(x_1,\ldots,x_n)$ holds. Our main result is a new randomized algorithm that tests whether two given polynomials are shift equivalent. Our ... more >>>

TR14-052 | 14th April 2014
Joshua Grochow, Toniann Pitassi

Circuit complexity, proof complexity, and polynomial identity testing

We introduce a new and very natural algebraic proof system, which has tight connections to (algebraic) circuit complexity. In particular, we show that any super-polynomial lower bound on any Boolean tautology in our proof system implies that the permanent does not have polynomial-size algebraic circuits ($VNP \neq VP$). As a ... more >>>

TR14-157 | 27th November 2014
Rafael Mendes de Oliveira, Amir Shpilka, Ben Lee Volk

Subexponential Size Hitting Sets for Bounded Depth Multilinear Formulas

In this paper we give subexponential size hitting sets for bounded depth multilinear arithmetic formulas. Using the known relation between black-box PIT and lower bounds we obtain lower bounds for these models.

For depth-3 multilinear formulas, of size $\exp(n^\delta)$, we give a hitting set of size $\exp(\tilde{O}(n^{2/3 + 2\delta/3}))$. ... more >>>

TR15-071 | 23rd April 2015
Mrinal Kumar, Shubhangi Saraf

Sums of products of polynomials in few variables : lower bounds and polynomial identity testing

We study the complexity of representing polynomials as a sum of products of polynomials in few variables. More precisely, we study representations of the form $$P = \sum_{i = 1}^T \prod_{j = 1}^d Q_{ij}$$
such that each $Q_{ij}$ is an arbitrary polynomial that depends on at most $s$ variables.

... more >>>

TR15-194 | 30th November 2015
Mrinal Kumar, Shubhangi Saraf

Arithmetic circuits with locally low algebraic rank

Revisions: 1

In recent years there has been a flurry of activity proving lower bounds for
homogeneous depth-4 arithmetic circuits [GKKS13, FLMS14, KLSS14, KS14c], which has brought us very close to statements that are known to imply VP $\neq$ VNP. It is a big question to go beyond homogeneity, and in ... more >>>

TR16-098 | 16th June 2016
Michael Forbes, Amir Shpilka, Iddo Tzameret, Avi Wigderson

Proof Complexity Lower Bounds from Algebraic Circuit Complexity

We give upper and lower bounds on the power of subsystems of the Ideal Proof System (IPS), the algebraic proof system recently proposed by Grochow and Pitassi, where the circuits comprising the proof come from various restricted algebraic circuit classes. This mimics an established research direction in the ... more >>>

TR16-101 | 1st July 2016
Toniann Pitassi, Iddo Tzameret

Algebraic Proof Complexity: Progress, Frontiers and Challenges

We survey recent progress in the proof complexity of strong proof systems and its connection to algebraic circuit complexity, showing how the synergy between the two gives rise to new approaches to fundamental open questions, solutions to old problems, and new directions of research. In particular, we focus on tight ... more >>>

TR16-182 | 14th November 2016
Rohit Gurjar, Thomas Thierauf

Linear Matroid Intersection is in quasi-NC

Given two matroids on the same ground set, the matroid intersection problem asks to find a common independent set of maximum size. We show that the linear matroid intersection problem is in quasi-NC$^2$. That is, it has uniform circuits of quasi-polynomial size $n^{O(\log n)}$, and $O(\log^2 n)$ depth. This generalizes ... more >>>

TR17-007 | 19th January 2017
Michael Forbes, Amir Shpilka, Ben Lee Volk

Succinct Hitting Sets and Barriers to Proving Algebraic Circuits Lower Bounds

We formalize a framework of algebraically natural lower bounds for algebraic circuits. Just as with the natural proofs notion of Razborov and Rudich for boolean circuit lower bounds, our notion of algebraically natural lower bounds captures nearly all lower bound techniques known. However, unlike the boolean setting, there has been ... more >>>

TR17-009 | 19th January 2017
Joshua Grochow, Mrinal Kumar, Michael Saks, Shubhangi Saraf

Towards an algebraic natural proofs barrier via polynomial identity testing

We observe that a certain kind of algebraic proof - which covers essentially all known algebraic circuit lower bounds to date - cannot be used to prove lower bounds against VP if and only if what we call succinct hitting sets exist for VP. This is analogous to the Razborov-Rudich ... more >>>

TR17-012 | 17th January 2017
Dominik Barth, Moritz Beck, Titus Dose, Christian Glaßer, Larissa Michler, Marc Technau

Emptiness Problems for Integer Circuits

We study the computational complexity of emptiness problems for circuits over sets of natural numbers with the operations union, intersection, complement, addition, and multiplication. For most settings of allowed operations we precisely characterize the complexity in terms of completeness for classes like NL, NP, and PSPACE. The case where intersection, ... more >>>

TR17-135 | 10th September 2017
Ramprasad Saptharishi, Anamay Tengse

Quasi-polynomial Hitting Sets for Circuits with Restricted Parse Trees

We study the class of non-commutative Unambiguous circuits or Unique-Parse-Tree (UPT) circuits, and a related model of Few-Parse-Trees (FewPT) circuits (which were recently introduced by Lagarde, Malod and Perifel [LMP16] and Lagarde, Limaye and Srinivasan [LLS17]) and give the following constructions:
• An explicit hitting set of quasipolynomial size for ... more >>>

ISSN 1433-8092 | Imprint