There are two families of approaches to proving circuit lower bounds: exploiting properties of functions computed by small circuits, and building hard functions by “brute force.” The first approach leads to “natural proofs” in the sense of Razborov and Rudich, which is a problem because natural proofs are unlikely to give lower bounds for circuit classes such as (constant-depth circuits with threshold gates), and maybe even (constant-depth circuits with AND, OR, NOT, and MOD gates). The second approach creates proofs that “algebraize,” in the sense of Aaronson and Wigderson, and algebaizing proofs construct hard functions of very high uniform complexity; it is not even possible to use an algebraizing proof to show that the huge complexity class contains problems of super-polynomial circuit complexity.

The circuit lower bound of Williams avoids both barriers, by exploiting (among other things) a property of circuits (the existence of slightly faster-than-brute-force satisfiability algorithms) that is not a “natural” property, neither is an “algebraizing” property.

This post, written by a non-expert for non-experts (but experts are welcome to read it and to point out any mistakes), describes some of the context.