Fetching the paper…
Reading the bibliography…
Diverse applications of Kolmogorov complexity to learning [CIKK16], circuit complexity [OPS19], cryptography [LP20], average-case complexity [Hir21], and proof search [Kra22] have been discovered in recent years.
A complexity theoretic approach to randomness
Michael Sipser · 1983
Earlier work this paper cites.
Randomness conservation inequalities; information and independence in mathematical theories
Leonid A. Levin · 1984
Earlier work this paper cites.
Computing π \pi (x): An analytic method
Jeffrey C. Lagarias and Andrew M. Odlyzko · 1987
Earlier work this paper cites.
On the complexity of learning minimum time-bounded Turing machines
Ker-I Ko · 1991
Earlier work this paper cites.
Applications of time-bounded Kolmogorov complexity in complexity theory
Eric Allender · 1992
Earlier work this paper cites.
Average-case complexity under the universal distribution equals worst-case complexity
Ming Li and Paul M. B. Vitányi · 1992
Earlier work this paper cites.
An Introduction to Computational Learning Theory
Michael J. Kearns and Umesh V. Vazirani · 1994
Earlier work this paper cites.
P = BPP if E requires exponential circuits: Derandomizing the XOR lemma
Russell Impagliazzo and Avi Wigderson · 1997
Earlier work this paper cites.
Natural proofs
Alexander A. Razborov and Steven Rudich · 1997
Earlier work this paper cites.
Computational depth
Luis Antunes, Lance Fortnow, and Dieter van Melkebeek · 2001
Earlier work this paper cites.
When worlds collide: Derandomization, lower bounds, and Kolmogorov complexity
Eric Allender · 2001
Earlier work this paper cites.
On the complexity of k k -SAT
Russell Impagliazzo and Ramamohan Paturi · 2001
Earlier work this paper cites.
PRIMES is in P
Manindra Agrawal, Neeraj Kayal, and Nitin Saxena · 2002
Earlier work this paper cites.
A probabilistic-time hierarchy theorem for “slightly non-uniform” algorithms
Boaz Barak · 2002
Earlier work this paper cites.
Kolmogorov complexity and computational complexity
Lance Fortnow · 2004
Earlier work this paper cites.
Hierarchy theorems for probabilistic polynomial time
Lance Fortnow and Rahul Santhanam · 2004
Earlier work this paper cites.
Some results on derandomization
Harry Buhrman, Lance Fortnow, and Aduri Pavan · 2005
Earlier work this paper cites.
Language compression and pseudorandom generators
Harry Buhrman, Troy Lee, and Dieter van Melkebeek · 2005
Earlier work this paper cites.
Power from random strings
Eric Allender, Harry Buhrman, Michal Koucký, Dieter van Melkebeek, and Detlef Ronneburger · 2006
Earlier work this paper cites.
Average-case complexity
Andrej Bogdanov and Luca Trevisan · 2006
Earlier work this paper cites.
Kolmogorov complexity and formula lower bounds
Troy Lee · 2006
Earlier work this paper cites.
Worst-case running times for average-case algorithms
Luis Antunes and Lance Fortnow · 2009
Cited alongside, same era.
Probabilistic search algorithms with unique answers and their cryptographic applications
Eran Gat and Shafi Goldwasser · 2011
Cited alongside, same era.
The complexity of explicit constructions
Rahul Santhanam · 2012
Cited alongside, same era.
Deterministic methods to find primes
Terence Tao, Ernest Croot, III, and Harald Helfgott · 2012
Cited alongside, same era.
The equivalence of sampling and searching
Scott Aaronson · 2014
Cited alongside, same era.
Time hierarchies for sampling distributions
Thomas Watson · 2014
Cited alongside, same era.
Learning algorithms from natural proofs
NP-hardness of circuit minimization for multi-output functions
Rahul Ilango, Bruno Loff, and Igor C. Oliveira · 2020
Later among the works it cites.
On one-way functions and Kolmogorov complexity
Yanyi Liu and Rafael Pass · 2020
Later among the works it cites.
Vaughan Jones, Kolmogorov complexity, and the new complexity landscape around circuit minimization
Eric Allender · 2021
Later among the works it cites.
Average-case hardness of NP from exponential worst-case hardness assumptions
Shuichi Hirahara · 2021
Later among the works it cites.
On worst-case learning in relativized heuristica
Shuichi Hirahara and Mikito Nanashima · 2021
Later among the works it cites.
The minimum formula size problem is (ETH) hard
Rahul Ilango · 2021
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, and Antonina Kolokolova · 2016
Cited alongside, same era.
The complexity of complexity
Eric Allender · 2017
Cited alongside, same era.
Conspiracies between learning algorithms, circuit lower bounds, and pseudorandomness
Igor C. Oliveira and Rahul Santhanam · 2017
Cited alongside, same era.
Pseudodeterministic constructions in subexponential time
Igor C. Oliveira and Rahul Santhanam · 2017
Cited alongside, same era.
Kolmogorov Complexity and Algorithmic Randomness
Alexander Shen, Vladimir Andreyevich Uspensky, and Nikolay Vereshchagin · 2017
Cited alongside, same era.
On learning vs. refutation
Salil P. Vadhan · 2017
Cited alongside, same era.
Hardness on any samplable distribution suffices: New characterizations of one-way functions by meta-complexity
Rahul Ilango, Hanlin Ren, and Rahul Santhanam · 2021
Later among the works it cites.
The hardest explicit construction
Oliver Korten · 2021
Later among the works it cites.
An efficient coding theorem via probabilistic representations and its applications
Zhenjian Lu and Igor C. Oliveira · 2021
Later among the works it cites.
Pseudodeterministic algorithms and the structure of probabilistic time
Zhenjian Lu, Igor C. Oliveira, and Rahul Santhanam · 2021
Later among the works it cites.
On the possibility of basing cryptography on EXP ≠ \neq BPP
Yanyi Liu and Rafael Pass · 2021
Later among the works it cites.
Hardness of KT characterizes parallel cryptography
Hanlin Ren and Rahul Santhanam · 2021
Later among the works it cites.
27 open problems in Kolmogorov complexity
Andrei E. Romashchenko, Alexander Shen, and Marius Zimand · 2021
Later among the works it cites.
Average-case hardness of NP and PH from worst-case fine-grained assumptions
Lijie Chen, Shuichi Hirahara, and Neekon Vafa · 2022
Closest in time.
A simpler proof of the worst-case to average-case reduction for polynomial hierarchy via symmetry of information
Halley Goldberg and Valentine Kabanets · 2022
Closest in time.
Probabilistic Kolmogorov complexity with applications to average-case complexity
Halley Goldberg, Valentine Kabanets, Zhenjian Lu, and Igor C. Oliveira · 2022
Closest in time.
Meta-computational average-case complexity: A new paradigm toward excluding heuristica
Shuichi Hirahara · 2022
Closest in time.
Symmetry of information in heuristica
Shuichi Hirahara · 2022
Closest in time.
Errorless versus error-prone average-case complexity
Shuichi Hirahara and Rahul Santhanam · 2022
Closest in time.
Information in propositional proofs and algorithmic proof search
Jan Krajíček · 2022
Closest in time.
Optimal coding theorems in time-bounded Kolmogorov complexity
Zhenjian Lu, Igor C. Oliveira, and Marius Zimand · 2022
Closest in time.