Florida International University
Edit Your Profile
FIU Discovery
Toggle navigation
Browse
Home
People
Organizations
Scholarly & Creative Works
Research Facilities
Support
Edit Your Profile
Testing non-uniform k-wise independent distributions over product spaces
Conference
Rubinfeld, R, Xie, N. (2010). Testing non-uniform k-wise independent distributions over product spaces .
EURO-PAR 2011 PARALLEL PROCESSING, PT 1,
6198 LNCS(PART 1), 565-581. 10.1007/978-3-642-14165-2_48
Share this citation
Twitter
Email
Rubinfeld, R, Xie, N. (2010). Testing non-uniform k-wise independent distributions over product spaces .
EURO-PAR 2011 PARALLEL PROCESSING, PT 1,
6198 LNCS(PART 1), 565-581. 10.1007/978-3-642-14165-2_48
Copy Citation
Share
Overview
Identifiers
Additional Document Info
View All
Overview
cited authors
Rubinfeld, R; Xie, N
authors
Xie, Ning
abstract
A distribution D over ∑1×⋯×∑ n is called (non-uniform) k-wise independent if for any set of k indices {i 1, ..., i k } and for any , . We study the problem of testing (non-uniform) k-wise independent distributions over product spaces. For the uniform case we show an upper bound on the distance between a distribution D from the set of k-wise independent distributions in terms of the sum of Fourier coefficients of D at vectors of weight at most k. Such a bound was previously known only for the binary field. For the non-uniform case, we give a new characterization of distributions being k-wise independent and further show that such a characterization is robust. These greatly generalize the results of Alon et al. [1] on uniform k-wise independence over the binary field to non-uniform k-wise independence over product spaces. Our results yield natural testing algorithms for k-wise independence with time and sample complexity sublinear in terms of the support size when k is a constant. The main technical tools employed include discrete Fourier transforms and the theory of linear systems of congruences. © 2010 Springer-Verlag Berlin Heidelberg.
publication date
August 12, 2010
published in
DISTRIBUTED COMPUTING (DISC 2014)
Book
Identifiers
Digital Object Identifier (DOI)
https://doi.org/10.1007/978-3-642-14165-2_48
Additional Document Info
start page
565
end page
581
volume
6198 LNCS
issue
PART 1