We stand with Ukraine  

Leslie G. Valiant

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

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 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2021
How to Augment Learning with Reasoning?
[BibTeX]
[DOI]
Leslie G. Valiant
Proceedings of the WI-IAT '21: IEEE/WIC/ACM International Conference on Web Intelligence, Melbourne VIC Australia, December 14, 2021

2018
Some observations on holographic algorithms.
[BibTeX]
[DOI]
Leslie G. Valiant
Comput. Complex., 2018

What needs to be added to machine learning?
[BibTeX]
[DOI]
Leslie G. Valiant
Proceedings of ACM Turing Celebration Conference - China, 2018

2017
Capacity of Neural Networks for Lifelong Learning of Composable Tasks.
[BibTeX]
[DOI]
Leslie G. Valiant
Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

2013
The Complexity of Symmetric Boolean Parity Holant Problems.
[BibTeX]
[DOI]
Heng Guo
,
Pinyan Lu
,
Leslie G. Valiant
SIAM J. Comput., 2013

2012
The Hippocampus as a Stable Memory Allocator for Cortex.
[BibTeX]
[DOI]
Leslie G. Valiant
Neural Comput., 2012

An Algorithmic View of the Universe.
[BibTeX]
[DOI]
Christos H. Papadimitriou
,
Leonard M. Adleman
,
Richard M. Karp
,
Donald E. Knuth
,
Robert E. Tarjan
,
Leslie G. Valiant
Proceedings of the ACM Turing Centenary Celebration, 2012

2011
A bridging model for multi-core computing.
[BibTeX]
[DOI]
Leslie G. Valiant
J. Comput. Syst. Sci., 2011

The Complexity of Symmetric Boolean Parity Holant Problems - (Extended Abstract).
[BibTeX]
[DOI]
Heng Guo
,
Pinyan Lu
,
Leslie G. Valiant
Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

2010
Evolution with Drifting Targets.
[BibTeX]
[DOI]
Varun Kanade
,
Leslie G. Valiant
,
Jennifer Wortman Vaughan
Proceedings of the COLT 2010, 2010

2009
Experience-Induced Neural Circuits That Achieve High Capacity.
[BibTeX]
[DOI]
Vitaly Feldman
,
Leslie G. Valiant
Neural Comput., 2009

Evolvability.
[BibTeX]
[DOI]
Leslie G. Valiant
J. ACM, 2009

Neural Computations That Support Long Mixed Sequences of Knowledge Acquisition Tasks.
[BibTeX]
[DOI]
Leslie G. Valiant
Proceedings of the Theory and Applications of Models of Computation, 6th Annual Conference, 2009

2008
A First Experimental Demonstration of Massive Knowledge Infusion.
[BibTeX]
[DOI]
Loizos Michael
,
Leslie G. Valiant
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.
[BibTeX]
[DOI]
Leslie G. Valiant
Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2008

The Learning Power of Evolution.
[BibTeX]
[DOI]
Vitaly Feldman
,
Leslie G. Valiant
Proceedings of the 21st Annual Conference on Learning Theory, 2008

2006
A Quantitative Theory of Neural Computation.
[BibTeX]
[DOI]
Leslie G. Valiant
Biol. Cybern., 2006

Accidental Algorithms.
[BibTeX]
[DOI]
Leslie G. Valiant
Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

Knowledge Infusion.
[BibTeX]
[DOI]
Leslie G. Valiant
Proceedings of the Proceedings, 2006

2005
Memorization and Association on a Realistic Neural Model.
[BibTeX]
[DOI]
Leslie G. Valiant
Neural Comput., 2005

Holographic Algorithms
[BibTeX]
[DOI]
Leslie G. Valiant
Electron. Colloquium Comput. Complex., 2005

Holographic Circuits.
[BibTeX]
[DOI]
Leslie G. Valiant
Proceedings of the Automata, Languages and Programming, 32nd International Colloquium, 2005

Completeness for Parity Problems.
[BibTeX]
[DOI]
Leslie G. Valiant
Proceedings of the Computing and Combinatorics, 11th Annual International Conference, 2005

2004
Holographic Algorithms (Extended Abstract).
[BibTeX]
[DOI]
Leslie G. Valiant
Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

2003
Three problems in computer science.
[BibTeX]
[DOI]
Leslie G. Valiant
J. ACM, 2003

2002
Expressiveness of matchgates.
[BibTeX]
[DOI]
Leslie G. Valiant
Theor. Comput. Sci., 2002

Quantum Circuits That Can Be Simulated Classically in Polynomial Time.
[BibTeX]
[DOI]
Leslie G. Valiant
SIAM J. Comput., 2002

2001
Quantum computers that can be simulated classically in polynomial time.
[BibTeX]
[DOI]
Leslie G. Valiant
Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

2000
A neuroidal architecture for cognitive computation.
[BibTeX]
[DOI]
Leslie G. Valiant
J. ACM, 2000

Robust logics.
[BibTeX]
[DOI]
Leslie G. Valiant
Artif. Intell., 2000

1999
Projection Learning.
[BibTeX]
[DOI]
Leslie G. Valiant
Mach. Learn., 1999

Relational Learning for NLP using Linear Threshold Elements.
[BibTeX]
[DOI]
Roni Khardon
,
Dan Roth
,
Leslie G. Valiant
Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, 1999

1996
Managing Complexity in Neurodial Circuits.
[BibTeX]
[DOI]
Leslie G. Valiant
Proceedings of the Algorithmic Learning Theory, 7th International Workshop, 1996

1995
Bulk synchronous parallel computing-a paradigm for transportable software.
[BibTeX]
[DOI]
Thomas E. Cheatham
,
Amr F. Fahmy
,
Dan C. Stefanescu
,
Leslie G. Valiant
Proceedings of the 28th Annual Hawaii International Conference on System Sciences (HICSS-28), 1995

Cognitive Computation (Extended Abstract).
[BibTeX]
[DOI]
Leslie G. Valiant
Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

Rationality.
[BibTeX]
[DOI]
Leslie G. Valiant
Proceedings of the Eigth Annual Conference on Computational Learning Theory, 1995

Circuits of the mind.
[BibTeX]
Leslie G. Valiant
Oxford University Press, ISBN: 978-0-19-508926-4, 1995

1994
Direct Bulk-Synchronous Parallel Algorithms.
[BibTeX]
[DOI]
Alexandros V. Gerbessiotis
,
Leslie G. Valiant
J. Parallel Distributed Comput., 1994

Cryptographic Limitations on Learning Boolean Formulae and Finite Automata.
[BibTeX]
[DOI]
Michael J. Kearns
,
Leslie G. Valiant
J. ACM, 1994

Learning Boolean Formulas.
[BibTeX]
[DOI]
Michael J. Kearns
,
Ming Li
,
Leslie G. Valiant
J. ACM, 1994

A Computational Model for Cognition (Abstract).
[BibTeX]
Leslie G. Valiant
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
Why BSP Computers?
[BibTeX]
[DOI]
Leslie G. Valiant
Proceedings of the Seventh International Parallel Processing Symposium, 1993

A neuroidal model for cognitive functions.
[BibTeX]
Leslie G. Valiant
Proceedings of the First European Conference on Computational Learning Theory, 1993

1992
A Combining Mechanism for Parallel Computers.
[BibTeX]
[DOI]
Leslie G. Valiant
Proceedings of the Parallel Architectures and Their Efficient Use, 1992

1990
A Bridging Model for Parallel Computation.
[BibTeX]
[DOI]
Leslie G. Valiant
Commun. ACM, 1990

General Purpose Parallel Architectures.
[BibTeX]
Leslie G. Valiant
Proceedings of the Handbook of Theoretical Computer Science, 1990

1989
A General Lower Bound on the Number of Examples Needed for Learning
[BibTeX]
[DOI]
Andrzej Ehrenfeucht
,
David Haussler
,
Michael J. Kearns
,
Leslie G. Valiant
Inf. Comput., September, 1989

1988
Computational limitations on learning from examples.
[BibTeX]
[DOI]
Leonard Pitt
,
Leslie G. Valiant
J. ACM, 1988

Functionality in Neural Nets.
[BibTeX]
[DOI]
Leslie G. Valiant
Proceedings of the 7th National Conference on Artificial Intelligence, 1988

1987
A logarithmic time sort for linear size networks.
[BibTeX]
[DOI]
John H. Reif
,
Leslie G. Valiant
J. ACM, 1987

On the Learnability of Boolean Formulae
[BibTeX]
[DOI]
Michael J. Kearns
,
Ming Li
,
Leonard Pitt
,
Leslie G. Valiant
Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987

Recent Developments in the Theory of Learning (Abstract).
[BibTeX]
[DOI]
Leslie G. Valiant
Proceedings of the Automata, Languages and Programming, 14th International Colloquium, 1987

1986
NP is as Easy as Detecting Unique Solutions.
[BibTeX]
[DOI]
Leslie G. Valiant
,
Vijay V. Vazirani
Theor. Comput. Sci., 1986

Random Generation of Combinatorial Structures from a Uniform Distribution.
[BibTeX]
[DOI]
Mark Jerrum
,
Leslie G. Valiant
,
Vijay V. Vazirani
Theor. Comput. Sci., 1986

Negation is Powerless for Boolean Slice Functions.
[BibTeX]
[DOI]
Leslie G. Valiant
SIAM J. Comput., 1986

Pragmatic Aspects of Complexity Theory (Panel).
[BibTeX]
Leslie G. Valiant
Proceedings of the Information Processing 86, 1986

1985
A Complexity Theory Based on Boolean Algebra
[BibTeX]
[DOI]
Sven Skyum
,
Leslie G. Valiant
J. ACM, April, 1985

Learning Disjunction of Conjunctions.
[BibTeX]
[DOI]
Leslie G. Valiant
Proceedings of the 9th International Joint Conference on Artificial Intelligence. Los Angeles, 1985

1984
Short Monotone Formulae for the Majority Function.
[BibTeX]
[DOI]
Leslie G. Valiant
J. Algorithms, 1984

A Theory of the Learnable.
[BibTeX]
[DOI]
Leslie G. Valiant
Commun. ACM, 1984

1983
Size Bounds for Superconcentrators.
[BibTeX]
[DOI]
G. Lev
,
Leslie G. Valiant
Theor. Comput. Sci., 1983

Optimality of a Two-Phase Strategy for Routing in Interconnection Networks.
[BibTeX]
[DOI]
Leslie G. Valiant
IEEE Trans. Computers, 1983

Fast Parallel Computation of Polynomials Using Few Processors.
[BibTeX]
[DOI]
Leslie G. Valiant
,
Sven Skyum
,
S. Berkowitz
,
Charles Rackoff
SIAM J. Comput., 1983

Exponential Lower Bounds for Restricted Monotone Circuits
[BibTeX]
[DOI]
Leslie G. Valiant
Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 1983

1982
A Scheme for Fast Parallel Communication.
[BibTeX]
[DOI]
Leslie G. Valiant
SIAM J. Comput., 1982

1981
Universality Considerations in VLSI Circuits.
[BibTeX]
[DOI]
Leslie G. Valiant
IEEE Trans. Computers, 1981

A Fast Parallel Algorithm for Routing in Permutation Networks.
[BibTeX]
[DOI]
Gavriela Freund Lev
,
Nicholas Pippenger
,
Leslie G. Valiant
IEEE Trans. Computers, 1981

Addendum: Computing Multivariate Polynomials in Parallel.
[BibTeX]
Leslie G. Valiant
Inf. Process. Lett., 1981

Universal Schemes for Parallel Communication
[BibTeX]
[DOI]
Leslie G. Valiant
,
Gordon J. Brebner
Proceedings of the 13th Annual ACM Symposium on Theory of Computing, 1981

Fast Parallel Computation of Polynomials Using Few Processes.
[BibTeX]
[DOI]
Leslie G. Valiant
,
Sven Skyum
Proceedings of the Mathematical Foundations of Computer Science 1981, Strbske Pleso, Czechoslovakia, August 31, 1981

1980
Negation can be Exponentially Powerful.
[BibTeX]
[DOI]
Leslie G. Valiant
Theor. Comput. Sci., 1980

Computing Multivariate Polynomials in Parallel.
[BibTeX]
[DOI]
Leslie G. Valiant
Inf. Process. Lett., 1980

1979
The Complexity of Computing the Permanent.
[BibTeX]
[DOI]
Leslie G. Valiant
Theor. Comput. Sci., 1979

The Complexity of Enumeration and Reliability Problems.
[BibTeX]
[DOI]
Leslie G. Valiant
SIAM J. Comput., 1979

Fast Probabilistic Algorithms for Hamiltonian Circuits and Matchings.
[BibTeX]
[DOI]
Dana Angluin
,
Leslie G. Valiant
J. Comput. Syst. Sci., 1979

Negative Results on Counting.
[BibTeX]
[DOI]
Leslie G. Valiant
Proceedings of the Theoretical Computer Science, 1979

Completeness Classes in Algebra
[BibTeX]
[DOI]
Leslie G. Valiant
Proceedings of the 11h Annual ACM Symposium on Theory of Computing, April 30, 1979

1978
The Complexity of Combinatorial Computations: An Introduction.
[BibTeX]
[DOI]
Leslie G. Valiant
Proceedings of the GI - 8. Jahrestagung, Berlin, 1978, Proceedings, 1978

1977
On Time Versus Space.
[BibTeX]
[DOI]
John E. Hopcroft
,
Wolfgang J. Paul
,
Leslie G. Valiant
J. ACM, 1977

Graph-Theoretic Arguments in Low-Level Complexity.
[BibTeX]
[DOI]
Leslie G. Valiant
Proceedings of the Mathematical Foundations of Computer Science 1977, 1977

1976
A Note on the Succinctness of Descriptions of Deterministic Languages
[BibTeX]
[DOI]
Leslie G. Valiant
Inf. Control., October, 1976

Circuit Size is Nonlinear in Depth.
[BibTeX]
[DOI]
Mike Paterson
,
Leslie G. Valiant
Theor. Comput. Sci., 1976

Graph-Theoretic Properties in computational Complexity.
[BibTeX]
[DOI]
Leslie G. Valiant
J. Comput. Syst. Sci., 1976

Shifting Graphs and Their Applications.
[BibTeX]
[DOI]
Nicholas Pippenger
,
Leslie G. Valiant
J. ACM, 1976

Relative Complexity of Checking and Evaluating.
[BibTeX]
[DOI]
Leslie G. Valiant
Inf. Process. Lett., 1976

Universal Circuits (Preliminary Report)
[BibTeX]
[DOI]
Leslie G. Valiant
Proceedings of the 8th Annual ACM Symposium on Theory of Computing, 1976

The Equivalence Problem for D0L Systems and its Decidability for Binary Alphabets.
[BibTeX]
Leslie G. Valiant
Proceedings of the Third International Colloquium on Automata, 1976

1975
Parallelism in Comparison Problems.
[BibTeX]
[DOI]
Leslie G. Valiant
SIAM J. Comput., 1975

Deterministic One-Counter Automata.
[BibTeX]
[DOI]
Leslie G. Valiant
,
Mike Paterson
J. Comput. Syst. Sci., 1975

General Context-Free Recognition in Less than Cubic Time.
[BibTeX]
[DOI]
Leslie G. Valiant
J. Comput. Syst. Sci., 1975

Regularity and Related Problems for Deterministic Pushdown Automata.
[BibTeX]
[DOI]
Leslie G. Valiant
J. ACM, 1975

On Non-linear Lower Bounds in Computational Complexity
[BibTeX]
[DOI]
Leslie G. Valiant
Proceedings of the 7th Annual ACM Symposium on Theory of Computing, 1975

On Time versus Space and Related Problems
[BibTeX]
[DOI]
John E. Hopcroft
,
Wolfgang J. Paul
,
Leslie G. Valiant
Proceedings of the 16th Annual Symposium on Foundations of Computer Science, 1975

1974
The Equivalence Problem for Deterministic Finite-Turn Pushdown Automata
[BibTeX]
[DOI]
Leslie G. Valiant
Inf. Control., June, 1974

The Decidability of Equivalence for Deterministic Finite-Turn Pushdown Automata
[BibTeX]
[DOI]
Leslie G. Valiant
Proceedings of the 6th Annual ACM Symposium on Theory of Computing, April 30, 1974

1973
Decision procedures for families of deterministic pushdown automata.
[BibTeX]
[DOI]
Leslie G. Valiant
PhD thesis, 1973


  Loading...