The work of Leslie Valiant: alle die Strassen
führen nach Strassen

J. ANDRÉS MONTOYA^*

Universidad Nacional de Colombia, Departamento de Matemáticas, Bogotá, Colombia.

Abstract. This year Leslie VALIANT becomes sixty five years old; we celebrate his fest with this work in which we analyze some of his major achievements. We focus our attention on those of his works for which a strong influence of Volker Strassen can be easily detected. Strassen's work has had a strong and lasting influence on Valiant. It does not means, as the title could suggest, that the manyfaced, relevant and complex work of Leslie Valiant can be understood as a corollary to Strassen.

Keywords: Complexity, algorithms, parsing, matrix algorithms.
MSC2010: 01AXX, 03D15.

La obra de Leslie Valiant

Resumen. Este año Leslie VALIANT cumple 65 años y nosotros queremos celebrar este importante aniversario con este trabajo en el que se analiza su obra. Centramos nuestra atención en aquellos de sus trabajos en los que una clara influencia de Volker STRASSEN puede ser detectada. Es patente la influencia de Strassen en la obra de Valiant, pero esto no quiere decir que el trabajo de Valiant, complejo y multifacético, sea un simple corolario a la obra del primero.

Palabras claves: Complejidad, algoritmos, análisis sintáctico, algoritmos para matrices.

Texto Completo disponible en PDF

References

[1] Angluin D. and Valiant L., "Fast probabilistic algorithms for Hamiltonian circuits and matching", Proceedings of STOC, (1977), 30-41

[2] Bernstein E. and Vazirani U., "Quantum complexity theory", SIAM J. Comput. 26 (1997), no. 5, 1411-1473.

[3] S. Cook., "The complexity of theorem-proving procedures", Proceedings of STOC, (1971), 151-158.

[4] Cooley J. and Tukey J., "An algorithm for the machine calculation of complex Fourier series", Math. Comput. 19 (1965), 297-301.

[5] Coppersmith D. and Winograd S., "On the asymptotic complexity of matrix multiplication", SIAM J. Comput. 11 (1982), no. 3, 472-492.

[6] Chomsky N., "On certain formal properties of grammars", Information and Control 2 (1959), no. 3, 137-167.

[7] Chung F., "Spectral graph theory", in CBMS Regional Conference Series in Mathematics, 92, American Mathematical Society, (1997).

[8] Deutsch D., "Quantum theory, the Church-Turing principle, and the universal quantum computer", Proc. Roy. Soc. London Ser. A 400 (1985), 97-117.

[9] Earley J., "An Efficient Context-Free Parsing Algorithm", Commun. ACM 13 (1970), no. 2, 94-102.

[10] Fürer M., "Faster integer multiplication", SIAM Journal on Computing 39 (2009), no. 3, 979-1005.

[11] Hartmanis J. and Stearns R., "The complexity of recursive sequences", Proceedings of FOCS (1964), 82-90.

[12] Hopcroft J. and Ullman J., Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1979.

[13] Horner W., "A new method of solving numerical equations of all orders, by continuous approximation", Philosophical Transactions of the Royal Society of London, (1819), 308-335.

[14] Jerrum M. and Sinclair A., "The Markov chain Monte Carlo method: an approach to approximate counting and integration", in Approximation Algorithms for NP-hard Problems (ed. Dorit Hochbaum), PWS, (1996).

[15] Jerrum M. and Sni M., "Some Exact Complexity Results for Straight-Line Computations over Semirings", Journal of the ACM 29 (1982), no. 3, 874-897.

[16] JerrumM., Valiant L. and Vazirani V., "Random Generation of Combinatorial Structures from a Uniform Distribution", Theo. Comput. Sci. 43 (1986), 169-188.

[17] Kasami T., "An efficient recognition and syntax-analysis algorithm for context-free languages", in Scientific report AFCRL-65-758, Air Force Cambridge Research Lab, Bedford, MA, (1965).

[18] Kasteleyn P., "The statistics of dimers on a lattice", Physica 27 (1961), 1209-1225.

[19] Munro I. and PatersonM., "Optimal Algorithms for Parallel Polynomial Evaluation", FOCS, (1971), 132-139.

[20] Ostrowski A., "On two problems in abstract algebra connected with Horner's rule", Studies in Mathematics and Mechanics Presented to Richard Von Mises, (1954), 40-48.

[21] Paterson M. and Stockmeyer L., "Bounds on the Evaluation Time for Rational Polynomials", FOCS, (1971), 140-143.

[22] Pan V., How to Multiply Matrices Faster, New York, Springer-Verlag, 1982.

[23] Pan V., "Some schemes for computation of polynomials with real coefficients", (Russian), Dokl. Akad. Nauk. SSSR 127 (1959), 266-269.

[24] Pitt L. and Valiant L., "Computational limitations on learning from examples", J. ACM 35 (1988), no. 4, 965-984.

[25] Spielman D., "Linear-time encodable and decodable error-correcting codes", IEEE Trans. Inform. Theory 42 (1996), no. 6, 1723-1731.

[26] Strassen V., "Gaussian elimination is not optimal", Numerische Mathematik 14 (1969), no. 3, 354-356.

[27] Strassen V. and Schönhage A., "Schnelle Multiplikation Grosser Zahlen", Computing 7 (1971), 281-292.

[28] Strassen V. and Solovay R., "A fast Monte-Carlo test for primality", SIAM Journal on Computing 6 (1977), 84-85.

[29] Strassen V., "A converse of the law of the iterated logarithm", Z. Warscheinlichkeitstheorie verw. Geb. 4 (1966), 265-268.

[30] Strassen V., "My Latest Talk", Slides available at https://cosec.bit.uni-bonn.de/?id=574.

[31] Tardos E., "The gap between monotone and nonmonotone circuit complexity is exponential", Combinatorica 7 (1987), 141-142.

[32] Turing A., "On Computable number with an application to the Entscheidung Problem", Proceedings of the London Mathematical Society 2 (1937), no. 42, 230-265.

[33] Valiant L., "The Equivalence Problem for Deterministic Finite-Turn Pushdown", Automata Information and Control 25 (1974), no. 2, 123-133.

[34] Valiant L., "General Context-Free Recognition in Less than Cubic Time", Journal of Comput. and Syst. Sci. 10 (1975), no. 2, 308-315.

[35] Valiant L., "Graph-Theoretic Properties in computational Complexity", J. Comput. Syst. Sci. 13 (1976), no. 3, 278-285.

[36] Valiant L., "Graph-theoretic arguments in low-level complexity", in Proc. 6th MFCS, (1977), 162-176.

[37] Valiant L., "The Complexity of Enumeration and Reliability Problems", SIAM J. Comput. 8 (1979), no. 3, 410-421.

[38] Valiant L., "The Complexity of Computing the Permanent", Theor. Comput. Sci. 8 (1979), 189-201.

[39] Valiant L., "Parallel computation", in Proc. 7th IBM Symposium on Mathematical Foundations of Computer Science, (1982).

[40] Valiant L., "A scheme for fast parallel communication", SIAM J. Comput. 11 (1982), no. 2, 350-361.

[41] Valiant L. "A neuroidal architecture for cognitive computation", J. ACM 47 (2000), no. 5, 854-882.

[42] Valiant L., "Memorization and Association on a Realistic Neural Model", Neural Computation, 17 (2005), no. 3, 527-555.

[43] Valiant L., "Quantum Circuits That Can Be Simulated Classically in Polynomial Time", SIAM J. Comput. 31 (2002), no. 4, 1229-1254.

[44] Valiant L., "Holographic Algorithms (Extended Abstract)", FOCS, (2004), 306-315.

[45] Valiant L., "Holographic Algorithms", SIAM J. Comput. 37 (2008), no. 5, 1565-1594.

[46] Vassilevska V., "Multiplying matrices faster than Coopersmith-Winograd", To appear in proceedings of STOC, (2012).

[47] http://en.wikipedia.org/wiki/Strassen_algorithm [citado el 24 de julio de 2014]

^*E-mail: jamontoyaa@unal.edu.co.
Received: 03 February 2014, Accepted: 07 July 2014.
To cite this article: J. Andrés Montoya, The work of Leslie Valiant: alle die Strassen führen nach Strassen,
Rev. Integr. Temas Mat. 32 (2014), no. 2, 153-168.