The 1-versus-2 queries problem revisited
From MaRDI portal
Publication:970102
DOI10.1007/s00224-008-9126-xzbMath1203.68052MaRDI QIDQ970102
Publication date: 10 May 2010
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-008-9126-x
68Q25: Analysis of algorithms and problem complexity
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
68W20: Randomized algorithms
Cites Work
- Unnamed Item
- Some consequences of non-uniform conditions on uniform classes
- \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\)
- On the complexity of succinct zero-sum games
- The complexity of optimization problems
- Symmetric alternation captures BPP
- More on BPP and the polynomial-time hierarchy
- Some connections between bounded query classes and non-uniform complexity.
- 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
- The Boolean Hierarchy I: Structural Properties
- The Boolean Hierarchy II: Applications
- A Downward Collapse within the Polynomial Hierarchy
- BANISHING ROBUST TURING COMPLETENESS
- 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
- The 1-Versus-2 Queries Problem Revisited
- Oblivious Symmetric Alternation