Leslie G. Valiant

According to our database1, Leslie G. Valiant authored at least 115 papers between 1973 and 2018.

Collaborative distances:

Awards

Turing Prize recipient

Turing Prize 2010, "For transformative contributions to the theory of computation, including the theory of probably approximately correct (Probably approximately correct learning|PAC) learning, the complexity of enumeration and of algebraic computation, and the theory of parallel and distributed computing.".

ACM Fellow

ACM Fellow 2012, "For transformative contributions to the theory of computation.".

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2018
Some observations on holographic algorithms.
Computational Complexity, 2018

2017
Capacity of Neural Networks for Lifelong Learning of Composable Tasks.
Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

2013
The Complexity of Symmetric Boolean Parity Holant Problems.
SIAM J. Comput., 2013

2012
The Hippocampus as a Stable Memory Allocator for Cortex.
Neural Computation, 2012

An Algorithmic View of the Universe.
Proceedings of the ACM Turing Centenary Celebration, 2012

2011
A bridging model for multi-core computing.
J. Comput. Syst. Sci., 2011

The Complexity of Symmetric Boolean Parity Holant Problems - (Extended Abstract).
Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

2010
Evolution with Drifting Targets
CoRR, 2010

Some Observations on Holographic Algorithms.
Proceedings of the LATIN 2010: Theoretical Informatics, 2010

Evolution with Drifting Targets.
Proceedings of the COLT 2010, 2010

2009
Experience-Induced Neural Circuits That Achieve High Capacity.
Neural Computation, 2009

Evolvability.
J. ACM, 2009

Neural Computations That Support Long Mixed Sequences of Knowledge Acquisition Tasks.
Proceedings of the Theory and Applications of Models of Computation, 6th Annual Conference, 2009

2008
Holographic Algorithms.
SIAM J. Comput., 2008

A First Experimental Demonstration of Massive Knowledge Infusion.
Proceedings of the Principles of Knowledge Representation and Reasoning: Proceedings of the Eleventh International Conference, 2008

Knowledge Infusion: In Pursuit of Robustness in Artificial Intelligence.
Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2008

A Bridging Model for Multi-core Computing.
Proceedings of the Algorithms, 2008

The Learning Power of Evolution.
Proceedings of the 21st Annual Conference on Learning Theory, 2008

2007
Evolvability.
Proceedings of the Mathematical Foundations of Computer Science 2007, 2007

2006
Evolvability.
Electronic Colloquium on Computational Complexity (ECCC), 2006

A Quantitative Theory of Neural Computation.
Biological Cybernetics, 2006

Accidental Algorithms.
Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

Knowledge Infusion.
Proceedings of the Proceedings, 2006

2005
Memorization and Association on a Realistic Neural Model.
Neural Computation, 2005

Holographic Algorithms
Electronic Colloquium on Computational Complexity (ECCC), 2005

Memorization and Association on a Realistic Neural Model
Electronic Colloquium on Computational Complexity (ECCC), 2005

Holographic Circuits.
Proceedings of the Automata, Languages and Programming, 32nd International Colloquium, 2005

Completeness for Parity Problems.
Proceedings of the Computing and Combinatorics, 11th Annual International Conference, 2005

2004
Holographic Algorithms (Extended Abstract).
Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

2003
Three problems in computer science.
J. ACM, 2003

2002
Expressiveness of matchgates.
Theor. Comput. Sci., 2002

Quantum Circuits That Can Be Simulated Classically in Polynomial Time.
SIAM J. Comput., 2002

2001
Quantum computers that can be simulated classically in polynomial time.
Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

2000
A neuroidal architecture for cognitive computation.
J. ACM, 2000

Robust logics.
Artif. Intell., 2000

1999
Projection Learning.
Machine Learning, 1999

Robust Logics.
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Relational Learning for NLP using Linear Threshold Elements.
Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, 1999

1998
A Neuroidal Architecture for Cognitive Computation.
Proceedings of the Automata, Languages and Programming, 25th International Colloquium, 1998

Projection Learning.
Proceedings of the Eleventh Annual Conference on Computational Learning Theory, 1998

1996
Managing Complexity in Neurodial Circuits.
Proceedings of the Algorithmic Learning Theory, 7th International Workshop, 1996

1995
Bulk synchronous parallel computing-a paradigm for transportable software.
Proceedings of the 28th Annual Hawaii International Conference on System Sciences (HICSS-28), 1995

Cognitive Computation (Extended Abstract).
Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

Rationality.
Proceedings of the Eigth Annual Conference on Computational Learning Theory, 1995

Circuits of the mind.
Oxford University Press, ISBN: 978-0-19-508926-4, 1995

1994
Direct Bulk-Synchronous Parallel Algorithms.
J. Parallel Distrib. Comput., 1994

Cryptographic Limitations on Learning Boolean Formulae and Finite Automata.
J. ACM, 1994

Learning Boolean Formulas.
J. ACM, 1994

A Computational Model for Cognition (Abstract).
Proceedings of the Technology and Foundations - Information Processing '94, Volume 1, Proceedings of the IFIP 13th World Computer Congress, Hamburg, Germany, 28 August, 1994

1993
Cryptographic Limitations on Learning Boolean Formulae and Finite Automata.
Proceedings of the Machine Learning: From Theory to Applications, 1993

Why BSP Computers?
Proceedings of the Seventh International Parallel Processing Symposium, 1993

1992
Direct Bulk-Synchronous Parallel Algorithms.
Proceedings of the Algorithm Theory, 1992

A Combining Mechanism for Parallel Computers.
Proceedings of the Parallel Architectures and Their Efficient Use, 1992

1990
A Bridging Model for Parallel Computation.
Commun. ACM, 1990

General Purpose Parallel Architectures.
Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity (A), 1990

1989
A General Lower Bound on the Number of Examples Needed for Learning
Inf. Comput., September, 1989

Cryptographic Limitations on Learning Boolean Formulae and Finite Automata
Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989

1988
Computational limitations on learning from examples.
J. ACM, 1988

Functionality in Neural Nets.
Proceedings of the First Annual Workshop on Computational Learning Theory, 1988

A General Lower Bound on the Number of Examples Needed for Learning.
Proceedings of the First Annual Workshop on Computational Learning Theory, 1988

Functionality in Neural Nets.
Proceedings of the 7th National Conference on Artificial Intelligence, 1988

1987
A logarithmic time sort for linear size networks.
J. ACM, 1987

On the Learnability of Boolean Formulae
Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987

Recent Developments in the Theory of Learning (Abstract).
Proceedings of the Automata, Languages and Programming, 14th International Colloquium, 1987

1986
NP is as Easy as Detecting Unique Solutions.
Theor. Comput. Sci., 1986

Random Generation of Combinatorial Structures from a Uniform Distribution.
Theor. Comput. Sci., 1986

Negation is Powerless for Boolean Slice Functions.
SIAM J. Comput., 1986

Pragmatic Aspects of Complexity Theory (Panel).
IFIP Congress, 1986

1985
A Complexity Theory Based on Boolean Algebra
J. ACM, April, 1985

NP Is as Easy as Detecting Unique Solutions
Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 1985

Learning Disjunction of Conjunctions.
Proceedings of the 9th International Joint Conference on Artificial Intelligence. Los Angeles, 1985

1984
Short Monotone Formulae for the Majority Function.
J. Algorithms, 1984

A Theory of the Learnable.
Commun. ACM, 1984

A Theory of the Learnable
Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30, 1984

1983
Size Bounds for Superconcentrators.
Theor. Comput. Sci., 1983

Optimality of a Two-Phase Strategy for Routing in Interconnection Networks.
IEEE Trans. Computers, 1983

Fast Parallel Computation of Polynomials Using Few Processors.
SIAM J. Comput., 1983

Exponential Lower Bounds for Restricted Monotone Circuits
Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 1983

A Logarithmic Time Sort for Linear Size Networks
Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 1983

1982
A Scheme for Fast Parallel Communication.
SIAM J. Comput., 1982

1981
Universality Considerations in VLSI Circuits.
IEEE Trans. Computers, 1981

A Fast Parallel Algorithm for Routing in Permutation Networks.
IEEE Trans. Computers, 1981

Addendum: Computing Multivariate Polynomials in Parallel.
Inf. Process. Lett., 1981

Universal Schemes for Parallel Communication
Proceedings of the 13th Annual ACM Symposium on Theory of Computing, 1981

Fast Parallel Computation of Polynomials Using Few Processes.
Proceedings of the Mathematical Foundations of Computer Science 1981, Strbske Pleso, Czechoslovakia, August 31, 1981

A Complexity Theory Based on Boolean Algebra
Proceedings of the 22nd Annual Symposium on Foundations of Computer Science, 1981

1980
Negation can be Exponentially Powerful.
Theor. Comput. Sci., 1980

Computing Multivariate Polynomials in Parallel.
Inf. Process. Lett., 1980

1979
The Complexity of Computing the Permanent.
Theor. Comput. Sci., 1979

The Complexity of Enumeration and Reliability Problems.
SIAM J. Comput., 1979

Fast Probabilistic Algorithms for Hamiltonian Circuits and Matchings.
J. Comput. Syst. Sci., 1979

Negative Results on Counting.
Proceedings of the Theoretical Computer Science, 1979

Completeness Classes in Algebra
Proceedings of the 11h Annual ACM Symposium on Theory of Computing, April 30, 1979

Negation Can Be Exponentially Powerful
Proceedings of the 11h Annual ACM Symposium on Theory of Computing, April 30, 1979

1978
The Complexity of Combinatorial Computations: An Introduction.
Proceedings of the GI - 8. Jahrestagung, Berlin, 1978, Proceedings, 1978

1977
On Time Versus Space.
J. ACM, 1977

Fast Probabilistic Algorithms for Hamiltonian Circuits and Matchings
Proceedings of the 9th Annual ACM Symposium on Theory of Computing, 1977

Graph-Theoretic Arguments in Low-Level Complexity.
Proceedings of the Mathematical Foundations of Computer Science 1977, 1977

1976
A Note on the Succinctness of Descriptions of Deterministic Languages
Information and Control, October, 1976

Circuit Size is Nonlinear in Depth.
Theor. Comput. Sci., 1976

Graph-Theoretic Properties in computational Complexity.
J. Comput. Syst. Sci., 1976

Shifting Graphs and Their Applications.
J. ACM, 1976

Relative Complexity of Checking and Evaluating.
Inf. Process. Lett., 1976

Universal Circuits (Preliminary Report)
Proceedings of the 8th Annual ACM Symposium on Theory of Computing, 1976

The Equivalence Problem for D0L Systems and its Decidability for Binary Alphabets.
ICALP, 1976

1975
Parallelism in Comparison Problems.
SIAM J. Comput., 1975

Deterministic One-Counter Automata.
J. Comput. Syst. Sci., 1975

General Context-Free Recognition in Less than Cubic Time.
J. Comput. Syst. Sci., 1975

Regularity and Related Problems for Deterministic Pushdown Automata.
J. ACM, 1975

On Non-linear Lower Bounds in Computational Complexity
Proceedings of the 7th Annual ACM Symposium on Theory of Computing, 1975

On Time versus Space and Related Problems
Proceedings of the 16th Annual Symposium on Foundations of Computer Science, 1975

1974
The Equivalence Problem for Deterministic Finite-Turn Pushdown Automata
Information and Control, June, 1974

The Decidability of Equivalence for Deterministic Finite-Turn Pushdown Automata
Proceedings of the 6th Annual ACM Symposium on Theory of Computing, April 30, 1974

1973
Decision procedures for families of deterministic pushdown automata.
PhD thesis, 1973

Deterministic one-counter automata.
Proceedings of the 1. Fachtagung über Automatentheorie und Formale Sprachen, 1973


  Loading...