Sample Spaces with Small Bias on Neighborhoods and Error-Correcting Communication Protocols |
| |
Authors: | M Saks S Zhou |
| |
Affiliation: | (1) Department of Mathematics, Rutgers University, New Brunswick, NJ 08854, USA. saks@math.rutgers.edu., US;(2) Department of Computer and Information Science, University of Pennsylvania, Philadelphia, PA 19104, USA. shiyu@cis.upenn.edu., US |
| |
Abstract: | We give a deterministic algorithm which, on input an integer n , collection \cal F of subsets of {1,2,\ldots,n} , and ɛ∈ (0,1) , runs in time polynomial in n| \cal F |/ɛ and produces a \pm 1 -matrix M with n columns and m=O(log | \cal F |/ɛ
2
) rows with the following property: for any subset F ∈ \cal F , the fraction of 1's in the n -vector obtained by coordinatewise multiplication of the column vectors indexed by F is between (1-ɛ)/2 and (1+ɛ)/2 . In the case that \cal F is the set of all subsets of size at most k , k constant, this gives a polynomial time construction for a k -wise ɛ -biased sample space of size O(log n/ɛ
2
) , compared with the best previous constructions in NN] and AGHP] which were, respectively, O(log n/ɛ
4
) and O(log
2
n/ɛ
2
) . The number of rows in the construction matches the upper bound given by the probabilistic existence argument. Such constructions
are of interest for derandomizing algorithms.
As an application, we present a family of essentially optimal deterministic communication protocols for the problem of checking
the consistency of two files.
Received October 30, 1997; revised September 17, 1999, and April 17, 2000. |
| |
Keywords: | , ɛ, -Biased sample space, Explicit construction, Derandomization, |
本文献已被 SpringerLink 等数据库收录! |
|