Circuit lower bounds over arbitrary sets of gates

Question

In the 1980s, Razborov famously showed that there are explicit monotone Boolean functions (such as the CLIQUE function) that require exponentially many AND and OR gates to compute. However, the basis {AND,OR} over the Boolean domain {0,1} is just one example of an interesting gate set that falls short of being universal. This leads to my question:

Is there any other set of gates, interestingly different from the monotone gates, for which exponential lower bounds on circuit size are known (with no depth or other restrictions on the circuit)? If not, is there any other set of gates that's a plausible candidate for such lower bounds---bounds that wouldn't necessarily require breaking through the Natural Proofs barrier, as Razborov's monotone-circuits result didn't?

If such a gate set exists, then certainly it will be over a k-ary alphabet for k≥3. The reason is that, over a binary alphabet, the

(1) monotone gates ({AND, OR}),

(2) linear gates ({NOT, XOR}), and

(3) universal gates ({AND, OR, NOT})

basically exhaust the interesting possibilities, as follows from Post's classification theorem. (Note that I assume that constants---0 and 1 in the binary case---are always available for free.) With the linear gates, every Boolean function f:{0,1}ⁿ→{0,1} that's computable at all is computable by a linear-size circuit; with a universal set, of course we're up against Natural Proofs and the other terrifying barriers.

On the other hand, if we consider gate sets over a 3- or 4-symbol alphabet (for example), then a wider set of possibilities opens up---and at least to my knowledge, those possibilities have never been fully mapped out from the standpoint of complexity theory (please correct me if I'm wrong). I know that the possible gate sets are studied extensively under the name of "clones" in universal algebra; I wish I were more conversant with that literature so that I knew what if anything the results from that area mean for circuit complexity.

In any case, it doesn't seem out of the question that there are other dramatic circuit lower bounds ripe for the proving, if we simply expand the class of gate sets over finite alphabets that we're willing to consider. If I'm wrong, please tell me why!

Answer 1

(Moved from comments as Suresh suggested. Note some errors in the comment are fixed here.)

Thanks to Scott for a great question.

Scott seems to suggest that the reason for the difficulty of lower bounds may be the restricted language of operations in the Boolean case. Shannon's counting argument that shows most circuits must be large relies on the gap between countable expressive power and uncountably many circuits. This gap seems to go away when the alphabet has at least 3 symbols.

For alphabet size 2 (the Boolean case), the lattice of clones is countably infinite, and is called Post's lattice.

Post's lattice also makes clear why there are only a few interesting bases of operations for the Boolean case.

For alphabet size 3 or greater the lattice of clones is uncountable. Further, the lattice does not satisfy any nontrivial lattice identity, so it seems impossible to provide a complete description of the lattice. For alphabet size 4 or greater the lattice of clones actually contains every finite lattice as a sublattice. So there are infinitely many possibly interesting bases of operations to consider when the alphabet has 3 or more symbols.

• Bulatov, Andrei A., Conditions satisfied by clone lattices, Algebra Universalis 46 237–241, 2001. doi: 10.1007/PL00000340

Scott asked further: does the lattice of clones remain uncountable if we assume constants are available for free?

The answer is that it does, see for instance

• Gradimir Vojvodić, Jovanka Pantović, and Ratko Tošić, The number of clones containing an unary function, NSJOM 27 83–87, 1997. (PDF)
• J. Pantović, R. Tošić, and G. Vojvodić, The cardinality of functionally complete algebras on a three element set, Algebra Universalis 38 136–140, 1997. doi: 10.1007/s000120050042

although apparently this was published earlier:

• Ágoston, I., Demetrovics, J., and Hannák, L. On the number of clones containing all constants, Coll. Math. Soc. János Bolyai 43 21–25, 1983.

A nice specific statement is from:

• A. Bulatov, A. Krokhin, K. Safin, and E. Sukhanov, On the structure of clone lattices, In: "General Algebra and Discrete Mathematics", editors: K. Denecke and O. Lueders, 27–34. Heldermann Verlag, Berlin, 1995. (PS)

Corollary 3 (attributed to Ágoston et al. as above): Let $k \ge 3$. Then the number of clones in $\mathcal{L}_k$ containing all constants is $2^{\aleph_0}$.

To wrap up, I am not aware of any work on using non-Boolean clones for circuit lower bounds. This seems worth investigating in more depth. Given the relatively little that is known about the lattice of clones, there may be interesting bases of operations waiting to be discovered.

More links between clone theory and computer science would probably also be of great interest to mathematicians working in universal algebra. A previous example of this kind of interaction came about when Peter Jeavons showed that algebras could be associated with constraint languages, in a way that allows tractability results to be translated into properties of the algebra. Andrei Bulatov used this to prove the dichotomy for CSPs with domain size 3. Going the other way, there has been a revival in interest in tame congruence theory as a result of the computer science application. I wonder what would follow from a link between clone theory and non-Boolean circuit complexity.

Answer 2

This is moved from comments, as Suresh suggested.

If you consider functions $f:{0,1}^n \rightarrow {0,1}^n$, then the situation is more involved for linear gates, because the counting argument shows that there are functions that require $\Omega(\frac{n^2}{\log(n)})$ gates to be computed, though there are no explicit examples of a function that requires circuits of superlinear size.

Edit. Also it can be shown using counting argument that most of the functions have complexity larger than $\frac{n^2}{\log(n) * c}$ for some constant $c$, so if you just select a function randomly you will get a complex function with high probability.

On the other hand, as Scott Aaronson points in the comments, it's not hard to come up with candidates for linear transformations that should require $\Omega(n log n)$ XOR gates (the Fourier Transform, the "Sierpinski Gasket" matrix...), and Bram Cohen proposed an example function that should require $\Omega(n^{3/2})$ XOR gates.

Edit 2. The main obstacle is that we don't have any methods for proving non-linear lower bounds even for linear gates, as far as I know (for linear lower bounds one can use gate elimination, that is very unlikely to give non-linear bounds). Though it looks like some methods from linear algebra really must be helpful. So coming up with candidates is nice, but some new methods are needed anyway.

Answer 3

1. Actually, there were attempts to prove lower bounds for circuits working over larger domains than $\{0,1\}$. Say, Tkachov [Vestnik of Moscow University, Nr. 1, 1977, in Russian] considered circuits working with input vectors $a$ in $Z_3^n=\{0,1,2\}^n$. As gates he allowed $\min(x,y)$ and $xy\mod{2}$. He considered the following function: $f(a)=0$ if $a$ contains a $0$ or the number of $2$'s in $a$ is at least the number of $1$'s. He shows that any circuit (over that MIN/XOR) basis requires about $2^n/\sqrt{n}$ gates to compute $f$. But that was! I am not aware of any further results in a similar favor (going to larger, but still finite, domains)except, of course, the stuff of arithmetic circuits. But only for circuits - for branching program going to larger domains makes the task of lower bounds somewhat easier.

2. On circuits with XOR gates. Here even the case of depth $2$ is widely open. The highest lower bounds for explicit linear transformations $y=Ax$ over $GF(2)$ have the form $n\log^{3/2}n$. To prove a bound like $n^{1+c}$ for a constant $c>0$, even in depth $2$ and even if only XOR gates are allowed, is a challenge.