Go to the roots of calculations! Group the operations. Classify them according to their complexities rather than their appearances! This, I believe, is the mission of future mathematicians.
- Evariste Galois
Boolean (or switching) functions map each sequence of bits to a single bit $0$ or $1$. Bit $0$ is usually interpreted as ``false'', and bit $1$ as ``true''. The simplest of such functions are the And $x\cdot y$, non-exclusive Or $x\lor y$, negation $\neg x=1-x$. The central problem of Boolean function complexity---the lower bounds problem---is:
Lower Bounds Problem: Given a boolean function, how many of these simplest operations do we need to compute the function on all input vectors?The difficulty in proving that a given boolean function has high complexity lies in the nature of our adversary: the circuit. Small circuits may work in a counterintuitive fashion, using deep, devious, and fiendishly clever ideas. How can one prove that there is no clever way to quickly compute the function? This is the main issue confronting complexity theorists. The problem lies on the border between mathematics and computer science: lower bounds are of great importance for computer science, but their proofs require techniques from combinatorics, algebra, analysis, probability theory, and other branches of mathematics.
My book "Boolean Function Complexity" is all about the lower bounds problem.