Home
Document Actions
Leslie Valiant
- T. Jefferson Coolidge Professor of Computer Science and Applied Mathematics
Contact Information
| Nickname: | Les |
| Office: | Maxwell Dworkin Building 351 |
| Email: | valiant [ AT ] seas [ DOT ] harvard [ DOT ] edu |
| Office Phone: | (617) 495-5817 |
| Office Fax: | (617) 496-6404 |
| Assistant: | Carol Harlow |
| Office: | Maxwell Dworkin 343 |
| Email: | harlow [ AT ] seas [ DOT ] harvard [ DOT ] edu |
| Office Phone: | 617/496-1440 |
| Lab Phone: | (617) 495-5817 |
Recruitment Status
Education
- B.A., 1970, Mathematics, University of Cambridge
- D.I.C., 1973, Computer Science, Imperial College, London
- Ph.D., 1974, Computer Science, University of Warwick
Research Interests
-
- Applied Mathematics & Computational Science
- Theory of Computation
-
- Marriage of Biological & Artificial Systems
- Computational Neuroscience and Evolution
Primary Teaching Area
Profile
Computer science encompasses the study of both artificial as well as natural phenomena. The former concern artificially created devices such as computers. The latter relate to the many step-by-step, or computational, processes found in nature such as in the brain or in the course of biological evolution. In most areas, whether natural or artificial, the ultimate limitations of such processes are as yet not well understood. The potential of computing devices may be currently far from being fully realized, while fundamental quantitative questions in neuroscience and evolution remain unanswered. Professor Valiant's current research focuses on a number of such basic questions.
The majority of computational problems, including those with explicit mathematical characterizations such as the NP-complete problems, fall within the category of those for which the question of how best to compute them is little understood. These core problems of complexity theory remain the most fundamental mathematical challenges of computer science. They are related to foundational questions in quantum physics, most notably through polynomial time versions of the Turing hypothesis. Professor Valiant has proposed algebraic formulations of these questions, and is currently pursuing the holographic approach.
In computer systems major conceptual challenges remain in controlling, load-balancing and programming large parallel systems, whether they be multicore devices on a chip or highly distributed systems. Professor Valiant's most recent interest in this area concerns the problem of how to design algorithms for multi-core devices that are portable, and run efficiently on wide classes of architectural designs with widely varying performance characteristics.
A fundamental question for artificial intelligence is to characterize the computational building blocks that are necessary for cognition. A specific challenge is to build on the success of machine learning so as to cover broader issues in intelligence. This requires, in particular a reconciliation between two contradictory characteristics--the apparent logical nature of reasoning and the statistical nature of learning. Professor Valiant has developed a formal system, called robust logics, that aims to achieve such a reconciliation.
In neuroscience a widely open problem remains how the weak model of computation that cortex apparently offers can support cognitive computation at all. Professor Valiant has been working on showing how broad sets of primitive operations can be computed robustly and on a significant scale even on such a weak model.
A challenge in a different direction is understanding how Darwinian evolution can evolve complex mechanisms in the numbers of generations and with population sizes that have apparently been available on earth. Darwin's notions of variation and selection are computational notions and offer a very direct challenge for quantitative analysis by the methods of computer science. What is sought is a quantitative understanding of the possibilities and limitations of the basic Darwinian process.
Positions & Employment
Harvard School of Engineering and Applied Sciences
- 1982-Present. Since 2001: T. Jefferson Coolidge Professor of Computer Science and Applied Mathematics
- 1977-1982: Faculty Member
- 1974-1976: Faculty Member
- 1973-1974: Visiting Faculty Member
Other Experience
- Fellow, Royal Society (London)
- Fellow, American Association for Artificial Intelligence
- Member, National Academy of Sciences
Honors
- Turing Award, 2010
- European Association for Theoretical Computer Science Award, 2008
- Knuth Prize, 1997
- Nevanlinna Prize, 1986
Selected Publications
71. Circuits of the Mind, Oxford University Press, (1994, 2000).
72. Robust logics, Artificial Intelligence Journal, 117 (2000) 231-253.
73. A neuroidal architecture for cognitive computation, J. Assoc. Computing Machinery, 47:5 (2000) 854-882.
74. Quantum circuits that can be simulated classically in polynomial time, SIAM J. on Computing, 31:4 (2002) 1229-1254.
75. Expressiveness of matchgates, Theoretical Computer Science, 289:1 (2002) 457-471 (and 299 (2003) 795.
76. Three problems in computer science, J. Assoc. Computing Machinery, 50:1 (2003) 96-99.
77. Holographic algorithms (extended abstract), Proc. 45th Annual IEEE Symposium on Foundations of Computer Science, Oct 17-19, Rome, Italy, (2004). IEEE Press, 306-315.
78. Memorization and association on a realistic neural model, Neural Computation, 17:3 (2005) 527-555.
79. Holographic circuits, Proc. 32nd International Colloquium on Automata, Languages and Programming, July 11-15, Lisbon, Portugal, LNCS, Vol. 3580, (2005), Springer-Verlag, 1-15.
80. Completeness for parity problems, Proc. 11th International Computing and Combinatorics Conference, Aug 16-19, Kunming, China, LNCS, Vol. 3959, (2005), Springer-Verlag, 1-9.
81. A quantitative theory of neural computation, Biological Cybernetics, 95:3 (2006) 205-211.
82. Knowledge infusion, Proc. 21st National Conference on Artificial Intelligence, AAAI06, Jul 16-20, Boston, MA, AAAI Press, (2006), 1546-1551.
83. Accidental algorithms, Proc. 47th Annual IEEE Symposium on Foundations of Computer Science, Oct 22 -24, Berkeley, CA, IEEE Press, (2006), 509-517.
84. Holographic algorithms, SIAM J. on Computing, 37:5 (2008) 1565-1594. (Earlier version: Electronic Colloquium on Computational Complexity, Report TR05-099, (2005).)
85. A first experimental demonstration of massive knowledge infusion, (with Loizos Michael), Proc. 11th International Conference on Principles of Knowledge Representation and Reasoning, Sept. 16-20, 2008, Sydney, Australia, 378-389.
86. Knowledge infusion: In pursuit of robustness in artificial intelligence, Proc 28th Conference on Foundations of Software Technology and Theoretical Computer Science, Dec 9-11, 2008, Bangalore, India, Indian Association for Research in Computing Science, 415-422.
87. Evolvability, J. Assoc. Computing Machinery, 56:1 (2009) 3:1 - 3:21. (Earlier version: Proc. 32nd International Symposium on Mathematical Foundations of Computer Science, Aug. 26-31, Český Krumlov, Czech Republic, LNCS, Vol 4708, (2007) Springer-Verlag, 22-43.)
88. Experience-induced neural circuits that achieve high capacity, (with Vitaly Feldman), Neural Computation, 21:10 (2009) 2715-2754.
89. A bridging model for multi-core computing, Journal of Computer and System Sciences, 77:1 (2011) 154-166 . (Earlier version: Proc. 16th Annual European Symposium on Algorithms, Sept. 15-17, 2008, Karlsruhe, Germany, LNCS, Vol 5193, (2008), Springer-Verlag, 13-28.)
90. Some observations on holographic algorithms, Proc. 9th Latin American Theoretical Informatics Symposium, LATIN 2010: Oaxaca, Mexico, April 19-23, 2010, LNCS, Vol 6034 Springer-Verlag (2010), 577-590.
91. Evolution with drifting targets, (with Varun Kanade and Jennifer Wortman Vaughan), Proc, 23rd Annual Conference on Learning Theory, (COLT 2010).
