The 1-versus-2 queries problem revisited

DOI10.1007/S00224-008-9126-XzbMath1203.68052OpenAlexW2007849544MaRDI QIDQ970102

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) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Randomized algorithms (68W20)

Related Items (4)

Amplification with one \textsf{NP} oracle query ⋮ The landscape of communication complexity classes ⋮ Unnamed Item ⋮ Unnamed Item

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

This page was built for publication: The 1-versus-2 queries problem revisited