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

DOI10.1007/978-3-642-14165-2_35zbMath1288.68252OpenAlexW2153445467MaRDI QIDQ3587395

Ilya Volkovich, Amir Shpilka

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)

Related Items (13)

Algorithmic issues of AND-decomposition of Boolean formulas ⋮ Subexponential size hitting sets for bounded depth multilinear formulas ⋮ Factors of low individual degree polynomials ⋮ The complexity of AND-decomposition of Boolean functions ⋮ Unnamed Item ⋮ Recent Results on Polynomial Identity Testing ⋮ On the complexity of noncommutative polynomial factorization ⋮ Factorization of Boolean polynomials: parallel algorithms and experimental evaluation ⋮ AND–Decomposition of Boolean Polynomials with Prescribed Shared Variables ⋮ Factorization of polynomials given by arithmetic branching programs ⋮ 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 ⋮ Equivalence of polynomial identity testing and polynomial factorization

This page was built for publication: On the Relation between Polynomial Identity Testing and Finding Variable Disjoint Factors