On the relation between polynomial identity testing and finding variable disjoint factors

DOI10.1007/978-3-642-14165-2_35MaRDI QIDQ3587395zbMATH OpenOpenAlexFDO

Authors Amir Shpilka, Ilya Volkovich

Publication date 7 September 2010

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-14165-2_35

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

Recommendations

• Equivalence of polynomial identity testing and polynomial factorization
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Factors of low individual degree polynomials

Cited in

(22)

• Deterministic polynomial identity testing in non-commutative models
• Factorization of Boolean polynomials: parallel algorithms and experimental evaluation
• Factorization of polynomials given by arithmetic branching programs
• The complexity of AND-decomposition of Boolean functions
• Equivalence of polynomial identity testing and polynomial factorization
• AND-decomposition of Boolean polynomials with prescribed shared variables
• Jacobian hits circuits: hitting sets, lower bounds for depth-D occur-k formulas and depth-3 transcendence degree-k circuits
• Characterizing arithmetic read-once formulae
• Algorithmic issues of AND-decomposition of Boolean formulas
• Recent results on polynomial identity testing
• Subexponential size hitting sets for bounded depth multilinear formulas
• Factors of low individual degree polynomials
• Factors of low individual degree polynomials
• On some computations on sparse polynomials
• scientific article; zbMATH DE number 7204372 (Why is no real title available?)
• Reconstruction of depth-4 multilinear circuits
• On solving sparse polynomial factorization related problems
• Derandomization via symmetric polytopes: poly-time factorization of certain sparse polynomials
• Towards identity testing for sums of products of Read-once and multilinear bounded-Read formulae
• Towards deterministic algorithms for constant-depth factors of constant-depth circuits
• Structural testing with homomorphic encryption
• Faster \& deterministic FPT algorithm for worst-case tensor decomposition

This page was built for publication: On the relation between polynomial identity testing and finding variable disjoint factors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3587395)