Leonid A. Levin

I&C Journal 2025 Journal Article

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” random choice of the place of the observer in infinite cosmology models. This problem may be circumvented with what topologists call pointed spaces. Then randomness will be used only in building (infinite) models around the pre-designated “observance point”, that thus would not need to be randomly chosen. Additional complications come from the original randomness possibly being hidden. P. Gacs and A. Kucera proved that every sequence can be algorithmically generated from a random one. But Vladimir V'yugin discovered that randomized algorithms can with positive probability generate uncomputable sequences not algorithmically equivalent to any random ones.

TCS Journal 2022 Journal Article

Gacs – Kucera theorem

• Leonid A. Levin

Gacs – Kucera Theorem [2, 3, 5], tightened by Barmpalias, Lewis-Pye [1], w. t. t. -reduces each infinite sequence to a Kolmogorov – Martin-Lof random one and is broadly used in various Math and CS areas. Its early proofs are somewhat cumbersome, but using some general concepts yields significant simplification illustrated below.

STOC Conference 2021 Invited Paper

Climbing algorithms (invited talk)

• Leonid A. Levin

FOCS Conference 2012 Conference Paper

Rarity for Semimeasures

• Leonid A. Levin

The notion of Kolmogorov-Martin-Lof Random sequences is extended from computable to enumerable distributions. This allows definitions of various other properties, such as mutual information in infinite sequences. Enumerable distributions (as well as distributions faced in some finite multi-party settings) are semi measures, handling those requires care.

FOCS Conference 2002 Conference Paper

Forbidden Information

• Leonid A. Levin

There appears to be a gap between usual interpretations of Godel Theorem and what is actually proven. Closing this gap does not seem obvious and involves complexity theory. (This is unrelated to, well studied before, complexity quantifications of the usual Godel effects.) Similar problems and answers apply to other unsolvability results for tasks where required solutions are not unique, such as, e. g. , non-recursive tilings.

STOC Conference 2001 Conference Paper

Complex tilings

• Bruno Durand 0001
• Leonid A. Levin
• Alexander Shen 0001

We study the minimal complexity of tilings of a plane with a given tile set. We note that any tile set admits either no tiling or some tiling with \ooo( n ) Kolmogorov complexity of its ( n\times n )-squares. We construct tile sets for which this bound is nearly tight: all tilings have complexity > n/r(n) , given any unbounded computable monotone r . This adds a quantitative angle to classical results on non-recursivity of tilings -- that we also develop in terms of Turing degrees of unsolvability.

TCS Journal 2000 Journal Article

Self-stabilization of circular arrays of automata

• Leonid A. Levin

TCS Journal 1996 Journal Article

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 [9] (see also [6]). Earlier relevant work (classical theorems like Compression, Speed-up, etc.) was done in [15, 13, 2, 1, 14, 7]. I translated only the part with the statement of the results. Instead of the proof part, I appended a later (1979, unpublished) proof sketch of a slightly tighter version. The improvement is based on the results of Meyer and Winklmann [8] and Sipser [12]. Meyer and Winklmann extended earlier versions to machines with a separate input and working tape, thus allowing complexities smaller than the input length (down to its log). Sipser showed the space-bounded Halting Problem to require only additive constant overhead. The proof in the appendix below employs both advances to extend the original proofs to machines with a fixed alphabet and a separate input and working space. The extension has no (even logarithmic) restrictions on complexity and no overhead (beyond an additive constant). The sketch is very brief and a more detailed exposition is expected later [11].

FOCS Conference 1994 Conference Paper

Fast and Lean Self-Stabilizing Asynchronous Protocols

• Gene Itkis
• Leonid A. Levin

We consider asynchronous general topology dynamic networks of identical nameless nodes with worst-case transient faults. Starting from any faulty configuration, our protocols self-stabilize any computation in time polynomial in the (unknown) network diameter. This version sacrifices some diversity of tasks and efficiency for simplicity and clarity of details. Appendix gives more efficient procedures in less detail. >

STOC Conference 1991 Conference Paper

Checking Computations in Polylogarithmic Time

• László Babai
• Lance Fortnow
• Leonid A. Levin
• Mario Szegedy

FOCS Conference 1990 Conference Paper

No Better Ways to Generate Hard NP Instances than Picking Uniformly at Random

• Russell Impagliazzo
• Leonid A. Levin

Distributed NP (DNP) problems are ones supplied with probability distributions of instances. It is shown that every DNP problem complete for P-time computable distributions is also complete for all distributions that can be sampled. This result makes the concept of average-case NP completeness robust and the question of the average-case complexity of complete DNP problems a natural alternative to P=? NP. Similar techniques yield a connection between cryptography and learning theory.

FOCS Conference 1990 Conference Paper

Security Preserving Amplification of Hardness

• Oded Goldreich 0001
• Russell Impagliazzo
• Leonid A. Levin
• Ramarathnam Venkatesan
• David Zuckerman

The task of transforming a weak one-way function (which may be easily inverted on all but a polynomial fraction of the range) into a strong one-way function (which can be easily inverted only on a negligible function of the range) is considered. The previously known transformation does not preserve the security (i. e. the running time of the inverting algorithm) within any polynomial. Its resulting function, F(x), applies the weak one-way function to many small (of length mod x mod /sup theta /, theta >

STOC Conference 1989 Conference Paper

A Hard-Core Predicate for all One-Way Functions

• Oded Goldreich 0001
• Leonid A. Levin

FOCS Conference 1989 Conference Paper

Power of Fast VLSI Models Is Insensitive to Wires' Thinness

• Gene Itkis
• Leonid A. Levin

VLSI f-models which allow the switching time to decrease to f(D) when the length of all wires is restricted by D are called 'fast' if the decrease is slightly superlinear. The fast models are so strong and robust that their computational power cannot be increased by and combination of the following: (1) making zero the width of each wire of length d, except for its log d segment, thus eliminating layout and area considerations; (2) allowing wires to transmit log d bits simultaneously; (3) making the switching time f(d) of each node depend only on the length d of its own input wires, thus enabling small subcircuits to run faster; (4) changing f while preserving Sigma /sub k/ 1/f(k); (5) enabling the nodes to change connections arbitrarily in the run time. The authors construct a kind of operating system link server (linx, for short) that simulates all these powers online. The condition of superlinearity cannot be weakened. >

STOC Conference 1989 Conference Paper

Pseudo-random Generation from one-way functions (Extended Abstracts)

• Russell Impagliazzo
• Leonid A. Levin
• Michael Luby

FOCS Conference 1988 Conference Paper

Homogeneous Measures and Polynomial Time Invariants

• Leonid A. Levin

The usual probability distributions are concentrated on strings that do not differ noticeably in any fundamental characteristics, except their informational size (Kolmogorov complexity). The formalization of this statement is given and shown to distinguish a class of homogeneous probability measures suggesting various applications. In particular, it could explain why the average case NP-completeness results are so measure-independent and could lead to their generalization to this wider and more invariant class of measures. It also demonstrates a sharp difference between recently discovered pseudorandom strings and the objects known before. >

STOC Conference 1988 Conference Paper

Random Instances of a Graph Coloring Problem Are Hard

• Ramarathnam Venkatesan
• Leonid A. Levin

NP-complete problems should be hard on some (may be extremely rare) instances. But on generic instances many such problems (especially related to random graphs) have been proven easy. We show the intractability of random instances of a graph coloring problem by modifying the NP-completeness theorem.

STOC Conference 1985 Conference Paper

One-Way Functions and Pseudorandom Generators

• Leonid A. Levin

One-way are those functions which are easy to compute, but hard to invert on a non-negligible fraction of instances. The existence of such functions with some additional assumptions was shown to be sufficient for generating perfect pseudorandom strings |Blum, Micali 82|, |Yao 82|, |Goldreich, Goldwasser, Micali 84|. Below, among a few other observations, a weaker assumption about one-way functions is suggested, which is not only sufficient, but also necessary for the existence of pseudorandom generators. The main theorem can be understood without reading the sections 3-6.

STOC Conference 1984 Conference Paper

Problems, Complete in "Average" Instance

• Leonid A. Levin

Many interesting combinatorial problems were found to be NP-complete. Since there is little hope to solve them fast in the worst case, researchers look for algorithms which are fast just “on average”. This matter is sensitive to the choice of a particular NP-complete problem and a probability distribution of its instances. Some of these tasks were easy and some not. But one needs a way to distinguish the “difficult on average” problems. Such negative results could not only save “positive” efforts but may also be used in areas (like cryptography) where hardness of some problems is a frequent assumption. A concept of “NP-complete random problems” proposed below may serve this purpose.

FOCS Conference 1982 Conference Paper

An Old Linear Programming Algorithm Runs in Polynomial Time

• Boris Yamnitsky
• Leonid A. Levin

The Ellipsoid Algorithm (EA) for linear programming attracted recently great attention. EA was proposed in [N76] and developed in [K79, G81] and other works. It is a modification of Method of Centralized Splitting presented in [L65], which differs from EA in two essential respects. Firstly, [L65] uses simplexes instead of ellipsoids; it is admitted, secondly, that, several (q(n))splittings of the n-dimensional simplex may be needed before the remaining polyhedron can be enclosed into a simplex of a smaller volume. Only a very rough upper bound q(n) ≪ nlog(n)follows from the reasoning of [L65]. This does not imply polynomiality of the computation time, since n, log(n) splittings may make the simplex very complex. We prove below that, q(n)= 1. Let the problem be to find x∈Rn such that Ax ≫ 0, where A is an m × n matrix of rank n. We normalize solutions by a restriction (e - Ax) = 1 where e ≫ 0. On every step the algorithm considers a simplex BAx ≥ 0 containing all solutions, where B is a non-negative n × m matrix with det(BA) ≠ 0. Let us denote this simplex by ΔB, its volume by VB and its center by CB. Initially we take an arbitrary B and e = BT(1, .. ,1).

MFCS Conference 1977 Conference Paper

Invariant Properties of Informational Bulks

• Leonid A. Levin
• V. V. V'jugin