Leslie Valiant
T. Jefferson Coolidge Professor of Computer Science and Applied Mathematics,
School of Engineering and Applied Sciences, Harvard University.

Contact Info:
Email: valiant seas harvard edu
Office: 351, Maxwell Dworkin,
            33, Oxford Street,
            Cambridge, MA 02138.
Office Hours: Thursdays 1.30-2.30 pm. Also on September 6: 2.00-3.00 pm.

Earlier Publications

Recent 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. Evolution with drifting targets, (with Varun Kanade and Jennifer Wortman Vaughan), Proc. 23rd Annual Conference on Learning Theory, COLT 2010, (2010), 155-167.

90. 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.)

91. The complexity of symmetric Boolean parity holant problems, (with Heng Guo and Pinyan Lu), SIAM J. on Computing, 42:1 (2013) 324-356 .

92. The hippocampus as a stable memory allocator for cortex Neural Computation, 24:11 (2012) 2873-2899.

93. Probably Approximately Correct: Nature's Algorithms for Learning and Prospering in a Complex World, Basic Books, (2013).

94. What must a global theory of cortex explain? Current Opinion in Neurobiology, 25C (2014) 15-19.

95. Some observations on holographic algorithms, Computational Complexity, To appear (2017).

96. Capacity of neural networks for lifelong learning of composable tasks, Proc. 58th Annual IEEE Symposium on Foundations of Computer Science, October 15 - 17, 2017, Berkeley, California , To appear (2017).


Current Research Interests

Bio

cv