Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity (Q3297821): Difference between revisions

@@ Property / author @@
-Eric W. Allender
@@ Property / author: Eric W. Allender / rank @@
-Normal rank
@@ Property / author @@
+Eric W. Allender
@@ Property / author: Eric W. Allender / rank @@
+Normal rank
@@ 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-030-41672-0_2
+Normal rank
@@ Property / OpenAlex ID @@
+W3007294200
@@ Property / OpenAlex ID: W3007294200 / rank @@
+Normal rank
@@ Property / cites work @@
+Some consequences of the existnce of pseudorandom generators
+Normal rank
@@ Property / cites work @@
+The new complexity landscape around circuit minimization
+Normal rank
@@ Property / cites work @@
+Reductions to the set of random strings: The resource-bounded case
+Normal rank
@@ Property / cites work @@
+Power from Random Strings
@@ Property / cites work: Power from Random Strings / rank @@
+Normal rank
@@ Property / cites work @@
+Zero knowledge and circuit minimization
@@ Property / cites work: Zero knowledge and circuit minimization / rank @@
+Normal rank
@@ Property / cites work @@
+Minimum Circuit Size, Graph Isomorphism, and Related Problems
+Normal rank
@@ Property / cites work @@
+New Insights on the (Non-)Hardness of Circuit Minimization and Related Problems
+Normal rank
@@ Property / cites work @@
+The minimum oracle circuit size problem
@@ Property / cites work: The minimum oracle circuit size problem / rank @@
+Normal rank
@@ Property / cites work @@
+The non-hardness of approximating circuit size
@@ Property / cites work: The non-hardness of approximating circuit size / rank @@
+Normal rank
@@ Property / cites work @@
+The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
+Normal rank
@@ Property / cites work @@
+Kolmogorov complexity and degrees of tally sets
@@ Property / cites work: Kolmogorov complexity and degrees of tally sets / rank @@
+Normal rank
@@ Property / cites work @@
+Computational depth: Concept and applications
@@ Property / cites work: Computational depth: Concept and applications / rank @@
+Normal rank
@@ Property / cites work @@
+Reductions to sets of low information content
@@ Property / cites work: Reductions to sets of low information content / rank @@
+Normal rank
@@ Property / cites work @@
+Q4281491
@@ Property / cites work: Q4281491 / rank @@
+Normal rank
@@ Property / cites work @@
+How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
+Normal rank
@@ Property / cites work @@
+On Languages with Very High Space-Bounded Kolmogorov Complexity
+Normal rank
@@ Property / cites work @@
+Resource-Bounded Kolmogorov Complexity Revisited
@@ Property / cites work: Resource-Bounded Kolmogorov Complexity Revisited / rank @@
+Normal rank
@@ Property / cites work @@
+An excursion to the Kolmogorov random strings
@@ Property / cites work: An excursion to the Kolmogorov random strings / rank @@
+Normal rank
@@ Property / cites work @@
+On the inference of optimal descriptions
@@ Property / cites work: On the inference of optimal descriptions / rank @@
+Normal rank
@@ Property / cites work @@
+Algorithmic Randomness and Complexity
@@ Property / cites work: Algorithmic Randomness and Complexity / rank @@
+Normal rank
@@ Property / cites work @@
+Q3976035
@@ Property / cites work: Q3976035 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5091223
@@ Property / cites work: Q5091223 / rank @@
+Normal rank
@@ Property / cites work @@
+Kolmogorov characterizations of complexity classes
+Normal rank
@@ Property / cites work @@
+Q5111137
@@ Property / cites work: Q5111137 / rank @@
+Normal rank
@@ Property / cites work @@
+On the NP-Completeness of the Minimum Circuit Size Problem.
+Normal rank
@@ Property / cites work @@
+Q3862379
@@ Property / cites work: Q3862379 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5875732
@@ Property / cites work: Q5875732 / rank @@
+Normal rank
@@ Property / cites work @@
+Circuit minimization problem
@@ Property / cites work: Circuit minimization problem / rank @@
+Normal rank
@@ Property / cites work @@
+On the notion of infinite pseudorandom sequences
@@ Property / cites work: On the notion of infinite pseudorandom sequences / rank @@
+Normal rank
@@ Property / cites work @@
+On the Complexity of Learning Minimum Time-Bounded Turing Machines
+Normal rank
@@ Property / cites work @@
+Q4727431
@@ Property / cites work: Q4727431 / rank @@
+Normal rank
@@ Property / cites work @@
+Randomness conservation inequalities; information and independence in mathematical theories
+Normal rank
@@ Property / cites work @@
+An introduction to Kolmogorov complexity and its applications
+Normal rank
@@ Property / cites work @@
+Weak lower bounds on resource-bounded compression imply strong separations of complexity classes
+Normal rank
@@ Property / cites work @@
+Q5368903
@@ Property / cites work: Q5368903 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5111148
@@ Property / cites work: Q5111148 / rank @@
+Normal rank
@@ Property / cites work @@
+Hardness magnification near state-of-the-art lower bounds
+Normal rank
@@ Property / cites work @@
+Instance complexity
@@ Property / cites work: Instance complexity / rank @@
+Normal rank
@@ Property / cites work @@
+An information-theoretic approach to time bounds for on-line computation
+Normal rank
@@ Property / cites work @@
+Computational limitations on learning from examples
+Normal rank
@@ Property / cites work @@
+The minimum consistent DFA problem cannot be approximated within any polynomial
+Normal rank
@@ Property / cites work @@
+Discrete logarithm and minimum circuit size
@@ Property / cites work: Discrete logarithm and minimum circuit size / rank @@
+Normal rank
@@ Property / cites work @@
+A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:3297821