# Leslie Valiant

#765

Most Influential Person Now

British computer scientist

## Leslie Valiant's AcademicInfluence.com Rankings

Leslie Valiantcomputer-science Degrees

Computer Science

#69

World Rank

#72

Historical Rank

Theoretical Computer Science

#8

World Rank

#8

Historical Rank

Machine Learning

#18

World Rank

#18

Historical Rank

Database

#282

World Rank

#295

Historical Rank

## Download Badge

Computer Science

## Leslie Valiant's Degrees

- Masters Computer Science Imperial College London

## Similar Degrees You Can Earn

## Why Is Leslie Valiant Influential?

(Suggest an Edit or Addition)According to Wikipedia, Leslie Gabriel Valiant is a British American computer scientist and computational theorist. He was born to a chemical engineer father and a translator mother. He is currently the T. Jefferson Coolidge Professor of Computer Science and Applied Mathematics at Harvard University. Valiant was awarded the Turing Award in 2010, having been described by the A.C.M. as a heroic figure in theoretical computer science and a role model for his courage and creativity in addressing some of the deepest unsolved problems in science; in particular for his "striking combination of depth and breadth".

## Leslie Valiant's Published Works

### Published Works

- A theory of the learnable (1984) (4811)
- A bridging model for parallel computation (1990) (4073)
- The Complexity of Computing the Permanent (1979) (2713)
- The Complexity of Enumeration and Reliability Problems (1979) (2029)
- A theory of the learnable (1984) (1271)
- Random Generation of Combinatorial Structures from a Uniform Distribution (1986) (1022)
- Cryptographic limitations on learning Boolean formulae and finite automata (1994) (868)
- NP is as easy as detecting unique solutions (1985) (769)
- Fast probabilistic algorithms for hamiltonian circuits and matchings (1977) (726)
- Universal schemes for parallel communication (1981) (703)
- A Scheme for Fast Parallel Communication (1982) (669)
- Evolvability (2009) (601)
- Computational limitations on learning from examples (1988) (555)
- Completeness classes in algebra (1979) (528)
- A general lower bound on the number of examples needed for learning (1988) (515)
- General Purpose Parallel Architectures (1991) (414)
- Parallelism in Comparison Problems (1975) (396)
- Universality considerations in VLSI circuits (1981) (379)
- Graph-Theoretic Arguments in Low-Level Complexity (1977) (365)
- Direct Bulk-Synchronous Parallel Algorithms (1992) (349)
- General Context-Free Recognition in Less than Cubic Time (1975) (343)
- On the learnability of Boolean formulae (1987) (320)
- Fast Parallel Computation of Polynomials Using Few Processors (1983) (310)
- A fast parallel algorithm for routing in permutation networks (1981) (279)
- Relative Complexity of Checking and Evaluating (1976) (272)
- On Time Versus Space (1977) (265)
- Quantum Circuits That Can Be Simulated Classically in Polynomial Time (2002) (249)
- A logarithmic time sort for linear size networks (1987) (248)
- Learning Disjunction of Conjunctions (1985) (246)
- Crytographic limitations on learning Boolean formulae and finite automata (1989) (236)
- Short Monotone Formulae for the Majority Function (1984) (223)
- A bridging model for multi-core computing (2008) (215)
- Circuits of the mind (1994) (181)
- Universal circuits (Preliminary Report) (1976) (162)
- A complexity theory based on Boolean algebra (1981) (142)
- Deterministic One-Counter Automata (1973) (138)
- Recent Results on Boolean Concept Learning (1987) (137)
- Graph-Theoretic Properties in computational Complexity (1976) (126)
- The Equivalence Problem for Deterministic Finite-Turn Pushdown Automata (1974) (118)
- Bulk synchronous parallel computing-a paradigm for transportable software (1995) (107)
- Why is Boolean complexity theory difficult (1992) (97)
- Decision procedures for families of deterministic pushdown automata (1973) (97)
- Holographic algorithms (2004) (92)
- Negation can be exponentially powerful (1979) (91)
- Robust logics (1999) (89)
- Probably Approximately Correct: Nature's Algorithms for Learning and Prospering in a Complex World (2013) (88)
- On non-linear lower bounds in computational complexity (1975) (86)
- Accidental Algorithms (2006) (86)
- Holographic Algorithms (Extended Abstract) (2004) (83)
- Regularity and Related Problems for Deterministic Pushdown Automata (1975) (83)
- On time versus space and related problems (1975) (81)
- A neuroidal architecture for cognitive computation (1998) (78)
- Shifting Graphs and Their Applications (1976) (71)
- Learning Boolean formulas (1994) (71)
- Knowledge Infusion (2006) (66)
- Cognitive computation (1995) (62)
- Quantum computers that can be simulated classically in polynomial time (2001) (62)
- Functionality in neural nets (1988) (61)
- Three problems in computer science (2003) (61)
- Memorization and Association on a Realistic Neural Model (2005) (56)
- Expressiveness of matchgates (2002) (53)
- Exponential lower bounds for restricted monotone circuits (1983) (48)
- Projection Learning (1998) (43)
- A logarithmic time sort for linear size networks (1982) (43)
- A Note on the Succinctness of Descriptions of Deterministic Languages (1976) (42)
- Relational Learning for NLP using Linear Threshold Elements (1999) (36)
- Optimality of a Two-Phase Strategy for Routing in Interconnection Networks (1983) (36)
- A Quantitative Theory of Neural Computation (2006) (35)
- Optimally universal parallel computers (1988) (35)
- Deductive learning (1984) (35)
- A Combining Mechanism for Parallel Computers (1992) (34)
- Negation is Powerless for Boolean Slice Functions (1986) (34)
- Completeness for Parity Problems (2005) (33)
- A First Experimental Demonstration of Massive Knowledge Infusion (2008) (33)
- Circuit Size is Nonlinear in Depth (1975) (31)
- The Hippocampus as a Stable Memory Allocator for Cortex (2012) (27)
- Evolution with Drifting Targets (2010) (26)
- The Complexity of Symmetric Boolean Parity Holant Problems (2013) (25)
- Knowledge Infusion: In Pursuit of Robustness in Artificial Intelligence (2008) (24)
- Holographic Circuits (2005) (24)
- Efficient algorithms in computational learning theory (2001) (23)
- What must a global theory of cortex explain? (2014) (22)
- What can be learned (1986) (21)
- Experience-Induced Neural Circuits That Achieve High Capacity (2009) (20)
- A View of Computational Learning Theory (1993) (20)
- Why BSP computers? (bulk-synchronous parallel computers) (1993) (18)
- Autodidactic learning and reasoning (2008) (15)
- Fast Parallel Computation of Polynomials Using Few Processes (1981) (15)
- Why is Boolean Complexity Theory Di cult ? (1992) (14)
- Size Bounds for Superconcentrators (1983) (14)
- Leslie G. Valiant. A theory of the learnable. Communications of the ACM, (13)
- The Learning Power of Evolution (2008) (11)
- Why BSP Computers (1993) (10)
- Efficient learning from faulty data (1995) (9)
- Some observations on holographic algorithms (2010) (9)
- Computing Multivariate Polynomials in Parallel (1980) (7)
- The Complexity of Combinatorial Computations: An Introduction (1978) (7)
- The Complexity of Symmetric Boolean Parity Holant Problems - (Extended Abstract) (2011) (7)
- The decidability of equivalence for deterministic finite-turn pushdown automata (1974) (6)
- The Equivalence Problem for D0L Systems and its Decidability for Binary Alphabets (1976) (6)
- [Tou90] David Touretsky. Advances in Neural Information Processing Systems, volume (5)
- Computational questions in evolution (2012) (5)
- Cognitive Computation (Extended Abstract). (1995) (4)
- Communication issues in parallel computation (1990) (3)
- Capacity of Neural Networks for Lifelong Learning of Composable Tasks (2017) (3)
- Negative Results on Counting (1979) (2)
- Proceedings of the Fourth Annual Workshop on Computational Learning Theory, University of California, Santa Cruz, August 5-7, 1991 (1991) (2)
- Efficiency and computational limitations of learning algorithms (2007) (2)
- Managing Complexity in Neurodial Circuits (1996) (2)
- What needs to be added to machine learning? (2018) (2)
- Classical Simulation of Quantum Computations (2005) (2)
- The intrinsic complexity of parallelism in comparison problems (1974) (1)
- Toward Identifying the Systems-Level Primitives of Cortex by In-Circuit Testing (2018) (1)
- Addendum: Computing Multivariate Polynomials in Parallel (1981) (1)
- A Neuroidal Architecture for Cognitive Computation a Neuroidal Architecture for Cognitive Computation (1996) (1)
- Primes in Arbitrarily Long Arithmetic Progression (2012) (0)
- Published Version Accessed (2009) (0)
- Functionality in Neurd Nets * (1999) (0)
- Corrigendum: Corrigendum to Expressiveness of matchgates (2003) (0)
- Valiant-Vazirani Theorem Ilya Posov June 24 , 2006 1 Introduction (0)
- Pragmatic Aspects of Complexity Theory (Panel) (1986) (0)
- Chapter 8 A View of Computational Learning Theory * (0)
- GRAPH-THEORETIC ARGUMENTS IN LOW-LEVEL CONAOLEXITY (2005) (0)
- Cognitive Com utation (1995) (0)
- A Combining Mechanism for Parallel Computers a Combining Mechanism for Parallel Computers (1992) (0)
- Perspectives on massively parallel computation (1992) (0)
- How to Augment Learning with Reasoning? (2021) (0)
- The Extent and Limitations of Mechanistic Explanations of Nature (2007) (0)
- A Computational Model for Cognition (Abstract) (1994) (0)
- Interconnection patterns for parallel computers (1986) (0)
- Biological evolution as a form of learning (2020) (0)
- Some observations on holographic algorithms (2017) (0)
- Space-time tradeoffs in computations (2019) (0)
- A neuroidal model for cognitive functions (1994) (0)
- Projection Learning Projection Learning (1997) (0)
- Recent Developments in the Theory of Learning (Abstract) (1987) (0)
- Neural Computations That Support Long Mixed Sequences of Knowledge Acquisition Tasks (2009) (0)
- An Algorithmic View of the Universe (2012) (0)

This paper list is powered by the following services:

## Other Resources About Leslie Valiant

## What Schools Are Affiliated With Leslie Valiant?

Leslie Valiant is affiliated with the following schools: