SL ⊆L4/3

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

SL ⊆L^4/3

Full text

Pdf (1.42 MB)

Source

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

El Paso, Texas, United States

Pages: 230 - 239

Year of Publication: 1997

ISBN:0-89791-888-6

Authors

Roy Armoni	Institute of Computer Science, The Hebrew University of Jerusalem, Israel
Amnon Ta-Shma	Weizmann Institute, Rehovot, Israel
Avi Wigderson	Institute of Computer Science, The Hebrew University of Jerusalem, Israel
Shiyu Zhou	Bell Laboratories, Murray Hill, New Jersey

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): 10, Citation Count: 8

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

	AKL+79	Romas Aleliunas, Richard M. Karp, Richard J. Lipton, Laszl6 Lovksz, and Charles Rackoff. Random walks, universal traversal sequences and the complexity of maze problems. In 20th Annual Symposium on Foundation of Computer Science, pages 218-223. IEEE, 1979.
	BF93	Greg Barnes , Uriel Feige, Short random walks on graphs, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.728-737, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167275]
	BGG93	Mihir Bellare , Oded Goldreich , Shafi Goldwasser, Randomness in interactive proofs, Computational Complexity, v.3 n.4, p.319-354, Oct. 1993 [doi>10.1007/BF01275487]
	BR94	Mihir Bellare and John Rompel. Randomness-efficient oblivious sampling. In Proceedings of the 32nd Symposium on Foundalion of Computer Science, pages 276-287. IEEE, 1994.
	Lin92	Nati Linial. Private communication. Unpublished manuscript, 1992.
	LP82	Harry R. Lewis and Cristos H. Papadimitriou. Symmetric space-bounded computation. Theoretical Computer Science, 19:161- 187, 1982.
	Nis92	Noam Nisan. Pseudorandom generators for space-bounded computation. Combinatorica, 12(4)'449-461, June 1992.
	Nis94	Noam Nisan, RL⊆SC , Computational Complexity, v.4 n.1, p.1-11, Jan. 1994 [doi>10.1007/BF01205052]
	NSW92	Noam Nisan, Endre Szemeredi, and Avi Wigderson. Undirected connectivity in O(logl's n)space. In Proc. 33th IEEE Symposium on Foundations of Computer Science (FOU$), pages 24-29, 1992.
	Sak96	Michael Saks, Randomization and Derandomization in Space-Bounded Computation, Proceedings of the 11th Annual IEEE Conference on Computational Complexity, p.128, May 24-27, 1996
	Sav70	Walter J. Savitch. Relationships between nondeterministic and deterministic space complexities. Journal of Computer and System Sciences, 4(2)'177-192, 1970.
	SZ95	M. Saks , S. Zhou, RSPACE(S) " DSPACE(S^3/2), Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.344, October 23-25, 1995
	Wig92	Avi Wigderson, The Complexity of Graph Connectivity, Proceedings of the 17th International Symposium on Mathematical Foundations of Computer Science, p.112-132, August 24-28, 1992
	Zuc96	David Zuckerman, Randomness-optimal sampling, extractors, and constructive leader election, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.286-295, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237878]

CITED BY 8

	Ka Wong Chong , Yijie Han , Tak Wah Lam, Concurrent threads and optimal parallel minimum spanning trees algorithm, Journal of the ACM (JACM), v.48 n.2, p.297-323, March 2001
	Ran Raz , Omer Reingold, On recycling the randomness of states in space bounded computation, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.159-168, May 01-04, 1999, Atlanta, Georgia, United States
	Michal Koucký, Log-Space constructible universal traversal sequences for cycles of length O(n^4.03), Theoretical Computer Science, v.296 n.1, p.117-144, 4 March 2003
	D. Sivakumar, Algorithmic derandomization via complexity theory, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Michal Koucký, Universal traversal sequences with backtracking, Journal of Computer and System Sciences, v.65 n.4, p.717-726, December 2002
	Vladimir Trifonov, An O(log n log log n) space algorithm for undirected st-connectivity, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Atish Das Sarma , Sreenivas Gollapudi , Rina Panigrahy, Estimating PageRank on graph streams, Proceedings of the twenty-seventh ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 09-12, 2008, Vancouver, Canada
	Lane A. Hemaspaandra, SIGACT news complexity theory column 51, ACM SIGACT News, v.37 n.2, June 2006