Articles by Leslie Valiant before 2000:

1. The equivalence problem for deterministic finite-turn pushdown automata. Information and Control, 25, (1974), pp.123-133.


2. Regularity and related problems for deterministic pushdown automata. J. ACM, 22, (1975), pp.1-10.


3. Deterministic one-counter automata, (with M. S. Paterson). J. Computer and System Sciences 10, (1975) pp.340-350.


4. Parallelism in comparison problems. SIAM J. on Computing, 4, (1975), pp.348-355.


5. General context-free recognition in less than cubic time. J. Computer and System Sciences, 10, (1975), pp.308-315.


6. On non-linear lower bounds in computational complexity. Proc. 7th ACM. Symp. on Theory of Computing, Albuquerque, NM, May 5-7, 1975. pp.45-53.


7. Relative complexity of checking and evaluating. Information Processing Letters, 5 (1976), pp.20-23.


8. Shifting graphs and their applications, (with N. J. Pippenger). J. ACM 23 (1976), pp.423-432.


9. Graph theoretic properties in computational complexity. J. Computer and System Sciences, 13, (1976), pp.278-285.


10. Circuit size is non-linear in depth, (with M. S. Paterson). Theoretical Computer Science, 2 (1976) pp.397-400.


11. The equivalence problem for DOL systems and its decidability for binary alphabets.; In Automata, Languages and Programming, (S. Michaelson and R. Milner, eds.), Edinburgh University Press (1976), pp.31-37.


12. Space time tradeoffs in computation. Asterisque 38, (1976), pp. 253-264.


13. A note on the succinctness of descriptions of deterministic languages. Information and Control 32, (1976), pp.139-145.


14. On time versus space, (with J. E. Hopcroft and W. J. Paul). J. ACM 24, (1977), pp.332-337.


15. Fast probabilistic algorithms for Hamiltonian circuits and matchings, (with D. Angluin). J. Computer and System Sciences, 18: 2, (1979), pp.155-193.


16. Graph theoretic arguments in low-level complexity. Lecture Notes in Computer Science, 53, Springer Verlag (1977), pp.162-176.


17. Universal circuits. Proc. 8th ACM. Symp. on Theory of Computing, Hershey, PA, May (1976), pp.196-203.


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


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


20. The complexity of combinatorial computations. In GI8 Jahrestagung Informatik, Fachbereichte Band 16, (S. Schindler and W. K. Giloi, eds.) Springer-Verlag (1978), pp.326-337.


21. Completeness classes in algebra. Proc. 11th ACM. Symp. on Theory of Computing, Atlanta, GA, April 30 - May 2, 1979. pp. 249-261.


22. Negative results on counting. Lecture Notes in Computer Science, 67, Springer-Verlag (1979), pp. 38-46.


23. Negation can be exponentially powerful. Theoretical Computer Science 12 (1980), pp.303-314.


24. A fast parallel algorithm for routing in permutation networks. (with G. Lev and N. J. Pippenger), IEEE Trans. on Computers C-30, 2 (1981), pp.93-100.


25. Computing multivariate polynomials in parallel. Information Processing Letters, 11:1 (1980), pp. 44-45 and 12:1 (1981), p. 54.


26. Universality considerations in VLSI circuits. IEEE Trans. on Computers C-30:2 (1981), pp. 135-140.


27. Reducibility by algebraic projections. Monographie No. 30 de L'Enseignement Mathematique: Logic and Algorithmic, Geneva (1982),pp.365-380.


28. A scheme for fast parallel communication. SIAM J. Computing, 11: 2 (1982), 350-361.


29. Experiments with a parallel communication scheme. Proc. 18th Allerton Conference on Communication Control and Computing, University of Illinois (1980), pp. 802-811.


30. Size bounds for superconcentrators, (with G. Lev). Theoretical Computer Science 22, 3 (1983), pp.233-252.


31. Universal schemes for parallel communication, (with G. J. Brebner). Proc. 13th ACM. Symp. on Theory of Computing, Milwaukee, IL, May 11-13, 1981, pp.263-277.


32. Fast parallel computation of polynomials using few processors, (with S. Skyum). Lecture Notes in Computer Science, 118, Springer Verlag (1981), pp.132-139.


33. A complexity theory based on Boolean algebra, (with S. Skyum). J. ACM 32: 2 (1985) pp.484-502.


34. Parallel computation. Proc. of 7th IBM Symp. on Mathematical Foundations of Computer Science, Hakone, Japan, May 24-26, 1982, pp.171-189.


35. Optimality of a two-phase strategy for routing in interconnection network. IEEE Trans. on Computers, C-32:9 (1983), pp.861-863.


36. Fast parallel computation of polynomials using few processors, (with S. Skyum, S. Berkowitz and C. Rackoff). SIAM J. Computing, 12:4 (1983), pp.641-644.


37. A logarithmic time sort on linear size networks, (with J. H. Reif). J. ACM. 34:1 (1987) 60-76.


38. Exponential lower bounds for restricted monotone circuits. Proc. 15th ACM. Symp. on Theory of Computing, Boston, MA, April 25-27, 1983. pp.110-117.


39. Short monotone formulae for the majority function. J. Algorithms 5 (1984), pp.363-366.


40. An algebraic approach to computational complexity. Proc. International Congress of Mathematicians, August 1983. Polish Scientific Publishers, Warsaw, and Elsevier Science Publishers, Amsterdam, Vol. 2, pp. 1637-1644.


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


42. Deductive learning. Phil. Trans. R. Soc. Lond. A 312 (1984), pp.441-446. (Also in Mathematical Logic and Programming Languages, C. A. R. Hoare and J. C. Shepherdson, eds. Prentice-Hall, Englewood Cliffs, NJ. (1985), pp. 107-112.


43. Negation is powerless for Boolean slice functions. SIAM J. Computing. 15:2 (1986) 531-535.


44. NP is as easy as detecting single solutions. (with V. V. Vazirani) Theoretical Computer . 47 (1986) 85-93.


45. Learning disjunctions of conjunctions. Proc. Ninth International Joint Conferences on Artificial Intelligence, Los Angeles, CA (August 1985) pp. 560-566.


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


47. On the learnability of Boolean formulae. (with M. Kearns, M. Li, and L. Pitt) Proc. 19th ACM Symp. on Theory of Computing, New York, NY, May 25-27 (1987) 285-295.


48. Recent results on Boolean concept learning. (with M. Kearns, M. Li and L. Pitt) Proc 4th Int. Workshop on Machine Learning, Morgan Kaufmann, Los Altos, CA (1987) 337-352.


49. Computational limitations on learning from examples, (with L. Pitt). J. ACM, 35:4 (1988) 965-984.


50. A general lower bound on the number of examples needed for learning. (with A. Ehrenfeucht, D. Haussler and M. Kearns) Inf. and Computation. 82:2 (1989) 247-261.


51. Optimally universal parallel computers. Phil. Trans. R. Soc. London. A326 (1988) 373-376.


52. Functionality in neural nets. Proc. American Association for Artificial Intelligence 1988, Morgan Kaufmann, San Mateo, CA, (1988) 629-634.


53. Bulk-synchronous parallel computers. In Parallel Processing and Artificial Intelligence. (M. Reeve and S. Zenith, eds.), John Wiley and Sons, (1989) 15-22.


54. General purpose parallel architectures. In Handbook of Theoretical Computer Science (J. van Leeuwen, ed.), North Holland, Amsterdam (1990) pp. 944-971.


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


56. A view of computational learning theory. In Computation and Cognition (C.W. Gear, ed.), Soc. Ind. and Appl. Math., Philadelphia, (1990) 32-53.


57. Why is Boolean complexity theory difficult? In Boolean Function Complexity, (M.S. Paterson, ed.), London Mathematical Society Lecture Note Series, Cambridge University Press, 169 (1992) 84-94.


58. Direct bulk-synchronous parallel algorithms. (with A.V. Gerbessiotis.) J. of Parallel and Distributed Computing, 22 (1994) 251-267.


59. A combining mechanism for parallel computers. In Parallel Architectures and Their Efficient Use. Lecture Notes in Computer Science vol. 678, Springer-Verlag, (1993) 1-10.


60. Why BSP computers? In Proc 7th International Parallel Processing Symposium, IEEE Computer Society Press, Los Alamitos, CA (1993) 2-5.


61. Cryptographic limitations on learning Boolean formulae and finite automata. (with M. Kearns) J. ACM, 41:1 (1994) 67-95. (Preliminary version in Proc. 21st ACM Symp. on Theory of Computing , ACM Press, New York, NY. (1989) 433-444.)


62. Learning Boolean formulas (with M. Kearns and M. Li).J.ACM, 41:6 (1994) 1298-1328.


63. A neuroidal model for cognition. In Natural and Artificial Parallel Computation, (D.L. Waltz, ed.) Soc. Ind. and Appl. Math., Philadelphia, (1995) 127-140.


64. Bulk-synchronous parallel computing - a paradigm for transportable software. (with T. Cheatham, A. Fahmy, and D. Stefanescu.) In Proc. 28th Hawaii International Conference on System Science, Wailea, Maui, Hawaii, Jan 3-6 (1995).


65. Rationality. Proc. 8th ACM Workshop on Computational Learning Theory, ACM Press, (1995), 3-14.


66. Some theoretical questions in neuroscience, In Cortical Dynamics in Jerusalem (M. Abeles and H. Sompolinsky, eds.), The Hebrew University Center for Neural Computation, (1995) 793-798.


67. Cognitive computation. Proc. 36th IEEE Symp. on Foundations of Computer Science, IEEE Press, (1995) 2-3.


68. Managing complexity in neuroidal circuits. In Algorithmic Learning Theory (S. Arikawa and A.K. Sharma, eds.) Lecture Notes in Artificial Intelligence, Vol. 1160, Springer Verlag, Berlin 1996, pp. 1-11.


69. Relational learning for NLP using linear threshold elements. (with R. Khardon and D. Roth), In Proc Sixteenth International Joint Conferences on Artificial Intelligence, IJCAI 1999, Stockholm, Sweden, July 1999. Morgan Kaufmann, 911-917.


70. Projection learning. Machine Learning 37:2 (1999)115-130.