Improved Polynomial Identity Testing for Read-Once Formulas

DOI10.1007/978-3-642-03685-9_52MaRDI QIDQ3638914zbMATH OpenOpenAlexFDO

Authors 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) Randomized algorithms (68W20) Fault detection; testing in circuits and networks (94C12)

Recommendations

• Read-once polynomial identity testing
• Read-once polynomial identity testing
• On reconstruction and testing of read-once formulas
• Complete derandomization of identity testing and reconstruction of read-once formulas
• scientific article; zbMATH DE number 7204283

Cited in

(22)

• Complete derandomization of identity testing and reconstruction of read-once formulas
• Isomorphism testing of read-once functions and polynomials
• Recent results on polynomial identity testing
• Identity testing, multilinearity testing, and monomials in read-once/twice formulas and branching programs
• Subexponential size hitting sets for bounded depth multilinear formulas
• Building above read-once polynomials: identity testing and hardness of representation
• Exact learning from an honest teacher that answers membership queries
• Read-once polynomial identity testing
• Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in
• scientific article; zbMATH DE number 7758310 (Why is no real title available?)
• 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
• A note on parameterized polynomial identity testing using hitting set generators
• Isomorphism testing of read-once functions and polynomials
• Deterministic polynomial identity tests for multilinear bounded-read formulae
• Read-once polynomial identity testing
• Building above read-once polynomials: identity testing and hardness of representation
• Sums of read-once formulas: how many summands are necessary?
• On reconstruction and testing of read-once formulas
• Sum of products of read-once formulas
• Sums of read-once formulas: how many summands suffice?
• Geometric complexity theory. V: Efficient algorithms for Noether normalization

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

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