Revista Integración, temas de matemáticas.

Revista Integración, temas de matemáticas

Vol. 32 No. 2 (2014): Revista Integración, temas de matemáticas
Research and Innovation Articles

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

PDF (Español (España)) HTML (Español (España))
  • J. Andrés Montoya
J. Andrés Montoya
Universidad Nacional de Colombia

Published 2014-11-04

Keywords

  • Complexity,,
  • algorithms,
  • parsing,
  • matrix algorithms

How to Cite

Montoya, J. A. (2014). The work of Leslie Valiant: alle die Strassen führen nach Strassen. Revista Integración, Temas De matemáticas, 32(2), 153–168. Retrieved from https://revistas.uis.edu.co/index.php/revistaintegracion/article/view/4388

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.

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.

PDF (Español (España)) HTML (Español (España))

Downloads

Download data is not yet available.

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 quantumcomputer”, 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
  15. Problems (ed. Dorit Hochbaum), PWS, (1996).
  16. 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.
  17. Jerrum M., Valiant L. and Vazirani V., “Random Generation of Combinatorial Structures from a Uniform Distribution”, Theo. Comput. Sci. 43 (1986), 169-188.
  18. 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).
  19. Kasteleyn P., “The statistics of dimers on a lattice”, Physica 27 (1961), 1209-1225.
  20. Munro I. and Paterson M., “Optimal Algorithms for Parallel Polynomial Evaluation”, FOCS, (1971), 132-139.
  21. 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.
  22. Paterson M. and Stockmeyer L., “Bounds on the Evaluation Time for Rational Polynomials”, FOCS, (1971), 140-143.
  23. Pan V., How to Multiply Matrices Faster, New York, Springer-Verlag, 1982.
  24. Pan V., “Some schemes for computation of polynomials with real coefficients”, (Russian), Dokl. Akad. Nauk. SSSR 127 (1959), 266-269.
  25. Pitt L. and Valiant L., “Computational limitations on learning from examples”, ACM 35 (1988), no. 4, 965-984.
  26. Spielman D., “Linear-time encodable and decodable error-correcting codes”, IEEE Trans. Inform. Theory 42 (1996), no. 6, 1723-1731.
  27. Strassen V., “Gaussian elimination is not optimal”, Numerische Mathematik 14 (1969), no. 3, 354-356.
  28. Strassen V. and Schönhage A., “Schnelle Multiplikation Grosser Zahlen”, Computing 7 (1971), 281-292.
  29. Strassen V. and Solovay R., “A fast Monte-Carlo test for primality”, SIAM Journal on Computing 6 (1977), 84-85.
  30. Strassen V., “A converse of the law of the iterated logarithm”, Z. Warscheinlichkeitstheorie verw. Geb. 4 (1966), 265-268.
  31. Strassen V., “My Latest Talk”, Slides available at http://cosec.bit.unibonn.de/?id=574.
  32. Tardos E., “The gap between monotone and nonmonotone circuit complexity is exponential”, Combinatorica 7 (1987), 141-142.
  33. Turing A., “On Computable number with an application to the Entscheidung Problem”, Proceedings of the London Mathematical Society 2 (1937), no. 42, 230-265.
  34. Valiant L., “The Equivalence Problem for Deterministic Finite-Turn Pushdown”,Automata Information and Control 25 (1974), no. 2, 123-133.
  35. Valiant L., “General Context-Free Recognition in Less than Cubic Time”, Journal of Comput. and Syst. Sci. 10 (1975), no. 2, 308-315.
  36. Valiant L., “Graph-Theoretic Properties in computational Complexity”, J. Comput. Syst. Sci. 13 (1976), no. 3, 278-285.
  37. Valiant L., “Graph-theoretic arguments in low-level complexity”, in Proc. 6th MFCS, (1977), 162-176.
  38. Valiant L., “The Complexity of Enumeration and Reliability Problems”, SIAM J. Comput. 8 (1979), no. 3, 410-421.
  39. Valiant L., “The Complexity of Computing the Permanent”, Theor. Comput. Sci. 8 (1979), 189-201.
  40. Valiant L., “Parallel computation”, in Proc. 7th IBM Symposium on Mathematical Foundations of Computer Science, (1982).
  41. Valiant L., “A scheme for fast parallel communication”, SIAM J. Comput. 11 (1982), no. 2, 350-361.
  42. Valiant L. “A neuroidal architecture for cognitive computation”, J. ACM 47 (2000), no. 5, 854-882.
  43. Valiant L., “Memorization and Association on a Realistic Neural Model”, Neural Computation, 17 (2005), no. 3, 527-555.
  44. Valiant L., “Quantum Circuits That Can Be Simulated Classically in Polynomial Time”, SIAM J. Comput. 31 (2002), no. 4, 1229-1254.
  45. Valiant L., “Holographic Algorithms (Extended Abstract)”, FOCS, (2004), 306-315.
  46. Valiant L., “Holographic Algorithms”, SIAM J. Comput. 37 (2008), no. 5, 1565-1594.
  47. Vassilevska V., “Multiplying matrices faster than Coopersmith-Winograd”, To appear in proceedings of STOC, (2012).
  48. http://en.wikipedia.org/wiki/Strassen_algorithm [citado el 24 de julio de 2014]