The 1-Versus-2 Queries Problem Revisited

DOI10.1007/978-3-540-77120-3_14zbMATH Open1193.68118OpenAlexW2277688569MaRDI QIDQ5387752

Rahul Tripathi

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• The complexity of optimization problems
• Oracles and queries that are sufficient for exact learning
• The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
• Some consequences of non-uniform conditions on uniform classes
• Competing provers yield improved Karp-Lipton collapse results
• On computing Boolean connectives of characteristic functions
• Symmetric alternation captures BPP
• More on BPP and the polynomial-time hierarchy
• Proving SAT does not have small circuits with an application to the two queries problem
• Oblivious Symmetric Alternation
• \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\)
• Two queries
• The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection
• A Downward Collapse within the Polynomial Hierarchy
• On zero error algorithms having oracle access to one query
• 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

Cited In (2)

• The 1-versus-2 queries problem revisited
• Title not available (Why is that?)

Recommendations

• A dichotomy in the complexity of consistent query answering for queries with two atoms 👍 👎
• Extending Downward Collapse from 1-versus-2 Queries tom-versus-m+ 1 Queries 👍 👎
• The 1-versus-2 queries problem revisited 👍 👎
• Separation Between Deterministic and Randomized Query Complexity 👍 👎
• Towards Better Separation between Deterministic and Randomized Query Complexity 👍 👎
• \(Q\)-ary search with one Lie and bi-interval queries 👍 👎
• Efficient and optimal query answering on independent schemes 👍 👎
• A Trichotomy in the Complexity of Counting Answers to Conjunctive Queries 👍 👎
• Title not available (Why is that?) 👍 👎

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)