Leonid A. Levin

Publication Activity (10 Years)

Years Active: 1977-2023
Publications (10 Years): 10

Top Topics

Algorithm For Linear Programming

Top Venues

Comb. Probab. Comput.

Ann. Pure Appl. Log.

Publications

Leonid A. Levin
Invited Paper: How Do Humans Succeed in Tasks Like Proving Fermat's Theorem or Predicting the Higgs Boson? SSS (2023)
Leonid A. Levin
Gacs-Kucera Theorem. CoRR (2022)
Leonid A. Levin
On Power Set Axiom. CoRR (2022)
Leonid A. Levin
How do humans succeed in tasks like proving Fermat's Theorem or predicting the Higgs boson? CoRR (2022)
Leonid A. Levin
Gacs - Kucera theorem. Theor. Comput. Sci. 929 (2022)
Leonid A. Levin
The Dual Matrix Algorithm for Linear Programming. CoRR (2021)
Leonid A. Levin
Climbing algorithms (invited talk). STOC (2021)
Leonid A. Levin
Fundamentals of Computing. CoRR (2020)
Leonid A. Levin, Ramarathnam Venkatesan
An Average Case NP-complete Graph Colouring Problem. Comb. Probab. Comput. 27 (5) (2018)
Leonid A. Levin
Occam bound on lowest complexity of elements. Ann. Pure Appl. Log. 167 (10) (2016)
Leonid A. Levin
Computational Complexity of Functions. CoRR (2014)
Leonid A. Levin
Sets Have Simple Members. (repost). CoRR (2014)
Leonid A. Levin
Forbidden information. J. ACM 60 (2) (2013)
Leonid A. Levin
Turing's Password: What Internet Cannot Leak. LICS (2012)
Leonid A. Levin
Enumerable Distributions, Randomness, Dependence CoRR (2012)
Leonid A. Levin
Rarity for Semimeasures. FOCS (2012)
Leonid A. Levin
Randomness and Non-determinism CoRR (2012)
Leonid A. Levin
Universal Heuristics: How Do Humans Solve "Unsolvable" Problems? Algorithmic Probability and Friends (2011)
Leonid A. Levin
Some theorems on the algorithmic approach to probability theory and information theory: (1971 Dissertation directed by A.N. Kolmogorov). Ann. Pure Appl. Log. 162 (3) (2010)
Leonid A. Levin
Arcane Information, Solving Relations, and Church Censorship. SSS (2010)
Leonid A. Levin
Some Theorems on the Algorithmic Approach to Probability Theory and Information Theory CoRR (2010)
Leonid A. Levin
The Grace of Quadratic Norms: Some Examples. Pillars of Computer Science (2008)
Bruno Durand, Leonid A. Levin, Alexander Shen
Complex tilings. J. Symb. Log. 73 (2) (2008)
Gene Itkis, Leonid A. Levin
Flat Holonomies on Automata Networks. STACS (2006)
Leonid A. Levin
Self-stabilization of Circular Arrays of Automata CoRR (2006)
Jeffrey Considine, Matthias Fitzi, Matthew K. Franklin, Leonid A. Levin, Ueli M. Maurer, David Metcalf
Byzantine Agreement Given Partial Broadcast. J. Cryptol. 18 (3) (2005)
Leonid A. Levin
Notes for Miscellaneous Lectures CoRR (2005)
Leonid A. Levin
Aperiodic Tilings: Breaking Translational Symmetry. Comput. J. 48 (6) (2005)
Gene Itkis, Leonid A. Levin
Flat Holonomies on Automata Networks CoRR (2005)
Leonid A. Levin
Aperiodic Tilings: Breaking Translational Symmetry CoRR (2004)
Leonid A. Levin
The Tale of One-Way Functions. Probl. Inf. Transm. 39 (1) (2003)
Leonid A. Levin
Forbidden Information CoRR (2002)
Leonid A. Levin
Forbidden Information. FOCS (2002)
Bruno Durand, Leonid A. Levin, Alexander Shen
Complex Tilings CoRR (2001)
Leonid A. Levin, Ramarathnam Venkatesan
An Average Case NP-complete Graph Problem CoRR (2001)
Bruno Durand, Leonid A. Levin, Alexander Shen
Complex tilings. STOC (2001)
Jeffrey Considine, Leonid A. Levin, David Metcalf
Byzantine Agreement with Faulty Majority using Bounded Broadcast CoRR (2000)
Leonid A. Levin
The Equity Tax and Shelter CoRR (2000)
Leonid A. Levin
The Tale of One-way Functions CoRR (2000)
Leonid A. Levin
Self-stabilization of circular arrays of automata. Theor. Comput. Sci. 235 (1) (2000)
Johan Håstad, Russell Impagliazzo, Leonid A. Levin, Michael Luby
A Pseudorandom Generator from any One-way Function. SIAM J. Comput. 28 (4) (1999)
Leonid A. Levin
Robust Measures of Information. Comput. J. 42 (4) (1999)
Leonid A. Levin
Errata to "Fundamentals of Computing". SIGACT News 28 (2) (1997)
Leonid A. Levin
Fundamentals of computing (a cheatlist). SIGACT News 27 (3) (1996)
Leonid A. Levin
Computational Complexity of Functions. Theor. Comput. Sci. 157 (2) (1996)
Oded Goldreich, Leonid A. Levin, Noam Nisan
On Constructing 1-1 One-Way Functions Electron. Colloquium Comput. Complex. 2 (29) (1995)
Leonid A. Levin
STOC Criteria. SIGACT News 26 (2) (1995)
Gene Itkis, Leonid A. Levin
Fast and Lean Self-Stabilizing Asynchronous Protocols FOCS (1994)
Leonid A. Levin
Theory of computation: how to start. SIGACT News 22 (1) (1991)
László Babai, Lance Fortnow, Leonid A. Levin, Mario Szegedy
Checking Computations in Polylogarithmic Time STOC (1991)
Shafi Goldwasser, Leonid A. Levin
Fair Computation of General Functions in Presence of Immoral Majority. CRYPTO (1990)
Russell Impagliazzo, Leonid A. Levin
No Better Ways to Generate Hard NP Instances than Picking Uniformly at Random FOCS (1990)
Oded Goldreich, Russell Impagliazzo, Leonid A. Levin, Ramarathnam Venkatesan, David Zuckerman
Security Preserving Amplification of Hardness FOCS (1990)
Oded Goldreich, Leonid A. Levin
A Hard-Core Predicate for all One-Way Functions STOC (1989)
Russell Impagliazzo, Leonid A. Levin, Michael Luby
Pseudo-random Generation from one-way functions (Extended Abstracts) STOC (1989)
Gene Itkis, Leonid A. Levin
Power of Fast VLSI Models Is Insensitive to Wires' Thinness FOCS (1989)
Ramarathnam Venkatesan, Leonid A. Levin
Random Instances of a Graph Coloring Problem Are Hard STOC (1988)
Leonid A. Levin
Homogeneous Measures and Polynomial Time Invariants FOCS (1988)
Leonid A. Levin
One-way functions and pseudorandom generators. Comb. 7 (4) (1987)
Leonid A. Levin
Average Case Complete Problems. SIAM J. Comput. 15 (1) (1986)
Leonid A. Levin
One-Way Functions and Pseudorandom Generators STOC (1985)
Leonid A. Levin
Randomness Conservation Inequalities; Information and Independence in Mathematical Theories Inf. Control. 61 (1) (1984)
Leonid A. Levin
Problems, Complete in "Average" Instance STOC (1984)
Boris Yamnitsky, Leonid A. Levin
An Old Linear Programming Algorithm Runs in Polynomial Time FOCS (1982)
Leonid A. Levin, V. V. V'jugin
Invariant Properties of Informational Bulks. MFCS (1977)