A zero-one law for RP and derandomization of AM if NP is not small (Q2389331): Difference between revisions

← Older edit

@@ Property / DOI @@
-.1016/j.ic.2009.02.002
@@ Property / DOI: 10.1016/j.ic.2009.02.002 / rank @@
-Normal rank
@@ Property / OpenAlex ID @@
+W2122475800
@@ Property / OpenAlex ID: W2122475800 / rank @@
+Normal rank
@@ Property / cites work @@
+Power from Random Strings
@@ Property / cites work: Power from Random Strings / rank @@
+Normal rank
@@ Property / cites work @@
+Q4370034
@@ Property / cites work: Q4370034 / rank @@
+Normal rank
@@ Property / cites work @@
+FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
+Normal rank
@@ Property / cites work @@
+In search of an easy witness: Exponential time vs. probabilistic polynomial time.
+Normal rank
@@ Property / cites work @@
+Easiness assumptions and hardness tests: Trading time for zero error
+Normal rank
@@ Property / cites work @@
+Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses
+Normal rank
@@ Property / cites work @@
+Randomness conservation inequalities; information and independence in mathematical theories
+Normal rank
@@ Property / cites work @@
+Derandomizing Arthur-Merlin games under uniform assumptions
+Normal rank
@@ Property / cites work @@
+Almost everywhere high nonuniform complexity
@@ Property / cites work: Almost everywhere high nonuniform complexity / rank @@
+Normal rank
@@ Property / cites work @@
+Observations on measure and lowness for \(\Delta_ 2^ p\)
+Normal rank
@@ Property / cites work @@
+Q4359463
@@ Property / cites work: Q4359463 / rank @@
+Normal rank
@@ Property / cites work @@
+The zero-one law holds for BPP
@@ Property / cites work: The zero-one law holds for BPP / rank @@
+Normal rank
@@ Property / cites work @@
+Baire categories on small complexity classes and meager-comeager laws
+Normal rank
@@ Property / cites work @@
+Martingale families and dimension in P
@@ Property / cites work: Martingale families and dimension in P / rank @@
+Normal rank
@@ Property / cites work @@
+Q4298260
@@ Property / cites work: Q4298260 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4231907
@@ Property / cites work: Q4231907 / rank @@
+Normal rank
@@ Property / DOI @@
+.1016/J.IC.2009.02.002
@@ Property / DOI: 10.1016/J.IC.2009.02.002 / rank @@
+Normal rank
@@ Property / Recommended article @@
+Q2753664
@@ Property / Recommended article: Q2753664 / rank @@
+Normal rank
@@ Property / Recommended article: Q2753664 / qualifier @@
+Similarity Score: 0.8365187Amount 0.8365187
Unit 1
-Amount
+.8365187
 Unit
@@ Property / Recommended article: Q2753664 / qualifier @@
+Recommender Run: Recommender Run 3
@@ Property / Recommended article @@
+On uniform amplification of hardness in NP
+Normal rank
+Similarity Score: 0.8228416Amount 0.8228416
Unit 1
-Amount
+.8228416
 Unit
+Recommender Run: Recommender Run 3
@@ Property / Recommended article @@
+A Note on Randomized Polynomial Time
@@ Property / Recommended article: A Note on Randomized Polynomial Time / rank @@
+Normal rank
+Similarity Score: 0.82142687Amount 0.82142687
Unit 1
-Amount
+.82142687
 Unit
+Recommender Run: Recommender Run 3
@@ Property / Recommended article @@
+On circuit lower bounds from derandomization
+Normal rank
+Similarity Score: 0.8161593Amount 0.8161593
Unit 1
-Amount
+.8161593
 Unit
+Recommender Run: Recommender Run 3
@@ Property / Recommended article @@
+Q4938630
@@ Property / Recommended article: Q4938630 / rank @@
+Normal rank
@@ Property / Recommended article: Q4938630 / qualifier @@
+Similarity Score: 0.8139262Amount 0.8139262
Unit 1
-Amount
+.8139262
 Unit
@@ Property / Recommended article: Q4938630 / qualifier @@
+Recommender Run: Recommender Run 3
@@ Property / Recommended article @@
+Computing and Combinatorics
@@ Property / Recommended article: Computing and Combinatorics / rank @@
+Normal rank
@@ Property / Recommended article: Computing and Combinatorics / qualifier @@
+Similarity Score: 0.8136638Amount 0.8136638
Unit 1
-Amount
+.8136638
 Unit
@@ Property / Recommended article: Computing and Combinatorics / qualifier @@
+Recommender Run: Recommender Run 3
@@ Property / Recommended article @@
+Q5009542
@@ Property / Recommended article: Q5009542 / rank @@
+Normal rank
@@ Property / Recommended article: Q5009542 / qualifier @@
+Similarity Score: 0.8115761Amount 0.8115761
Unit 1
-Amount
+.8115761
 Unit
@@ Property / Recommended article: Q5009542 / qualifier @@
+Recommender Run: Recommender Run 3
@@ Property / Recommended article @@
+Round Complexity of Common Randomness Generation: The Amortized Setting
+Normal rank
+Similarity Score: 0.80966717Amount 0.80966717
Unit 1
-Amount
+.80966717
 Unit
+Recommender Run: Recommender Run 3
@@ Property / Recommended article @@
+Hardness amplification within NP against deterministic algorithms
+Normal rank
+Similarity Score: 0.808975Amount 0.808975
Unit 1
-Amount
+.808975
 Unit
+Recommender Run: Recommender Run 3
@@ Property / Recommended article @@
+Relative to a random oracle, NP is not small
+Normal rank
+Similarity Score: 0.8084966Amount 0.8084966
Unit 1
-Amount
+.8084966
 Unit
+Recommender Run: Recommender Run 3