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. https://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: https://resolver.caltech.edu/CaltechAUTHORS:20120223-112750729
Abstract
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 | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Related URLs: |
| |||||||||
| ORCID: |
| |||||||||
| 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 | |||||||||
| Funders: |
| |||||||||
| Other Numbering System: |
| |||||||||
| DOI: | 10.1109/SFCS.1995.492475 | |||||||||
| Record Number: | CaltechAUTHORS:20120223-112750729 | |||||||||
| Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20120223-112750729 | |||||||||
| 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. | |||||||||
| ID Code: | 29440 | |||||||||
| Collection: | CaltechAUTHORS | |||||||||
| Deposited By: | Ruth Sustaita | |||||||||
| Deposited On: | 23 Feb 2012 21:04 | |||||||||
| Last Modified: | 09 Nov 2021 17:07 |
Repository Staff Only: item control page
