Leslie Valiant - Selected Publications#

1. Some observations on holographic algorithms, Computational Complexity, 27(3): 351-374 (2018).

2. Capacity of Neural Networks for Lifelong Learning of Composable Tasks. Proc. 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS), (2017) 367-378.

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

4. A bridging model for multi-core computing, Journal of Computer and System Sciences, 77:1 (2011) 154-166.

5. Holographic algorithms, SIAM J. on Computing, 37:5, (2008) 1565-1594.

6. Circuits of the Mind, Oxford University Press, (2000)

7. Cryptographic limitations on learning Boolean formulae and finite automata. (with M. Kearns) J. ACM, 41:1 (1994) 67-95.

8. A bridging model for parallel computation. C.ACM, 33:8 (1990) pp. 103-111.

9. Random generation of combinatorial structures from a uniform distribution. (with M. R. Jerrum and V. V. Vazirani). Theoretical Computer Science 43 (1986) 169-188.

10. A theory of the learnable. C.ACM 27:11 (1984) pp.1134-1142.

11. The complexity of enumeration and reliability problems. SIAM J. Computing, 8:3 (1979), pp.410-421.

12. The complexity of computing the permanent. Theoretical Computer Science, 8 (1979), pp. 189-201.

Valiant's work has been recognized by numerous awards, such as the Nevanlinna Prize in 1986 from the International Mathematical Union, the Knuth Prize in 1997, the European Association for Theoretical Computer Science (EATCS) Award in 2008, and the Turing Award in 2010.