An Average Case NP-complete Graph Colouring Problem
LEONID A. LEVIN , RAMARATHNAM VENKATESAN
Combinatorics, Probability & Computing 27 ( 5) 808 -828
2
2018
Robust Measures of Information
Leonid. A. Levin
The Computer Journal 42 ( 4) 284 -286
1
1999
No better ways to generate hard NP instances than picking uniformly at random
R. Impagliazzo , L.A, Levin
foundations of computer science 812 -821
115
1990
Uniform tests of randomness
Leonid Anatolevich Levin
Doklady Akademii Nauk 227 ( 1) 33 -35
128
1976
On a concrete method of assigning complexity measures
Leonid Anatolevich Levin
Doklady Akademii Nauk 234 ( 3) 536 -539
29
1977
The Tale of One-way Functions
Leonid A. Levin
arXiv: Cryptography and Security
106
2000
Checking computations in polylogarithmic time
László Babai , Lance Fortnow , Leonid A. Levin , Mario Szegedy
symposium on the theory of computing 21 -32
522
1991
Computational complexity of functions
Leonid A. Levin
Theoretical Computer Science 157 ( 2) 267 -271
5
1996
Randomness conservation inequalities; information and independence in mathematical theories
Leonid A. Levin
Information & Computation 61 ( 1) 15 -37
353
1984
Randomness and Nondeterminism
Leonid A. Levin
Birkhäuser, Basel 1418 -1419
10
1995
Average case complete problems
Leonid A. Levin
SIAM Journal on Computing 15 ( 1) 285 -286
417
1986
On constructing 1-1 one-way functions
Oded Goldreich , Leonid A. Levin , Noam Nisan
Studies in complexity and cryptography 13 -25
15
2011
Rarity for Semimeasures
Leonid A. Levin
2012 IEEE 53rd Annual Symposium on Foundations of Computer Science 510 -513
1
2012
A Pseudorandom Generator from any One-way Function
Johan HÅstad , Russell Impagliazzo , Leonid A. Levin , Michael Luby
SIAM Journal on Computing 28 ( 4) 1364 -1396
1,378
1999
Forbidden information
Leonid A. Levin
Journal of the ACM 60 ( 2) 1 -9
9
2013
One-way functions and Pseudorandom generators
Leonid A. Levin
Combinatorica 7 ( 4) 357 -363
257
1987
Byzantine Agreement Given Partial Broadcast
Jeffrey Considine , Matthias Fitzi , Matthew Franklin , Leonid A. Levin
Journal of Cryptology 18 ( 3) 191 -217
32
2005
Aperiodic Tilings: Breaking Translational Symmetry
Leonid A. Levin
The Computer Journal 48 ( 6) 642 -645
17
2005
Occam bound on lowest complexity of elements
Leonid A. Levin
Annals of Pure and Applied Logic 167 ( 10) 897 -900
2016
Fundamentals of computing (a cheatlist)
Leonid A. Levin
Sigact News 27 ( 3) 89
1996