The 1-Versus-2 Queries Problem Revisited (Q5387752): Difference between revisions

@@ Property / cites work @@
+Oracles and queries that are sufficient for exact learning
+Normal rank
@@ Property / cites work @@
+A relationship between difference hierarchies and relativized polynomial hierarchies
+Normal rank
@@ Property / cites work @@
+Two queries
@@ Property / cites work: Two queries / rank @@
+Normal rank
@@ Property / cites work @@
+\(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\)
+Normal rank
@@ Property / cites work @@
+More on BPP and the polynomial-time hierarchy
@@ Property / cites work: More on BPP and the polynomial-time hierarchy / rank @@
+Normal rank
@@ Property / cites work @@
+On zero error algorithms having oracle access to one query
+Normal rank
@@ Property / cites work @@
+Competing provers yield improved Karp-Lipton collapse results
+Normal rank
@@ Property / cites work @@
+On computing Boolean connectives of characteristic functions
+Normal rank
@@ Property / cites work @@
+The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection
+Normal rank
@@ Property / cites work @@
+Oblivious Symmetric Alternation
@@ Property / cites work: Oblivious Symmetric Alternation / rank @@
+Normal rank
@@ Property / cites work @@
+Proving SAT does not have small circuits with an application to the two queries problem
+Normal rank
@@ Property / cites work @@
+A Downward Collapse within the Polynomial Hierarchy
+Normal rank
@@ Property / cites work @@
+Extending Downward Collapse from 1-versus-2 Queries to<i>m</i>-versus-<i>m</i>+ 1 Queries
+Normal rank
@@ Property / cites work @@
+The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
+Normal rank
@@ Property / cites work @@
+The complexity of optimization problems
@@ Property / cites work: The complexity of optimization problems / rank @@
+Normal rank
@@ Property / cites work @@
+Some Results on Average-Case Hardness Within the Polynomial Hierarchy
+Normal rank
@@ Property / cites work @@
+Symmetric alternation captures BPP
@@ Property / cites work: Symmetric alternation captures BPP / rank @@
+Normal rank
@@ Property / cites work @@
+Some consequences of non-uniform conditions on uniform classes
+Normal rank