|
| Scholar | (Selected) Results for author:"Leonid Levin" OR author:"LA Levin". |
A hard-core predicate for all one-way functions
O Goldreich, LA Levin STOC, 1989 -
portal.acm.org
Cited by:
787
A Pseudorandom Generator from any One-way Function -
J Hastad, R Impagliazzo, LA Levin,
M Luby - SIAM J. Comput., 1999 - epubs.siam.org
Cited by:
734 +
47 +
6 +
2 +
2 +
2 +
2 +
2
Universal search problems
LA Levin
- Problemy Peredachi Informatsii, 1973
Cited by:
669 +
90 +
13 +
10 +
5 +
3 +
2
The complexity of finite
objects ... (also dissertation: "Some theorems on the algorithmic
approach ...")
AK Zvonkin, LA Levin - Russian Math.
Surveys, 1970 - turpion.org
Cited by:
524 +
49 +
23 +
10 +
8 +
2 +
2 +
2 +
2 +
2 +
2 +
2 +
1 +
1 +
1 +
1
Pseudo-random generation from one-way functions
R Impagliazzo, LA Levin, M Luby -
STOC, 1989
- portal.acm.org
Cited by:
490 +
2 +
2
Checking computations in
polylogarithmic time - L.
Babai, L. Fortnow, LA Levin, M Szegedy -
STOC, 1991
- portal.acm.org
Cited by:
414 +
3
Average case complete problems - LA Levin - SIAM Journal on Computing, 1986
- portal.acm.org
Cited by:
363 +
29 +
2
Fair Computation of
General Functions in Presence of Immoral Majority - S Goldwasser, LA Levin - CRYPTO, 1990
- Springer
Cited by:
291 +
2
One-way functions and pseudorandom generators -
all 10 versions
LA Levin - STOC, 1985. Also, Combinatorica, 1987.
Cited by:
270 +
2
On the notion of
a random sequence
LA Levin
- Soviet Math. Dokl, 1973
Cited by:
188 +
39 +
10
Laws of information conservation (nongrowth) and aspects of
the foundation of ...
LA Levin - Problems Inform. Transmission,
1974
Cited by:
215 +
11 +
6
Randomness
conservation inequalities; information and independence in mathematical
theories - LA Levin -
Information and Control, 1984.
Earlier versions: A General Concept of Independence of Mathematical
Objects, Math. Dissertation, MIT, 1979;
A Concept of Independence
with Applications in Various Fields of Mathematics,
TR-235/MIT/LCS, 1980.
Cited by:
195 +
6
Security preserving
amplification of hardness -
O Goldreich, R Impagliazzo, LA Levin,
R Venkatesan, D Zuckerman - FOCS, 1990.
- ieeexplore.ieee.org
Cited by:
116 +
3
One-dimensional uniform arrays that wash out finite islands
P Gacs, GL Kurdyumov, LA Levin
- Probl. Peredachi. Inform, 1978
Cited by:
86 +
26 +
2
Random instances of a graph coloring problem are hard
R Venkatesan, LA Levin - STOC, 1988 -
portal.acm.org
Cited by:
66 +
2
Various measures of complexity for finite objects (axiomatic description)
LA Levin
- Soviet Math. Dokl, 1976
Cited by:
61 +
4 +
1
Uniform Tests of Randomness
LA Levin
- Soviet Math. Dokl, 1976
Cited by:
52 +
2
Randomness and Non-determinism
- all 2 versions
LA Levin
- JSL 1993 - mathunion.org
Cited by:
45
The Tale of One-Way Functions -
LA Levin - Problems of Information Transmission,
2003 - Springer
Cited by:
33 +
10 +
2 +
1 +
1 +
1
Fast and Lean
Self-stabilizing Asynchronous Protocols -
G Itkis, LA Levin -
FOCS, 1994 - ieeexplore.ieee.org
Cited by:
39
Complex tilings
-
[PDF] from arxiv.org;
All 12 versions
Computational complexity of functions
[PS]
On constructing 1-1 one-way functions - O Goldreich, LA Levin, N Nisan
[PS]
An old linear programming algorithm runs in polynomial time
Byzantine Agreement Given Partial Broadcast -
Considine, Fitzi, Franklin,
Levin, Maurer, Metcalf, - J. Cryptology, 18: 191 - 217
C, 2005.
Local Rules and Global Order, Or Aperiodic Tilings.
B Durand, LA Levin, A Shen - J.
Symbolic Logic, 2008
Cited by:
37
LA Levin
- Theoretical Computer Science, 1996
Earlier version: On storage capacity for algorithms
- Soviet Math., Doklady, 1973
Cited by:
10 +
6 +
5
Cited by:
20
B Yamnitsky, LA Levin
- FOCS, 1982
Cited by:
23 +
1
Earlier version: Byzantine Agreement
with Faulty Majority using Bounded Broadcast -
Considine, Levin, Metcalf, 2000 -
arxiv.org
Cited by:
9 +
3 +
2
B Durand, LA Levin, A Shen -
Mathematical Intelligencer, 2005.
Cited by:
14