Leslie G. Valiant
According to our database^{1},
Leslie G. Valiant
authored at least 115 papers
between 1973 and 2018.
Collaborative distances:
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 learningPAC) 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 OtherLinks
Homepages:

at zbmath.org

at viaf.org

at isni.org

at id.loc.gov

at dnb.info

at dl.acm.org
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 multicore 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
ExperienceInduced 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 Multicore 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 ThirtyFirst 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 computinga paradigm for transportable software.
Proceedings of the 28th Annual Hawaii International Conference on System Sciences (HICSS28), 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: 9780195089264, 1995
1994
Direct BulkSynchronous 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 BulkSynchronous 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 TwoPhase 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
GraphTheoretic Arguments in LowLevel 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
GraphTheoretic 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 OneCounter Automata.
J. Comput. Syst. Sci., 1975
General ContextFree Recognition in Less than Cubic Time.
J. Comput. Syst. Sci., 1975
Regularity and Related Problems for Deterministic Pushdown Automata.
J. ACM, 1975
On Nonlinear 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 FiniteTurn Pushdown Automata
Information and Control, June, 1974
The Decidability of Equivalence for Deterministic FiniteTurn 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 onecounter automata.
Proceedings of the 1. Fachtagung über Automatentheorie und Formale Sprachen, 1973