Room 327

Separations between Combinatorial Measures for Transitive Functions

Chandrima Kayal

ISI Kolkota

The role of symmetry in Boolean functions has been extensively studied in complexity theory. For example, Symmetric functions (functions that are invariant under all possible permutations on the input strings) are widely studied and well-understood classes of function. But there are a lot of functions with different types of symmetry which cannot be captured by the classes of symmetric functions. What happens for them? How different type of symmetry affects different complexity measures?

In this work, we study transitive functions in light of several combinatorial measures which is a natural generalization and a bigger class than symmetric functions. The question that we try to address in this paper is what are 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.

Based on the various kinds of pointer functions, we construct new transitive functions whose complexity measures are similar to that of the original pointer functions. We have argued the barriers of Cheat Sheet techniques and also summarized 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.

This is a joint work with Sourav Chakraborty and Manaswi Paraashar.