A general sequential time-space tradeoff for finding unique elements

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A general sequential time-space tradeoff for finding unique elements

Full text

Pdf (735 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-first annual ACM symposium on Theory of computing table of contents

Seattle, Washington, United States

Pages: 197 - 203

Year of Publication: 1989

ISBN:0-89791-307-8

Author

P. Beame

Computer Science Department, FR-35, University of Washington, Seattle, Washington

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 21, Citation Count: 3

Additional Information:

abstract references cited by index terms collaborative colleagues

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/73007.73026 What is a DOI?

ABSTRACT

An optimal &OHgr;(n2) lower bound is shown for the time-space product of any R-way branching program that determines those values which occur exactly once in a list of n integers in the range [1, R] where R ≥ n. This &OHgr;(n2) tradeoff also applies to the sorting problem and thus improves the previous time-space tradeoffs for sorting. Because the R-way branching program is a such a powerful model these time-space product tradeoffs also apply to all models of sequential computation that have a fair measure of space such as off-line multi-tape Turing machines and off-line log-cost RAMs.

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.

	Abr86	K. Abrahamson. Time-space tradeoffs for branching programs contrasted with those for straight-line programs. In Proceedings of the 27th IEEE-FOCS, pages 402-409, 1986.
	Abr87	Karl Abrahamson, Generalized string matching, SIAM Journal on Computing, v.16 n.6, p.1039-1051, December 1, 1987 [doi>10.1137/0216067]
	BC82	A. Borodin and S. Cook. A time-space tradeoff for sorting on a general sequential model of computation. SIAM Journal on Computing, 11(2):287-297, 1982.
	BFK+81	A. Borodin, M. Fischer, D. Kirkpatrick, N. Lynch, and M. Tompa. A time-space tradeoff for sorting on non-oblivious machines. Journal of Computer and System Sciences, 22(3):351-364, June 1981.
	BFM+87	A. Borodin , F. Fich , F. Meyer auf der Heide , E. Upfal , A. Wigderson, A time-space tradeoff for element distinctness, SIAM Journal on Computing, v.16 n.1, p.97-99, Feb. 1987 [doi>10.1137/0216007]
	Kar86	Mauricio Karchmer, Two time-space tradeoffs for element distinctness, Theoretical Computer Science, v.47 n.3, p.237-246, Nov., 1986
	RS82	S. Reisch and G. Schnitger. Three applications of Kolmogorov complexity. In Proceedings of the 23rd IEEE-FOCS, pages 45-52~ 1982.
	Yao88	A. Yao. Near optimal time-space tradeoff for element distinctness. In Proceedings of the 29th IEEE-FOCS, pages 91- 97, 1988.
	Yes84	Y. ~esha. Time-space tradeoffs for matrix multiplication and the discrete Fourier transform on any general sequential random-access computer. SIAM Journal on Computing, 29:183-197, 1984.

CITED BY 3

	Yishay Mansour , Noam Nisan , Uzi Vishkin, Trade-offs between communication throughput and parallel time, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.372-381, May 23-25, 1994, Montreal, Quebec, Canada
	Y. Mansour , N. Nisan , P. Tiwari, The computational complexity of universal hashing, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.235-243, May 13-17, 1990, Baltimore, Maryland, United States
	André Gronemeier, A note on the decoding complexity of error-correcting codes, Information Processing Letters, v.100 n.3, p.116-119, 15 November 2006