We examine a hierarchy of equivalence classes of local quasi-random properties of Boolean Functions. In particular, we prove an equivalence between a number of properties including balanced influences, spectral discrepancy, local strong regularity, subgraph counts in a Cayley graph associated to a Boolean function, and equidistribution of additive derivatives among many others. In addition, we construct families of quasi-random Boolean functions which exhibit the properties of our equivalence theorem and separate the levels of our hierarchy. Furthermore, we relate our properties to several extant notions of pseudo-randomness for Boolean functions.

Given an \(n\)-vertex digraph \(D\) and a labeling \(\sigma:V(D)\to [n]\), we say that an arc \(u\to v\) of \(D\) is a descent of \(\sigma\) if \(\sigma(u)›\sigma(v)\). Foata and Zeilberger introduced a generating function \(A_D(t)\) for labelings of \(D\) weighted by descents, which simultaneously generalizes both Eulerian polynomials and Mahonian polynomials. Motivated in part by work of Kalai, we prove three results related to \(-1\) evaluations of \(A_D(t)\): we give combinatorial interpretations of \(|A_D(-1)|\) for a large class of digraphs (such as digraphs whose underlying graph is bipartite), we determine the maximum and minimum possible values of \(|A_D(-1)|\) obtained by directed trees, and we obtain bounds on the mulitiplicity of \(-1\) as a root of \(A_D(t)\).

Mathematics Subject Classifications: 05C20, 05A15

Keywords: Eulerian polynomials, alternating permutations, combinatorial reciprocity