Improved Polynomial Identity Testing for Read-Once Formulas
From MaRDI portal
Publication:3638914
DOI10.1007/978-3-642-03685-9_52zbMath1255.68297OpenAlexW1571321110MaRDI QIDQ3638914
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
Analysis of algorithms and problem complexity (68Q25) Fault detection; testing in circuits and networks (94C12) Randomized algorithms (68W20)
Related Items
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
