The 1-Versus-2 Queries Problem Revisited
From MaRDI portal
Publication:5387752
DOI10.1007/978-3-540-77120-3_14zbMath1193.68118OpenAlexW2277688569MaRDI QIDQ5387752
Publication date: 27 May 2008
Published in: Algorithms and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-77120-3_14
Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Randomized algorithms (68W20)
Related Items (1)
Cites Work
- Some consequences of non-uniform conditions on uniform classes
- \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\)
- The complexity of optimization problems
- Symmetric alternation captures BPP
- More on BPP and the polynomial-time hierarchy
- Competing provers yield improved Karp-Lipton collapse results
- Oracles and queries that are sufficient for exact learning
- Two queries
- Proving SAT does not have small circuits with an application to the two queries problem
- On zero error algorithms having oracle access to one query
- The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
- A Downward Collapse within the Polynomial Hierarchy
- On computing Boolean connectives of characteristic functions
- The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection
- A relationship between difference hierarchies and relativized polynomial hierarchies
- Extending Downward Collapse from 1-versus-2 Queries tom-versus-m+ 1 Queries
- Some Results on Average-Case Hardness Within the Polynomial Hierarchy
- Oblivious Symmetric Alternation
This page was built for publication: The 1-Versus-2 Queries Problem Revisited
