There still remains much to be understood about the complexity of Boolean functions and the many complexity measures that are used
to study various models of computation such as certificate complexity, degree, sensitivity, block sensitivity, their variants, to name a few. Some of the questions we ask about these measures are: How are these measures related, and what polynomial upper bounds can be given on these measures in terms of the smaller measures such as sensitivity? What separations can be shown between the measures? Do they have a natural computational interpretation? What properties do they have, for example, do they behave well under composition? How do they behave for symmetric functions?
Since the sensitivity conjecture was resolved [1]}, one important new goal is to determine precisely how the larger measures, such as query complexity and certificate complexity, are bounded above by smaller measures such as sensitivity. The best known upper bound on deterministic query complexity is \(f) \le O(\mathsf {s}(f)^6)\) , [2]}, [3]}, [1]}
