Boolean functions #

A Boolean function is a function $$f:{0,1}^n \to {0,1}$$ (this is an $$n$$ -ary Boolean function). Every such function can be expressed as a propositional formula in $$n$$ variables, and two such formulas are equivalent if and only if they express the same Boolean function.

Complexity measures #

The complexity of Boolean functions can be measured in a number of ways. The most intuitive is sensitivity: given an input $$x=x_1,\ldots,x_n$$ to $$f$$, the sensitivity of $$x$$, or $$s_x(f)$$, is the number of bits of $$x$$ that you can flip to change the value of $$f$$. The sensitivity of $$f$$ is $$s(f)$$ = $$\max_x s_x(f)$$. It can be viewed as a discrete analog to smoothness of continuous functions (low-sensitivity = smooth).

Another way to measure it is block sensitivity: the block-sensitivity of an input $$x$$, or $$bs_x(f)$$, is the maximum number of disjoint sets of bits of $$x$$ (called “blocks”) that you can flip to change the value of $$f$$, and the block sensitivity of $$f$$ is $$bs(f) = \max_x bs_x(f)$$.

There are many other interesting measures of complexity:

• the decision-tree complexity of f
• the certificate complexity of f
• the randomized query complexity of f
• the quantum query complexity of f
• the degree of f as a real polynomial

and these have all over the years been shown to be polynomially equivalent to block sensitivity.

The sensitivity conjecture #

Proved in 2021, the sensitivity conjecture proposes that sensitivity is polynomially equivalent to block sensitivity. The proof by Hao Huang is a simple and elegant combinatorial argument that proves a related conjecture.

• Scott Aaronson describing the sensitivity conjecture.
• A good survey of the field.
• Scott Aaronson discussion the proof of the conjecture, now a theorem.
• The paper by Huang proving the conjecture.