On randomized semi-algebraic test complexity

DOI10.1006/JCOM.1993.1016zbMATH Open0806.68045OpenAlexW2032022602MaRDI QIDQ1260656FDOQ1260656

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

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

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)

Cited In (11)

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

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)