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

Michael Saks, Shiyu Zhou

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationRandomization and Approximation Techniques in Computer Science - International Workshop, RANDOM 1997, Proceedings
EditorsJosé Rolim
PublisherSpringer Verlag
Pages95-109
Number of pages15
ISBN (Print)3540632484, 9783540632481
DOIs
StatePublished - 1997
EventInternational Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 1997 - Bologna, Italy
Duration: Jul 11 1997Jul 12 1997

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1269
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

OtherInternational Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 1997
Country/TerritoryItaly
CityBologna
Period7/11/977/12/97

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Sample spaces with small bias on neighborhoods and error-correcting communication protocols'. Together they form a unique fingerprint.

Cite this