Circuit lower bounds over arbitrary sets of gates
(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.