#

### Volume 2019

#### Article 3

Published by the Department of Computer Science, The University of Chicago.

#### H-wise Independence

Ishay Haviv

School of Computer Science

The Academic College of Tel Aviv-Yaffo

Tel Aviv 61083, Israel

and

Michael Langberg

Dept. of Electrical Engineering

University at Buffalo

Buffalo, NY, USA

*November 19, 2019*
#### Abstract

For a hypergraph $H$ on the vertex set $\{1,\ldots,n\}$, a distribution
$D = (D_1,\ldots,D_n)$ over $\{0,1\}^n$ is *H-wise independent* if every
restriction of $D$ to indices which form an edge in $H$ is uniform. This
generalizes the notion of $k$-wise independence obtained by taking $H$ to be the
complete $n$ vertex $k$-uniform hypergraph. This generalization was studied by
Schulman (STOC 1992), who presented constructions of $H$-wise independent
distributions that are *linear*, i.e., the samples are strings of inner
products (over $\mathbb{F}_2$) of a fixed set of vectors with a uniformly chosen random
vector.
Let $\ell(H)$ denote the minimum possible size of a sample space of a uniform
$H$-wise independent distribution. The $\ell$ parameter is well understood for the
special case of $k$-wise independence. In this work we study the notion of
$H$-wise independence and the $\ell$ parameter for general graphs and hypergraphs.
For graphs, we show how the $\ell$ parameter relates to standard graph parameters
(e.g., clique number, chromatic number, Lovász theta function, minrank). We
derive algorithmic and hardness results for this parameter as well as an explicit
construction of graphs $G$ for which $\ell(G)$ is exponentially smaller than the
size of the sample space of any linear $G$-wise independent distribution. For
hypergraphs, we study the problem of testing whether a given distribution is
$H$-wise independent, generalizing results of Alon et al. (STOC 2007).

- The article:
**PDF** (265 KB)
- Source material: ZIP (77 KB)
**BibTeX** entry for this
article (265 bytes)

Submitted January 8, 2018, revised September 24, 2019,
published October 24, 2019.

Volume 2019, Article 2

Volume 2019
Published articles