The random oracle hypothesis is false (Q1333397): Difference between revisions

@@ Property / cites work @@
+Non-deterministic exponential time has two-prover interactive protocols
+Normal rank
@@ Property / cites work @@
+Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
+Normal rank
@@ Property / cites work @@
+Relative to a Random Oracle<i>A</i>, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
+Normal rank
@@ Property / cites work @@
+On Isomorphisms and Density of $NP$ and Other Complete Sets
+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 @@
+Q3773331
@@ Property / cites work: Q3773331 / rank @@
+Normal rank
@@ Property / cites work @@
+The Boolean Hierarchy I: Structural Properties
@@ Property / cites work: The Boolean Hierarchy I: Structural Properties / rank @@
+Normal rank
@@ Property / cites work @@
+The Boolean Hierarchy II: Applications
@@ Property / cites work: The Boolean Hierarchy II: Applications / rank @@
+Normal rank
@@ Property / cites work @@
+The random oracle hypothesis is false
@@ Property / cites work: The random oracle hypothesis is false / rank @@
+Normal rank
@@ Property / cites work @@
+Are there interactive protocols for co-NP languages?
+Normal rank
@@ Property / cites work @@
+Computational Complexity of Probabilistic Turing Machines
+Normal rank
@@ Property / cites work @@
+Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
+Normal rank
@@ Property / cites work @@
+Q3830531
@@ Property / cites work: Q3830531 / rank @@
+Normal rank
@@ Property / cites work @@
+The Knowledge Complexity of Interactive Proof Systems
+Normal rank
@@ Property / cites work @@
+Structural complexity theory: Recent surprises
@@ Property / cites work: Structural complexity theory: Recent surprises / rank @@
+Normal rank
@@ Property / cites work @@
+The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
+Normal rank
@@ Property / cites work @@
+The isomorphism conjecture fails relative to a random oracle
+Normal rank
@@ Property / cites work @@
+Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1016/s0022-0000(05)80084-4
+Normal rank
@@ Property / OpenAlex ID @@
+W2016506875
@@ Property / OpenAlex ID: W2016506875 / rank @@
+Normal rank
@@ Property / DBLP publication ID @@
+journals/jcss/ChangCGHHRR94
@@ Property / DBLP publication ID: journals/jcss/ChangCGHHRR94 / rank @@
+Normal rank