License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2022.36
URN: urn:nbn:de:0030-drops-163779
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16377/
Chakraborty, Sourav ;
Kayal, Chandrima ;
Paraashar, Manaswi
Separations Between Combinatorial Measures for Transitive Functions
Abstract
The role of symmetry in Boolean functions f:{0, 1}ⁿ → {0, 1} has been extensively studied in complexity theory. For example, symmetric functions, that is, functions that are invariant under the action of ?_n, is an important class of functions in the study of Boolean functions. A function f:{0, 1}ⁿ → {0, 1} is called transitive (or weakly-symmetric) if there exists a transitive group ? of ?_n such that f is invariant under the action of ?. In other words, the value of the function remains unchanged even after the input bits of f are moved around according to some permutation σ ∈ ?. Understanding various complexity measures of transitive functions has been a rich area of research for the past few decades.
This work studies transitive functions in light of several combinatorial measures. 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 many years. Aaronson et al. (STOC, 2021) have nicely compiled the current best-known results for general Boolean functions. But before this paper, no such systematic study had been done on the case of transitive functions.
Separations between a pair of combinatorial measures are 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 "pointer functions". Ambainis et al. (JACM, 2017) constructed several functions, which are modifications of the pointer function in Göös et al. (SICOMP, 2018 / FOCS, 2015), to demonstrate the 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 (Eg: Mukhopadhyay et al. (FSTTCS, 2015), Ben-David et al. (ITCS, 2017), Göö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, which we use to demonstrate similar separations between various pairs of combinatorial measures as demonstrated by the original pointer functions. Our construction of transitive functions depends crucially on the construction of particular classes of transitive groups whose actions, though involved, help 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.
BibTeX - Entry
@InProceedings{chakraborty_et_al:LIPIcs.ICALP.2022.36,
author = {Chakraborty, Sourav and Kayal, Chandrima and Paraashar, Manaswi},
title = {{Separations Between Combinatorial Measures for Transitive Functions}},
booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
pages = {36:1--36:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-235-8},
ISSN = {1868-8969},
year = {2022},
volume = {229},
editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16377},
URN = {urn:nbn:de:0030-drops-163779},
doi = {10.4230/LIPIcs.ICALP.2022.36},
annote = {Keywords: Transitive functions, Combinatorial complexity of Boolean functions}
}
|
Keywords: |
|
Transitive functions, Combinatorial complexity of Boolean functions |
|
Collection: |
|
49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
28.06.2022 |
