Revista Integración, temas de matemáticas.

Revista Integración, temas de matemáticas

Vol. 32 Núm. 2 (2014): Revista Integración, temas de matemáticas
Artículo Original

La obra de Leslie Valiant

PDF HTML
  • J. Andrés Montoya
J. Andrés Montoya
Universidad Nacional de Colombia

Publicado 2014-11-04

Palabras clave

  • Complejidad,
  • algoritmos,
  • análisis sintáctico,
  • algoritmos para matrices

Cómo citar

Montoya, J. A. (2014). La obra de Leslie Valiant. Revista Integración, Temas De matemáticas, 32(2), 153–168. Recuperado a partir de https://revistas.uis.edu.co/index.php/revistaintegracion/article/view/4388

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.

Para citar este artículo: 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 HTML

Descargas

Los datos de descargas todavía no están disponibles.

Referencias

  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]