TY - GEN

T1 - Sample spaces with small bias on neighborhoods and error-correcting communication protocols

AU - Saks, Michael

AU - Zhou, Shiyu

N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1997.

PY - 1997

Y1 - 1997

N2 - We give a deterministic algorithm which, on input an integer n, collection f of subsets of {1,2,⋯, n} and ∈ ∃ (0,1) runs in time polynomial in n‖f‖/∈ and produces a ±1-matrix M with n columns and m=O(log ‖f‖/∈2) rows with the following property: for any subset F ∃ f, the fraction of 1's in the n-vector obtained by coordinate-wise multiplication of the column vectors indexed by F is between (1−∈)/2 and (1+∈)/2. In the case that 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), as compared to the best previous constructions of [NN90] and [AGHP91] which were, respectively, O(log n/∈ 4) and O((log n)2/∈ 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.

AB - We give a deterministic algorithm which, on input an integer n, collection f of subsets of {1,2,⋯, n} and ∈ ∃ (0,1) runs in time polynomial in n‖f‖/∈ and produces a ±1-matrix M with n columns and m=O(log ‖f‖/∈2) rows with the following property: for any subset F ∃ f, the fraction of 1's in the n-vector obtained by coordinate-wise multiplication of the column vectors indexed by F is between (1−∈)/2 and (1+∈)/2. In the case that 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), as compared to the best previous constructions of [NN90] and [AGHP91] which were, respectively, O(log n/∈ 4) and O((log n)2/∈ 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.

UR - http://www.scopus.com/inward/record.url?scp=84957648557&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84957648557&partnerID=8YFLogxK

U2 - 10.1007/3-540-63248-4_9

DO - 10.1007/3-540-63248-4_9

M3 - Conference contribution

AN - SCOPUS:84957648557

SN - 3540632484

SN - 9783540632481

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 95

EP - 109

BT - Randomization and Approximation Techniques in Computer Science - International Workshop, RANDOM 1997, Proceedings

A2 - Rolim, José

PB - Springer Verlag

T2 - International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 1997

Y2 - 11 July 1997 through 12 July 1997

ER -