On randomized semi-algebraic test complexity

DOI10.1006/JCOM.1993.1016MaRDI QIDQ1260656zbMATH OpenOpenAlexFDO

Authors Peter Bürgisser, Marek Karpinski, Thomas Lickteig

Publication date 24 August 1993

Published in Journal of Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jcom.1993.1016

zbMATH Keywords

randomized decision complexityrandomized decision trees

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Semialgebraic sets and related spaces (14P10)

Recommendations

• Semi-algebraic decision complexity, the real spectrum, and degree
• A lower bound for randomized algebraic decision trees
• scientific article; zbMATH DE number 1984321
• scientific article; zbMATH DE number 1256781

Cited in

(11)

• Semi-algebraic decision complexity, the real spectrum, and degree
• Randomization and the computational power of analytic and algebraic decision trees
• scientific article; zbMATH DE number 5999718 (Why is no real title available?)
• A lower bound for randomized algebraic decision trees
• Randomness-efficient low degree tests and short PCPs via epsilon-biased sets
• On certain computable tests and componentwise error bounds
• On the decisional complexity of problems over the reals
• Complexity bounds for zero-test algorithms
• A tight lower bound for computing the diameter of a 3D convex polytope
• Nondeterministic seedless oritatami systems and hardness of testing their equivalence
• scientific article; zbMATH DE number 1775407 (Why is no real title available?)

This page was built for publication: On randomized semi-algebraic test complexity

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