Determinism versus non-determinism for linear time RAMs (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Determinism versus non-determinism for linear time RAMs (extended abstract)

Full text

Pdf (1.00 MB)

Source

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

Atlanta, Georgia, United States

Pages: 632 - 641

Year of Publication: 1999

ISBN:1-58113-067-8

Author

Miklós Ajtai

IBM Almaden Research Center, San Jose, CA

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): 18, Citation Count: 11

Additional Information:

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/301250.301424 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.

	AHU	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	Ajt	M. Ajtai, Determinism versus Non-Determinism for Linear Time RAMs with Memory Restrictions, ECCC http://www, eccc.uni-trier, de/eccc/(revised version)
	BC	A. Borodin and S. Cook, A time-space trade, off for sorting on a general sequential model of computation, SIAM J. Comput., 11, (1982), pp. 287-297
	Bea	Paul Beame, A general sequential time-space tradeoff for finding unique elements, SIAM Journal on Computing, v.20 n.2, p.270-277, April 1990 [doi>10.1137/0220017]
	BFKLT	A. Borodin, M. Fischer, D. Kirckpatrick, N. Lynch, and M. Tompa, A time-space tmdeoff for sorting on nonoblivious machines, J. Comput. System Sci., 22 (1981), pp. 351-364.
	BFMUW	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]
	Bo	B. Bollobfis, Combinatorics, Cambridge University Press, 1986. p 129. Section 16, Theorem 5.
	BST	Paul Beame , Michael Saks , Jayram S. Thathachar, Time-Space Tradeoffs for Branching Programs, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.254, November 08-11, 1998
	K	Mauricio Karchmer, Two time-space tradeoffs for element distinctness, Theoretical Computer Science, v.47 n.3, p.237-246, Nov., 1986
	PPST	W. J. Paul, N. Pippenger, E. Szemer0xli, W. T. Trotter, On Determinism versus Non-determinism and Related Problems, 24th Annual Symposium on Foundations of Computer Science, 1983, pp. 429-,*38
	PR	Jakob Pagter , Theis Rauhe, Optimal Time-Space Trade-Offs for Sorting, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.264, November 08-11, 1998
	Y	A. C. Yao, Near-optimal Time-space Tradeoff for Element Distinctness.

CITED BY 11

	Miklos Ajtai , Randal Burns , Ronald Fagin , Darrell D. E. Long , Larry Stockmeyer, Compactly encoding unstructured inputs with differential compression, Journal of the ACM (JACM), v.49 n.3, p.318-367, May 2002
	Rasmus Pagh , Jakob Pagter, Optimal time-space trade-offs for non-comparison-based sorting, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.9-18, January 06-08, 2002, San Francisco, California
	Miklós Ajtai, The invasiveness of off-line memory checking, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Martin Sauerhoff , Philipp Woelfel, Time-space tradeoff lower bounds for integer multiplication and graphs of arithmetic functions, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Beate Bolling , Martin Sauerhoff , Ingo Wegener, On the nonapproximability of boolean Function by OBDDs and read-k-times Branching Programs, Information and Computation, v.178 n.1, p.263-278, October 10, 2002
	Paul Beame , Michael Saks , Xiaodong Sun , Erik Vee, Time-space trade-off lower bounds for randomized computation of decision problems, Journal of the ACM (JACM), v.50 n.2, p.154-195, March 2003
	Martin Sauerhoff, Approximation of boolean functions by combinatorial rectangles, Theoretical Computer Science, v.301 n.1-3, p.45-78, 14 May 2003
	Omer Barkol , Yuval Rabani, Tighter lower bounds for nearest neighbor search and related problems in the cell probe model, Journal of Computer and System Sciences, v.64 n.4, p.873-896, June 2002
	Paul Beame , Erik Vee, Time-space tradeoffs, multiparty communication complexity, and nearest-neighbor problems, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Omer Barkol , Yuval Rabani, Tighter bounds for nearest neighbor search and related problems in the cell probe model, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.388-396, May 21-23, 2000, Portland, Oregon, United States
	Beate Bollig , Stephan Waack , Philipp Woelfel, Parity graph-driven read-once branching programs and an exponential lower bound for integer multiplication, Theoretical Computer Science, v.362 n.1, p.86-99, 11 October 2006