The Library
Explicit ORdispersers with polylogarithmic degree
Tools
UNSPECIFIED (1998) Explicit ORdispersers with polylogarithmic degree. In: 27th Annual ACM Symposium on Theory of Computing, LAS VEGAS, NEVADA, MAY 29JUN 01, 1995. Published in: JOURNAL OF THE ACM, 45 (1). pp. 123154.
Full text not available from this repository.Abstract
An (N, M, T)ORdisperser 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)ORdisperser such that the outdegree of any vertex in V is at most polylogarithmic in N. Using this with known applications of ORdispersers yields several results. First, our construction implies that the complexity class StrongRP defined by Sipser, equals RP. Second, for any fixed eta > 0, we give the first polynomialtime simulation of RP algorithms using the output of any "etaminimally random" source. For any integral R > 0, such a source accepts a single request for an Rbit 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 blackbox polynomialtime 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:  00045411  
Official Date:  January 1998  
Dates: 


Volume:  45  
Number:  1  
Number of Pages:  32  
Page Range:  pp. 123154  
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 29JUN 01, 1995  
URI:  http://wrap.warwick.ac.uk/id/eprint/15830 
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Actions (login required)
View Item 