A Time-Space Trade-Off

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A Time-Space Trade-Off

Full text

Pdf (403 KB)

Source

Journal of the ACM (JACM) archive
Volume 25 , Issue 3 (July 1978) table of contents

Pages: 509 - 515

Year of Publication: 1978

ISSN:0004-5411

Author

Nicholas Pippenger

Mathematical Sciences Department, Research Division, IBM Thomas J Watson Research Center, Post Office Box 218, Yorktown Heights, NY

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 18, Citation Count: 11

Additional Information:

references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/322077.322091 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	CHANDRA, A K Efticlent compllaUon of linear recurslve programs Proc 14th Annual IEEE Symp on Foundatmns of Comptr Sc~, Iowa City, Iowa, Oct 1973, pp 16-25
	2	GRIGOREV, D Yu lspolzovame ponyatu otdelnosu i nezawsunostl dlya poluchemya nizhnlkh otsenok slozhnostl skhem lssled po Konstr Mat ~ Mat Log (VII), Nauka, Leningrad, 1976, pp. 38-48.
	3	HOPCROFT, J E, PAUL, W J, AND VALIANT, L G On ttme versus space and related problems Proc 16th Annual IEEE Syrup on Foundations of Comptr Sc~, Berkeley, Cahf, Oct 1975, pp. 57-64
	4	PATERSON, M S, AND HEWITT, C E Comparative schematology. Proj MAC Conf. on Concurrent Syst. and Parallel Comput, Woods Hole, Mass, June 1970, pp 119-127
	5	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
	6	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]
	7	SAVAGE, J E, AND SWAMY, S Space-tune tradeoffs on the FFT algonthrn IEEE Trans on Inform Theory (to appear)
	8	Martin Tompa, Time-space tradeoffs for computing functions, using connectivity properties of their circuits, Proceedings of the tenth annual ACM symposium on Theory of computing, p.196-204, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804348]

CITED BY 11

	Rudiger Reischuk, Improved Bounds on the Problem of Time-Space Trade-Off in the Pebble Game, Journal of the ACM (JACM), v.27 n.4, p.839-849, Oct. 1980
	Sowmitri Swamy , John E. Savage, Space-time tradeoffs for linear recursion, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.135-142, January 29-31, 1979, San Antonio, Texas
	David A. Carlson, Time-space tradeoffs for tree search and traversal, Proceedings of 1986 ACM Fall joint computer conference, p.585-594, November 1986, Dallas, Texas, United States
	Ashok K. Chandra , Merrick L. Furst , Richard J. Lipton, Multi-party protocols, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.94-99, December 1983
	John R. Gilbert , Thomas Lengauer , Robert Endre Tarjan, The pebbling problem is complete in polynomial space, Proceedings of the eleventh annual ACM symposium on Theory of computing, p.237-248, April 30-May 02, 1979, Atlanta, Georgia, United States
	C. K. Yap, Space-time tradeoffs and first order problems in a model of programs, Proceedings of the twelfth annual ACM symposium on Theory of computing, p.318-325, April 28-30, 1980, Los Angeles, California, United States
	Joseph Ja'Ja', Time-space tradeoffs for some algebraic problems, Proceedings of the twelfth annual ACM symposium on Theory of computing, p.339-350, April 28-30, 1980, Los Angeles, California, United States
	Thomas Lengauer , Robert Endre Tarjan, Upper and lower bounds on time-space tradeoffs, Proceedings of the eleventh annual ACM symposium on Theory of computing, p.262-277, April 30-May 02, 1979, Atlanta, Georgia, United States
	R. S. Bird, Tabulation Techniques for Recursive Programs, ACM Computing Surveys (CSUR), v.12 n.4, p.403-417, Dec. 1980
	Joseph Ja'Ja', Time-Space trade-offs for some algebraic problems, Journal of the ACM (JACM), v.30 n.3, p.657-667, July 1983
	Thomas Lengauer , Robert E. Tarjan, Asymptotically tight bounds on time-space trade-offs in a pebble game, Journal of the ACM (JACM), v.29 n.4, p.1087-1130, Oct. 1982