Shmuel Winograd
ABSTRACT
Construction of algorithms is a time honored mathematical activity. Euclid's algorithm for finding the greatest common divisor of two integers, as well as the many constructions by a ruler and compass are some of the fruits of the search for algorithms by the Greek mathematicians. In our days, we have the whole field of Numerical Analysis devoted to finding a variety of algorithms for numerical integration of differential equations.
- 1.M. O. Rabin, "Complexity of Computations," Comm. of ACM, Vol. 20, No. 9, 1977, pp. 624-633. Google Scholar
Digital Library
- 2.M. Presburger, "Über die Vollständigkeit eines gewissen Systems Arithmetic ganzer Zahlen in welchem die Addition als einzige Operation hervortritt," Comptesrendus, I Congrés de Mathematiciens de Pays Slaves, Warsaw, 1930, pp. 92-101, 395.Google Scholar
- 3.M. J. Fischer and M.O. Rabin, "Super-exponential complexity of Presburger arithmetic," Complexity of Computation, SIAM-AMS Proc., Vol. 7, 1974, R. Karp, ed., pp. 27-41.Google Scholar
- 4.A. R. Meyer, "Weak SIS cannot be decided," (abstract 72T-E67), AMS Notices 19,5 (1972), p. A-598.Google Scholar
- 5.A. R. Meyer, "Weak monadic second-order theory of successor is not elementary-recursive," Lecture Notes in Mathematics, No. 453, Springer-Verlag, 1975, pp. 132-154.Google Scholar
- 6.A.R. Meyer, "The inherent computational complexity of theories of ordered sets," Proc. of the International Congress of Mathematicians, Vol. 1, Vancouver, 1974, pp. 477-482.Google Scholar
- 7.M.O. Rabin, "Theoretic impediments to artificial intelligence," Information Processing 74, J. Rosenfeld, ed., North-Holland, Amsterdam, 1977, pp. 615-619.Google Scholar
- 8.S.A. Cook, "The complexity of theorem proving procedures," Proc. Third Annual ACM Symp. on Theory of Computing, 1971, pp. 151-158. Google ScholarDigital Library
- 9.R.M. Karp, "Reducibility among combinatorial problems," Complexity of Computer Computations, R. Miller and J. Thatcher, eds., Plenum Press, 1971, pp. 85-103.Google Scholar
- 10.T. Baker, J. Gill, and R. Solovay, "Relativization of the P&equil;?NP question," SIAM J. Comp., Vol. 4, No. 4, 1975, pp. 431-442.Google ScholarDigital Library
- 11.D. J. Rosencrantz, R. E. Stearns, and P. M. Lewis, "An analysis of several heuristics for traveling salesman problem," SIAM J. Comp., Vol. 6, 1977, pp. 563-581.Google ScholarDigital Library
- 12.O. H. Ibarra and C. E. Kim, "Fast approximation algorithms for the knapsack and sum of subset problems," JACM, Vol. 22, 1975, pp. 463-468. Google ScholarDigital Library
- 13.M. R. Garey and D. S. Johnson, "The complexity of near-optimal graph coloring," JACM, Vol. 13, 1976, pp. 43-49. Google ScholarDigital Library
- 14.S. Sahni and T. Gonzalez, "P-complete approximation problems," JACM, Vol. 23, 1976, pp. 555-565. Google ScholarDigital Library
- 15.R. Solovay and V. Strassen, "Fast Monte-Carlo test for primality," SIAM J. Comp., Vol. 6, 1977, pp. 84-85.Google ScholarDigital Library
- 16.M. O. Rabin, "Probabilistic algorithms," Algorithms and Complexity, J. F. Traub, ed., Academic Press, 1976, pp. 21-39.Google Scholar
- 17.J. W. Cooley and J. W. Tukey, "An algorithm for the machine calculation of complex Fourier series," Math. of Comp., Vol. 19, No. 90,. 1965, pp. 714-716.Google ScholarCross Ref
- 18.V Strassen, "Gaussian elimination is not optimal," Num. Math., Vol. 13, 1969, pp. 354-356.Google ScholarDigital Library
- 19.V. Pan, "Strassen's algorithm is not optimal," Proc. 19th Annual Symp. on Foundations of Computer Science, 1978.Google Scholar
- 20.S. Winograd, "On the number of multiplications necessary to compute certain functions," Comm. on Pure and Appl. Math., Vol. 23, 1970, pp. 165-179.Google ScholarCross Ref
- 21.A. Borodin and I. Munro, The Computational Complexity of Algebraic and Numeric Problems, American Elsevier Publishing Company, 1975.Google Scholar
- 22.S. Winograd, "On computing the discrete Fourier transform," Math. of Comp., Vol. 32, 1978, pp. 175-199.Google ScholarCross Ref
Index Terms
- Complexity Of Computations
Recommendations
Surprising computations
In the course of simulation of differential equations, especially of marginally stable differential problems using marginally stable numerical methods, one occasionally comes across a correct computation that yields surprising, or unexpected results. We ...
Using parity to accelerate Hermite function computations: Zeros of truncated Hermite series, Gaussian quadrature and Clenshaw summation
AbstractAlthough Hermite functions have been studied for over a century and have been useful for analytical and numerical solutions in a myriad of areas, the theory of Hermite functions has gaps. This article is a unified treatment of all the ...
Computations with half-range Chebyshev polynomials
An efficient construction of two non-classical families of orthogonal polynomials is presented in the paper. The so-called half-range Chebyshev polynomials of the first and second kinds were first introduced by Huybrechs in Huybrechs (2010) [5]. Some ...
Comments