Progress on polynomial identity testing
From MaRDI portal
Abstract: 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.
Recommendations
- Recent results on polynomial identity testing
- Progress on polynomial identity testing. II
- Polynomial identity testing for depth 3 circuits
- Arithmetic circuits: a survey of recent results and open questions
- Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in
Cited in
(45)- On division polynomial PIT and supersingularity
- Deterministic identity testing for sum of read-once oblivious arithmetic branching programs
- Polynomial interpolation and identity testing from high powers over finite fields
- A case of depth-3 identity testing, sparse factorization and duality
- Blackbox identity testing for sum of special ROABPs and its border class
- A promenade through correct test sequences. I: Degree of constructible sets, Bézout's inequality and density
- Improved hitting set for orbit of ROABPs
- An improved finiteness test and a systematic procedure to compute the strong \(\mathscr{H}_2\) norm of differential algebraic systems with multiple delays
- Emptiness problems for integer circuits
- Learning algebraic decompositions using Prony structures
- A note on parameterized polynomial identity testing using hitting set generators
- Lower bounds and PIT for non-commutative arithmetic circuits with restricted parse trees
- Equivalence of polynomial identity testing and polynomial factorization
- Polynomial identity testing for depth 3 circuits
- Exact learning from an honest teacher that answers membership queries
- Progress on polynomial identity testing. II
- Recent results on polynomial identity testing
- Arithmetic circuits: a survey of recent results and open questions
- Sampling algebraic varieties for sum of squares programs
- scientific article; zbMATH DE number 7009617 (Why is no real title available?)
- Algorithms based on \(*\)-algebras, and their applications to isomorphism of polynomials with one secret, group isomorphism, and polynomial identity testing
- A Wronskian approach to the real \(\tau\)-conjecture
- Towards blackbox identity testing of log-variate circuits
- scientific article; zbMATH DE number 7471587 (Why is no real title available?)
- The Multivariate Schwartz--Zippel Lemma
- A generalized sylvester-gallai type theorem for quadratic polynomials
- scientific article; zbMATH DE number 7561765 (Why is no real title available?)
- Emptiness problems for integer circuits
- scientific article; zbMATH DE number 7250150 (Why is no real title available?)
- Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits
- Algebraic independence in positive characteristic: a p-adic calculus
- Improved Explicit Hitting-Sets for ROABPs
- scientific article; zbMATH DE number 7758310 (Why is no real title available?)
- Testing the satisfiability of algebraic formulas over the field of two elements
- Hardness of graph-structured algebraic and symbolic problems
- Variety evasive subspace families
- Lower bounds for the sum of small-size algebraic branching programs
- On matrix multiplication and polynomial identity testing
- Optimal pseudorandom generators for low-degree polynomials over moderately large fields
- Lower bounds for the sum of small-size algebraic branching programs
- Hitting sets for orbits of circuit classes and polynomial families
- A largish sum-of-squares implies circuit hardness and derandomization
- A note on the computational complexity of chain rule differentiation
- Uniform bounds on product Sylvester-Gallai configurations
- Deterministic polynomial identity tests for multilinear bounded-read formulae
This page was built for publication: Progress on polynomial identity testing
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3656204)
