ask others

Leonid A. Levin

Леони́д Анато́льевич Ле́вин

> Home > Persons

Person information

unicode name: Леони́д Анато́льевич Ле́вин
affiliation: Boston University, MA, USA

Refine list

refinements active!

zoomed in on ?? of ?? records

view refined list in

export refined list as

showing all ?? records

2010 – today

see FAQ

What is the meaning of the colors in the publication lists?

2018
[j18]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - journals/cpc/LevinV18
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/cpc/LevinV18
Leonid A. Levin, Ramarathnam Venkatesan:
An Average Case NP-complete Graph Colouring Problem. Combinatorics, Probability & Computing 27(5): 808-828 (2018)
2016
[j17]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - journals/apal/Levin16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/apal/Levin16
Leonid A. Levin:
Occam bound on lowest complexity of elements. Ann. Pure Appl. Logic 167(10): 897-900 (2016)
2014
[i16]
- view
  - electronic edition @ arxiv.org
- export record
  dblp key:
  - journals/corr/Levin14
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/corr/Levin14
Leonid A. Levin:
Sets Have Simple Members. (repost). CoRR abs/1403.4539 (2014)
[i15]
- view
  - electronic edition @ arxiv.org
- export record
  dblp key:
  - journals/corr/Levin14b
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/corr/Levin14b
Leonid A. Levin:
Computational Complexity of Functions. CoRR abs/1411.3010 (2014)
2013
[j16]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - journals/jacm/Levin13
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/jacm/Levin13
Leonid A. Levin:
Forbidden information. J. ACM 60(2): 9:1-9:9 (2013)
2012
[c22]
- view
  - electronic edition via DOI
  - electronic edition @ ieeecomputersociety.org
- export record
  dblp key:
  - conf/focs/Levin12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/focs/Levin12
Leonid A. Levin:
Rarity for Semimeasures. FOCS 2012: 510-513
[c21]
- view
  - electronic edition @ ieeecomputersociety.org
- export record
  dblp key:
  - conf/lics/Levin12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/lics/Levin12
Leonid A. Levin:
Turing's Password: What Internet Cannot Leak. LICS 2012: 11
[i14]
- view
  - electronic edition @ arxiv.org
- export record
  dblp key:
  - journals/corr/abs-1208-2955
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/corr/abs-1208-2955
Leonid A. Levin:
Enumerable Distributions, Randomness, Dependence. CoRR abs/1208.2955 (2012)
[i13]
- view
  - electronic edition @ arxiv.org
- export record
  dblp key:
  - journals/corr/abs-1211-0071
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/corr/abs-1211-0071
Leonid A. Levin:
Randomness and Non-determinism. CoRR abs/1211.0071 (2012)
2011
[c20]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - conf/birthday/Levin11
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/birthday/Levin11
Leonid A. Levin:
Universal Heuristics: How Do Humans Solve "Unsolvable" Problems? Algorithmic Probability and Friends 2011: 53-54
[p1]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - books/sp/goldreich2011/GoldreichLN11
- ask others
- share record
  short URL:
  - https://dblp.org/rec/books/sp/goldreich2011/GoldreichLN11
Oded Goldreich, Leonid A. Levin, Noam Nisan:
On Constructing 1-1 One-Way Functions. Studies in Complexity and Cryptography 2011: 13-25
2010
[j15]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - journals/apal/Levin10
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/apal/Levin10
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. Logic 162(3): 224-235 (2010)
[c19]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - conf/sss/Levin10
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/sss/Levin10
Leonid A. Levin:
Arcane Information, Solving Relations, and Church Censorship. SSS 2010: 1
[i12]
- view
  - electronic edition @ arxiv.org
- export record
  dblp key:
  - journals/corr/abs-1009-5894
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/corr/abs-1009-5894
Leonid A. Levin:
Some Theorems on the Algorithmic Approach to Probability Theory and Information Theory. CoRR abs/1009.5894 (2010)

2000 – 2009

see FAQ

What is the meaning of the colors in the publication lists?

2008
[j14]
- view
- export record
  dblp key:
  - journals/jsyml/DurandLS08
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/jsyml/DurandLS08
Bruno Durand, Leonid A. Levin, Alexander Shen:
Complex tilings. J. Symb. Log. 73(2): 593-613 (2008)
[c18]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - conf/birthday/Levin08
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/birthday/Levin08
Leonid A. Levin:
The Grace of Quadratic Norms: Some Examples. Pillars of Computer Science 2008: 457-459
2006
[c17]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - conf/stacs/ItkisL06
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/stacs/ItkisL06
Gene Itkis, Leonid A. Levin:
Flat Holonomies on Automata Networks. STACS 2006: 23-49
[i11]
- view
  - electronic edition @ arxiv.org
- export record
  dblp key:
  - journals/corr/abs-cs-0602033
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/corr/abs-cs-0602033
Leonid A. Levin:
Self-stabilization of Circular Arrays of Automata. CoRR abs/cs/0602033 (2006)
2005
[j13]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - journals/cj/Levin05
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/cj/Levin05
Leonid A. Levin:
Aperiodic Tilings: Breaking Translational Symmetry. Comput. J. 48(6): 642-645 (2005)
[j12]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - journals/joc/ConsidineFFLMM05
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/joc/ConsidineFFLMM05
Jeffrey Considine, Matthias Fitzi, Matthew K. Franklin, Leonid A. Levin, Ueli M. Maurer, David Metcalf:
Byzantine Agreement Given Partial Broadcast. J. Cryptology 18(3): 191-217 (2005)
[i10]
- view
  - electronic edition @ arxiv.org
- export record
  dblp key:
  - journals/corr/abs-cs-0503039
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/corr/abs-cs-0503039
Leonid A. Levin:
Notes for Miscellaneous Lectures. CoRR abs/cs/0503039 (2005)
[i9]
- view
  - electronic edition @ arxiv.org
- export record
  dblp key:
  - journals/corr/abs-cs-0512077
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/corr/abs-cs-0512077
Gene Itkis, Leonid A. Levin:
Flat Holonomies on Automata Networks. CoRR abs/cs/0512077 (2005)
2004
[i8]
- view
  - electronic edition @ arxiv.org
- export record
  dblp key:
  - journals/corr/cs-DM-0409024
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/corr/cs-DM-0409024
Leonid A. Levin:
Aperiodic Tilings: Breaking Translational Symmetry. CoRR cs.DM/0409024 (2004)
2003
[j11]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - journals/poit/Levin03
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/poit/Levin03
Leonid A. Levin:
The Tale of One-Way Functions. Probl. Inf. Transm. 39(1): 92-103 (2003)
2002
[c16]
- view
  - electronic edition via DOI
  - electronic edition @ ieeecomputersociety.org
- export record
  dblp key:
  - conf/focs/Levin02
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/focs/Levin02
Leonid A. Levin:
Forbidden Information. FOCS 2002: 761-
[i7]
- view
  - electronic edition @ arxiv.org
- export record
  dblp key:
  - journals/corr/cs-CC-0203029
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/corr/cs-CC-0203029
Leonid A. Levin:
Forbidden Information. CoRR cs.CC/0203029 (2002)
2001
[c15]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - conf/stoc/DurandLS01
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/stoc/DurandLS01
Bruno Durand, Leonid A. Levin, Alexander Shen:
Complex tilings. STOC 2001: 732-739
[i6]
- view
  - electronic edition @ arxiv.org
- export record
  dblp key:
  - journals/corr/cs-CC-0107008
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/corr/cs-CC-0107008
Bruno Durand, Leonid A. Levin, Alexander Shen:
Complex Tilings. CoRR cs.CC/0107008 (2001)
[i5]
- view
  - electronic edition @ arxiv.org
- export record
  dblp key:
  - journals/corr/cs-CC-0112001
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/corr/cs-CC-0112001
Leonid A. Levin, Ramarathnam Venkatesan:
An Average Case NP-complete Graph Problem. CoRR cs.CC/0112001 (2001)
2000
[j10]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - journals/tcs/Levin00
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/tcs/Levin00
Leonid A. Levin:
Self-stabilization of circular arrays of automata. Theor. Comput. Sci. 235(1): 143-144 (2000)
[i4]
- view
  - electronic edition @ arxiv.org
- export record
  dblp key:
  - journals/corr/cs-CE-0012013
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/corr/cs-CE-0012013
Leonid A. Levin:
The Equity Tax and Shelter. CoRR cs.CE/0012013 (2000)
[i3]
- view
  - electronic edition @ arxiv.org
- export record
  dblp key:
  - journals/corr/cs-CR-0012023
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/corr/cs-CR-0012023
Leonid A. Levin:
The Tale of One-way Functions. CoRR cs.CR/0012023 (2000)
[i2]
- view
  - electronic edition @ arxiv.org
- export record
  dblp key:
  - journals/corr/cs-DC-0012024
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/corr/cs-DC-0012024
Jeffrey Considine, Leonid A. Levin, David Metcalf:
Byzantine Agreement with Faulty Majority using Bounded Broadcast. CoRR cs.DC/0012024 (2000)

1990 – 1999

see FAQ

What is the meaning of the colors in the publication lists?

1999
[j9]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - journals/cj/Levin99
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/cj/Levin99
Leonid A. Levin:
Robust Measures of Information. Comput. J. 42(4): 284-286 (1999)
[j8]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - journals/siamcomp/HastadILL99
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/siamcomp/HastadILL99
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
[j7]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - journals/sigact/Levin97
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/sigact/Levin97
Leonid A. Levin:
Errata to "Fundamentals of Computing". SIGACT News 28(2): 80 (1997)
1996
[j6]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - journals/sigact/Levin96
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/sigact/Levin96
Leonid A. Levin:
Fundamentals of computing (a cheatlist). SIGACT News 27(3): 89 (1996)
[j5]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - journals/tcs/Levin96
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/tcs/Levin96
Leonid A. Levin:
Computational Complexity of Functions. Theor. Comput. Sci. 157(2): 267-271 (1996)
1995
[j4]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - journals/sigact/Levin95
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/sigact/Levin95
Leonid A. Levin:
STOC Criteria. SIGACT News 26(2): 77 (1995)
[i1]
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/ECCC-TR95-029
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/ECCC-TR95-029
Oded Goldreich, Leonid A. Levin, Noam Nisan:
On Constructing 1-1 One-Way Functions. Electronic Colloquium on Computational Complexity (ECCC) 2(29) (1995)
1994
[c14]
- view
  - electronic edition via DOI
  - electronic edition @ ieeecomputersociety.org
- export record
  dblp key:
  - conf/focs/ItkisL94
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/focs/ItkisL94
Gene Itkis, Leonid A. Levin:
Fast and Lean Self-Stabilizing Asynchronous Protocols. FOCS 1994: 226-239
1991
[c13]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - conf/stoc/BabaiFLS91
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/stoc/BabaiFLS91
László Babai, Lance Fortnow, Leonid A. Levin, Mario Szegedy:
Checking Computations in Polylogarithmic Time. STOC 1991: 21-31
1990
[c12]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - conf/crypto/GoldwasserL90
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/crypto/GoldwasserL90
Shafi Goldwasser, Leonid A. Levin:
Fair Computation of General Functions in Presence of Immoral Majority. CRYPTO 1990: 77-93
[c11]
- view
  - electronic edition via DOI
  - electronic edition @ ieeecomputersociety.org
- export record
  dblp key:
  - conf/focs/GoldreichILVZ90
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/focs/GoldreichILVZ90
Oded Goldreich, Russell Impagliazzo, Leonid A. Levin, Ramarathnam Venkatesan, David Zuckerman:
Security Preserving Amplification of Hardness. FOCS 1990: 318-326
[c10]
- view
  - electronic edition via DOI
  - electronic edition @ ieeecomputersociety.org
- export record
  dblp key:
  - conf/focs/ImpagliazzoL90
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/focs/ImpagliazzoL90
Russell Impagliazzo, Leonid A. Levin:
No Better Ways to Generate Hard NP Instances than Picking Uniformly at Random. FOCS 1990: 812-821

1980 – 1989

see FAQ

What is the meaning of the colors in the publication lists?

1989
[c9]
- view
  - electronic edition via DOI
  - electronic edition @ ieeecomputersociety.org
- export record
  dblp key:
  - conf/focs/ItkisL89
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/focs/ItkisL89
Gene Itkis, Leonid A. Levin:
Power of Fast VLSI Models Is Insensitive to Wires' Thinness. FOCS 1989: 402-407
[c8]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - conf/stoc/ImpagliazzoLL89
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/stoc/ImpagliazzoLL89
Russell Impagliazzo, Leonid A. Levin, Michael Luby:
Pseudo-random Generation from one-way functions (Extended Abstracts). STOC 1989: 12-24
[c7]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - conf/stoc/GoldreichL89
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/stoc/GoldreichL89
Oded Goldreich, Leonid A. Levin:
A Hard-Core Predicate for all One-Way Functions. STOC 1989: 25-32
1988
[c6]
- view
  - electronic edition via DOI
  - electronic edition @ ieeecomputersociety.org
- export record
  dblp key:
  - conf/focs/Levin88
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/focs/Levin88
Leonid A. Levin:
Homogeneous Measures and Polynomial Time Invariants. FOCS 1988: 36-41
[c5]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - conf/stoc/VenkatesanL88
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/stoc/VenkatesanL88
Ramarathnam Venkatesan, Leonid A. Levin:
Random Instances of a Graph Coloring Problem Are Hard. STOC 1988: 217-222
1987
[j3]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - journals/combinatorica/Levin87
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/combinatorica/Levin87
Leonid A. Levin:
One-way functions and pseudorandom generators. Combinatorica 7(4): 357-363 (1987)
1986
[j2]
- view
  - electronic edition via DOI
  - electronic edition @ wikidata.org
- export record
  dblp key:
  - journals/siamcomp/Levin86
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/siamcomp/Levin86
Leonid A. Levin:
Average Case Complete Problems. SIAM J. Comput. 15(1): 285-286 (1986)
1985
[c4]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - conf/stoc/Levin85
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/stoc/Levin85
Leonid A. Levin:
One-Way Functions and Pseudorandom Generators. STOC 1985: 363-365
1984
[j1]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - journals/iandc/Levin84
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/iandc/Levin84
Leonid A. Levin:
Randomness Conservation Inequalities; Information and Independence in Mathematical Theories. Information and Control 61(1): 15-37 (1984)
[c3]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - conf/stoc/Levin84
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/stoc/Levin84
Leonid A. Levin:
Problems, Complete in "Average" Instance. STOC 1984: 465
1982
[c2]
- view
  - electronic edition via DOI
  - electronic edition @ ieeecomputersociety.org
- export record
  dblp key:
  - conf/focs/YamnitskyL82
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/focs/YamnitskyL82
Boris Yamnitsky, Leonid A. Levin:
An Old Linear Programming Algorithm Runs in Polynomial Time. FOCS 1982: 327-328

1970 – 1979

see FAQ

What is the meaning of the colors in the publication lists?

1977
[c1]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - conf/mfcs/LevinV77
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/mfcs/LevinV77
Leonid A. Levin, V. V. V'jugin:
Invariant Properties of Informational Bulks. MFCS 1977: 359-364

Coauthor Index

see FAQ

maintained by

, founded at