On zero error algorithms having oracle access to one query (Q2498984): Difference between revisions

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1007/s10878-006-7130-0
+Normal rank
@@ Property / OpenAlex ID @@
+W1977921381
@@ Property / OpenAlex ID: W1977921381 / rank @@
+Normal rank
@@ Property / cites work @@
+Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
+Normal rank
@@ Property / cites work @@
+Does co-NP have short interactive proofs ?
@@ Property / cites work: Does co-NP have short interactive proofs ? / rank @@
+Normal rank
@@ Property / cites work @@
+Computing and Combinatorics
@@ Property / cites work: Computing and Combinatorics / rank @@
+Normal rank
@@ Property / cites work @@
+Q4418679
@@ Property / cites work: Q4418679 / rank @@
+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 the complexity of succinct zero-sum games
@@ Property / cites work: On the complexity of succinct zero-sum games / 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 @@
+Another Proof That $\mathcal{BPP}\subseteq \mathcal{PH}$ (and More)
+Normal rank
@@ Property / cites work @@
+Q4526985
@@ Property / cites work: Q4526985 / rank @@
+Normal rank
@@ Property / cites work @@
+Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
+Normal rank
@@ Property / cites work @@
+BPP and the polynomial hierarchy
@@ Property / cites work: BPP and the polynomial hierarchy / rank @@
+Normal rank
@@ Property / cites work @@
+Derandomizing Arthur-Merlin games using hitting sets
+Normal rank
@@ Property / cites work @@
+Hardness vs randomness
@@ Property / cites work: Hardness vs randomness / rank @@
+Normal rank
@@ Property / cites work @@
+Symmetric alternation captures BPP
@@ Property / cites work: Symmetric alternation captures BPP / rank @@
+Normal rank
@@ Property / cites work @@
+Pseudorandomness for approximate counting and sampling
+Normal rank
@@ Property / cites work @@
+Simulating BPP using a general weak random source
@@ Property / cites work: Simulating BPP using a general weak random source / rank @@
+Normal rank