CaltechAUTHORS
  A Caltech Library Service

Splitters and near-optimal derandomization

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

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:
URLURL TypeDescription
http://dx.doi.org/10.1109/SFCS.1995.492475 DOIUNSPECIFIED
http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=492475PublisherUNSPECIFIED
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:
Funding AgencyGrant Number
Alon Fellowship UNSPECIFIED
Israel Science Foundation (ISF) UNSPECIFIED
Other Numbering System:
Other Numbering System NameOther Numbering System ID
INSPEC Accession Number5125637
Record Number:CaltechAUTHORS:20120223-112750729
Persistent URL:http://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:23 Feb 2012 21:04

Repository Staff Only: item control page