**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.