M. Ajtai, J. Komlos, and E. Szemeredi, Deterministic simulation in LOGSPACE, Proceedings of the nineteenth annual ACM conference on Theory of computing (1987), 132--140.  @ NUS  Home/Search   Document Not in Database   Summary   Related Articles   Check

....among those resources for which we have agreeable computational models, determination of the exact relationship between randomness and other such computational resources has become a major project. The relationship between space and randomness, elucidated by startling pseudorandom constructions ([1, 9]) is remarkably well understood. These constructions demonstrate that space bounded computation benefits little by the use of randomness. The analogous relationship with time has proved E mail address: acr theory.lcs.mit.edu. Supported by an NSF Graduate Fellowship and grants NSF 92 12184, ....

M. Ajtai, J. Komlos, and E. Szemeredi. Deterministic simulation in logspace. In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, pages 132--140, 1987.

.... transform FPCP Gammak [log k; k Delta f ] ignoring multiplicative factors of 1 ffl for arbitrarily small ffl 0) This transformation is analogous to the well known transformation of Berman and Schnitger [BeSc] Alternatively, using a known deterministic amplification method based on [AKS, LPS] one can transform FPCP 1; Gammak [log 2k; k Delta f ] To the best of our knowledge this transformation has never appeared with a full proof. Both alternatives are important ingredients in transforming pcp results into clique in approximability results via the FGLSS method. A second type ....

....7. Arora and Safra [ArSa] reduced the randomness complexity of a PCP verifier for NP to logarithmic they showed NP = PCP 1;1=2 [ coins = log ; query = log N ] On the other hand, it is easy to see that that random bits can be recycled for error reduction via the standard techniques of [AKS, CW, ImZu]. The consequence was the first NP hardness result for Max Clique approximation. The corresponding factor was 2 . Arora et al. ALMSS] showed that NP = PCP 1;1=2 [ coins = log ; query = O(1) which implied that there exists an ffl 0 for which approximating Max Clique within N was ....

[Article contains additional citation context not shown here]

M. Ajtai, J. Komlos and E. Szemeredi. Deterministic Simulation in Logspace. Proceedings of the 19th Annual Symposium on the Theory of Computing, ACM, 1987, pp. 132-- 140.

....it turns out that to construct provably good pseudorandom generators for space bounded computation, it is enough to prove hardness results for a model of space bounded computation in which the input is accessible only by a one way tape. This observation opened the way for a sequence of papers [2, 7, 30, 19, 37, 6], presenting ingenious constructions of pseudorandom number generators that can be proved unconditionally to look random to space bounded machines. These constructions provide the basis for some significant deterministic simulations of randomness: that any bounded error randomized log space, ....

....says that bounded error log space poly time probabilistic computation (BPH L) can be simulated in deterministic polylog space poly time (SC, or Steve s class ) In contrast, the known deterministic simulations of NL in polylog space require n log n time. In another direction, Ajtai, et al. [2] looked at the problem of deterministically simulating space s PTMs that operate with some randomness bound r. As noted in Proposition 2.4, if r = #(s) then such a simulation is trivial and for r = 2 this the problem is equivalent to simulating any halting computation. They showed that a ....

[Article contains additional citation context not shown here]

M. Ajtai, J. Komlos, and E. Szemeredi. Deterministic simulation of logspace. In 19th ACM Symposium on Theory of Computing, pages 132-- 140, 1987.

....the property that every subset of the vertices has many neighbors. Expander graphs enjoy wide use in computer science; a very incomplete list of applications includes network constructions [FFP88] sorting [AKS83, Pip87] complexity theory [Val76] cryptography [GIL 90] and pseudorandomness [AKS87] We consider two type of expanders: bipartite expanders and ordinary expander graphs. We use bipartite expanders in our construction of authentication graphs and ordinary expander graphs in our construction of overlay networks. De nition 2.1 (bipartite graph) A bipartite graph G = V 1 ; V 2 ....

M. Ajtai, J. Komlos, and E. Szemeredi. Deterministic Simulation in Logspace. In ACM Symposium on Theory of Computing, 1987.

....bipartite graph with m nodes on the left side, each with degree at most d, n nodes on the right side with the property that every subset of a nodes in the left side is connected to at least b of the nodes of the right side. These graphs have been used, for instance by Ajtai, Koml os and Szemer edi [1] and Sipser [7] to remove randomness in probabilistic algorithms. Cohen and Wigderson [3] provide a survey of constructions and applications. Let m = n log n . We first show how to construct a rainbow with log n colors for such m and n, and then show how to apply it with a (m; n; log 2 n; n; ....

....construction for a disperser with those parameters yields an implicit O(1) probe search scheme for m = n log n . No explicit construction with parameters close to the ones given in [7] is known. The best explicit construction for such expanders is given in Ajtai, Koml os and Szemer edi [1]. 14 8 Conclusions and Open Problems As a consequence of the results of this paper, the maximal m for which implicit O(1) probe is possible lies between 2 poly(n) and a constant height tower of powers. One obvious open problem is to close this gap. Finding an explicit construction for ....

M. Ajtai, J. Koml'os, E. Szemer'edi, Deterministic Simulation in LOGSPACE, Proc. 19th ACM Symposium on Theory of Computing, 1987, pp. 132-140.

....by NSF grant CCR 9820806 and by a Guggenheim Fellowship. 2 Jin Yi Cai Gabber Galil proof also has the added advantage of being relatively elementary. We will follow the proofs of [10] closely. There is an extensive literature on expanders and their applications to the theory of computing [1][2][4] 5] 6] 8] 9] 14] 15] It was realized that expansion properties are closely related to the second largest eigenvalues of the graph #(G) see [6] and for d regular graphs the gap between d and #(G) provides estimates for both upper and lower bound for the expansion constant. The best ....

M. Ajtai, J. Komlos and E. Szemeredi, Deterministic simulation in LOGSPACE, Proc. of the 19th ACM STOC, 132--140, 1987.

....is also accepted by a deterministic space(S log(R=S) machine. There is only one result that improves this bound for some R. Namely, Ajtai, Komlos, and Szemeredi showed that any randomized space(S) algorithm using only O(S 2 = log S) random bits can be simulated deterministically in space(S) [AKS]. In this paper we improve upon this result and give a deterministic simulation of algorithms using poly(S) random bits. What we obtain is a pseudo random generator. Our generator converts O(S) truly random bits to poly(S) bits that look random to all space(S) machines. The generator can be ....

....generator for space S with parameter ffl running on line in space O(S) Proof: The fact that G runs on line in space O(S) follows immediately from the fact that E can be computed in space O(n) To prove that G is a pseudorandom generator we will show that it fools any space(S) machine M . As in [AKS], we model M as a layered multi graph L with a layer for each 0 i l, where each layer has 2 S vertices. This will represent M reading S random bits at a time: the ith layer of L represents the configuration of M after reading i sets of S bits. More formally, L consists of vertices (i; j) and ....

M. Ajtai, J. Komlos, and E. Szemeredi, Deterministic Simulation in Logspace, Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987, pp. 132-140.

....An expander graph has the property that every not toolarge subset of the vertices has many neighbors, relative to its degree. Expanders have had numerous applications in computer science: network constructions [6] sorting [1, 16] complexity theory [30] cryptography [8] and pseudorandomness [2]. Many of these applications require bipartite graphs, where only subsets on one side are required to expand. Definition 1.5.1 (expander) A bipartite graph G = V1 ; V2 ; E) is (K; c) expanding if for every A V1 of cardinality at most K, j(A)j cjAj, where (A) is the set of neighbors of A. ....

M. Ajtai, J. Komlos, and E. Szemeredi. Deterministic simulation in Logspace. In 19th STOC, pages 132-140, 1987.

....and Szegedy [15] implies that, unless P = NP , no polynomial time approximation algorithm for the clique number problem can achieve a constant performance guarantee. Further results of Feige, Goldwasser, Lov asz, Safra and Szegedy, using random walk techniques of Ajtai, Koml os and Szemer edi [1] resp. Impagliazzo and Zuckerman [22] give in combination with the NP = PCP(log n; 1) result a much stronger statement: there exists a constant ffl such that no polynomial time approximation algorithm for the clique number can have a performance guarantee that is n ffl unless P = NP . This ....

.... the restricted verifier k times with k satisfying (1=2) k n Gammaffi : This means k ffi log n and thus we would need O(log 2 n) random bits and O(log n) query bits which gives only NP PCP n Gammaffi (log 2 n; log n) However, relying on a method of Ajtai, Koml os and Szemer edi [1] resp. Impagliazzo and Zuckerman [22] that makes use of random walks on expanders it can be shown that in fact O(log n) random bits are sufficient (i.e. one can show NP PCP n Gammaffi (log n; log n) The idea behind this technique is as follows. Instead of using truly random bits one ....

M. Ajtai, J. Koml'os, and E. Szemer'edi (1987): Deterministic simulation in LOGSPACE, in: STOC, 132--140, 1987.

....such that with probability greater than 1 Gamma fi Gammal , at least one of them is a member of the desired set. A straightforward implementation would require kl random bits. Several papers have addressed the question of achieving the probability error while requiring fewer random bits [1, 20, 28, 32, 47, 49]. We consider the method of [1] which is used by [20, 28] For a graph G = V; E) consider any 1 1 correspondence f : V f0; 1g k , the different assignments to the random bits of the sampling algorithm. To generate the l samples, choose a random vertex of G and perform a random walk of length ....

....fi Gammal , at least one of them is a member of the desired set. A straightforward implementation would require kl random bits. Several papers have addressed the question of achieving the probability error while requiring fewer random bits [1, 20, 28, 32, 47, 49] We consider the method of [1] which is used by [20, 28] For a graph G = V; E) consider any 1 1 correspondence f : V f0; 1g k , the different assignments to the random bits of the sampling algorithm. To generate the l samples, choose a random vertex of G and perform a random walk of length l. Each vertex in the random ....

M. Ajtai, J. Komlos and E. Szemeredi, Deterministic simulation in LOGSPACE, Proceedings of the 19th ACM Annual Symposium on Theory of Computing, (1987) pp. 132-140. 23

....the verifier rejects all proofs for a majority of the random strings. Feige et al. FGLSS91] were the first who used results in the theory of interactive proofs to obtain some non approximability results for the clique number. Feige et al. exploited a technique of Ajtai, Koml os and Szemer edi [AKS87] and Impagliazzo and Zuckerman [IZ89] for generating long pseudo random bit strings in order to prove that if NP = PCP(log n; q(n) then the clique number of a graph cannot be approximated within a factor of 2 Omega (log n=q(n) unless P = NP . Since Arora and Safra [AS92] characterized NP as ....

....number of a graph cannot be approximated in polynomial time within a factor of n ffl unless P = NP . Hougardy, Promel and Steger [HPS94] provide an excellent survey on the recent work concerning probabilistically checkable proofs and their concequences for approximation algorithms. Relying on [AKS87] and [IZ89] for generating long pseudo random bit strings by random walks on expander graphs, we further develop the ideas of [AS92] and [ALMSS92] in order to prove that PCP(log log n; 1) NP is equivalent to P = NP. Our techniques also imply that any language in NP has a restricted verifier that ....

[Article contains additional citation context not shown here]

M. Ajtai, J. Koml'os, and E. Szemer'edi. Deterministic simulation in logspace. Proc. of the 19th ACM Symposium on Theory of Computing, pp. 132--140, 1987.

....in place of quadratic time methods for MDS codes. However, it is unlikely that using these methods in places where we use quadratic time MDS codes will be as efficient in practice. The construction in Section 4 can be improved by using walks in expanders instead of edges, using the methods of [1]. The relevance of this method to the case of expander based error correcting codes has been observed by us (cf. 15] and a similar remark holds here also. Combining our technique here with the methods of Spielman in [16] we can obtain explicit, linear time encodable and decodable error ....

M. Ajtai, J. Koml'os, E. Szemer'edi, "Deterministic Simulation in Logspace", Proc. of the 19 th ACM Symp. on the Theory of Computing, 1987, pp. 132-140.

....Email: fotakis cti.gr, spirakis cti.gr Fax: 30 61 993973 Abstract. In this work we use random walks on expanders in order to relax the properties of hitting sets required for partially derandomizing one side error algorithms. Building on a well known probability amplification technique [AKS87, CW89, IZ89], we use random walks on expander graphs of subexponential (in the random bit complexity) size so as to avoid particular sets of misleading strings, while reducing the random bit complexity of the algorithm. Then, we introduce the idea of conditional hitting sets in order to avoid the ....

....sets suffice for derandomization. Thus, we obtain general sufficient conditions for reducing the random bit complexity of any one side error randomized algorithm. 1. 1 Previous Work The techniques for analyzing the hitting properties of random walks on expander graphs were first introduced by [AKS87]. Then, random walks on expanders used for decreasing the error rate of randomized algorithms [CW89, IZ89, MR95] and interactive proof systems [BGG93] while not substantially increasing the random bit complexity. Up to our knowledge, the first time that recursive random walks on expanders were ....

[Article contains additional citation context not shown here]

M. Ajtai, J. Koml'os, and E. Szemer'edi. Deterministic simulation in logspace. Proc. of the 19th ACM Symposium on Theory of Computing, pp. 132--140, 1987.

....the clique problem within a ratio 2 c log 0:5 Gammaffl n , then P = NP. Proof: We show that the hypothesis implies a polynomial time algorithm for SAT. We use a reduction from PCP to clique described in [FGL 91] see Theorem 26 in the Appendix) and an error amplification technique from [AKS87] the idea of using this technique in the context of proof checking is from [Zuc91] Since NP = PCP(log n; log 0:5 ffl=2 n) there is a (log n; log 0:5 ffl=2 n) restricted verifier that checks membership proofs for SAT. The randomness efficient error amplification in [AKS87] allows us to ....

....technique from [AKS87] the idea of using this technique in the context of proof checking is from [Zuc91] Since NP = PCP(log n; log 0:5 ffl=2 n) there is a (log n; log 0:5 ffl=2 n) restricted verifier that checks membership proofs for SAT. The randomness efficient error amplification in [AKS87] allows us to change the verifier into one that is (log n; log n) restricted and has the following property. If x 2 SAT , there is a proof Pi x that the verifier accepts with probability 1. But if x 62 SAT , the verifier accepts every proof with probability less than p = 2 Gamma log n log ....

M. Ajtai, J. Kom'os, and E. Szemeredi. Deterministic simulation in logspace. In Proc. 19th ACM Symp. on Theory of Computing, pages 132--140, 1987.

....of random bits. We refer the reader to [Nis96] for a survey on this method. With respect to polynomial time randomized computation, there are two fundamental approaches to derandomization: the method of conditional probabilities [ES73, Spe87, Rag88] and constructing small sized sample spaces [KW84, Lub85, ABI86, AKS87, NN90]. In the former approach, we search for a good point in a large sample space by improving certain conditional probabilities (or expectations) in an adaptive manner; in the latter method, we construct a sample space of polynomial size while guaranteeing the existence of a good point so that we ....

....we could accomplish finding such a point by exhaustive search. The most commonly used tools for constructing small sized sample spaces are: k wise independent hashing [CW79] sample spaces with limited independence [KW84, Lub85, ABI86] sample spaces with small bias [NN90] and expander graphs [AKS87]. Remark: Here we have assumed that the polynomial time randomized computation has one side error, in which case, finding a good sample point is sufficient for derandomization. In fact, for almost all the problems that are known to have randomized algorithms, their corresponding computations are ....

[Article contains additional citation context not shown here]

M. Ajtai, J. Koml'os and E. Szemer'edi. Deterministic Simulation of Logspace. In Proc. of 19th ACM Symposium on Theory of Computing, pp. 132-140, 1987.

....declared safe, find a collection of elements that intersects every set except for the safe one. After giving a simple randomized solution, we show that this problem can be solved in NC by combining the techniques of pairwise independence [7, 25] with the technique of random walks on expanders [2]. We feel that this combination should have further application in derandomizing algorithms; similar ideas were used previously to save random bits, e.g. in the work of Bellare, Goldreich, and Goldwasser [4] Finally, in section 6, we apply the above results to finding minimum cuts, minimum ....

....n, there exists a graph G n on n vertices with the following properties: the graph is 7 regular; it has a constant expansion factor; and, for some constant #, the second eigenvalue of the graph is at most 1 #. The following is a minor adaptation of a result due to Ajtai, Komlos, and Szemeredi [2] which presents a crucial property of random walks on the expander G n . Refer to Cohen and Wigderson [8] Impagliazzo and Zuckerman [16] and Motwani and Raghavan [28] for a formal definition of expanders and further details about random walks on expanders. Theorem 7.5 (see [2] There exist ....

[Article contains additional citation context not shown here]

M. Ajtai, J. Koml os, and E. Szemer edi, Deterministic simulation in logspace, in Proc. 19th ACM Symposium on Theory of Computing, ACM, New York, 1987, pp. 132--140.

....at most 2 Gammak . We want to achieve this using as few random bits as possible. 70 This problem, known as the deterministic amplification problem, was extensively studied by [KPS85, CG89, IZ89, CW89] and many others. Using expanders, this can be done using only n O(k) random bits [AKS87, IZ89, CW89] Sipser [Sip88] noted that the existence of explicit extractors imply stronger amplification. Theorem: Assume there is an (n k; m = n; t; m 0 = n; ffl = 1 n ) extractor. If L is accepted by a BPTime(f(n) algorithm using n random bits and having 1 2 Gamma 1 n error, ....

Ajtai, Komlos, and Szemeredi. Deterministic simulation in LOGSPACE. In ACM Symposium on Theory of Computing (STOC), 1987. 87

.... CW89, IZ89] Weak Random Sources The attempts to perform them using a source of biased, correlated coin flips (initiated in [Blu86, SV86, CG88, VV85] and Derandomization The attempts to derandomize completely probabilistic small space algorithms which use a few random bits (initiated in [AKS87] In 1990, Zuckerman (cf. Zuc96] proposed the following definition of a weak random source (parametrized by a number k and termed a k source) It is a probability distribution on n bits in which no string has probability larger than 2 k . So, intuitively, the distribution has k bits of ....

Miklos Ajtai, Janos Komlos, and E. Szemeredi. Deterministic simulation in LOGSPACE. In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, pages 132-- 140, New York City, 25--27 May 1987.

....We say that k bits can be fully derandomized for RL (correspondingly, for SL) if every such machine that uses up to k random bits can be simulated in L. A trivial argument shows that O(log n) bits can be fully derandomized for RL (and hence also for SL) The only non trivial results were proved in [1, 8]. In particular, Nisan and Zuckerman showed that any poly logarithmic number of random bits can be fully derandomized [8] see also [2] One direction to attack the problem of derandomization is the concept of pseudo random generator, which is also very interesting in its own right. Given a ....

M. Ajtai, J. Komlos and E. Szemeredi, Deterministic simulations of Logspace, Proc. 19th Ann. ACM Symp. on Theory of Computing, pp. 132-140, 1987.

....if the walk is at vertex v, it moves to a vertex chosen uniformly at random from the neighbors of v. Random walks have been studied extensively, and have numerous applications in theoretical computer science, including space efficient algorithms for undirected connectivity [4, 8] derandomization [1], recycling of random bits [10, 15] approximation algorithms [6, 12, 17] efficient constructions in cryptography [14] and self stabilizing distributed computing [11, 16] Frequently (see, for example, Karger et al. 19] and Nisan et al. 20] we are interested in E[T (N ) the expected time ....

....immediate applications in many areas of computer science. Our results, of course, cannot be applied to all such areas. For example, much stronger results are already known about the properties of short random walks on the special class of graphs known as expanders (see, for example, Ajtai et al. [1], and Jerrum and Sinclair [17] One might hope our results would dramatically improve the algorithms of Karger et al. 19] and Nisan et al. 20] for undirected connectivity. As mentioned above, both require an estimate of E[T (N ) and both used the estimate E[T (N ) O(N 4 ) ....

M. Ajtai, J. Koml' os, and E. Szemer' edi, Deterministic simulation in LOGSPACE, in Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, New York, NY, May 1987, pp. 132--140.

....of 2 Gamma Omega Gamma p r) Nisan [10] improved on this by presenting an exponential amplification in the cost of a log k factor in the number of random bits. Cohen and Wigderson [3] and Impagliazzo and Zuckerman [6] independently noticed that a result of Ajtai, Komlos and Szemeredi [1] can be used to form an amplifier that reduces the error probabilityexponentially to 2 Gamma Omega Gamma k) while using only r O(k) random bits. Hence, this method is optimal up to a constant for BPP amplifications. The construction of AKS is based on expander graphs. These are graphs with a ....

....restated) Fix any constant 0 ffl 1 16 . Then, for any k = k(r) there exists an (O(k) k) explicit family of (r O(k) r; k) bipartite graphs, that are (ffl Omega Gamma k) ffl) weak extractors. Proof: We follow the [3, 6] construction of extractors using random walks on expander graphs [1]. Specifically, we construct a weak extractor H, using a constant power of the Margulis expander G 2 r , for which d ffl Omega Gamma02 . Call this expander G. The nodes in V 1 correspond to walks of length k on G and the nodes in V 2 correspond to the nodes of G. Each walk is connected to all ....

[Article contains additional citation context not shown here]

M. Ajtai, J. Komlos, and E. Szemeredi. Deterministic simulation in logspace. In Proceedings of the 19 th Annual ACM Symposium on Theory of Computing, pages 132--140, 1987.

....values is the average of O(ffl Gamma2 ) distinct oracle answers. 6 6 Each of the O(log(1=ffi) sequences of O(ffl Gamma2 ) queries is produced by a pairwise independent generator, and the seeds used for these different sequences are generated by a random walk on an expander graph (cf. [1] and [11, Sec. 3.6.3] 12 The randomness complexity can be further reduced to n O(log(1=fflffi) and both complexities are optimal up to a constant multiplicative factor; see [11, Sec. 3.6.4] Averaging samplers are closely related to extractors, but the study of the latter tends to focus more ....

M. Ajtai, J. Komlos, E. Szemer'edi. Deterministic Simulation in LogSpace. In 19th ACM Symposium on the Theory of Computing, pages 132--140, 1987.

....bits. The third is probability amplification [15] A basic such technique works for t 2 qdlog(2d Q )e by performing t pairwise independent evaluations of Q at dlog(2d Q )e bit integers, using 2qdlog(2d Q )e random bits. Stronger amplification can be obtained by means of random walks on expanders [1, 5, 8]. In x2, we propose a new general methodology for testing Q(x 1 ; x q ) Our methodology computes Q( 1 ; q ) where 1 , q are suitable irrational numbers such that Q( 1 ; q ) 0 if and only if Q(x 1 ; x q ) j 0. Since rational arithmetic is used in ....

M. Ajtai, J. Koml'os, and E. Szemer'edi. Deterministic simulation in Logspace. In Proceedings of the 19th Annual ACM Symposium on Theory of Computing, pages 132--140, 1987.

....Email: fotakis cti.gr, spirakis cti.gr Fax: 30 61 993973 Abstract. In this work we use random walks on expanders in order to relax the properties of hitting sets required for partially derandomizing one side error algorithms. Building on a well known probability amplification technique [AKS87, CW89, IZ89], we use random walks on expander graphs of subexponential (in the random bit complexity) size so as to avoid particular sets of misleading strings, while reducing the random bit complexity of the algorithm. Then, we introduce the idea of conditional hitting sets in order to avoid the ....

....that suffice for derandomization. Thus, we obtain general sufficient conditions for reducing the random bit complexity of any one side error randomized algorithm. 1. 1 Previous Work The techniques for analyzing the hitting properties of random walks on expander graphs were first introduced by [AKS87]. Then, random walks on expanders used for decreasing the error rate of randomized algorithms [CW89, IZ89, MR95] and interactive proof systems [BGG93] while not substantially increasing the random bit complexity. Up to our knowledge, the first time that recursive random walks on expanders were ....

[Article contains additional citation context not shown here]

M. Ajtai, J. Koml'os, and E. Szemer'edi. Deterministic simulation in logspace. Proc. of the 19th ACM Symposium on Theory of Computing, pp. 132--140, 1987.

....vertex set f0;1g r of G. Such a walk uses O(r) random bits and outputs O(r) r bit strings a considerable savings from the obvious O(r 2 ) random bits. Expander graphs have been studied extensively, and have proved to be a very valuable tool in computation theory. Ajtai, Komlos and Szemeredi [AKS87] showed how to (partially) derandomize space bounded randomized algorithms by using expanders; Cohen and Wigderson [CW89] and Impagliazzo and Zuckerman [IZ89] showed how to amplify the success probability of randomized algorithms in a neardeterministic fashion (without having to repeat the ....

M. Ajtai, J. Komlos, and E. Szemeredi. Deterministic simulation in Logspace. In Proc. 19th Annual ACM Symposium on the Theory of Computing, 1987.

....result to hold. We give a pseudo random generator which produces n instances of the function for which the analog of the XOR lemma holds. This is the first derandomization of a direct product result. Our generator is a combination of two known ones the random walks on expander graphs of [1, 9, 19] and the nearly disjoint subsets generator of [23] The quality of the generator is proved via a new proof of the XOR lemma, which might also be useful for other direct product results. Combining our generator with the approach of [25, 6] and the generator of [16] gives substantially improved ....

....achieve some nontrivial amplification (which we actually use) We give yet another proof of the lemma, based on an analysis of a simple card guessing game, which reveals two familiar requirements, for which the solutions (generators) are standard by now. One is the expander walk generator of [1, 9, 19] (used for deterministic amplification) and the other is the nearly disjoint subset generator of [23] used for fooling constant depth circuits, as well as in [25] Our generator is simply the XOR of these two generators, together with a proof that this combination does not ruin their respective ....

[Article contains additional citation context not shown here]

M. Ajtai, J. Komlos and E. Szemeredi, "Deterministic simulation in LOGSPACE", Proc. of 19th ACM STOC, 132-140, 1987.

....using as few random bits as possible. This problem, known as the deterministic amplification problem, was extensively studied [CG89, IZ89, CW89] Using expanders, this can be done using only n O(t) random bits 6 Previous result [SZ94] was for ffi 1=2, and required n O(log(n) time. 39 [AKS87, IZ89, CW89] Sipser [Sip88] defined dispersers as a tool which implies stronger RP amplification. Using extractors, we obtain BPP amplification. Theorem: If L is accepted by a BPP algorithm using m random bits and error 1=4, then L is also accepted by a BPP algorithm using n random bits and ....

....Extractors can also be used to construct pseudo random generators which fool certain classes of algorithms. The generator can use any good extractor for high min entropies, and our new constructions do not improve its operation. The following theorem of [NZ93] improves on previous results of [AKS87] 43 Theorem: NZ93] There exists a pseudo random generator which converts O(S) truly random bits into poly(S) bits which look random to any algorithm which runs in space S. The generator runs in O(S) space and poly(S) time. Proof: sketch) We will build a generator that, for any t, converts n ....

Ajtai, Komlos, and Szemeredi. Deterministic simulation in LOGSPACE. In ACM Symposium on Theory of Computing (STOC), 1987.

....is also accepted by a deterministic space(S log(R=S) machine. There is only one result that improves this bound for some R. Namely, Ajtai, Komlos, and Szemeredi showed that any randomized space(S) algorithm using only O(S 2 = log S) random bits can be simulated deterministically in space(S) [1]. In this paper we improve upon this result and give a deterministic simulation of algorithms using poly(S) random bits. What we obtain is a pseudo random generator. Our generator converts O(S) truly random bits to poly(S) bits that look random to all space(S) machines. The generator can be ....

....generator for space S with parameter ffl running on line in space O(S) Proof: The fact that G runs on line in space O(S) follows immediately from the fact that E can be computed in space O(n) To prove that G is a pseudorandom generator we will show that it fools any space(S) machine M . As in [1], we model M as a layered multi graph L with a layer for each 0 i l, where each layer has 2 S vertices. This will represent M reading S random bits at a time: the ith layer of L represents the configuration of M after reading i sets of S bits. More formally, L consists of vertices (i; j) and ....

M. Ajtai, J. Komlos, and E. Szemeredi, Deterministic Simulation of Logspace, Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987, pp. 132-140.

....universal methods. These usually involve constructing a generator, i.e. a function mapping short strings to longer ones, whose output is as good as a completely random string for a given class of algorithms. For example, a pairwise independent generator [CG89] and an expander walk generator [AKS87, CW89, IZ89] are often used when the total independence of random strings is not necessary. In particular, they allow probability amplification, i.e. the amplification of the success probability of an algorithm, without a significant increase in the number of random bits. Complete ....

....G mapping O(n) bits to n 2 bits such that if a boolean function f 2E has SUC 2 ffln (f) fl for some constant fl 0, then SUC 2 ffl 0 n (f n ffi G) 2 Gammaffl 00 n . This generator is a combination of a Nearly Disjoint Subsets generator [Nis91, NW94] and an Expander Walk generator [AKS87, CW89, IZ89] As usual, we can then obtain from f n a boolean function g of about the same hardness (exponentially small advantage by exponentially large circuits) by applying the Goldreich Levin Theorem. Theorem 9 (The Goldreich Levin Theorem [GL89, Lev93] For h : f0; 1g n f0; 1g n , ....

M. Ajtai, J. Komlos, and E. Szemeredy. Deterministic simulation in LOGSPACE. In

....walks is n O(1= 2 ) i.e. polynomial in n and therefore can be handled in NC. So, it remains to explain the following two points: first, how to construct in NC a constant degree expander, and second, how to simulate the random walk in NC. Both these points have been extensively treated in [10, 13, 9, 1], and we give a simple explanation as indicated in [12] A constant degree d expander on n nodes is an n node d regular graph in which the number of neighbors of any set of vertices S is larger than some positive constant multiple of the cardinality of S (see, e.g. 15, pages 108 112] It is ....

....: kg describing which edge to use in the j th step of the walk. Thus, y 1 is the i 1 th neighbor of z, and for j 2, y j is the i j th neighbor of y j Gamma1 . The number of random bits used in this process is r O(k) and therefore the whole process can be simulated deterministically in NC [1, 16]. Regarding the Randomized Rounding, this technique, in its general setting, seems to be inherently sequential [14] However, it is possible to derandomize it for several cases, and in particular, for the linear systems of all coefficients positive numbers. Application of this sort can be found ....

M. Ajtai, J. Komlos, and E. Szemeredi. Deterministic Simulation in LOGSPACE. In Proceedings of 19th ACM Symposium on Theory of Computing, page 132, 1987.

No context found.

M. Ajtai, J. Komlos, and E. Szemeredi, Deterministic simulation in LOGSPACE, Proceedings of the nineteenth annual ACM conference on Theory of computing (1987), 132--140.

No context found.

M. Ajtai, J. Komlos, and E. Szemeredi, "Deterministic simulation in logspace," Proc. 19th ACM Symp. on Theory of Computing (STOC), 1987.

No context found.

M. Ajtai, J. Komlos, and E. Szemeredi, "Deterministic simulation in logspace," Proc. 19th ACM Symp. on Theory of Computing (STOC), 1987.

No context found.

M. Ajtai, J. Komlos, and E. Szemeredi. Deterministic simulation in Logspace. In 19th STOC, pages 132-140, 1987.

No context found.

M. Ajtai, J. Komlos and E. Szemeredi. Deterministic Simulation in Logspace. Proceedings of the Nineteenth Annual Symposium on the Theory of Computing, ACM, 1987.

No context found.

M. Ajtai, J. Komlos, and E. Szemeredi. Deterministic simulation in Logspace. In 19th STOC, pages 132--140, 1987.

No context found.

M. Ajtai, J. Koml os, and E. Szemer edi. Deterministic simulation in LOGSPACE. In Proceedings of the 19th Annual ACM Symposium on Theory of Computing, pages 132--140, 1987.

No context found.

M. Ajtai, J. Komlos, and E. Szemeredi. Deterministic simulation in LOGSPACE. In Proc. 19th STOC, pages 132-140, 1987.

No context found.

M. Ajtai, J. Komlos and E. Szemeredi. Deterministic Simulation in Logspace. Proceedings of the Nineteenth Annual Symposium on the Theory of Computing, ACM, 1987.

No context found.

Ajtai, Komlos, and Szemeredi. Deterministic simulation in LOGSPACE. In ACM Symposium on Theory of Computing (STOC), 1987. 91

No context found.

M. Ajtai, J. Komlos, and E. Szemeredi, Deterministic simulation in LOGSPACE, in ACM Symposium on Theory of Computing (STOC), 1987."

No context found.

M. Ajtai, J. Komlos, and E. Szemeredi, "Deterministic simulation in logspace," Proc. 19th ACM Symp. on Theory of Computing (STOC), 1987.

No context found.

M. Ajtai, J. Komlos and E. Szemeredi. Deterministic Simulation in Logspace. Proceedings of the Nineteenth Annual Symposium on the Theory of Computing, ACM, 1987.

No context found.

M. Ajtai, J. Komlos, E. Szemeredi, "Deterministic Simulation in LogSpace", Proc. 19th STOC, 1987, pp. 132--140.

No context found.

M. Ajtai, J. Komlos, and E. Szemeredi. Deterministic simulation in logspace. In Proceedings of the 19th Annual ACM Symposium on Theory of Computing (STOC), pages 132-- 140, 1987.

No context found.

M. Ajtai, J. Komlos, and E. Szemeredi. Deterministic simulation in LOGSPACE. In Proc. 19th STOC, pages 132-140, 1987.

No context found.

M. Ajtai, J. Komlos and E. Szemeredi. Deterministic Simulation in Logspace. Proceedings of the Nineteenth Annual Symposium on the Theory of Computing, ACM, 1987.

No context found.

M. Ajtai, J. Komlos, and E. Szemeredi, "Deterministic Simulation of Logspace." In Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987, pp. 132-140.

No context found.

M. Ajtai, J. Komlos and E. Szemer'edi, Deterministic simulation in LogSpace, 19th ACM Symposium on the Theory of Computing, 1987, pp. 132-140.

No context found.

M. Ajtai, J. Komlos, E. Szemer'edi, "Deterministic Simulation in LogSpace", Proc. 19th STOC, 1987, pp. 132--140.

First 50 documents  Next 50

Online articles have much greater impact   More about CiteSeer.IST at NUS   Add search form to your site   Submit documents   Feedback  

CiteSeer.IST at NUS - Copyright Penn State and NEC. Hosted by the School of Computing, National University of Singapore.