The following pages link to BPP and the polynomial hierarchy (Q1052094):
Displaying 50 items.
- A classification of the probabilistic polynomial time hierarchy under fault tolerant access to oracle classes (Q294649) (← links)
- Randomness buys depth for approximate counting (Q483707) (← links)
- Average-case intractability vs. worst-case intractability (Q598182) (← links)
- If NP has polynomial-size circuits, then MA=AM (Q674343) (← links)
- Complexity classes of equivalence problems revisited (Q716333) (← links)
- Relations between communication complexity classes (Q751811) (← links)
- Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes (Q809600) (← links)
- \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\) (Q859979) (← links)
- Computational complexity of the landscape. I. (Q877685) (← links)
- Challenging epistemology: Interactive proofs and zero knowledge (Q959048) (← links)
- Robust algorithms: a different approach to oracles (Q1063417) (← links)
- Relativized circuit complexity (Q1069299) (← links)
- The complexity of combinatorial problems with succinct input representation (Q1090455) (← links)
- Some observations on the connection between counting and recursion (Q1098837) (← links)
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes (Q1106840) (← links)
- Probabilistic quantifiers and games (Q1112019) (← links)
- Graph isomorphism is in the low hierarchy (Q1116696) (← links)
- Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P (Q1193633) (← links)
- On sparse hard sets for counting classes (Q1210293) (← links)
- Probabilistic complexity classes and lowness (Q1263979) (← links)
- On bounded-probability operators and C\(_ =\)P (Q1313771) (← links)
- A general method to construct oracles realizing given relationships between complexity classes (Q1351504) (← links)
- More on BPP and the polynomial-time hierarchy (Q1351599) (← links)
- Non-interactive proofs of proximity (Q1745962) (← links)
- Tally NP sets and easy census functions. (Q1854340) (← links)
- How much randomness is needed to convert MA protocols to AM protocols? (Q2097236) (← links)
- On the possibility of basing cryptography on \(\mathsf{EXP}\ne \mathsf{BPP} \) (Q2120065) (← links)
- A note on perfect correctness by derandomization (Q2146431) (← links)
- Proving that \(\mathrm{prBPP}=\mathrm{prP}\) is as hard as proving that ``almost NP'' is not contained in P/poly (Q2328311) (← links)
- Uniform proofs of ACC representations (Q2402964) (← links)
- On zero error algorithms having oracle access to one query (Q2498984) (← links)
- Error-bounded probabilistic computations between MA and AM (Q2507698) (← links)
- $$P\mathop{ =}\limits^{?}NP$$ (Q2826803) (← links)
- Input-Oblivious Proof Systems and a Uniform Complexity Perspective on P/poly (Q2828212) (← links)
- Another Proof That $\mathcal{BPP}\subseteq \mathcal{PH}$ (and More) (Q3088174) (← links)
- Simplified Derandomization of BPP Using a Hitting Set Generator (Q3088176) (← links)
- Nonlevelable sets and immune sets in the accepting density hierarchy inNP (Q3711750) (← links)
- Classifying the computational complexity of problems (Q3781088) (← links)
- Simultaneous strong separations of probabilistic and unambiguous complexity classes (Q3992020) (← links)
- On the power of deterministic reductions to C=P (Q4032933) (← links)
- Immunity and Simplicity for Exact Counting and Other Counting Classes (Q4265536) (← links)
- Fault-tolerance and complexity (Extended abstract) (Q4630260) (← links)
- Generalized Quantum Arthur--Merlin Games (Q4634057) (← links)
- The Journey from NP to TFNP Hardness (Q4638115) (← links)
- Generalized lowness and highness and probabilistic complexity classes (Q4729352) (← links)
- On closure properties of bounded two-sided error complexity classes (Q4835865) (← links)
- On the power of parity polynomial time (Q5096157) (← links)
- Super-Perfect Zero-Knowledge Proofs (Q5098773) (← links)
- On the parameterized complexity of approximate counting (Q5198932) (← links)
- A Note on Perfect Correctness by Derandomization (Q5267419) (← links)
