Quasipolynomial hitting sets for circuits with restricted parse trees

DOI10.4230/LIPICS.FSTTCS.2018.6MaRDI QIDQ5090938zbMATH OpenFDO

Authors Ramprasad Saptharishi, Anamay Tengse

Publication date 21 July 2022

Full work available at URL https://arxiv.org/abs/1709.03068

zbMATH Keywords

lower boundspolynomial identity testingalgebraic circuit complexityRead-once oblivious ABPsunambiguous circuits

Mathematics Subject Classification ID

Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Theory of computing (68Qxx)

Recommendations

• Lower bounds and PIT for non-commutative arithmetic circuits with restricted parse trees
• scientific article; zbMATH DE number 7204375
• Non-commutative computations: lower bounds and polynomial identity testing
• Hitting sets for orbits of circuit classes and polynomial families

Cites work

• scientific article; zbMATH DE number 5899249 (Why is no real title available?)
• scientific article; zbMATH DE number 3651744 (Why is no real title available?)
• scientific article; zbMATH DE number 6820278 (Why is no real title available?)
• scientific article; zbMATH DE number 7204375 (Why is no real title available?)
• A probabilistic remark on algebraic program testing
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Deterministic identity testing for sum of read-once oblivious arithmetic branching programs
• Deterministic polynomial identity testing in non-commutative models
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• Fast Parallel Computation of Polynomials Using Few Processors
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits
• Identity testing for constant-width, and commutative, read-once oblivious ABPs
• Lower bounds for non-commutative skew circuits
• Non-commutative arithmetic circuits: depth reduction and size lower bounds
• Non-commutative circuits and the sum-of-squares problem
• Non-commutative computations: lower bounds and polynomial identity testing
• On the Parallel Evaluation of Multivariate Polynomials
• Pseudorandom generators for space-bounded computation
• Quasi-polynomial hitting-set for set-depth-\({\Delta}\) formulas
• Read-once polynomial identity testing
• Some lower bound results for set-multilinear arithmetic computations
• The complexity of partial derivatives

Cited in

(4)

• Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits
• A PSPACE construction of a hitting set for the closure of small algebraic circuits
• Lower bounds and PIT for non-commutative arithmetic circuits with restricted parse trees
• Hitting sets and reconstruction for dense orbits in VPe and ΣΠΣ circuits

This page was built for publication: Quasipolynomial hitting sets for circuits with restricted parse trees

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