Almost k-wise independence versus k-wise independence

Considering distributions over n-bit long strings, this work relates two natural notions of being approximately k-wise independent. The local notion refers to the distnaces of the various projections on any k coordinates, whereas the global notion refers to the distance from a single k-wise independent distribution.

Comments: Authored by N. Alon, O. Goldreich and Y. Mansour. Appeared in

• IPL, to appear.