Naor, Moni and Schulman, Leonard J. and Srinivasan, Aravind (1995) Splitters and near-optimal derandomization. In: 36th Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press , Los Alamitos, CA, pp. 182-191. ISBN 0-8186-7183-1 http://resolver.caltech.edu/CaltechAUTHORS:20120223-112750729
Full text is not posted in this repository. Consult Related URLs below.
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20120223-112750729
We present a fairly general method for finding deterministic constructions obeying what we call k-restrictions; this yields structures of size not much larger than the probabilistic bound. The structures constructed by our method include (n,k)-universal sets (a collection of binary vectors of length n such that for any subset of size k of the indices, all 2^k configurations appear) and families of perfect hash functions. The near-optimal constructions of these objects imply the very efficient derandomization of algorithms in learning, of fixed-subgraph finding algorithms, and of near optimal ΣIIΣ threshold formulae. In addition, they derandomize the reduction showing the hardness of approximation of set cover. They also yield deterministic constructions for a local-coloring protocol, and for exhaustive testing of circuits.
|Item Type:||Book Section|
|Additional Information:||© 1995 IEEE. Date of Current Version: 06 August 2002. We thank Oded Goldreich and Ravi Sundaram for explaining the implication of the construction of (n,k)-universal sets to the non-approximability of set cover; and we thank Mike Luby for a discussion. We thank Uri Feige for explaining his results. Supported by an Alon Fellowship and by a grant from the Israel Science Foundation administered by the Israeli Academy of Sciences|
|Other Numbering System:|
|Official Citation:||Naor, M.; Schulman, L.J.; Srinivasan, A.; , "Splitters and near-optimal derandomization," Foundations of Computer Science, 1995. Proceedings., 36th Annual Symposium on , vol., no., pp.182-191, 23-25 Oct 1995 doi: 10.1109/SFCS.1995.492475 URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=492475&isnumber=10957|
|Usage Policy:||No commercial reproduction, distribution, display or performance rights in this work are provided.|
|Deposited By:||Ruth Sustaita|
|Deposited On:||23 Feb 2012 21:04|
|Last Modified:||23 Aug 2016 10:10|
Repository Staff Only: item control page