Leonid A. Levin

Proceedings of the Stabilization, Safety, and Security of Distributed Systems, 2023

2022

Gacs - Kucera theorem.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2022

How do humans succeed in tasks like proving Fermat's Theorem or predicting the Higgs boson?

[BibT_eX]

[DOI]

CoRR, 2022

On Power Set Axiom.

[BibT_eX]

[DOI]

CoRR, 2022

2021

The Dual Matrix Algorithm for Linear Programming.

[BibT_eX]

[DOI]

CoRR, 2021

Climbing algorithms (invited talk).

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

2020

Fundamentals of Computing.

[BibT_eX]

[DOI]

CoRR, 2020

2018

An Average Case NP-complete Graph Colouring Problem.

[BibT_eX]

[DOI]

Comb. Probab. Comput., 2018

2016

Occam bound on lowest complexity of elements.

[BibT_eX]

[DOI]

Ann. Pure Appl. Log., 2016

2014

Sets Have Simple Members. (repost).

[BibT_eX]

[DOI]

CoRR, 2014

2013

Forbidden information.

[BibT_eX]

[DOI]

J. ACM, 2013

2012

Randomness and Non-determinism

[BibT_eX]

[DOI]

CoRR, 2012

Enumerable Distributions, Randomness, Dependence

[BibT_eX]

[DOI]

CoRR, 2012

Turing's Password: What Internet Cannot Leak.

[BibT_eX]

[DOI]

Proceedings of the 27th Annual IEEE Symposium on Logic in Computer Science, 2012

Rarity for Semimeasures.

[BibT_eX]

[DOI]

Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

2011

Universal Heuristics: How Do Humans Solve "Unsolvable" Problems?

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Probability and Friends. Bayesian Prediction and Artificial Intelligence, 2011

On Constructing 1-1 One-Way Functions.

[BibT_eX]

[DOI]

Noam Nisan

Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

2010

Some Theorems on the Algorithmic Approach to Probability Theory and Information Theory

[BibT_eX]

[DOI]

CoRR, 2010

Some theorems on the algorithmic approach to probability theory and information theory: (1971 Dissertation directed by A.N. Kolmogorov).

[BibT_eX]

[DOI]

Ann. Pure Appl. Log., 2010

Arcane Information, Solving Relations, and Church Censorship.

[BibT_eX]

[DOI]

Proceedings of the Stabilization, Safety, and Security of Distributed Systems, 2010

2008

Complex tilings.

[BibT_eX]

[DOI]

Bruno Durand

Alexander Shen

J. Symb. Log., 2008

The Grace of Quadratic Norms: Some Examples.

[BibT_eX]

[DOI]

Proceedings of the Pillars of Computer Science, 2008

2006

Flat Holonomies on Automata Networks.

[BibT_eX]

[DOI]

Gene Itkis

Proceedings of the STACS 2006, 2006

2005

Byzantine Agreement Given Partial Broadcast.

[BibT_eX]

[DOI]

J. Cryptol., 2005

Notes for Miscellaneous Lectures

[BibT_eX]

[DOI]

CoRR, 2005

Aperiodic Tilings: Breaking Translational Symmetry.

[BibT_eX]

[DOI]

Comput. J., 2005

2003

The Tale of One-Way Functions.

[BibT_eX]

[DOI]

Probl. Inf. Transm., 2003

2001

An Average Case NP-complete Graph Problem

[BibT_eX]

[DOI]

CoRR, 2001

2000

Self-stabilization of circular arrays of automata.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2000

Byzantine Agreement with Faulty Majority using Bounded Broadcast

[BibT_eX]

[DOI]

Jeffrey Considine

David Metcalf

CoRR, 2000

The Equity Tax and Shelter

[BibT_eX]

[DOI]

CoRR, 2000

1999

A Pseudorandom Generator from any One-way Function.

[BibT_eX]

[DOI]

SIAM J. Comput., 1999

Robust Measures of Information.

[BibT_eX]

[DOI]

Comput. J., 1999

1997

Errata to "Fundamentals of Computing".

[BibT_eX]

[DOI]

SIGACT News, 1997

1996

Computational Complexity of Functions.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1996

Fundamentals of computing (a cheatlist).

[BibT_eX]

[DOI]

SIGACT News, 1996

1995

STOC Criteria.

[BibT_eX]

[DOI]

SIGACT News, 1995

On Constructing 1-1 One-Way Functions

[BibT_eX]

[DOI]

Noam Nisan

Electron. Colloquium Comput. Complex., 1995

1994

Fast and Lean Self-Stabilizing Asynchronous Protocols

[BibT_eX]

[DOI]

Gene Itkis

Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

1991

Theory of computation: how to start.

[BibT_eX]

[DOI]

SIGACT News, 1991

Checking Computations in Polylogarithmic Time

[BibT_eX]

[DOI]

Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991

1990

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

[BibT_eX]

[DOI]

Russell Impagliazzo

Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

Security Preserving Amplification of Hardness

[BibT_eX]

[DOI]

Russell Impagliazzo

David Zuckerman

Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

Fair Computation of General Functions in Presence of Immoral Majority.

[BibT_eX]

[DOI]

Shafi Goldwasser

Proceedings of the Advances in Cryptology, 1990

1989

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

[BibT_eX]

[DOI]

Russell Impagliazzo

Michael Luby

Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989

A Hard-Core Predicate for all One-Way Functions

[BibT_eX]

[DOI]

Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989

Power of Fast VLSI Models Is Insensitive to Wires' Thinness

[BibT_eX]

[DOI]

Gene Itkis

Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989

1988

Random Instances of a Graph Coloring Problem Are Hard

[BibT_eX]

[DOI]

Proceedings of the 20th Annual ACM Symposium on Theory of Computing, 1988

Homogeneous Measures and Polynomial Time Invariants

[BibT_eX]

[DOI]

Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988

1987

One-way functions and pseudorandom generators.

[BibT_eX]

[DOI]

Comb., 1987

1986

Average Case Complete Problems.

[BibT_eX]

[DOI]

SIAM J. Comput., 1986

1984

Randomness Conservation Inequalities; Information and Independence in Mathematical Theories

[BibT_eX]

[DOI]

Inf. Control., April, 1984

Problems, Complete in "Average" Instance

[BibT_eX]

[DOI]

Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30, 1984

1982

An Old Linear Programming Algorithm Runs in Polynomial Time

[BibT_eX]

[DOI]

Boris Yamnitsky

Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, 1982

1977

Invariant Properties of Informational Bulks.

[BibT_eX]

[DOI]