Improved Polynomial Identity Testing for Read-Once Formulas

DOI10.1007/978-3-642-03685-9_52zbMath1255.68297OpenAlexW1571321110MaRDI QIDQ3638914

Amir Shpilka, Ilya Volkovich

Publication date: 28 October 2009

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-03685-9_52

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Fault detection; testing in circuits and networks (94C12) Randomized algorithms (68W20)

Related Items (12)

Subexponential size hitting sets for bounded depth multilinear formulas ⋮ Exact learning from an honest teacher that answers membership queries ⋮ Isomorphism testing of read-once functions and polynomials ⋮ Deterministic polynomial identity tests for multilinear bounded-read formulae ⋮ Unnamed Item ⋮ Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in ⋮ Read-once polynomial identity testing ⋮ Recent Results on Polynomial Identity Testing ⋮ A note on parameterized polynomial identity testing using hitting set generators ⋮ Blackbox identity testing for sum of special ROABPs and its border class ⋮ Jacobian Hits Circuits: Hitting Sets, Lower Bounds for Depth-$D$ Occur-$k$ Formulas and Depth-3 Transcendence Degree-$k$ Circuits ⋮ Geometric complexity theory V: Efficient algorithms for Noether normalization

This page was built for publication: Improved Polynomial Identity Testing for Read-Once Formulas