Leonid A. Levin

67 papers A* 18A 1B 1C 2Journal 42Unranked 2

Year	Rank	Type	Title / Venue / Authors
2025	J	`jnl`	Assumptions of randomness in cosmology models. Inf. Comput. Leonid A. Levin
2023	C	`conf`	Invited Paper: How Do Humans Succeed in Tasks Like Proving Fermat's Theorem or Predicting the Higgs Boson? SSS Leonid A. Levin
2022	J	`jnl`	Gacs - Kucera theorem. Theor. Comput. Sci. Leonid A. Levin
2022	J	`jnl`	Gacs-Kucera Theorem. CoRR Leonid A. Levin
2022	J	`jnl`	How do humans succeed in tasks like proving Fermat's Theorem or predicting the Higgs boson? CoRR Leonid A. Levin
2022	J	`jnl`	On Power Set Axiom. CoRR Leonid A. Levin
2021	A*	`conf`	Climbing algorithms (invited talk). STOC Leonid A. Levin
2021	J	`jnl`	The Dual Matrix Algorithm for Linear Programming. CoRR Leonid A. Levin
2020	J	`jnl`	Fundamentals of Computing. CoRR Leonid A. Levin
2018	J	`jnl`	An Average Case NP-complete Graph Colouring Problem. Comb. Probab. Comput. Leonid A. Levin, Ramarathnam Venkatesan
2016	J	`jnl`	Occam bound on lowest complexity of elements. Ann. Pure Appl. Log. Leonid A. Levin
2014	J	`jnl`	Computational Complexity of Functions. CoRR Leonid A. Levin
2014	J	`jnl`	Sets Have Simple Members. (repost). CoRR Leonid A. Levin
2013	J	`jnl`	Forbidden information. J. ACM Leonid A. Levin
2012	J	`jnl`	Enumerable Distributions, Randomness, Dependence CoRR Leonid A. Levin
2012	J	`jnl`	Randomness and Non-determinism CoRR Leonid A. Levin
2012	A*	`conf`	Rarity for Semimeasures. FOCS Leonid A. Levin
2012	A*	`conf`	Turing's Password: What Internet Cannot Leak. LICS Leonid A. Levin
2011	—	`ch.`	On Constructing 1-1 One-Way Functions. Studies in Complexity and Cryptography Oded Goldreich, Leonid A. Levin, Noam Nisan
2011	—	`conf`	Universal Heuristics: How Do Humans Solve "Unsolvable" Problems? Algorithmic Probability and Friends Leonid A. Levin
2010	C	`conf`	Arcane Information, Solving Relations, and Church Censorship. SSS Leonid A. Levin
2010	J	`jnl`	Some Theorems on the Algorithmic Approach to Probability Theory and Information Theory CoRR Leonid A. Levin
2010	J	`jnl`	Some theorems on the algorithmic approach to probability theory and information theory: (1971 Dissertation directed by A.N. Kolmogorov). Ann. Pure Appl. Log. Leonid A. Levin
2008	J	`jnl`	Complex tilings. J. Symb. Log. Bruno Durand, Leonid A. Levin, Alexander Shen
2008	—	`conf`	The Grace of Quadratic Norms: Some Examples. Pillars of Computer Science Leonid A. Levin
2006	A	`conf`	Flat Holonomies on Automata Networks. STACS Gene Itkis, Leonid A. Levin
2006	J	`jnl`	Self-stabilization of Circular Arrays of Automata CoRR Leonid A. Levin
2005	J	`jnl`	Aperiodic Tilings: Breaking Translational Symmetry. Comput. J. Leonid A. Levin
2005	J	`jnl`	Byzantine Agreement Given Partial Broadcast. J. Cryptol. Jeffrey Considine, Matthias Fitzi, Matthew K. Franklin, Leonid A. Levin, Ueli M. Maurer, David Metcalf
2005	J	`jnl`	Flat Holonomies on Automata Networks CoRR Gene Itkis, Leonid A. Levin
2005	J	`jnl`	Notes for Miscellaneous Lectures CoRR Leonid A. Levin
2004	J	`jnl`	Aperiodic Tilings: Breaking Translational Symmetry CoRR Leonid A. Levin
2003	J	`jnl`	The Tale of One-Way Functions. Probl. Inf. Transm. Leonid A. Levin
2002	J	`jnl`	Forbidden Information CoRR Leonid A. Levin
2002	A*	`conf`	Forbidden Information. FOCS Leonid A. Levin
2001	J	`jnl`	An Average Case NP-complete Graph Problem CoRR Leonid A. Levin, Ramarathnam Venkatesan
2001	J	`jnl`	Complex Tilings CoRR Bruno Durand, Leonid A. Levin, Alexander Shen
2001	A*	`conf`	Complex tilings. STOC Bruno Durand, Leonid A. Levin, Alexander Shen
2000	J	`jnl`	Byzantine Agreement with Faulty Majority using Bounded Broadcast CoRR Jeffrey Considine, Leonid A. Levin, David Metcalf
2000	J	`jnl`	Self-stabilization of circular arrays of automata. Theor. Comput. Sci. Leonid A. Levin
2000	J	`jnl`	The Equity Tax and Shelter CoRR Leonid A. Levin
2000	J	`jnl`	The Tale of One-way Functions CoRR Leonid A. Levin
1999	J	`jnl`	A Pseudorandom Generator from any One-way Function. SIAM J. Comput. Johan Håstad, Russell Impagliazzo, Leonid A. Levin, Michael Luby
1999	J	`jnl`	Robust Measures of Information. Comput. J. Leonid A. Levin
1997	J	`jnl`	Errata to "Fundamentals of Computing". SIGACT News Leonid A. Levin
1996	J	`jnl`	Computational Complexity of Functions. Theor. Comput. Sci. Leonid A. Levin
1996	J	`jnl`	Fundamentals of computing (a cheatlist). SIGACT News Leonid A. Levin
1995	J	`jnl`	On Constructing 1-1 One-Way Functions Electron. Colloquium Comput. Complex. Oded Goldreich, Leonid A. Levin, Noam Nisan
1995	J	`jnl`	STOC Criteria. SIGACT News Leonid A. Levin
1994	A*	`conf`	Fast and Lean Self-Stabilizing Asynchronous Protocols FOCS Gene Itkis, Leonid A. Levin
1991	A*	`conf`	Checking Computations in Polylogarithmic Time STOC László Babai, Lance Fortnow, Leonid A. Levin, Mario Szegedy
1991	J	`jnl`	Theory of computation: how to start. SIGACT News Leonid A. Levin
1990	A*	`conf`	Fair Computation of General Functions in Presence of Immoral Majority. CRYPTO Shafi Goldwasser, Leonid A. Levin
1990	A*	`conf`	No Better Ways to Generate Hard NP Instances than Picking Uniformly at Random FOCS Russell Impagliazzo, Leonid A. Levin
1990	A*	`conf`	Security Preserving Amplification of Hardness FOCS Oded Goldreich, Russell Impagliazzo, Leonid A. Levin, Ramarathnam Venkatesan, David Zuckerman
1989	A*	`conf`	A Hard-Core Predicate for all One-Way Functions STOC Oded Goldreich, Leonid A. Levin
1989	A*	`conf`	Power of Fast VLSI Models Is Insensitive to Wires' Thinness FOCS Gene Itkis, Leonid A. Levin
1989	A*	`conf`	Pseudo-random Generation from one-way functions (Extended Abstracts) STOC Russell Impagliazzo, Leonid A. Levin, Michael Luby
1988	A*	`conf`	Homogeneous Measures and Polynomial Time Invariants FOCS Leonid A. Levin
1988	A*	`conf`	Random Instances of a Graph Coloring Problem Are Hard STOC Ramarathnam Venkatesan, Leonid A. Levin
1987	J	`jnl`	One-way functions and pseudorandom generators. Comb. Leonid A. Levin
1986	J	`jnl`	Average Case Complete Problems. SIAM J. Comput. Leonid A. Levin
1985	A*	`conf`	One-Way Functions and Pseudorandom Generators STOC Leonid A. Levin
1984	A*	`conf`	Problems, Complete in "Average" Instance STOC Leonid A. Levin
1984	J	`jnl`	Randomness Conservation Inequalities; Information and Independence in Mathematical Theories Inf. Control. Leonid A. Levin
1982	A*	`conf`	An Old Linear Programming Algorithm Runs in Polynomial Time FOCS Boris Yamnitsky, Leonid A. Levin
1977	B	`conf`	Invariant Properties of Informational Bulks. MFCS Leonid A. Levin, V. V. V'jugin