# The Pattern Basis Approach to Circuit Complexity

Source: [The Pattern Basis Approach to Circuit Complexity](<https://www.sota2.com/research/paper/68fa62841e209131ce9f9c98>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-25T20:21:33.904Z

Authors: Bruce K. Smith

Published: 2016-06-16T19:43:28.000Z

## Abstract

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.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/1606.05331>)

[PDF](<https://arxiv.org/pdf/1606.05331.pdf>)
