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\}$ is called transitive (or weakly-symmetric) if there exists a transitive group $G$ of $S_n$ such that $f$ is invariant under the action of $G$. In other words, the value of a transitive function remains unchanged even after the input bits of $f$ are moved around according to some permutation $\sigma \in G$. Understanding various complexity measures of transitive functions has been a rich area of research for the past few decades.
In this work, we study transitive functions in light of several combinatorial measures. The question that we try to address in this paper is what is the maximum separations between various pairs of combinatorial measures for transitive functions. Such study for general Boolean functions has been going on for the past many years. The current best-known results for general Boolean functions have been nicely compiled by Aaronson et~al.~(STOC, 2021). But before this paper, no such systematic study has been done for the case of transitive functions.
The separation between a pair of combinatorial measures is shown by constructing interesting functions that demonstrate the separation. Over the past three decades, various interesting classes of functions have been designed for this purpose. In this context, one of the celebrated classes of functions is the class of ``pointer functions''.
Ambainis et al.~(JACM, 2017) constructed several functions, which are modifications of the pointer function, first introduced in G{\"{o}}{\"{o}}s et~al.~(SICOMP, 2018 / FOCS, 2015), to demonstrate separation between various pairs of measures. In the last few years, pointer functions have been used to show separation between various other pairs of measures (for example, Mukhopadhyay et~al.~(FSTTCS, 2015), Ben-David et~al.~(ITCS, 2017), G{\"{o}}{\"{o}}s et~al.~(ToCT, 2018 / ICALP, 2017)).
However, the pointer functions themselves are not transitive.
Based on the various kinds of pointer functions, we construct new transitive functions whose deterministic query complexity, randomized query complexity, zero-error randomized query complexity, quantum query complexity, degree, and approximate degree are similar to that of the original pointer functions. Thus we demonstrate that even for transitive functions similar separations between pairs of combinatorial measures can be achieved.
Our constructions of transitive functions depend crucially on construction of particular classes of transitive groups, whose actions, though involved, helps to preserve certain structural features of the input strings. The transitive groups we construct may be of independent interest in other areas of mathematics and theoretical computer science.
We summarize the current knowledge of relations between various combinatorial measures of transitive functions in a table similar to the table compiled by Aaronson et~al.~(STOC, 2021) for general functions.
