UC San Diego

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.