Limits on the Computational Power of Random Strings (Q3012814): 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/978-3-642-22006-7_25
+Normal rank
@@ Property / OpenAlex ID @@
+W190215904
@@ Property / OpenAlex ID: W190215904 / rank @@
+Normal rank
@@ Property / cites work @@
+What can be efficiently reduced to the Kolmogorov-random strings?
+Normal rank
@@ Property / cites work @@
+Power from Random Strings
@@ Property / cites work: Power from Random Strings / rank @@
+Normal rank
@@ Property / cites work @@
+Limits on the computational power of random strings
+Normal rank
@@ Property / cites work @@
+The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
+Normal rank
@@ Property / cites work @@
+\(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
+Normal rank
@@ Property / cites work @@
+On Languages Reducible to Algorithmically Random Languages
+Normal rank
@@ Property / cites work @@
+An observation on probability versus randomness with applications to complexity classes
+Normal rank
@@ Property / cites work @@
+On the robustness of ALMOST-$\mathcal {R}$
@@ Property / cites work: On the robustness of ALMOST-$\mathcal {R}$ / rank @@
+Normal rank
@@ Property / cites work @@
+Limitations of Hardness vs. Randomness under Uniform Reductions
+Normal rank
@@ Property / cites work @@
+Lower Bounds for Reducibility to the Kolmogorov Random Strings
+Normal rank
@@ Property / cites work @@
+Randomness vs time: Derandomization under a uniform assumption
+Normal rank
@@ Property / cites work @@
+Circuit minimization problem
@@ Property / cites work: Circuit minimization problem / rank @@
+Normal rank
@@ Property / cites work @@
+An introduction to Kolmogorov complexity and its applications
+Normal rank
@@ Property / cites work @@
+Kolmogorov entropy in the context of computability theory
+Normal rank
@@ Property / cites work @@
+Theory of Cryptography
@@ Property / cites work: Theory of Cryptography / rank @@
+Normal rank
@@ Property / cites work @@
+Pseudorandomness and average-case complexity via uniform reductions
+Normal rank