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…
Computational Complexity of Functions
Leonid A. Levin
Below is a translation from my Russian paper. I added references, unavailable to me in Moscow. Similar results have been also given in [Schnorr Stumpf 75] (see also [Lynch 75]). Ea…
Occam Bound on Lowest Complexity of Elements
Leonid A. Levin
The combined universal probability M(D) of strings x in sets D is close to max_{x \in D} M({x}): their ~ logs differ by at most D's information j = I(D:H) about the halting sequenc…
Randomness and Non-determinism
Leonid A. Levin
Exponentiation makes the difference between the bit-size of this line and the number (<< 2^{300}) of particles in the known Universe. The expulsion of exponential time algorithms f…
Enumerable Distributions, Randomness, Dependence
Leonid A. Levin
Mutual information I in infinite sequences (and in their finite prefixes) is essential in theoretical analysis of many situations. Yet its right definition has been elusive for a l…
Sets Have Simple Members
Samuel Epstein, Leonid A. Levin
The combined Universal Probability M(D) of strings x in sets D is close to max M({x}) over x in D: their ~logs differ by at most D's information j=I(D:H) about the halting sequence…
Some Theorems on the Algorithmic Approach to Probability Theory and Information Theory
Leonid A. Levin
This is a 1971 dissertation. Only its extended abstract was published at the time. While some results appeared in other publications, a number of details remained unpublished and m…
Self-stabilization of Circular Arrays of Automata
Leonid A. Levin
[Gacs, Kurdiumov, Levin, 78] proposed simple one-dimensional cellular automata with 2 states. In an infinite array they are self-stabilizing: if all but a finite minority of automa…
Flat Holonomies on Automata Networks
Gene Itkis, Leonid A. Levin
We consider asynchronous networks of identical finite (independent of network's size or topology) automata. Our automata drive any network from any initial configuration of states,…
Aperiodic Tilings: Breaking Translational Symmetry
Leonid A. Levin
Classical results on aperiodic tilings are rather complicated and not widely understood. Below, an alternative approach is discussed in hope to provide additional intuition not app…
Forbidden Information
Leonid A. Levin
Goedel Incompleteness Theorem leaves open a way around it, vaguely perceived for a long time but not clearly identified. (Thus, Goedel believed informal arguments can answer any ma…
An Average Case NP-Complete Graph Coloring Problem
Leonid A. Levin, Ramarathnam Venkatesan
NP-complete problems should be hard on some instances but those may be extremely rare. On generic instances many such problems, especially related to random graphs, have been prove…
Complex Tilings
Bruno Durand, Leonid A. Levin, Alexander Shen
We study the minimal complexity of tilings of a plane with a given tile set. We note that every tile set admits either no tiling or some tiling with O(n) Kolmogorov complexity of i…
Byzantine Agreement with Faulty Majority using Bounded Broadcast
Jeffrey Considine, Leonid A. Levin, David Metcalf
Byzantine Agreement introduced in [Pease, Shostak, Lamport, 80] is a widely used building block of reliable distributed protocols. It simulates broadcast despite the presence of fa…
The Tale of One-way Functions
Leonid A. Levin
The existence of one-way functions is arguably the most important problem in computer theory. The article discusses and refines a number of concepts relevant to this problem. For i…
Taxation and Valuation
Leonid A. Levin
I explain the root of persistent failure of efforts to remove tax-induced distortions of economic incentives. It lies in FUNDAMENTAL IMPOSSIBILITY of objectively evaluating tax bas…