Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > POLYNOMIAL IDENTITY TESTING:
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

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

#### 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 Revisions: 1 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 Revisions: 1 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 >>> TR17-163 | 2nd November 2017 Michael Forbes, Amir Shpilka #### A PSPACE Construction of a Hitting Set for the Closure of Small Algebraic Circuits In this paper we study the complexity of constructing a hitting set for$\overline{VP}$, the class of polynomials that can be infinitesimally approximated by polynomials that are computed by polynomial sized algebraic circuits, over the real or complex numbers. Specifically, we show that there is a PSPACE algorithm that given ... more >>> TR18-036 | 21st February 2018 Michael Forbes, Sumanta Ghosh, Nitin Saxena #### Towards blackbox identity testing of log-variate circuits Derandomization of blackbox identity testing reduces to extremely special circuit models. After a line of work, it is known that focusing on circuits with constant-depth and constantly many variables is enough (Agrawal,Ghosh,Saxena, STOC'18) to get to general hitting-sets and circuit lower bounds. This inspires us to study circuits with few ... 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 >>> TR18-132 | 17th July 2018 Mrinal Kumar, Ramprasad Saptharishi, Anamay Tengse #### Near-optimal Bootstrapping of Hitting Sets for Algebraic Circuits Revisions: 2 The classical lemma of Ore-DeMillo-Lipton-Schwartz-Zippel states that any nonzero polynomial$f(x_1,\ldots, x_n)$of degree at most$s$will evaluate to a nonzero value at some point on a grid$S^n \subseteq \mathbb{F}^n$with$|S| > s$. Thus, there is a deterministic polynomial identity test (PIT) for all degree-$s$size-$s$... more >>> TR19-035 | 5th March 2019 Alexey Milovanov #### PIT for depth-4 circuits and Sylvester-Gallai theorem for polynomials This text is a development of a preprint of Ankit Gupta. We present an approach for devising a deterministic polynomial time whitekbox identity testing (PIT) algorithm for depth-$4$circuits with bounded top fanin. This approach is similar to Kayal-Saraf approach for depth-$3$circuits. Kayal and Saraf based their ... more >>> TR20-081 | 21st May 2020 Robert Andrews #### Algebraic Hardness versus Randomness in Low Characteristic We show that lower bounds for explicit constant-variate polynomials over fields of characteristic$p > 0$are sufficient to derandomize polynomial identity testing over fields of characteristic$p$. In this setting, existing work on hardness-randomness tradeoffs for polynomial identity testing requires either the characteristic to be sufficiently large or the ... more >>> TR21-014 | 15th February 2021 Dori Medini, Amir Shpilka #### Hitting Sets and Reconstruction for Dense Orbits in VP$_e$and$\Sigma\Pi\Sigma$Circuits In this paper we study polynomials in VP$_e$(polynomial-sized formulas) and in$\Sigma\Pi\Sigma$(polynomial-size depth-$3$circuits) whose orbits, under the action of the affine group GL$^{aff}_n({\mathbb F})$, are dense in their ambient class. We construct hitting sets and interpolating sets for these orbits as well as give reconstruction algorithms. As ... more >>> TR21-067 | 6th May 2021 Zeyu Guo #### Variety Evasive Subspace Families Revisions: 1 We introduce the problem of constructing explicit variety evasive subspace families. Given a family$\mathcal{F}$of subvarieties of a projective or affine space, a collection$\mathcal{H}$of projective or affine$k$-subspaces is$(\mathcal{F},\epsilon)$-evasive if for every$\mathcal{V}\in\mathcal{F}$, all but at most$\epsilon$-fraction of$W\in\mathcal{H}$intersect every irreducible component of$\mathcal{V}$... more >>> TR21-172 | 1st December 2021 Robert Andrews, Michael Forbes #### Ideals, Determinants, and Straightening: Proving and Using Lower Bounds for Polynomial Ideals We show that any nonzero polynomial in the ideal generated by the$r \times r$minors of an$n \times n$matrix$X$can be used to efficiently approximate the determinant. Specifically, for any nonzero polynomial$f$in this ideal, we construct a small depth-three$f$-oracle circuit that approximates the ... more >>> TR22-022 | 18th February 2022 Vikraman Arvind, Pushkar Joglekar #### On Efficient Noncommutative Polynomial Factorization via Higman Linearization Revisions: 3 In this paper we study the problem of efficiently factorizing polynomials in the free noncommutative ring F of polynomials in noncommuting variables x_1,x_2,…,x_n over the field F. We obtain the following result: Given a noncommutative arithmetic formula of size s computing a noncommutative polynomial f in F as input, where ... more >>> TR22-037 | 10th March 2022 Abhibhav Garg, Rafael Mendes de Oliveira, Akash Sengupta #### Robust Radical Sylvester-Gallai Theorem for Quadratics We prove a robust generalization of a Sylvester-Gallai type theorem for quadratic polynomials, generalizing the result in [S'20]. More precisely, given a parameter$0 < \delta \leq 1$and a finite collection$\mathcal{F}$of irreducible and pairwise independent polynomials of degree at most 2, we say that$\mathcal{F}$is a ... more >>> TR22-042 | 31st March 2022 Vikraman Arvind, Pushkar Joglekar #### Matrix Polynomial Factorization via Higman Linearization In continuation to our recent work on noncommutative polynomial factorization, we consider the factorization problem for matrices of polynomials and show the following results. \begin{itemize} \item Given as input a full rank$d\times d$matrix$M$whose entries$M_{ij}$are polynomials in the free noncommutative ring more >>> TR22-111 | 1st August 2022 Robert Andrews #### On Matrix Multiplication and Polynomial Identity Testing We show that lower bounds on the border rank of matrix multiplication can be used to non-trivially derandomize polynomial identity testing for small algebraic circuits. Letting$\underline{R}(n)$denote the border rank of$n \times n \times n$matrix multiplication, we construct a hitting set generator with seed length$O(\sqrt{n} \cdot ... more >>>

TR22-115 | 17th August 2022
Dieter van Melkebeek, Andrew Morgan

#### Polynomial Identity Testing via Evaluation of Rational Functions

We introduce a hitting set generator for Polynomial Identity Testing
based on evaluations of low-degree univariate rational functions at
abscissas associated with the variables. Despite the univariate
nature, we establish an equivalence up to rescaling with a generator
introduced by Shpilka and Volkovich, which has a similar structure but
uses ... more >>>

ISSN 1433-8092 | Imprint