Tribes

Definition

The tribe function with [math]t[/math] tribes of size [math]n[/math] is the boolean function [math]\mathrm{Tribes}_{t,n} : \{-1 ,+1\}^{tn} \rightarrow \{-1,+1\}[/math] defined by the DNF formula

[math]\mathrm{Tribes}_{t,n}(x) = \bigvee_{i=1}^{t} \bigwedge_{j=1}^{n} x_{i,j}[/math],

where we identify [math]-1[/math] with logical True and [math]+1[/math] with logical False.