Error-bounded probabilistic computations between MA and AM
From MaRDI portal
Recommendations
Cites work
- A comparison of polynomial time reducibilities
- A complexity theory for feasible closure properties
- A Fast Monte-Carlo Test for Primality
- A note on complete problems for complexity classes
- A second step toward the polynomial hierarchy
- An oracle builder's toolkit
- Are there interactive protocols for co-NP languages?
- Automata Studies. (AM-34)
- BANISHING ROBUST TURING COMPLETENESS
- Bounded Query Classes
- BPP and the polynomial hierarchy
- Complete sets and the polynomial-time hierarchy
- Complexity classes without machines: on complete languages for UP
- Complexity limitations on quantum computation
- Computation times of NP sets of different densities
- Computational Complexity of Probabilistic Turing Machines
- Does co-NP have short interactive proofs ?
- Gap-definable counting classes
- scientific article; zbMATH DE number 3814972 (Why is no real title available?)
- scientific article; zbMATH DE number 3597592 (Why is no real title available?)
- scientific article; zbMATH DE number 1500532 (Why is no real title available?)
- ON THE DIFFERENCE BETWEEN CONSECUTIVE PRIMES
- Perceptrons, PP, and the polynomial hierarchy
- PP is closed under intersection
- PP-lowness and a simple definition of AWPP
- PRIMES is in P
- Probabilistic complexity classes and lowness
- Quantum Complexity Theory
- Relativized Arthur-Merlin versus Merlin-Arthur games
- Relativized separation of EQP from \(\text{P}^{\text{NP}}\)
- Relativized worlds with an infinite hierarchy
- Robustness of probabilistic computational complexity classes under definitional perturbations
- Some observations on the probabilistic algorithms and NP-hard problems
- The difference and truth-table hierarchies for NP
- The polynomial-time hierarchy
- Threshold Computation and Cryptographic Security
- Universal classes of hash functions
Cited in
(12)- The landscape of communication complexity classes
- On the probabilistic closure of the loose unambiguous hierarchy
- The complexity of estimating min-entropy
- Zero-information protocols and unambiguity in Arthur-Merlin communication
- Resource Bounded Frequency Computations with Three Errors
- scientific article; zbMATH DE number 1304314 (Why is no real title available?)
- The Untold Story of $$\mathsf {SBP}$$
- Quantum lower bounds for approximate counting via Laurent polynomials
- The layer complexity of Arthur-Merlin-like communication
- Mathematical Foundations of Computer Science 2003
- Rectangles are nonnegative juntas
- Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
This page was built for publication: Error-bounded probabilistic computations between MA and AM
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2507698)
