And a possible approach to avoid this obstacle

Valentine Kabanets is a famous complexity theorist from Simon Fraser University. He has been at the forefront of lower bounds for over two decades.

Today we draw attention to this work and raise an idea about trying to unravel what makes circuit lower bounds hard.

He is the common author on two new papers on the Minimum Circuit Size Problem (MCSP), which belongs to ${\mathsf{NP}}$ but is not known to be complete or in ${\mathsf{P}}$. We posted on MCSP four years ago and mentioned his 1999 paper with Jin-Yi Cai, which gives evidence for MCSP truly being neither complete nor in ${\mathsf{P}}$. This “intermediate” status and the problem’s simplicity have raised hopes that direct attacks might succeed. The new papers prove direct lower bounds against some restricted circuit/formula models, including constant-depth circuits with mod-${p}$ gates for ${p}$ prime. But they stop short of mod-${m}$ for ${m}$ composite and other barrier cases.

He has a nifty research statement on his home page. It shows how derandomization, pseudorandomness, circuit complexity, and crypto combine into his two current projects. In a clickable tab for the third heading, he puts the meta-issue in pithy terms:

Why is proving circuit lower bounds so difficult?

His first answer tab speaks a connection we have also often emphasized here:

Traditionally, designing efficient algorithms is the subject of the theory of algorithms, while lower bounds are sought in complexity theory. It turns out, however, that there is a deep connection between the two directions: better algorithms (for a certain class of problems) also yield strong lower bounds (for related problems), and vice versa: strong lower bounds translate into more efficient algorithms.

Of course we agree, and we love connections shown in the new papers to problems such as distinguishing a very slightly biased coin from a true one. But we will try to supplement the algorithmic view of circuit lower bounds with a direct look at the underlying logic.

## Logical Structure of Lower Bounds

Okay we all know that circuit lower bounds are hard. For all Kabanets’ success and beautiful work—he like the rest of the complexity field—are unable to prove what we believe is true. They cannot in the full circuit model prove anything close to what is believed to be true for at least a half a century: There are explicit Boolean functions that cannot be computed by any linear size circuit.

We feel that the logical structure of lower bounds statements gives insight into their difficulty. Perhaps this is almost a tautology. Of course the logical structure of any mathematical statement helps us understand its inherent difficulty. But we believe more: That this structure can reveal quite a bit about lower bounds. Let’s take a look at lower bounds and see if this belief holds up.

In particular let’s compare the two main approaches to proving lower bounds: non-uniform and uniform. Our claim is that they have different logical structure, and that this difference explains why there is such a gap between the two. While lower bounds—non-uniform or uniform—are hard, uniform ones are at least possible now. Non-uniform lower bounds are really very difficult.

Here is one example. To prove an explicit size lower bound for Boolean circuits—we’ll be content with just a linear one—we must give a particular family of Boolean functions ${f_{n}(x)}$ (each of ${n}$ inputs) so that:

1. Given ${n}$ and ${x}$ we can evaluate ${f_{n}(x)}$ in polynomial time;

2. There is no Boolean circuit of size ${\alpha n}$ that correctly computes ${f_{n}(x)}$ on all ${x}$ of length ${n}$.

Here ${\alpha}$ is a constant and ${n}$ is assumed to be large enough. The terrific paper of Kazuo Iwama, Oded Lachish, Hiroki Morizumi, and Ran Raz gives explicit Boolean functions whose size for circuits with the usual not and binary and and or operators exceeds ${5n-o(n)}$.

## An Approach

Let’s look at the above example more carefully. Suppose that in place of a single Boolean function on ${n}$ inputs we have a list of them:

$\displaystyle f_{n,1}(x),\dots,f_{n,m}(x).$

Can we prove the following?

$\displaystyle \exists n_{0}\ \forall n > n_{0} \ \exists f_{n,k} \ \forall C \in \mathsf{SIZE}(\alpha n) \ \neg\mathsf{compute}(C,f_{n,k}).$

The first thing to note is the effect of letting the number ${\bf m}$ of functions vary:

${\bullet }$ If ${\bf m = 1}$, this just becomes our original explicit circuit lower bound problem.

${\bullet }$ If ${\bf m}$ is a huge value, however, this becomes the exponential lower bound shown by Claude Shannon—a known quantity.

In our terms, the latter takes ${\bf m}$ equal to ${2^{2^{n}}}$, so that given ${n}$ our function list is just the list of all Boolean functions. If all we care about is an ${\alpha n}$ lower bound, then the high end of the range can be something like ${m = 2^{2\alpha n\log(n)} = n^{2\alpha n}}$. So at the high end we have a simple counting argument for the proof but have traded away explicitness. The question will be about the tradeoffs for ${\bf m}$ in-between the extremes.

## An Analogy

The above idea that we can model the lower bound methods by controlling the length of the list of the functions is the key to our approach. Perhaps it may help to note an analogy to other famous hard problems of constructing explicit objects. In particular, let’s look at constructing transcendental numbers. Recall these are real numbers that are not algebraic: they are not roots of polynomials with integer coefficients. They include ${\pi = 3.14159\dots}$ and ${e = 2.71828\dots}$

${\bullet }$ The Liouville numbers of Joseph Liouville.

$\displaystyle x = \sum_{k=1}^\infty \frac{a_k}{b^{k!}}.$

These are explicit numbers that were proved by him in 1844 to be transcendental. In terms of our model ${\bf m=1}$.

${\bullet }$ The great ${\pi}$ and ${e}$ puzzle. This is the observation that of ${\pi + e}$ or ${\pi - e}$, at least one is a transcendental number. In our terms this gives ${\bf m=2}$.

${\bullet }$ The famous theorem of Georg Cantor—read as proving the existence of transcendental numbers since algebraic ones are countable.

Here the high end of the range is as extreme as can be. Cantor’s `list’ of numbers is uncountable—in our model, ${\bf m}$ is the cardinality of the real numbers. Note, the fact that his ${\bf m}$ is huge, really huge, may explain why some at the time were unimpressed by this result. They wanted the ‘list’ to be small, actually they wanted ${\bf m=1}$. See this for a discussion of the history of these ideas.

${\bullet}$ The theorem by Waim Zudilin, in a 2001 paper, that at least one of the numbers ${\zeta(5), \zeta(7), \zeta(9), \zeta(11)}$ must be irrational. It is for “irrational” not “transcendental,” but exemplified ${\bf m = 4}$ in a highly nontrivial manner. The technical point that makes this work is interactions among these numbers that cannot be captured just by considering any one of them separately. This has ${\bf m = 4}$.

## Joining Functions

The issue is this: Suppose that we have a list of several boolean functions ${f_{1}(x),\dots,f_{m}(x)}$. Then we can join them together to form one function ${g(x,y)}$ so that

$\displaystyle g(x,1) = f_{1}(x), \cdots, g(x,m) = f_{m}(x).$

Clearly the function ${g(x,y)}$ is easy implies that all of the ${f_{y}(x)}$ are easy. This join trick shows that we can encode several boolean functions into one function. Note, we can even make ${y}$ have only order ${\log(n)}$ where ${x}$ has ${n}$ bits.

Thus we can join any collection of functions to make a “universal” one that is at least as hard as the worst of the single functions. More precisely,

$\displaystyle \mathsf{complexity}(g) \ge \mathsf{complexity}(f_{y}) \text{ for } y=1,\dots,m.$

Here ${\mathsf{complexity}(h)}$ is the circuit complexity of the boolean function ${h}$.

If ${m}$ is bigger than ${2^{O(n)}}$, that is if ${m = 2^{\omega(n)}}$, then the joined function has more than linearly many variables. Can we possibly establish nontrivial interactions among so many functions, say ${{\bf m} = n^{2n}}$?

One can also try to get this effect with fewer or no additional variables by taking the XOR of some subset of functions in the list. If this is done randomly for each input length ${n}$ then one can expect hard functions to show up for many ${n}$. If this process can then be de-randomized, then this may yield an explicit hard function. We wonder how this idea might meld with Andy Yao’s famous XOR Lemma and conditions to de-randomize it.

## Joining Numbers

Ken and I thought about the above simple fact about joins, which seems special to functions. Joining by interleaving the decimal expansions is not an arithmetic operation. However, it appears that there may be a similar result possible for transcendental numbers.

Lemma 1 Suppose that ${\alpha}$ and ${\beta}$ are real numbers. Then

$\displaystyle \alpha + i\beta$

is a transcendental complex number if at least one of ${\alpha}$ or ${\beta}$ are transcendental.

Proof: Let ${\gamma = \alpha + i\beta}$ be an algebraic number. Thus there must be a polynomial ${q(x)}$ with integer coefficients so that

$\displaystyle q(\gamma) = q(\alpha + i\beta) = 0.$

Then it follows by complex conjugation that

$\displaystyle q(\alpha - i\beta) = 0.$

Therefore ${\alpha + i\beta}$ and ${\alpha -i\beta}$ are both algebraic; thus, so is their sum which is ${2\alpha}$. Thus ${\alpha}$ is algebraic. It follows that ${\beta}$ is also algebraic. This shows that ${\gamma}$ is transcendental. $\Box$

A question: Can we show that we can do a “join” operation for three or more numbers? That is given numbers ${x_{1},\dots,x_{m}}$ can we construct a number ${y}$ that is transcendental if and only if at least one of ${x_{i}}$ is transcendental?

## Open Problems

Is the ${\bf m}$ model useful? Is it possible for it to succeed where a direct explicit argument (${{\bf m} = 1}$) does not? Does it need ${{\bf m} \gg 2^n}$ to rise above technical dependence on the ${\bf m = 1}$ case via the join construction?

 Maybe the barriers just need 3-Dan martial-arts treatment. Source—our congrats.
One Comment leave one →
April 22, 2019 11:43 pm

It is interesting that even a very small amount of nonuniformity can be very powerful. An example: the beautiful result by Lance Fortnow and Rahul Santhanam on hierarchy theorems for probabilistic polynomial time:

In analogy with the deterministic and nondeterministic models, one would expect that probabilistic Turing machines would have “hierarchy theorems”: more time would yield more languages. One would expect a theorem of the form

If a > b there is a language in BPTIME[n^a] that is not in BPTIME[n^b]

(where BPTIME denotes bounded error probabilistic Turing machine classes)

Perhaps surprisingly, no such result is known.

However, the theorem can be proven if the machines are given a single bit of advice.