Ir al contenido

Documat

La obra de Leslie Valiant

    1. [1] Universidad Nacional de Colombia

      Universidad Nacional de Colombia

      Colombia

  • Localización: Integración: Temas de matemáticas, ISSN 0120-419X, Vol. 32, Nº. 2, 2014 (Ejemplar dedicado a: Revista Integración), págs. 153-168
  • Idioma: español
  • Títulos paralelos:
    • The work of Leslie Valiant: alle die Strassen führen nach Strassen
  • Enlaces
  • Resumen
    • español

      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.

    • English

      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.

  • Referencias bibliográficas
    • Citas [1] Angluin D. and Valiant L., “Fast probabilistic algorithms for Hamiltonian circuits and matching”, Proceedings of STOC,(1977),...
    • [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),...
    • [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...
    • [14] Jerrum M. and Sinclair A., “The Markov chain Monte Carlo method: an approach to approximate counting and integration”, in Approximation...
    • 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....
    • [16] Jerrum M., Valiant L. and Vazirani V., “Random Generation of Combinatorial Structures from a Uniform Distribution”, Theo. Comput. Sci....
    • [17] Kasami T., “An efficient recognition and syntax-analysis algorithm for context-free languages”, in Scientific report AFCRL-65-758, Air...
    • [18] Kasteleyn P., “The statistics of dimers on a lattice”, Physica 27 (1961), 1209-1225.
    • [19] Munro I. and Paterson M., “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...
    • [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”, 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 http://cosec.bit.unibonn.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),...
    • [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]
Fundación Dialnet

Mi Documat

Opciones de artículo

Opciones de compartir

Opciones de entorno