The role of symmetry in Boolean functions $f:\{0,1\}^n \to \{0,1\}$ has been extensively studied in complexity theory.
For example, symmetric functions, that is, functions that are invariant under the action of $S_n$ is an important class of functions in the study of Boolean functions.
A function $f:\{0,1\}^n \to \{0,1\}$ ... more >>>

We give new bounds on the cosystolic expansion constants of several families of high dimensional expanders, and the known coboundary expansion constants of order complexes of homogeneous geometric lattices, including the spherical building of $SL_n(F_q)$. The improvement applies to the high dimensional expanders constructed by Lubotzky, Samuels and Vishne, and ... more >>>

We study Frege proofs for the one-to-one graph Pigeon Hole Principle
defined on the $n\times n$ grid where $n$ is odd.
We are interested in the case where each formula
in the proof is a depth $d$ formula in the basis given by
$\land$, $\lor$, and $\neg$. We prove that ... more >>>