Complete derandomization of identity testing and reconstruction of read-once formulas

DOI10.1145/3196836MaRDI QIDQ4973878zbMATH OpenOpenAlexWikidataFDO

Authors Daniel Minahan, Ilya Volkovich

Publication date 6 December 2019

Published in ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3196836

zbMATH Keywords

arithmetic circuitarithmetic formulacircuit reconstructionderandomizationidentity testing

Mathematics Subject Classification ID

Randomized algorithms (68W20) Analysis of algorithms (68W40)

Recommendations

• scientific article; zbMATH DE number 7204283
• Improved Polynomial Identity Testing for Read-Once Formulas
• Read-once polynomial identity testing
• On reconstruction and testing of read-once formulas
• Read-once polynomial identity testing

Cited in

(13)

• Deterministic identity testing for sum of read-once oblivious arithmetic branching programs
• Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions
• Limitations of sums of bounded read formulas and ABPs
• A note on parameterized polynomial identity testing using hitting set generators
• Improved Polynomial Identity Testing for Read-Once Formulas
• Random arithmetic formulas can be reconstructed efficiently
• scientific article; zbMATH DE number 7204283 (Why is no real title available?)
• Read-once polynomial identity testing
• Identity Testing for Constant-Width, and Any-Order, Read-Once Oblivious Arithmetic Branching Programs
• On reconstruction and testing of read-once formulas
• Reconstruction of depth-4 multilinear circuits
• Towards identity testing for sums of products of Read-once and multilinear bounded-Read formulae
• Hitting sets for orbits of circuit classes and polynomial families

This page was built for publication: Complete derandomization of identity testing and reconstruction of read-once formulas

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