default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDLeonid A. Levin
Person information
- unicode name: Леони́д Анато́льевич Ле́вин
- affiliation: Boston University, MA, USA
- award (2012): Knuth Prize
- award: Humboldt Prize
SPARQL queries 
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
2020 – today
- 2023
[c24]Leonid A. Levin
:
Invited Paper: How Do Humans Succeed in Tasks Like Proving Fermat's Theorem or Predicting the Higgs Boson? SSS 2023: 513-517- 2022
- [j20]Leonid A. Levin:
Gacs - Kucera theorem. Theor. Comput. Sci. 929: 172-173 (2022) - [i21]Leonid A. Levin:
Gacs-Kucera Theorem. CoRR abs/2207.12489 (2022) - [i20]Leonid A. Levin:
On Power Set Axiom. CoRR abs/2209.07497 (2022) - [i19]Leonid A. Levin:
How do humans succeed in tasks like proving Fermat's Theorem or predicting the Higgs boson? CoRR abs/2209.09121 (2022) - 2021
- [c23]Leonid A. Levin:
Climbing algorithms (invited talk). STOC 2021: 2-3 - [i18]Leonid A. Levin:
The Dual Matrix Algorithm for Linear Programming. CoRR abs/2101.00101 (2021) - 2020
- [i17]Leonid A. Levin:
Fundamentals of Computing. CoRR abs/2005.06436 (2020)
2010 – 2019
- 2018
- [j19]Leonid A. Levin, Ramarathnam Venkatesan:
An Average Case NP-complete Graph Colouring Problem. Comb. Probab. Comput. 27(5): 808-828 (2018) - 2016
- [j18]Leonid A. Levin:
Occam bound on lowest complexity of elements. Ann. Pure Appl. Log. 167(10): 897-900 (2016) - 2014
- [i16]Leonid A. Levin:
Sets Have Simple Members. (repost). CoRR abs/1403.4539 (2014) - [i15]Leonid A. Levin:
Computational Complexity of Functions. CoRR abs/1411.3010 (2014) - 2013
- [j17]Leonid A. Levin:
Forbidden information. J. ACM 60(2): 9:1-9:9 (2013) - 2012
- [c22]Leonid A. Levin:
Rarity for Semimeasures. FOCS 2012: 510-513 - [c21]Leonid A. Levin:
Turing's Password: What Internet Cannot Leak. LICS 2012: 11 - [i14]Leonid A. Levin:
Enumerable Distributions, Randomness, Dependence. CoRR abs/1208.2955 (2012) - [i13]Leonid A. Levin:
Randomness and Non-determinism. CoRR abs/1211.0071 (2012) - 2011
- [c20]Leonid A. Levin:
Universal Heuristics: How Do Humans Solve "Unsolvable" Problems? Algorithmic Probability and Friends 2011: 53-54 - [p1]Oded Goldreich, Leonid A. Levin, Noam Nisan:
On Constructing 1-1 One-Way Functions. Studies in Complexity and Cryptography 2011: 13-25 - 2010
- [j16]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): 224-235 (2010) - [c19]Leonid A. Levin:
Arcane Information, Solving Relations, and Church Censorship. SSS 2010: 1 - [i12]Leonid A. Levin:
Some Theorems on the Algorithmic Approach to Probability Theory and Information Theory. CoRR abs/1009.5894 (2010)
2000 – 2009
- 2008
- [j15]Bruno Durand, Leonid A. Levin, Alexander Shen:
Complex tilings. J. Symb. Log. 73(2): 593-613 (2008) - [c18]Leonid A. Levin:
The Grace of Quadratic Norms: Some Examples. Pillars of Computer Science 2008: 457-459 - 2006
- [c17]Gene Itkis, Leonid A. Levin:
Flat Holonomies on Automata Networks. STACS 2006: 23-49 - [i11]Leonid A. Levin:
Self-stabilization of Circular Arrays of Automata. CoRR abs/cs/0602033 (2006) - 2005
- [j14]Leonid A. Levin:
Aperiodic Tilings: Breaking Translational Symmetry. Comput. J. 48(6): 642-645 (2005) - [j13]Jeffrey Considine, Matthias Fitzi, Matthew K. Franklin, Leonid A. Levin, Ueli M. Maurer, David Metcalf:
Byzantine Agreement Given Partial Broadcast. J. Cryptol. 18(3): 191-217 (2005) - [i10]Leonid A. Levin:
Notes for Miscellaneous Lectures. CoRR abs/cs/0503039 (2005) - [i9]Gene Itkis, Leonid A. Levin:
Flat Holonomies on Automata Networks. CoRR abs/cs/0512077 (2005) - 2004
- [i8]Leonid A. Levin:
Aperiodic Tilings: Breaking Translational Symmetry. CoRR cs.DM/0409024 (2004) - 2003
- [j12]Leonid A. Levin:
The Tale of One-Way Functions. Probl. Inf. Transm. 39(1): 92-103 (2003) - 2002
- [c16]Leonid A. Levin:
Forbidden Information. FOCS 2002: 761- - [i7]Leonid A. Levin:
Forbidden Information. CoRR cs.CC/0203029 (2002) - 2001
- [c15]Bruno Durand, Leonid A. Levin, Alexander Shen:
Complex tilings. STOC 2001: 732-739 - [i6]Bruno Durand, Leonid A. Levin, Alexander Shen:
Complex Tilings. CoRR cs.CC/0107008 (2001) - [i5]Leonid A. Levin, Ramarathnam Venkatesan:
An Average Case NP-complete Graph Problem. CoRR cs.CC/0112001 (2001) - 2000
- [j11]Leonid A. Levin:
Self-stabilization of circular arrays of automata. Theor. Comput. Sci. 235(1): 143-144 (2000) - [i4]Leonid A. Levin:
The Equity Tax and Shelter. CoRR cs.CE/0012013 (2000) - [i3]Leonid A. Levin:
The Tale of One-way Functions. CoRR cs.CR/0012023 (2000) - [i2]Jeffrey Considine, Leonid A. Levin, David Metcalf:
Byzantine Agreement with Faulty Majority using Bounded Broadcast. CoRR cs.DC/0012024 (2000)
1990 – 1999
- 1999
- [j10]Leonid A. Levin:
Robust Measures of Information. Comput. J. 42(4): 284-286 (1999) - [j9]Johan Håstad, Russell Impagliazzo, Leonid A. Levin, Michael Luby:
A Pseudorandom Generator from any One-way Function. SIAM J. Comput. 28(4): 1364-1396 (1999) - 1997
- [j8]Leonid A. Levin:
Errata to "Fundamentals of Computing". SIGACT News 28(2): 80 (1997) - 1996
- [j7]Leonid A. Levin:
Fundamentals of computing (a cheatlist). SIGACT News 27(3): 89 (1996) - [j6]Leonid A. Levin:
Computational Complexity of Functions. Theor. Comput. Sci. 157(2): 267-271 (1996) - 1995
- [j5]Leonid A. Levin:
STOC Criteria. SIGACT News 26(2): 77 (1995) - [i1]Oded Goldreich, Leonid A. Levin, Noam Nisan:
On Constructing 1-1 One-Way Functions. Electron. Colloquium Comput. Complex. TR95 (1995) - 1994
- [c14]Gene Itkis, Leonid A. Levin:
Fast and Lean Self-Stabilizing Asynchronous Protocols. FOCS 1994: 226-239 - 1991
- [j4]Leonid A. Levin:
Theory of computation: how to start. SIGACT News 22(1): 47-56 (1991) - [c13]László Babai, Lance Fortnow, Leonid A. Levin, Mario Szegedy:
Checking Computations in Polylogarithmic Time. STOC 1991: 21-31 - 1990
- [c12]Shafi Goldwasser, Leonid A. Levin:
Fair Computation of General Functions in Presence of Immoral Majority. CRYPTO 1990: 77-93 - [c11]Oded Goldreich, Russell Impagliazzo, Leonid A. Levin, Ramarathnam Venkatesan, David Zuckerman:
Security Preserving Amplification of Hardness. FOCS 1990: 318-326 - [c10]Russell Impagliazzo, Leonid A. Levin:
No Better Ways to Generate Hard NP Instances than Picking Uniformly at Random. FOCS 1990: 812-821
1980 – 1989
- 1989
- [c9]Gene Itkis, Leonid A. Levin:
Power of Fast VLSI Models Is Insensitive to Wires' Thinness. FOCS 1989: 402-407 - [c8]Russell Impagliazzo, Leonid A. Levin, Michael Luby:
Pseudo-random Generation from one-way functions (Extended Abstracts). STOC 1989: 12-24 - [c7]Oded Goldreich, Leonid A. Levin:
A Hard-Core Predicate for all One-Way Functions. STOC 1989: 25-32 - 1988
- [c6]Leonid A. Levin:
Homogeneous Measures and Polynomial Time Invariants. FOCS 1988: 36-41 - [c5]Ramarathnam Venkatesan, Leonid A. Levin:
Random Instances of a Graph Coloring Problem Are Hard. STOC 1988: 217-222 - 1987
- [j3]Leonid A. Levin:
One-way functions and pseudorandom generators. Comb. 7(4): 357-363 (1987) - 1986
- [j2]Leonid A. Levin:
Average Case Complete Problems. SIAM J. Comput. 15(1): 285-286 (1986) - 1985
- [c4]Leonid A. Levin:
One-Way Functions and Pseudorandom Generators. STOC 1985: 363-365 - 1984
- [j1]Leonid A. Levin:
Randomness Conservation Inequalities; Information and Independence in Mathematical Theories. Inf. Control. 61(1): 15-37 (1984) - [c3]Leonid A. Levin:
Problems, Complete in "Average" Instance. STOC 1984: 465 - 1982
- [c2]Boris Yamnitsky, Leonid A. Levin:
An Old Linear Programming Algorithm Runs in Polynomial Time. FOCS 1982: 327-328
1970 – 1979
- 1977
- [c1]Leonid A. Levin, V. V. V'jugin:
Invariant Properties of Informational Bulks. MFCS 1977: 359-364
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from 
to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the 
of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from 
, 
, and 
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from 
.
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2025-01-20 23:01 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
