Difference between revisions of "Tribes"

From Boolean Zoo
Jump to: navigation, search
 
(10 intermediate revisions by 3 users not shown)
Line 1: Line 1:
 
== Definition ==
 
== 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  
+
Let <math>n = ws</math>. The tribes function with <math>s</math> tribes of width <math>w</math> is the boolean function <math>\mathrm{Tribes}_{w,s} : \{-1 ,+1\}^{ws} \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>,
+
:::{| class="wikitable"
 +
|-
 +
|<math>\mathrm{Tribes}_{w,s}(x) = \bigvee_{i=1}^{s} \bigwedge_{j=1}^{w} x_{i,j}</math>,
 +
|}
  
 
where we identify <math>-1</math> with logical True and <math>+1</math> with logical False.
 
where we identify <math>-1</math> with logical True and <math>+1</math> with logical False.
  
−
The Tribes function corresponds to the follows voting scheme. There are <math>t</math> tribes, each consists of <math>n</math> members and the value of <math>x_{i,j}</math> corresponds to the vote of the j-th member from the i-th tribe (with the above identification of logical values). First, each tribe takes a unanimous vote. Namely, if all tribe members voted True then the tribe vote is counted as True, otherwise the tribe vote is considered False. Then, if at least tribe voted True then the entire vote is considered True and otherwise it is considered False. In other words, the value of <math>\mathrm{Tribes}_{t,n}(x)</math> is True if and only if at all the members of at least one tribe voted True.
+
The Tribes function corresponds to the follows voting scheme. There are <math>s</math> tribes, each consists of <math>w</math> members and the value of <math>x_{i,j}</math> corresponds to the vote of the j-th member from the i-th tribe (with the above identification of logical values). First, each tribe takes a unanimous vote. Namely, if all tribe members voted True then the tribe vote is counted as True, otherwise the tribe vote is considered False. Then, if at least tribe voted True then the entire vote is considered True and otherwise it is considered False. In other words, the value of <math>\mathrm{Tribes}_{w,s}(x)</math> is True if and only if at all the members of at least one tribe voted True.  
−
 
 
−
 
 
−
== Generalized Tribes Function ==
 
−
The generalized tribe function 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 <ref>TODO [TODO]</ref>. Their 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.
 
−
 
 
−
 
 
  
 +
The Tribes function is also known by the name of "read-once CNF".
  
 
== Properties ==
 
== Properties ==
−
* Bias: When choosing an input <math>x</math> uniformly at random, <math>\mathrm{Pr}_{x}[\mathrm{Tribes}_{t,n}(x) = -1] = 1 - (1-2^{-n})^{t}</math>.
+
* Bias: When choosing an input <math>x</math> uniformly at random, <math>\mathrm{Pr}_{x}[\mathrm{Tribes}_{w,s}(x) = -1] = 1 - (1-2^{-w})^{s}</math>.
−
* Fourier Expansion: Index the Fourier coefficients of <math>\mathrm{Tribes}_{t,n}(x)</math> as follows. Given <math>T \subseteq [nt]</math> write <math>T = (T_1,\ldots,T_s)</math> where <math>T_i \subseteq \{(i-1)\cdot n+1,.\ldots , i\cdot n + n\}</math> for <math>i = 1,2,\ldots,t</math>. Then,
+
* The tribes function is [[:Category:evasive function|evasive]] so the [[decision tree complexity]] is <math>D(f)=n</math>.
 +
* Fourier Expansion: Index the Fourier coefficients of <math>\mathrm{Tribes}_{w,s}(x)</math> as follows. Given <math>T \subseteq [n]</math> write <math>T = (T_1,\ldots,T_s)</math> where <math>T_i \subseteq \{(i-1)\cdot w+1,.\ldots , i\cdot w + w\}</math> for <math>i = 1,2,\ldots,s</math>. Then,
  
−
:<math>\widehat{\mathrm{Tribes}_{t,n}}(T)  
+
:::{| class="wikitable"
 +
|-
 +
|<math>\widehat{\mathrm{Tribes}_{w,s}}(T)  
 
=
 
=
 
\begin{cases}
 
\begin{cases}
−
2(1-2^{-n})^{t}-1 & T = \emptyset\\
+
2(1-2^{-w})^{s}-1 & T = \emptyset\\
−
2(-1)^{|\{i : T_i \neq \emptyset\}|+|T|}2^{-|\{i : T_i \neq \emptyset\}| \cdot n}(1-2^{-n})^{t-|\{i : T_i \neq \emptyset\}|} & T \neq \emptyset\\
+
2(-1)^{|\{i : T_i \neq \emptyset\}|+|T|}2^{-|\{i : T_i \neq \emptyset\}| \cdot w}(1-2^{-w})^{s-|\{i : T_i \neq \emptyset\}|} & T \neq \emptyset\\
 
\end{cases}
 
\end{cases}
 
</math>
 
</math>
 +
|}
  
 +
* Among almost asymptotically unbiased functions, Tribes asymptotically has smallest influence variables: One can choose the number of tribes and the tribe size so that the tribes function is almost an unbiased function, and with each variable having very little influence. Specifically, when <math>w = \log n - \log\log n + O(1)</math> and <math>s = n / w</math>, we get that <math>\mathrm{Pr}_{x}[\mathrm{Tribes}_{w,s}(x) = -1] = 1/2 - O(\frac{\log n}{n})</math> and the influence of every variable equals <math>\frac{\ln n}{n}(1+o(1))</math>. This is the smallest maximum influence possible according to the [[Functional_inequalities#Maximum_influence_formulation| KKL theorem]] <ref>Ryan O'Donnell, Analysis of Boolean functions, Chapter 4.2, [http://www.contrib.andrew.cmu.edu/~ryanod/?p=2245]</ref>.
 +
* With the above choice of <math>w</math> and <math>s</math>, the Tribes function is saturates (up to a constant factor) both the [[Functional_inequalities#Influence_inequality_formulation | KKL]] and [[Functional_inequalities#Talagrand.27s_influence_inequality | Talagrand's]] influence inequalities.
  
−
* Among almost asymptotically unbiased functions, Tribes asymptotically has smallest influence variables: One can choose the number of tribes and the tribe size so that the tribes function is almost an unbiased function, and with each variable having very little influence. Specifically, one can set <math>t,n</math> such that <math>\mathrm{Pr}_{x}[\mathrm{Tribes}_{t,n}(x) = -1] = 1/2 - O(\frac{\log n}{n})</math> and the influence of every variable equals <math>\frac{\ln n}{n}(1+o(1))</math>. In fact, according to the KKL theorem this is tight up to constant factors, namely any unbiased function must have a variable with influence <math>\Omega(\frac{\log n}{n})</math>. <ref>Ryan O'Donnell, Analysis of Boolean functions, Chapter 4.2, [http://www.contrib.andrew.cmu.edu/~ryanod/?p=2245]</ref>
+
== See also ==
−
 
+
* [[Generalized_Tribes|Generalized tribes]]
−
 
 
  
 
== Refrences ==
 
== Refrences ==
Line 40: Line 39:
  
  
−
[[Category:monotone function]]
+
[[Category:monotone function]] [[Category:balanced function]] [[Category:evasive function]] [[Category:transitive-symmetric function]] [[Category:Noise sensitive function]]

Latest revision as of 10:27, 20 March 2022

Definition

Let [math]n = ws[/math]. The tribes function with [math]s[/math] tribes of width [math]w[/math] is the boolean function [math]\mathrm{Tribes}_{w,s} : \{-1 ,+1\}^{ws} \rightarrow \{-1,+1\}[/math] defined by the DNF formula

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

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

The Tribes function corresponds to the follows voting scheme. There are [math]s[/math] tribes, each consists of [math]w[/math] members and the value of [math]x_{i,j}[/math] corresponds to the vote of the j-th member from the i-th tribe (with the above identification of logical values). First, each tribe takes a unanimous vote. Namely, if all tribe members voted True then the tribe vote is counted as True, otherwise the tribe vote is considered False. Then, if at least tribe voted True then the entire vote is considered True and otherwise it is considered False. In other words, the value of [math]\mathrm{Tribes}_{w,s}(x)[/math] is True if and only if at all the members of at least one tribe voted True.

The Tribes function is also known by the name of "read-once CNF".

Properties

  • Bias: When choosing an input [math]x[/math] uniformly at random, [math]\mathrm{Pr}_{x}[\mathrm{Tribes}_{w,s}(x) = -1] = 1 - (1-2^{-w})^{s}[/math].
  • The tribes function is evasive so the decision tree complexity is [math]D(f)=n[/math].
  • Fourier Expansion: Index the Fourier coefficients of [math]\mathrm{Tribes}_{w,s}(x)[/math] as follows. Given [math]T \subseteq [n][/math] write [math]T = (T_1,\ldots,T_s)[/math] where [math]T_i \subseteq \{(i-1)\cdot w+1,.\ldots , i\cdot w + w\}[/math] for [math]i = 1,2,\ldots,s[/math]. Then,
[math]\widehat{\mathrm{Tribes}_{w,s}}(T) = \begin{cases} 2(1-2^{-w})^{s}-1 & T = \emptyset\\ 2(-1)^{|\{i : T_i \neq \emptyset\}|+|T|}2^{-|\{i : T_i \neq \emptyset\}| \cdot w}(1-2^{-w})^{s-|\{i : T_i \neq \emptyset\}|} & T \neq \emptyset\\ \end{cases} [/math]
  • Among almost asymptotically unbiased functions, Tribes asymptotically has smallest influence variables: One can choose the number of tribes and the tribe size so that the tribes function is almost an unbiased function, and with each variable having very little influence. Specifically, when [math]w = \log n - \log\log n + O(1)[/math] and [math]s = n / w[/math], we get that [math]\mathrm{Pr}_{x}[\mathrm{Tribes}_{w,s}(x) = -1] = 1/2 - O(\frac{\log n}{n})[/math] and the influence of every variable equals [math]\frac{\ln n}{n}(1+o(1))[/math]. This is the smallest maximum influence possible according to the KKL theorem [1].
  • With the above choice of [math]w[/math] and [math]s[/math], the Tribes function is saturates (up to a constant factor) both the KKL and Talagrand's influence inequalities.

See also

Refrences

  1. ↑ Ryan O'Donnell, Analysis of Boolean functions, Chapter 4.2, [1]
Retrieved from "https://booleanzoo.weizmann.ac.il/index.php?title=Tribes&oldid=412"