The Pattern Basis Approach to Circuit Complexity

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} by2^{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.

Sponsored Post Learn from the experts: Create a successful blog with our brand new courseThe WordPress.com Blog

Are you new to blogging, and do you want step-by-step guidance on how to publish and grow your blog? Learn more about our new Blogging for Beginners course and get 50% off through December 10th.

WordPress.com is excited to announce our newest offering: a course just for beginning bloggers where you’ll learn everything you need to know about blogging from the most trusted experts in the industry. We have helped millions of blogs get up and running, we know what works, and we want you to to know everything we know. This course provides all the fundamental skills and inspiration you need to get your blog started, an interactive community forum, and content updated annually.