Leonid Levin | Academic Influence

Leonid Levin's AcademicInfluence.com Rankings

Leonid Levin

Computer Science

#97

World Rank

#103

Historical Rank

#57

USA Rank

Theoretical Computer Science

#10

World Rank

#10

Historical Rank

#6

USA Rank

computer-science Degrees

Leonid Levin

Mathematics

#189

World Rank

#436

Historical Rank

#87

USA Rank

Measure Theory

#561

World Rank

#782

Historical Rank

#234

USA Rank

mathematics Degrees

Download Badge

Computer Science
Mathematics

Leonid Levin's Degrees

PhD Mathematics Moscow State University

Why Is Leonid Levin Influential?

(Suggest an Edit or Addition)

According to Wikipedia, Leonid Anatolievich Levin is a Soviet-American mathematician and computer scientist. He is known for his work in randomness in computing, algorithmic complexity and intractability, average-case complexity, foundations of mathematics and computer science, algorithmic probability, theory of computation, and information theory. He obtained his master's degree at Moscow University in 1970 where he studied under Andrey Kolmogorov and completed the Candidate Degree academic requirements in 1972.

(See a Problem?)

Leonid Levin's Published Works

Number of citations in a given year to any of this author's works

Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author

Published Works

A Pseudorandom Generator from any One-way Function (1999) (1534)
A hard-core predicate for all one-way functions (1989) (1189)
THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS (1970) (675)
Pseudo-random generation from one-way functions (1989) (663)
Checking computations in polylogarithmic time (1991) (625)
Average Case Complete Problems (1986) (470)
Fair Computation of General Functions in Presence of Immoral Majority (1990) (368)
Randomness Conservation Inequalities; Information and Independence in Mathematical Theories (1984) (299)
One-way functions and pseudorandom generators (1985) (294)
Construction of a pseudo-random generator from any one-way function (1989) (201)
Pseudo-random Generation from one-way functions (Extended Abstracts) (1989) (180)
No better ways to generate hard NP instances than picking uniformly at random (1990) (159)
Security preserving amplification of hardness (1990) (123)
One way functions and pseudorandom generators (1987) (102)
The Tale of One-Way Functions (2000) (98)
Random instances of a graph coloring problem are hard (1988) (91)
Fast and lean self-stabilizing asynchronous protocols (1994) (70)
Complex tilings (2001) (69)
Byzantine Agreement Given Partial Broadcast (2005) (45)
An old linear programming algorithm runs in polynomial time (1982) (40)
Some theorems on the algorithmic approach to probability theory and information theory: (1971 Dissertation directed by A.N. Kolmogorov) (2010) (39)
Local rules and global order, or aperiodic tilings (2005) (27)
On Constructing 1-1 One-Way Functions (1995) (27)
Problems, complete in “average” instance (1984) (26)
Forbidden information (2002) (25)
Invariant Properties of Informational Bulks (1977) (22)
Aperiodic Tilings: Breaking Translational Symmetry (2004) (17)
Randomness and Nondeterminism (1995) (16)
Randomness and Non-determinism (2012) (14)
Homogeneous measures and polynomial time invariants (1988) (14)
Sets Have Simple Members (2011) (11)
Occam bound on lowest complexity of elements (2016) (10)
Computational Complexity of Functions (1996) (10)
Universal Heuristics: How Do Humans Solve "Unsolvable" Problems? (2011) (9)
A CONCEPT OF INDEPENDENCE WITH APPLICATIONS IN VARIOUS FIELDS OF MATHEMATICS (1980) (9)
On Sets of High Complexity Strings (2011) (7)
Byzantine Agreement with Faulty Majority using Bounded Broadcast (2000) (6)
Power of fast VLSI models is insensitive to wires' thinness (1989) (5)
An Average Case NP-complete Graph Colouring Problem (2001) (5)
Notes for Miscellaneous Lectures (2005) (5)
Theory of computation: how to start (1991) (4)
Causal nets or what is a deterministic computation? (1982) (4)
Robust Measures of Information (1999) (3)
Self-stabilization of circular arrays of automata (2000) (3)
Fundamentals of Computing (2020) (3)
Byzantine Agreement with Bounded Broadcast (2000) (2)
Gacs-Kucera Theorem (2022) (1)
The Second Part of the next Claim Follows from a Standard Application of Chernoo Bounds. B General Commodity Testing (1999) (1)
Taxation and Valuation. (2000) (1)
Rarity for Semimeasures (2012) (1)
PNA member Lee Levin: an entrepreneurial profile. Interview by Kimberley Jackson. (1991) (1)
Enumerable Distributions, Randomness, Dependence (2012) (1)
Turing's Password: What Internet Cannot Leak (2012) (1)
Leonid Levin Interview December 1982 (1982) (0)
Secure Multi-party Computation Dedication a Warning (1998) (0)
C E ] 1 8 D ec 2 00 0 Equity Tax and Shelter (2000) (0)
Arcane Information, Solving Relations, and Church Censorship (2010) (0)
Fundamentals of computing (a cheatlist) (1996) (0)
2 2 A pr 2 01 6 Notes for Miscellaneous Lectures (2016) (0)
ec 2 00 0 Byzantine Agreement with Bounded Broadcast (2008) (0)
2 J ul 2 02 0 Fundamentals of Computing (2020) (0)
Endosurgical aspects of diagnosis and treatment of strangulated inguinal hernias (a brief literature review) (2022) (0)
STOC Criteria (1995) (0)
C C ] 4 S ep 2 01 9 Enumerable Distributions , Randomness , Dependence (0)
Leonid Levin Interview February 1979 (1979) (0)
What Is a Deterministic Computation (1982) (0)
C C ] 1 5 D ec 2 01 7 An Average Case NP-complete Graph Coloring Problem ∗ (0)
Hard on average problems and their application (1996) (0)
The Equity Tax and Shelter (2000) (0)
Flat holonomies on automata networks : (a more recent version available at: http //arxiv.org/abs/cs.DC/0512077) (2006) (0)
The Dual Matrix Algorithm for Linear Programming (2021) (0)
How do humans succeed in tasks like proving Fermat's Theorem or predicting the Higgs boson? (2022) (0)
C C ] 8 A pr 2 01 9 Enumerable Distributions , Randomness , Dependence (0)
Does a Single Bit Accumulate the Hardness of the Inverting Problem (1987) (0)
Local Rulos and Gobal Order Or I Aperiodic Tilings an local rules impose a global order ? (2008) (0)
Errata to "Fundamentals of Computing" (1997) (0)
On Power Set Axiom (2022) (0)
Climbing algorithms (invited talk) (2021) (0)
Assumptions of Randomness in Cosmology Models (2017) (0)
The Tale of One-way Functions (in Russian) (2000) (0)
Thin Ice (2008) (0)
The Tale of One-way Functions: Part 1 (2000) (0)
Flat Holonomies on Automata Networks (2005) (0)
Sets Have Simple Members. (repost) (2014) (0)
C C ] 3 J ul 2 01 2 Sets Have Simple Members (2012) (0)
The Grace of Quadratic Norms: Some Examples (2008) (0)
Simple Members of Sets (2011) (0)
O ct 2 00 7 Notes for Miscellaneous Lectures (2008) (0)
Centennial Seminar on Kolmogorov Complexity and Applications (Dagstuhl Seminar 03181) (2021) (0)
Climbing LP Algorithms (2020) (0)

This paper list is powered by the following services:

Other Resources About Leonid Levin

en.wikipedia.org

What Schools Are Affiliated With Leonid Levin?

Leonid Levin is affiliated with the following schools:

Image Attributions

Image Source for Leonid Levin