M. Ajtai
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).
- 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-19Google Scholar
- BH.P. Bealne and j. Hastad. Oral ccmntunication.Google Scholar
- BM.Blum, M., and S. Micali, "How to generate cryptograpltically strong sequences of pseudorandom bits". Siam J. Comp. 13, 1984, 850-863. Google ScholarDigital Library
- GG.O. Gabber and Z. Galil., "Explicit construction of linear sized superconcentrators", J. Comp. and Sys. Sci. 22 (1981), 407-420.Google ScholarCross Ref
- LPS.A. Lubotzky, R. Phillips and P. Sarnak, "Ramanujan Graphs", (preprint) 1986, "Explicit expanders and the Ramanujan conjecture", STOC, 1986 pp 240-'246. Google ScholarDigital Library
- Si.Sipser M Expanders Randomnes,; or Time versus Spa. ceGoogle Scholar
- Ya.A. Yao "Theory and apl:,lications of trapdoor function s" FOCS 1982 80-91Google Scholar
Index Terms
- Deterministic simulation in LOGSPACE
Recommendations
Logspace Optimization Problems and Their Approximability Properties
Logspace optimization problems are the logspace analogues of the well-studied polynomial-time optimization problems. Similarly to them, logspace optimization problems can have vastly different approximation properties even though their underlying ...
Canonizing Graphs of Bounded Tree Width in Logspace
Graph canonization is the problem of computing a unique representative, a canon, from the isomorphism class of a given graph. This implies that two graphs are isomorphic exactly if their canons are equal. We show that graphs of bounded tree width can be ...
Logspace optimization problems and their approximability properties
FCT'05: Proceedings of the 15th international conference on Fundamentals of Computation TheoryThis paper introduces logspace optimization problems as analogues of the well-studied polynomial-time optimization problems. Similarly to them, logspace optimization problems can have vastly different approximation properties, even though the underlying ...
Comments