Recommendations
- The 1-versus-2 queries problem revisited
- scientific article; zbMATH DE number 1947429
- A dichotomy in the complexity of consistent query answering for queries with two atoms
- Towards better separation between deterministic and randomized query complexity
- Extending Downward Collapse from 1-versus-2 Queries tom-versus-m+ 1 Queries
- Efficient and optimal query answering on independent schemes
- \(Q\)-ary search with one Lie and bi-interval queries
- A trichotomy in the complexity of counting answers to conjunctive queries
- Separation between deterministic and randomized query complexity
Cites work
- A Downward Collapse within the Polynomial Hierarchy
- A relationship between difference hierarchies and relativized polynomial hierarchies
- Competing provers yield improved Karp-Lipton collapse results
- Extending Downward Collapse from 1-versus-2 Queries tom-versus-m+ 1 Queries
- More on BPP and the polynomial-time hierarchy
- Oblivious Symmetric Alternation
- On computing Boolean connectives of characteristic functions
- On zero error algorithms having oracle access to one query
- Oracles and queries that are sufficient for exact learning
- Proving SAT does not have small circuits with an application to the two queries problem
- Some Results on Average-Case Hardness Within the Polynomial Hierarchy
- Some consequences of non-uniform conditions on uniform classes
- Symmetric alternation captures BPP
- The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection
- The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
- The complexity of optimization problems
- Two queries
- \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\)
Cited in
(5)
This page was built for publication: The 1-Versus-2 Queries Problem Revisited
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5387752)
