PublicationsManuscripts

The complexity of Boolean functions on the Boolean cube can be measured in several ways, such as circuit complexity and decision tree complexity. Classical results show that many of these measures are polynomially related, such as decision tree complexity, certificate complexity, degree and sensitivity. Recently, the study of Boolean functions has been extended to functions on domains other than the Boolean cube, such as the slice, high-dimensional expanders and the Grassmann scheme. Can the study of different complexity measures can be generalized to some of these domains?

We begin with surveying recent work that generalizes the definitions of some of the classical complexity measures to domains other than the Boolean cube, including the symmetric group, which is our main focus. We then describe results regarding the relations between the different measures, generalizing the classical results and showing that polynomial relations exist between the considered measures for many other domains.

We then focus on functions with low sensitivity, with the goal of constructing efficient circuits for them. First, we generalize a result regarding the existence of small circuits for functions with low sensitivity on the Boolean cube, constructing a circuit of size $n^{O(s)}$, where $s$ is the sensitivity of $f$. Next, we generalize a result regarding the existence of low-depth circuits for functions with low sensitivity on the Boolean cube, and construct such circuits for functions over domains satisfying certain properties, including the symmetric group. Our construction results in an unbounded fan-in circuit of depth $O(s\log n)$ in the case of the symmetric group.

The last part of our work concerns intersecting families of permutations. A family of permutations is $t$-intersecting if any two permutations in the family agree on at least $t$ elements. It is known that for a large enough $n$, the maximal size of a $t$-intersecting family of permutations is $(n-t)!$, and a family of that size is a $t$-star, that is, the set of all permutations mapping some distinct $i_{1},\ldots,i_{t}$ to some distinct $j_{1},\ldots,j_{t}$ respectively. We generalize this result to the case of $t$-setwise-intersection, where any two permutations in the family agree on the image of a set of $t$ elements. We give an alternative proof to a known result stating that for a large enough $n$, the maximal size of a $t$-setwise-intersecting family of permutations is $t!(n-t)!$, and a family of that size is a $t$-setwise-star, that is, the set of all permutations mapping some set $S$ of size $t$ to some $T$ of size $t$. Our proof is much simpler than the known proof (which proves a stronger statement) and works for smaller values of $n$.