PublicationsManuscripts

Boolean functions in their original setting are functions $f\colon\{0,1\}^n\rightarrow\{0,1\}$, these functions are well studied, and one key property of them is that they have some notions of complexity measures. A classical result states that all these measures are polynomially related. Another result is that Boolean functions that are also of degree $1$ as real multi-linear polynomials are exactly the dictators $0,1,x_i,1-x_i$, which depends on at most $1$ coordinate.

In recent years, researchers have tried to widen the scope and investigate Boolean functions on various finite mathematical objects, for example, the multi-slice $M(k_1,\dots,k_m)$, the symmetric group $S_n$, and the perfect matching scheme $\mathcal{M}_{2n}$.

For all these cases, and more, researchers have proposed a general framework that enables us to define analogs for all the complexity measures of Boolean functions over the hypercube. Moreover, under some conditions, they have proved a theorem that relates all these complexity measures polynomially, where the polynomial coefficients only depend on some parameters of the domain.

Anther theorem classifies degree $1$ Boolean functions over the symmetric group and states that they are exactly the dictators, which are functions that depend on at most $1$ coordinate.

We examine boolean functions on the Alternating Group $A_n$ and the Generalized Symmetric Group $S(m,n)=\mathbf{Z}_m \wr {S_n}$, in particular, the Hyperoctheadral Group $B_n=S(2,n)$. We find how they fit this general framework, we prove that they satisfy the conditions of the main theorem and compute their parameters.

We also prove that except for some anomaly in $A_4$, degree $1$ boolean functions on these two types of groups, are exactly the dictators.