The Library
Explicit OR-dispersers with polylogarithmic degree
Tools
UNSPECIFIED (1998) Explicit OR-dispersers with polylogarithmic degree. In: 27th Annual ACM Symposium on Theory of Computing, LAS VEGAS, NEVADA, MAY 29-JUN 01, 1995. Published in: JOURNAL OF THE ACM, 45 (1). pp. 123-154. ISSN 0004-5411.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Abstract
An (N, M, T)-OR-disperser is a bipartite multigraph G = (V, W, E) with \V\ = N, and \W\ = M, having the following expansion property: any subset of V having at least T vertices has a neighbor set of size at least M/2. For any pair of constants xi, lambda, 1 greater than or equal to xi > lambda greater than or equal to 0, any sufficiently large N, and for any T greater than or equal to 2((log N)xi), M less than or equal to 2((log N))(lambda), we give an explicit elementary construction of an (N, M, T)-OR-disperser such that the out-degree of any vertex in V is at most polylogarithmic in N. Using this with known applications of OR-dispersers yields several results. First, our construction implies that the complexity class Strong-RP defined by Sipser, equals RP. Second, for any fixed eta > 0, we give the first polynomial-time simulation of RP algorithms using the output of any "eta-minimally random" source. For any integral R > 0, such a source accepts a single request for an R-bit string and generates the string according to a distribution that assigns probability at most 2(-R eta) to any string. It is minimally random in the sense that any weaker source is insufficient to do a black-box polynomial-time simulation of RP algorithms.
Item Type: | Conference Item (UNSPECIFIED) | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
Journal or Publication Title: | JOURNAL OF THE ACM | ||||
Publisher: | ASSOC COMPUTING MACHINERY | ||||
ISSN: | 0004-5411 | ||||
Official Date: | January 1998 | ||||
Dates: |
|
||||
Volume: | 45 | ||||
Number: | 1 | ||||
Number of Pages: | 32 | ||||
Page Range: | pp. 123-154 | ||||
Publication Status: | Published | ||||
Title of Event: | 27th Annual ACM Symposium on Theory of Computing | ||||
Location of Event: | LAS VEGAS, NEVADA | ||||
Date(s) of Event: | MAY 29-JUN 01, 1995 |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |