Time-space tradeoffs for computing functions, using connectivity properties of their circuits

ABSTRACT

Recent research has investigated time-space tradeoffs for register allocation strategies of certain fixed sets of expressions. This paper is concerned with the time-space tradeoff for register allocation strategies of any set of expressions which compute given functions. Time-space tradeoffs for pebbling superconcentrators and grates are developed. Corollaries which follow include tradeoffs for any straight-line program which computes polynomial multiplication, polynomial convolution, the discrete Fourier transform, oblivious merging, and most sets of linear forms.

REFERENCES

• 1: A. Borodin and I. Munro, The Computational Complexity of Algebraic and Numeric Problems; American Elsevier Publishing Company, Inc., New York, 1975.
• 2: J. Dieudonné,"Une Propriétédes Racines de l'Unité"(in French); Revista de la Unión Matemaacute;tica Argentina, vol. 25, 1970; pages 1-3.
• 3: D.Yu. Grigoryev, "An Application of Separability and Independence Notions for Proving Lower Bounds of Circuit Complexity" (in Russian);Notes of Scientific Seminars, Steklov Mathematical Institute, Leningrad Department, vol. 60, 1976; pages 38-48.
• 4: John Hopcroft , Wolfgang Paul , Leslie Valiant, On Time Versus Space, Journal of the ACM (JACM), v.24 n.2, p.332-337, April 1977 [doi>10.1145/322003.322015]
• 5: W. Hurewicz and H. Wallman,Dimension Theory; Princeton University Press, Princeton, N.J., 1941.
• 6: M.S. Paterson and C.E. Hewitt, "Comparative Schematology" Project MAC Conference on Concurrent Systems and Parallel Computation, Woods Hole, Mass., June 1970; pages 119-27.
• 7: Wolfgang J. Paul , Robert Endre Tarjan, Time-Space Trade-Offs in a Pebble Game, Proceedings of the Fourth Colloquium on Automata, Languages and Programming, p.365-369, July 18-22, 1977
• 8: Wolfgang J. Paul , Robert Endre Tarjan , James R. Celoni, Space bounds for a game on graphs, Proceedings of the eighth annual ACM symposium on Theory of computing, p.149-160, May 03-05, 1976, Hershey, Pennsylvania, United States [doi>10.1145/800113.803643]
• 9: N. Pippenger,"A Time-Space Trade-Off",Report RC6550, IBM Thomas J. Watson Research Center, Yorktown Heights, N.Y., 1977.
• 10: Nicholas Pippenger , Leslie G. Valiant, Shifting Graphs and Their Applications, Journal of the ACM (JACM), v.23 n.3, p.423-432, July 1976 [doi>10.1145/321958.321962]
• 11: J.E. Savage and S. Swamy, "Space-Time Tradeoffs on the FFT Algorithm",Brown university, Providence, R.I., August 1977.
• 12: L.G. Valiant, "Graph-Theoretic Properties in Computational Complexity" Journal of Computer and System Sciences,vol. 13, 1976; pages 278-85.
• 13: L.G. Valiant,"Graph-Theoretic Arguments in Low-Level Complexity" 6th Symposium on Mathematical Foundations of Computer Science,Tatranska Lominica, Czechoslovakia, September 1977.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.3 Tradeoffs among Complexity Measures

General Terms:
Theory