The 1-versus-2 queries problem revisited

DOI10.1007/S00224-008-9126-XMaRDI QIDQ970102zbMATH OpenOpenAlexFDO

Authors Rahul Tripathi

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

zbMATH Keywords

computational complexitycomplexity classesbounded querieszero-error algorithms

Mathematics Subject Classification ID

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

Recommendations

• The 1-Versus-2 Queries Problem Revisited
• On zero error algorithms having oracle access to one query
• Computing and Combinatorics
• scientific article; zbMATH DE number 1335876
• scientific article; zbMATH DE number 638299

Cites work

• scientific article; zbMATH DE number 3814972 (Why is no real title available?)
• A Downward Collapse within the Polynomial Hierarchy
• A relationship between difference hierarchies and relativized polynomial hierarchies
• BANISHING ROBUST TURING COMPLETENESS
• 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 the complexity of succinct zero-sum games
• 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 connections between bounded query classes and non-uniform complexity.
• Some consequences of non-uniform conditions on uniform classes
• Symmetric alternation captures BPP
• The 1-Versus-2 Queries Problem Revisited
• The Boolean Hierarchy I: Structural Properties
• The Boolean Hierarchy II: Applications
• 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

(8)

• Amplification with one \textsf{NP} oracle query
• The landscape of communication complexity classes
• A \(\mathrm{ZPP}^{\mathrm{NP[1]}}\) lifting theorem
• The 1-Versus-2 Queries Problem Revisited
• On zero error algorithms having oracle access to one query
• scientific article; zbMATH DE number 7561589 (Why is no real title available?)
• scientific article; zbMATH DE number 1304327 (Why is no real title available?)
• A \(\mathrm{ZPP}^{\mathrm{NP}[1]}\) lifting theorem

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 Q970102)