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.