oresmus

This post provides a place for discussion of my paper, “The Pattern Basis Approach to Circuit Complexity”, which describes a proposal for getting around the natural proofs barrier, and some of the ideas that led to it.

Here’s the abridged abstract I gave to arXiv:

We describe and motivate a proposed new approach to lowerbounding the circuit complexity of boolean functions, based on a new formalization of “patterns” as elements of a special basis of the vector space of all truth table properties. We prove that a “pattern basis” with certain properties would lead to a useful complexity formula of a specific form, and speculate on how to find such a basis. This formula might take as long to compute on arbitrary functions as a brute-force search among circuits, thus addressing the natural proofs barrier, but has a form amenable to proving lower bounds for well-understood explicit functions.

For the full-length abstract, see the paper at http://arxiv.org/abs/1606.05331 .

The basic idea is to turn a boolean function (from $n$ bits to $m$ bits) into a “pattern matrix” of doubly-exponential size ( $2^{2^m}$ by $2^{2^n}$ ), which linearly encodes all its truth table properties, and for which matrix multiplication corresponds to function composition. The log of a submultiplicative matrix norm (or similar measure) is then subadditive (with respect to composing circuits or functions), and could in principle be a useful lower bound on circuit complexity if the right basis could be found. The matrix is large enough that the “natural proofs barrier” doesn’t rule out this approach. The paper spells out how this could work, and argues for its plausibility as an approach to the general problem of circuit complexity.

For any questions or discussion (after reading the paper), feel free to comment below.