RL⊆SC

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

RL⊆SC

Full text

Pdf (384 KB)

Source

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

Victoria, British Columbia, Canada

Pages: 619 - 623

Year of Publication: 1992

ISBN:0-89791-511-9

Author

Noam Nisan

Dept. of CS, Hebrew University, Jerusalem

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 20, Citation Count: 14

Additional Information:

references cited by index terms review 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/129712.129772 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	R. Aleliunas, R.M. Karp, R.J. Lipton, L. Lovasz, and C. Rackoff. Random wMks, universal sequences and the complexity of maze problems. In 20#h Annual Symposium on Foundations of Computer Science, San Juan, Puerto Rico, 1979.
	BR91	Greg Barnes , Walter L. Ruzzo, Deterministic algorithms for undirected s-t connectivity using polynomial time and sublinear space., Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.43-53, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103430]
	BCD*89	A. Borodin , S. A. Cook , P. W. Dymond , W. L. Ruzzo , M. Tompa, Two applications of inductive counting for complementation problems, SIAM Journal on Computing, v.18 n.3, p.559-578, June 1989 [doi>10.1137/0218038]
	CW79	L. Carter and M. Wegman. Universal hash functions. J. Comp. and Syst. Sci., 18(2):143-154, 1979.
	Nis89	N. Nisan, Pseudorandom generators for space-bounded computations, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.204-212, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100242]
	Sav70	W.J. Savitch. Relationships between nondeterministic and deterministic space complexities. J. Comp. and Syst. Sci., 4(2):177-192, 1970.

CITED BY 14

	Noam Nisan , David Zuckerman, More deterministic simulation in logspace, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.235-244, May 16-18, 1993, San Diego, California, United States
	Uriel Feige , Joe Kilian, Impossibility results for recycling random bits in two-prover proof systems, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.457-468, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Noam Nisan , Amnon Ta-Shma, Symmetric logspace is closed under complement, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.140-146, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Oded Goldreich , Avi Wigderson, Tiny families of functions with random properties (preliminary version): a quality-size trade-off for hashing, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.574-584, May 23-25, 1994, Montreal, Quebec, Canada
	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
	Jeff Edmonds, Time-space trade-offs for undirected st-connectivity on a JAG, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.718-727, May 16-18, 1993, San Diego, California, United States
	Avi Wigderson, The amazing power of pairwise independence (abstract), Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.645-647, May 23-25, 1994, Montreal, Quebec, Canada
	Ittai Abraham , Cyril Gavoille , Dahlia Malkhi , Noam Nisan , Mikkel Thorup, Compact name-independent routing with minimum stretch, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain
	Shahar Dobzinski , Noam Nisan , Michael Schapira, Approximation algorithms for combinatorial auctions with complement-free bidders, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Omer Reingold, Undirected ST-connectivity in log-space, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Michael Luby , Avi Wigderson, Pairwise independence and derandomization, Foundations and Trends® in Theoretical Computer Science, v.1 n.4, p.237-301, August 2006
	Piotr Indyk, Stable distributions, pseudorandom generators, embeddings, and data stream computation, Journal of the ACM (JACM), v.53 n.3, p.307-323, May 2006
	Omer Reingold , Luca Trevisan , Salil Vadhan, Pseudorandom walks on regular digraphs and the RL vs. L problem, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Omer Reingold, Undirected connectivity in log-space, Journal of the ACM (JACM), v.55 n.4, p.1-24, September 2008

INDEX TERMS

Primary Classification:
G. Mathematics of Computing
G.3 PROBABILITY AND STATISTICS
Subjects: Probabilistic algorithms (including Monte Carlo)

Additional Classification:
F. Theory of Computation
F.1 COMPUTATION BY ABSTRACT DEVICES
F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
F.2.1 Numerical Algorithms and Problems
Subjects: Computations on polynomials

General Terms:
Algorithms, Theory

REVIEW

"Stefan Corneliu V. Stefanescu : Reviewer"

The complexity of a given algorithm can be measured by its running time and by the amount of memory space it uses. For the connectivity problem in undirected graphs, algorithms are known that run in polynomial time and use more...

Collaborative Colleagues:

Noam Nisan: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player