First of all this has no relevance if you're not a complexity theorist. No "practical" impact, not even remotely. A real downer, I know, but I thought that had

First of all this has no relevance if you're not a complexity theorist. No "practical" impact, not even remotely. A real downer, I know, but I thought that had to be stated up front. The question is why are complexity theorists excited about this. When a problem is too hard to solve, you look for easier versions to solve first. Here the easier version is to prove that the complexity class NEXP (which is intuitively vastly more powerful than even NP) is bigger than a certain class of circuits of constant depth (circuits with polynomial depth are known to be roughly equivalent to P, and constant-depth circuits are intuitively vastly less powerful). ETA: the circuits considered here are "non-uniform," which makes the previous paragraph slightly inaccurate. Nevertheless, the point stands that the goal here is to separate two complexity classes that are intuitively very different in their power. Circuit lower bounds -- proving that a restricted class of circuits, as above, is in fact limited in its computational power -- have been notorious for their hardness. The reason one would want to prove this kind of statement is not because these circuits are objects of practical interest, but because of the proof techniques that would come out as a side-effect, in the hope that these techniques would be applicable in solving other, harder problems. So that's the gist of it: the 3 reasons this theorem is exciting are: proof techniques, proof techniques and proof techniques. Now some of the statements from the post should hopefully make a lot more sense: This approach converts weak algorithms for solving circuit satisfiability questions into circuit lower bounds. Ryan's proof doesn't use deep mathematical techniques but rather puts together a series of known tools in amazingly clever ways. Ryan breaks through the natural proofs barrier in an interesting way. ... he avoids the issue by using diagonalization and so his proof does not fulfill the constructivity requirement of natural proofs. What's going on here is that there are often meta-proofs in complexity theory showing that a certain approach to proofs won't work. The "natural proofs barrier" being referred to is (apparently) a limit on what you can achieve by a certain type of "natural" construction that is explained in this post by Lipton: http://rjlipton.wordpress.com/2009/03/25/whos-afraid-of-natural-proofs/ http://rjlipton.wordpress.com/2009/03/25/whos-afraid-of-natu... The one thing I haven't touched upon is why there are "mod m" gates in the circuit class under consideration. That is also (surprise, surprise) related to proof techniques. As Luca Trevisan explains, using mod m gates instead of binary gates or mod-prime gates disables two well-known classes of proofs ("fixing variables to random values" and "low-degree polynomial approximation"), ensuring that some heavy artillery will need to be developed in order to prove statements about them. http://lucatrevisan.wordpress.com/2010/11/08/a-circuit-lower-bound-breakthrough/ http://lucatrevisan.wordpress.com/2010/11/08/a-circuit-lower...