39 citations · 89 across the 17 of their papers we have counts for
21 papers
Randomness Conservation Inequalities; Information and Independence in Mathematical Theories
Leonid A. Levin
The article develops further Kolmogorov's Algorithmic Complexity Theory. The definition of Randomness is modified to satisfy strong invariance properties (conservation inequalities…
How do humans succeed in tasks like proving Fermat's Theorem or predicting the Higgs boson?
Leonid A. Levin
I discuss issues of inverting feasibly computable functions, optimal discovery algorithms, and the constant overheads in their performance.
Gacs-Kucera Theorem
Leonid A. Levin
Gacs-Kucera Theorem, tightened by Barmpalias and Lewis-Pye, w.t.t.-reduces each infinite sequence to a Kolmogorov--Martin-Lof random one and is broadly used in various Math and CS…
Climbing LP Algorithms
Leonid A. Levin
NP (search) problems allow easy correctness tests for solutions. Climbing algorithms allow also easy assessment of how close to yielding the correct answer is the configuration at…
Fundamentals of Computing
Leonid A. Levin
These are notes for the course CS-172 I first taught in the Fall 1986 at UC Berkeley and subsequently at Boston University. The goal was to introduce the undergraduates to basic co…
Assumptions of Randomness in Cosmology Models
Leonid A. Levin
Non-compact symmetries cannot be fully broken by randomness since non-compact groups have no invariant probability distributions. In particular, this makes trickier the "Copernican…