In a recent result, Knop, Lovett, McGuire and Yuan (STOC 2021) proved the log-rank conjecture for communication complexity, up to \log n factor, for any Boolean function composed with AND function as the inner gadget. One of the main tools in this result was the relationship between monotone analogues of ... more >>>

For any Boolean functions f and g, the question whether \text{R}(f\circ g) = \tilde{\Theta}(\text{R}(f) \cdot \text{R}(g)), is known as the composition question for the randomized query complexity. Similarly, the composition question for the approximate degree asks whether \widetilde{\text{deg}}(f\circ g) = \tilde{\Theta}(\widetilde{\text{deg}}(f)\cdot\widetilde{\text{deg}}(g)). These questions are two of the most important and ... more >>>

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 >>>