Deterministic simulation in LOGSPACE

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Deterministic simulation in LOGSPACE

Full text

Pdf (723 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the nineteenth annual ACM symposium on Theory of computing table of contents

New York, New York, United States

Pages: 132 - 140

Year of Publication: 1987

ISBN:0-89791-221-7

Authors

M. Ajtai	IBM, Almaden Research Center
J. Komlos	Uuiiversity of California, San Diego, Dept. of Mathematics
E. Szemeredi	Rutgers University, Department of Computer Science

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): 40, Citation Count: 37

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

ABSTRACT

In this paper we show that a wide class of probabilistic algorithms can be simulated by deterministic algorithms. Namely if there is a test in LOGSPACE so that a random sequence of length (log n)2 / log log n passes the test with probability at least 1/n then a deterministic sequence can be constructed in LOGSPACE which also passes the test. It is important that the machine performing the test gets each bit of the sequence only once. The theorem remains valid if both the test and the machine constructing the satisfying sequence have access to the same oracle of polynomial size. The sequence that we construct does not really depend on the test, in the sense that a polynomial family of sequences is constructed so that at least one of them passes any test. This family is the same even if the test is allowed to use an oracle of polynomial size, and it can be constructed in LOGSPACE (without using an oracle).

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.

	AW	M. Ajtai and A. Wigderson. "Deterministic simulation of probabilistic const~tnt depth circuits", iBM Research Report, RJ 4866 (51296) 10/3/85 or FOCS, 1985, pp 11-19
	BH	P. Bealne and j. Hastad. Oral ccmntunication.
	BM	Manuel Blum , Silvio Micali, How to generate cryptographically strong sequences of pseudo-random bits, SIAM Journal on Computing, v.13 n.4, p.850-864, Nov. 1984 [doi>10.1137/0213053]
	GG	O. Gabber and Z. Galil., "Explicit construction of linear sized superconcentrators", J. Comp. and Sys. Sci. 22 (1981), 407-420.
	LPS	A Lubotzky , R Phillips , P Sarnak, Explicit expanders and the Ramanujan conjectures, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.240-246, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12154]
	Si	Sipser M Expanders Randomnes,; or Time versus Spa. ce
	Ya	A. Yao "Theory and apl:,lications of trapdoor function s" FOCS 1982 80-91

CITED BY 37

	Amnon Ta-Shma , Christopher Umans , David Zuckerman, Loss-less condensers, unbalanced expanders, and extractors, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.143-152, July 2001, Hersonissos, Greece
	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
	William Aiello , Sivaramakrishnan Rajagopalan , Ramarathnam Venkatesan, Design of practical and provably good random number generators, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.1-9, January 22-24, 1995, San Francisco, California, United States
	Yossi Azar , Andrei Z. Broder , Anna R. Karlin , Nathan Linial , Steven Phillips, Biased random walks, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.1-9, May 04-06, 1992, Victoria, British Columbia, Canada
	Avi Wigderson , David Zuckerman, Expanders that beat the eigenvalue bound: explicit construction and applications, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.245-251, May 16-18, 1993, San Diego, California, 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
	Russell Impagliazzo , Avi Wigderson, P = BPP if E requires exponential circuits: derandomizing the XOR lemma, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.220-229, May 04-06, 1997, El Paso, Texas, United States
	D. Zuckerman, A technique for lower bounding the cover time, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.254-259, May 13-17, 1990, Baltimore, Maryland, United States
	Nabil Kahale, Eigenvalues and expansion of regular graphs, Journal of the ACM (JACM), v.42 n.5, p.1091-1106, Sept. 1995
	Yuval Rabani , Yuri Rabinovich , Alistair Sinclair, A computational view of population genetics, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.83-92, May 29-June 01, 1995, Las Vegas, Nevada, United States
	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
	J. Naor , M. Naor, Small-bias probability spaces: efficient constructions and applications, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.213-223, May 13-17, 1990, Baltimore, Maryland, United States
	Sanjeev Arora , Shmuel Safra, Probabilistic checking of proofs: a new characterization of NP, Journal of the ACM (JACM), v.45 n.1, p.70-122, Jan. 1998
	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
	Sanjeev Arora , Yuval Rabani , Umesh Vazirani, Simulating quadratic dynamical systems is PSPACE-complete (preliminary version), Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.459-467, May 23-25, 1994, Montreal, Quebec, Canada
	David R. Karger , Rajeev Motwani, Derandomization through approximation: an NC algorithm for minimum cuts, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.497-506, May 23-25, 1994, Montreal, Quebec, Canada
	Ioannis Chatzigiannakis , Sotiris Nikoletseas , Paul Spirakis, Distributed communication algorithms for ad hoc mobile networks, Journal of Parallel and Distributed Computing, v.63 n.1, p.58-74, January 2003
	Moni Naor, On the decisional complexity of problems over the reals, Information and Computation, v.167 n.1, p.27-45, 5/25/2001
	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
	David R. Karger, Using randomized sparsification to approximate minimum cuts, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.424-432, January 23-25, 1994, Arlington, Virginia, United States
	James Aspnes , Udi Wieder, The expansion and mixing time of skip graphs with applications, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA
	Rajiv Gupta , Scott A. Smolka , Shaji Bhaskar, On randomization in sequential and distributed algorithms, ACM Computing Surveys (CSUR), v.26 n.1, p.7-86, March 1994
	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
	A. Fiat , M. Noar, Implicit O(1) probe search, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.336-344, May 14-17, 1989, Seattle, Washington, 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
	Yuval Ishai , Eyal Kushilevitz , Rafail Ostrovsky , Amit Sahai, Batch codes and their applications, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Ioannis Chatzigiannakis , Sotiris Nikoletseas, Design and analysis of an efficient communication strategy for hierarchical and highly changing ad-hoc mobile networks, Mobile Networks and Applications, v.9 n.4, p.319-332, August 2004
	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
	Christos Gkantsidis , Milena Mihail , Amin Saberi, Random walks in peer-to-peer networks: algorithms and evaluation, Performance Evaluation, v.63 n.3, p.241-263, March 2006
	Nabil Kahale, Large Deviation Bounds for Markov Chains, Combinatorics, Probability and Computing, v.6 n.4, p.465-474, December 1997
	Michael Luby , Avi Wigderson, Pairwise independence and derandomization, Foundations and Trends® in Theoretical Computer Science, v.1 n.4, p.237-301, August 2006
	David Zuckerman, Linear degree extractors and the inapproximability of max clique and chromatic number, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	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
	Seth Pettie , Vijaya Ramachandran, Randomized minimum spanning tree algorithms using exponentially fewer random bits, ACM Transactions on Algorithms (TALG), v.4 n.1, p.1-27, March 2008
	Omer Reingold, Undirected connectivity in log-space, Journal of the ACM (JACM), v.55 n.4, p.1-24, September 2008
	Alexander D. Healy, Randomness-Efficient Sampling within NC1, Computational Complexity, v.17 n.1, p.3-37, April 2008
	Dorit Aharonov , Itai Arad , Zeph Landau , Umesh Vazirani, The detectability lemma and quantum gap amplification, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA