**Articles by Leslie Valiant before 2000:**

- The equivalence problem for deterministic finite-turn pushdown automata.
*Information and**Control*,__25__, (1974), pp.123-133. - Regularity and related problems for deterministic pushdown automata.
*J. ACM*,__22__, (1975), pp.1-10. - Deterministic one-counter automata, (with M. S. Paterson).
*J. Computer and System**Sciences*__10__, (1975) pp.340-350. - Parallelism in comparison problems.
*SIAM J. on Computing*,__4__, (1975), pp.348-355. - General context-free recognition in less than cubic time.
*J. Computer and System Sciences*,__10__, (1975), pp.308-315. - 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. - Relative complexity of checking and evaluating.
*Information Processing Letters*, 5 (1976), pp.20-23. - Shifting graphs and their applications, (with N. J. Pippenger).
*J. ACM*__23__(1976), pp.423-432. - Graph theoretic properties in computational complexity.
*J. Computer and System**Sciences*,__13__, (1976), pp.278-285. - Circuit size is non-linear in depth, (with M. S. Paterson).
*Theoretical Computer Science*,__2__(1976) pp.397-400. - 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. - Space time tradeoffs in computation.
*Asterisque*__38__, (1976), pp. 253-264. - A note on the succinctness of descriptions of deterministic languages.
*Information and**Control*__32__, (1976), pp.139-145. - On time versus space, (with J. E. Hopcroft and W. J. Paul).
*J. ACM*__24__, (1977), pp.332-337. - Fast probabilistic algorithms for Hamiltonian circuits and matchings,
(with D. Angluin).
*J. Computer and System Sciences*,__18__: 2, (1979), pp.155-193. - Graph theoretic arguments in low-level complexity.
*Lecture Notes in Computer Science*,__53__, Springer Verlag (1977), pp.162-176. - Universal circuits.
*Proc. 8th ACM. Symp. on Theory of Computing*, Hershey, PA, May (1976), pp.196-203. - The complexity of computing the permanent.
*Theoretical Computer Science*,__8__(1979), pp. 189-201. - The complexity of enumeration and reliability problems.
*SIAM J. Computing*,__8__:3 (1979), pp.410-421. - 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. - Completeness classes in algebra.
*Proc. 11th ACM. Symp. on Theory of Computing*, Atlanta, GA, April 30 - May 2, 1979. pp. 249-261. - Negative results on counting.
*Lecture Notes in Computer Science*,__67__, Springer-Verlag (1979), pp. 38-46. - Negation can be exponentially powerful.
*Theoretical Computer Science*__12__(1980), pp.303-314. - 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. - Computing multivariate polynomials in parallel.
*Information Processing Letters*, 11:1 (1980), pp. 44-45 and__12__:1 (1981), p. 54. - Universality considerations in VLSI circuits.
*IEEE Trans. on Computers*C-__30__:2 (1981), pp. 135-140. - Reducibility by algebraic projections. Monographie No. 30 de
L'Enseignement Mathematique:
*Logic and Algorithmic,*Geneva (1982),pp.365-380. - A scheme for fast parallel communication.
*SIAM J. Computing*,__11__: 2 (1982), 350-361. - Experiments with a parallel communication scheme.
*Proc. 18th Allerton Conference on**Communication Control and Computing*, University of Illinois (1980), pp. 802-811. - Size bounds for superconcentrators, (with G. Lev).
*Theoretical Computer Science*__22__, 3 (1983), pp.233-252. - 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. - Fast parallel computation of polynomials using few processors, (with S.
Skyum).
*Lecture Notes in Computer Science*,__118__, Springer Verlag (1981), pp.132-139. - A complexity theory based on Boolean algebra, (with S. Skyum).
*J. ACM*__32__: 2 (1985) pp.484-502. - Parallel computation.
*Proc. of 7th IBM Symp. on Mathematical Foundations of**Computer Science*, Hakone, Japan, May 24-26, 1982, pp.171-189. - Optimality of a two-phase strategy for routing in interconnection network.
*IEEE Trans.**on Computers*, C-__32__:9 (1983), pp.861-863. - 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. - A logarithmic time sort on linear size networks, (with J. H. Reif).
*J. ACM*.__34__:1 (1987) 60-76. - Exponential lower bounds for restricted monotone circuits.
*Proc. 15th ACM. Symp. on**Theory of Computing*, Boston, MA, April 25-27, 1983. pp.110-117. - Short monotone formulae for the majority function.
*J. Algorithms*__5__(1984), pp.363-366. - 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. - A theory of the learnable.
*C.ACM*__27__:11 (1984) pp.1134-1142. - 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. - Negation is powerless for Boolean slice functions.
*SIAM J. Computing*.__15__:2 (1986) 531-535. - NP is as easy as detecting single solutions. (with V. V. Vazirani)
*Theoretical Computer*.__47__(1986) 85-93. - Learning disjunctions of conjunctions.
*Proc. Ninth International Joint Conferences on**Artificial Intelligence*, Los Angeles, CA (August 1985) pp. 560-566. - Random generation of combinatorial structures from a uniform
distribution. (with M. R. Jerrum and V. V. Vazirani).
*Theoretical Computer Science*__43__(1986) 169-188. - 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. - 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. - Computational limitations on learning from examples, (with L. Pitt).
*J. ACM*,__35__:4 (1988) 965-984. - 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. - Optimally universal parallel computers.
*Phil. Trans. R. Soc. London*. A*326*(1988) 373-376. - Functionality in neural nets.
*Proc. American Association for Artificial Intelligence*1988, Morgan Kaufmann, San Mateo, CA, (1988) 629-634. - Bulk-synchronous parallel computers. In
*Parallel Processing and Artificial**Intelligence*. (M. Reeve and S. Zenith, eds.), John Wiley and Sons, (1989) 15-22. - General purpose parallel architectures. In
*Handbook of Theoretical Computer Science*(J. van Leeuwen, ed.), North Holland, Amsterdam (1990) pp. 944-971. - A bridging model for parallel computation.
*C.ACM*,__33__:8 (1990) pp. 103-111. - A view of computational learning theory. In
*Computation and Cognition*(C.W. Gear, ed.), Soc. Ind. and Appl. Math., Philadelphia, (1990) 32-53. - 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. - Direct bulk-synchronous parallel algorithms. (with A.V. Gerbessiotis.)
*J. of Parallel and**Distributed Computing*,__22__(1994) 251-267. - 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. - Why BSP computers? In
*Proc 7th International Parallel Processing Symposium*, IEEE Computer Society Press, Los Alamitos, CA (1993) 2-5. - 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.) - Learning Boolean formulas (with M. Kearns and M. Li).
*J.ACM*,__41__:6 (1994) 1298-1328. - A neuroidal model for cognition. In
*Natural and Artificial Parallel Computation*, (D.L. Waltz, ed.) Soc. Ind. and Appl. Math., Philadelphia, (1995) 127-140. - 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). - Rationality.
*Proc. 8th ACM Workshop on Computational Learning Theory*, ACM Press, (1995), 3-14. - 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. - Cognitive computation.
*Proc. 36th IEEE Symp. on Foundations of Computer*Science, IEEE Press, (1995) 2-3. - 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. - 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. - Projection learning.
*Machine Learning*__37__:2 (1999)115-130.