Generalized Tribes
TODO: Fix definition so that the total number of bits will be n, and use w and s (so there are s tribes, each of width w)
Definition
The generalized tribe function is a class of functions that generalizes the tribes function. It was first introduced by Ajtai-Linial as an example of a boolean function that is unbiased and the influence of every small number of variables is small. Their construction extends the tribe function as follows. First, instead of using the AND function for the vote of each tribe, we add negations. Namely given arbitrary function [math]\delta : \{-1 ,+1\}^{tn} \rightarrow \{-1,+1\}[/math] we define,
[math]\mathrm{Tribes}_{t,n,\delta}(x) = \bigvee_{i=1}^{t} \bigwedge_{j=1}^{n} \delta(i,j)x_{i,j}[/math].
Second, instead instead of a single partition of the variables [math]\{x_1 , \ldots , x_{tn}\}[/math] to [math]t[/math] tribes each of size [math]n[/math], we consider multiple partitions and aggregate their voting by taking their AND. A partition of [math]\{x_1,\ldots , x_{tn}\}[/math] to [math]t[/math] tribes is a function [math]P : \{1,2,\ldots,tn\} \rightarrow \{1,\ldots,t\}[/math] where we interpret [math]P(j) = i[/math] as [math]x_i[/math] belongs to the j'th tribe. Also, we say that [math]P[/math] is an equi-partition if [math]|P^{-1}(i)| = n [/math] for every [math]i = 1,\ldots,t[/math]. Given [math]\ell[/math] equi-partitions [math]P_1 , \ldots , P_{\ell}[/math] we define,
[math]\mathrm{Tribes}_{t,n,(\delta_k)_{k=1}^{\ell},(P_k)_{k=1}^{\ell}}(x) = \bigwedge_{k=1}^{\ell} \bigvee_{i=1}^{t} \bigwedge_{j \in P_k^{-1}(i)} \delta_k(i,j)x_{i,j}[/math].
Roughly, Ajtai and Linial showed that if the partitions [math]P_1 , \ldots , P_{\ell}[/math] and the functions [math]\delta_1 , \ldots , \delta_{\ell}[/math] are chosen at random then with high probability, [math]\mathrm{Tribes}_{t,n,(\delta_k)_{k=1}^{\ell},(P_k)_{k=1}^{\ell}}[/math] satisfy the property that every small set of variables can change the output only with little probability over a uniformly chosen input [1]. This construction was de-randomized (with small variants) by Chattopadhyay and Zuckerman and is a key component in their construction of two-source extractor with poly-logarithmic seed. Later, a similar, and arguably simpler, construction was given by Meka.
Properties
- For a fixed [math]\epsilon[/math] and appropriate choice of [math]t,n,\ell[/math] there exists functions [math](\delta_k)_{k=1}^{\ell}[/math] and partitions [math](P_k)_{k=1}^{\ell}[/math] of the variables [math]\{x_1,\ldots ,x_{tn}\}[/math] to tribes such that the function [math]\mathrm{Tribes}_{t,n,(\delta_k)_{k=1}^{\ell},(P_k)_{k=1}^{\ell}}[/math] is unbiased, namely has bias [math]\frac{1}{2}+o(1)[/math] and every set of [math]\frac{\epsilon n}{\log^2 n}[/math] variables has influence [math]O(\epsilon)[/math] [2].
