Quasipolynomial hitting sets for circuits with restricted parse trees

DOI10.4230/LIPICS.FSTTCS.2018.6MaRDI QIDQ5090938FDOQ5090938

Authors: Ramprasad Saptharishi, Anamay Tengse 

Publication date: 21 July 2022

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

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

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)

Cites Work

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

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)