Circuit lower bounds over arbitrary sets of gates 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&ge;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}n&rarr;{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!
(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.