Leonid A. Levin. Papers.

• [DAN] DAN SSSR (Proceedings of National Academy of Sciences) = Soviet Mathematics Doklady.
• [PPI] Problemy Peredachi Informatsii = Problems of Information Transmission.
• [FOCS] Proceedings of the Annual IEEE Symposium on Foundations of Computer Science.
• [STOC] Proceedings of the Annual ACM Symposium on Theory of Computing.
• Some Syntactic Theorems on the Finite Problems Calculus of Ju.T. Medvedev, [DAN], 185(1):32-33, 1969.
  Completeness, syntactic characterization, other results on a model of intuitionistic propositional logic.
• A.K.Zvonkin, Leonid A.Levin. (Cyrillic alphabetic order.) The Complexity of finite objects and the Algorithmic Concepts of Information and Randomness. UMN = Russian Math. Surveys 25(6):83-124, 1970.
  The first systematic development of Kolmogorov's Algorithmic approach to information theory and foundations of probability theory based on the concepts of complexity, randomness, a priori probability and information.
• [diss] Some Theorems on the Algorithmic Approach to Probability Theory and Information Theory, Dissertation in Mathematics, Moscow, 1971 (in Russian). The main results are also described in [Zvonkin Levin].
• On the Concept of a Random Sequence. [DAN] 14(5):1413-1416, 1973 (a).
  Bounded ratio of the universal measure to the probability (or difference of length and complexity) of sequence segments is the strongest effective probabilistic law.
• On Storage Capacity for Algorithms. [DAN] 14(5):1464-1466, 1973 (b). Follow-up: Complexity of Functions Computation, in Complexity of Computations and Algorithms, Ed. Kosmidiadi, Maslov and Petri, Mir, Moscow, 1974, 174-185. In Russian; partial English translation in Theor.Comp.Sci, 157.
  The class of space (or time) resources needed by various algorithms computing the same predicate may be complicated. A complete characterization of such classes is given, including the strongest generalizations of the "Speed-up" and "Compression" Theorems.
• Universal Search Problems. [PPI] 9(3):265-266, 1973 (c). (submitted: 1972, reported in talks: 1971). In Russian; English translation in: B.A.Trakhtenbrot. A Survey of Russian Approaches to Perebor (Brute-force Search) Algorithms. Annals of the History of Computing 6(4):384-400, 1984.
  The concept of a universal search problem is introduced (and applied to several known problems) practically equivalent to the concept of NP-completeness, independently developed in U.S. by S. Cook and R. Karp. Also the existence of an optimal (impossible to speed-up) algorithm is shown for any function inverting (constructive NP) problem.
• Laws of Information Conservation (Non-growth) and Aspects of the Foundations of Probability Theory, [PPI] 10(3):206-210, 1974.
  Algorithmic Information has strong invariance properties. Bounded information in a random sequence about a given one is a very general probabilistic law. Combined with the Law of Randomness (see [Levin 1973a]) they imply all other probabilistic laws (not only effective ones), which makes algorithmic and classical foundations of probability equivalent.
• Uniform Tests of Randomness. [DAN] 17(2):337-340, 1976 (a).
  Topological Sperner Lemma is used to prove randomness conservation inequalities that allow to generalize the concept of randomness to include other concepts like information in a uniform way.
• Various Measures of Complexity for Finite Objects (Axiomatic Descriptions). [DAN] 17(2):522-526, 1976 (b).
  A big variety of complexity measures is systematized by linking them with appropriate Banach spaces. This uniform approach allows to distinguish two Complexity measures with a remarkable role.
• On the Principle of Information Conservation in Intuitionistic Mathematics. [DAN] 17:601-605, 1976 (c).
  This principle taken as an axiom scheme in second order intuitionistic arithmetic generates a maximal conservative extension of classical first order arithmetic. This kind of completeness is very unusual in Intuitionism.
• On a Concrete Method of Assigning Complexity Measures. [DAN], 18(3):727-731, 1977.
  The optimal complexity theorem is given in a very general form. A universal algorithmic language is proposed in hope to get small constants for it.
• Leonid A. Levin, V.V.V'yugin. Invariant Properties of Informational Bulks, Lecture Notes on Computer Science, 53, 1977, Springer.
  A set of sequences is [weakly] inaccessible if its complement has measure 0 and is closed under all [total] recursive mappings. Two properties of sequences are [weakly] equivalent if a superset of their symmetric difference is [weakly] inaccessible. There are infinitely many non-equivalent recursively invariant properties, but only four of them are not weakly equivalent.
• P. Gacs, G.L. Kurdiumov, Leonid A. Levin. One-Dimensional Homogeneous Media Dissolving Finite Islands. [PPI] 14(3):223-226, 1978.
  The problem of existence of phase transitions in uniform one dimensional media is addressed. A simple linear array of 2-state automata recovering from any finite distortion is constructed.

Available online (with xdvi or dvips):

• Leonid A. Levin. A General Concept of Independence of Mathematical Objects; Its Applications to Some Problems of Probability Theory, Mathematical Logic and Algorithms Theory. 1979, Dissertation in Mathematics, MIT. Technical Report: A Concept of Independence with Applications in Various Fields of Mathematics, TR-235/MIT/LCS, (1980). A journal version: Randomness Conservation Inequalities. Information and Control 61(1):15-37, 1984.
  Systematic development of algorithmic information theory and its applications based on strong invariance properties.
• Peter Gacs, Leonid A. Levin. Causal Nets or What Is a Deterministic Computation? Information and Control 51(1),1981.
  A uniform finitary approach to various models of computation is proposed. The aim is to make algebraic, geometric and combinatorial considerations convenient in general form. As an example, a group-theoretic criterion is given for the problem of which recursive functions are not computable on objects with symmetry (which cannot be broken deterministically).
• Boris Yamnitsky, Leonid A. Levin. An old linear programming algorithm runs in polynomial time. [FOCS] 1982.
  A version of Ellipsoidal Algorithm, using simplexes instead of ellipsoids was published in 1965 by A.Levin. It was harder to analyze, but we prove that its running time is also polynomial. Our version (simple, flexible and numerically stable) is still the fastest worst-case LP algorithm when the number of inequalities is a large polynomial of the dimension.
• Aki Kanamori, Leonid A. Levin. Championship Format? International Players Chess News, 9(8), 8/26/1985.
• Leonid A. Levin. Average Case Complete Problems. SIAM J.Comput. 15(1):285-286, 1986. Earlier version in [STOC] 1984.
  The first average case intractability result. The Tiling Problem with uniform distribution of instances has no polynomial on average algorithm, unless every NP problem with every simple probability distribution has one.
• Leonid A. Levin. One-Way Functions and Pseudorandom Generators. Combinatorica, 7(4):357-363, 1987. Earlier version in [STOC] 1985.
  A necessary and sufficient condition for the existence of pseudorandom generators.
• Ramarathnam Venkatesan, Leonid A. Levin. Random Instances of a Graph Coloring Problem are Hard. [STOC], 1988 pp.~217-222. arxiv.org/abs/cs.CC/0112001
• Oded Goldreich, Leonid A. Levin. A Hard-Core Predicate for all One-Way Functions. [STOC] pp. 25-32, 1989.
  [Blum Micali 82] discovered permutations f with "hard-core" predicates b(x) which cannot be efficiently guessed from f(x) with a noticeable correlation. Both b,f are easy to compute. [Yao 82] modifies any one-way permutation f into f* , which has a hard-core predicate. Its security may be lower than any constant power of the security of f and is too small for practical applications. We prove that most linear predicates are hard-cores for every one-way function and have the same, within a polynomial, security. The result extends to multiple (up to the logarithm of security) hidden bits and has wide applicability to pseudorandomness, cryptography, etc.
• Gene Itkis, Leonid A. Levin. Power of Fast VLSI Models is Insensitive to Wires' Thinness. [FOCS] 1989.
  Traditional VLSI models assume wires of constant width, taking most of chip's area, often squaring it. These models also assume switching time depending only on chip's diameter D, even if no wires are longer than d << D. Later models allow switching time f(d) to decrease with d (e.g., linearly, or even quadratically.) We show that for superlinear (even slightly) f, the chips' computing power loses any sensitivity to wires width. It is as strong as it would be if wires' were infinitesimally thin, all area used for nodes. We simulate such wires by arranging cooperation of nodes to transport data to each other in parallel so that no delays could occur even in the worst case.
• O.Goldreich, R.Impagliazzo, Leonid A. Levin, R.Venkatesan, D.Zuckerman. Security Preserving Amplification of Hardness. [FOCS] 1990, pp. 318-326.
  We transform any regular (e.g., 1-1) weak one-way function (hard to invert on a polynomial fraction of the range) into a strong one (easy to invert only on a negligible fraction). The use of random walks on constructive expanders allows to preserve security (running-time of inverting algorithms).
• R.Impagliazzo, Leonid A. Levin . No Better Ways to Generate Hard NP Instances than Picking Uniformly at Random. [FOCS] 1990, pp. 812-821.
  Every NP problem with a samplable distribution of instances reduces to one with a polynomial time distribution preserving the randomness of instances. This rather surprising observation makes the concept of average case NP completeness robust and the question of the average case complexity of complete distributional NP problems a natural alternative to P=?NP. Similar techniques yield equivalence of existence of universal extrapolation methods to non-existence of one-way functions: universal learning is possible precisely when cryptography is not.
• Shafi Goldwasser, Leonid A. Levin. Fair Computation of General Functions in Presence of Immoral Majority. Annual CRYPTO Conference (IEEE/LACR) St.Barbara, August 1990 (Proc. 1991).
  Any partial information game (with trusted arbitrator) is modified in a polynomial time into an equivalent full information game (no trusted parties). Private, broadcasting, and oblivious-transfer channels are used as primitives. Unlike predecessors, we assume neither honest majority of players nor boolean output nor polynomial chance of successful cheating.
• L.Babai, L.Fortnow, Leonid A. Levin, M.Szegedy. Checking computations in polylogarithmic time. [STOC] 1991, pp. 21-31.
  Any computation or mathematical proof can be put in a transparent or holographic form in nearly linear time. Proofs in this form can be verified instantly (in polylogarithmic Monte-Carlo time), using random access to the proof, to the proven statement (or input/output of computation) in error-correcting code, and to the source of coin-flips.
• Leonid A. Levin. Randomness and Nondeterminism; J.Symb.Logic, 58(3):1102-1103, 1993.
  A less technical version in International Congress of Mathematicians, (Zurich, 8/1994) Proc. v2 (Invited 45 Minute Addresses) . pp.1418-1419. Birkhauser Verlag, 1995.
  All one-way functions have hidden bits with the same security.
• Leonid A. Levin. Computational Complexity of Functions. Theoretical Computer Science, 157:267-271, 1996.
  Partial translation from [Levin 72(b)] with extensions in the Appendix.
• Gene Itkis, Leonid A. Levin. Fast and Lean Self-Stabilizing Asynchronous Protocols. [FOCS] 1994. Also invited ICALP Sunday Tutorial Lecture, 7/10/1994.
  All protocols can be efficiently made self-stabilizing and immune to asynchrony on any network even with constant memory per node, and worst-case dynamic faults.
• Oded Goldreich, Leonid A. Levin, Noam Nisan. On Constructing 1-1 One-Way Functions. ECCC TR-95-029, 6/15/95.
• Fundamentals of Computing. SIGACT News; Education Forum. Special 100-th issue, 27(3):89-110, 1996.
  Lecture notes on the Theory of Computation course.
• Leonid A. Levin. The Century of Bread and Circus. Tax Notes, 77(7):858-860, 11/17/1997.
  Analysis of the proportions between taxation and representation.
• Leonid A. Levin. Robust Measures of Information. The Computer Journal 42(4):284-286, 1999.
  The usual (i.e., easily computable) probability distributions share a remarkable feature. They are concentrated on strings which do not differ noticeably in any robust characteristic, except informational size (Kolmogorov complexity). The formalization of this statement (below) distinguishes a class of homogeneous probability measures suggesting various applications. In particular, it may explain why the average case NP-completeness results are so measure-independent and may lead to their generalization to this wider and more invariant class of measures. It also demonstrates a sharp difference between the pseudorandom strings and the objects known before.
• Leonid A. Levin. Holographic Proof. Encyclopaedia of Mathematics, Supplement II, Kluwer Acad. Publ, 1999. http://eom.springer.de/H/h120100.htm
• Johan Hastad, Russell Impagliazzo, Leonid A. Levin, Michael Luby. A Pseudorandom Generator from any One-way Function. SICOMP 28(4):1364-1396, 1999. (Awarded an "Outstanding Paper Prize" of the Society for Industrial and Applied Mathematics in 2003.)
• Leonid A. Levin. Self-stabilization of Circular Arrays of Automata. Theor. Comp. Sci., 235(1):143-144, 3/17/2000.
• Leonid A. Levin. The Equity Tax and Shelter. (Tax Analysts' Special Report.) Tax Notes 93(9):1203-1208, 11/26/2001.
• Leonid A. Levin. The Tale of One-Way Functions. [PPI] 39(1):92-103, 2003.
• Leonid A. Levin. Forbidden Information. Proc. Annual IEEE Symp. on Foundations of Computer Science, 2002. Also in abstracts of the plenary addresses to the annual meeting of Assoc. of Symbolic Logic (6/1-4 2003, Chicago IL): The Bulletin of Symbolic Logic 10(1):123, 2004, and in Proc. International conf. "Kolmogorov and Contemporary Mathematics", Moscow, June 16 - 21 2003.
• Jeffrey Considine, Matthias Fitzi, Matthew Franklin, Leonid A.~Levin, Ueli Maurer, David Metcalf. Byzantine Agreement Given Partial Broadcast. Journal of Cryptology 18(3):191-217, 2005.
• Leonid A. Levin. Aperiodic Tilings: Breaking Translational Symmetry. The Computer Journal, 48(6):642-645, 2005. On-line: Abstract, or PDF: http://comjnl.oxfordjournals.org/cgi/reprint/48/6/642.pdf?ijkey=5C13chAXDStNPEU&keytype=ref .
• Leonid A. Levin. Kolmogorov Glazami Shkolnika i Studenta. Колмогоров Глазами Школьника и Студента. In: ISBN 5-94057-198-0. A.N.Shiryaev, ed. Kolmogorov v Vospominaniyah Uchenikov. Sbornik Statey. 472 pages. Колмогоров в Воспоминаниях Учеников. Moscow, Nauka (MCNMO). 2006.
• Gene Itkis, Leonid A. Levin. Flat Holonomies on Automata Networks. A plenary address at the 23rd International Symposium on Theoretical Aspects of Computer Science (STACS, Marseille, Feb. 23-25 2006, Proc.). An updated on-line version: http://arXiv.org/abs/cs.DC/0512077 .
  We consider asynchronous dynamic networks of identical finite (independent of the network size) automata. A useful data structure on such networks is a partial orientation of its edges. It needs to be straight, i.e., have null holonomy (the difference between the number of up and down edges in each cycle). It also needs to be centered, have a unique node with no down edges. Using such orientation, any feasible computational task can be efficiently implemented with self-stabilization and synchronization. There are (interdependent) self- stabilizing asynchronous finite automata protocols assuring straight and centered orientation. Such protocols may vary in assorted efficiency parameters and it is desirable to have each replaceable with any alternative, responsible for a simple limited task. We describe an efficient reduction of any computational task to any such set of protocols compliant with our interface conditions.
• Leonid A. Levin. The Grace of Quadratic Norms: Some Examples. In Pillars of Computer Science . Arnon Avron, Nachum Dershowitz, and Alexander Rabinovich, eds. Lecture Notes in Computer Science, v. 4800, pp. 457-459. Springer-Verlag, Berlin Heidelberg, 2008.
• Bruno Durand, Leonid A. Levin, Alexander Shen. Complex Tilings. J.Symb.Logic, 73/2:593-613, 2008.