Depth-two TC^0 (by Ryan O'Donnell)

For today's post, some hard-core, old-school, low-level structural complexity, coupled with a woe-is-me tale.

A couple of summers ago a friend and I decided to gird ourselves and take a stab at proving a circuit lower bound. To dial down the quixotism as much as possible, we picked the absolutely least ambitious circuit class we could think of to work on: depth-two TC^0.

I should clarify what I mean here: TC^0 is usually defined as being the class of poly-size constant-depth circuits with constants, negations, and unlimited fan-in majority gates. But here when I say "depth-two TC^0", I want to allow arbitrary threshold gates instead of just majority gates. By a threshold gate I mean a function, determined by integer constants a_1, ..., a_m and c, which on input (x_1, ..., x_m) outputs 1 when a_1 x_1 + a_2 x_2 + ... + a_m x_m > c, and 0 otherwise. Siu and Bruck in 1991 showed that an arbitrary threshold gate can be simulated by a poly-size depth-three majority circuit (this was improved to depth two in a very nice paper by Goldmann, H�stad and Razborov, and the construction simplified a few times, most elegantly by Hofmeister). So if you only care about constant depth and poly size, it doesn't matter what sort of threshold gates you allow for TC^0. But we were interested in depth-two arbitrary thresholds of arbitrary thresholds.

[Side note: One might try to argue that small-depth threshold circuits are interesting from a physical point of view, due to resemblance to neural nets. Since allowing arbitrary threshold gates seems a bit dubious, physically -- Circuits Of The Mind people, what do you think? -- I won't try to argue this. I'll merely say that the class of thresholds of polynomially many thresholds is a pretty natural "circuit class".]

Now when people like to exclaim over how bad we are at circuit lower bounds, the usual trope is that "As far as we know, NP might be contained in AC^0 with mod 6 gates!" (Or do they say EXP?) But you can take it one step further: correct me if I'm wrong, readers, but I think that as far as we know NP might be in depth-two TC^0. To think: solving the travelling salesperson problem, say, with a threshold of polynomially many thresholds of inputs.

Also as far as I know, there would be no amazing consequence of a lower bound against depth-two TC^0; this is one reason why friend and I tried to tackle it. The other reason was that it seems like we already practically have it:

• If you restrict the top threshold gate to be a majority, then a neat 1993 result of Hajnal, Maass, Pudl�k, Szegedy and Tur�n shows that Inner Product Mod 2 is not in the class. The proof uses the classical randomized communication complexity lower bound for IP2 by Chor and Goldreich.
• If you instead restrict the lower level thresholds to be majorities (or any gates with logarithmic deterministic communication complexity), a superb result of J�rgen Forster -- published originally in NeuroCOLT (!) 2000 -- again excludes IP2 from the class. Forster showed this by proving IP2 has linear randomized communication complexity even when the players need only succeed with any probability exceeding 50%.

So. IP2 cannot be expressed as a majority of poly many thresholds nor as a threshold of poly many majorities. You'd think it would only be a small step from there to show that it cannot be expressed as a threshold of poly many thresholds...

Long story short, after a summer of banging our heads over it, we came up with absolutely nothing to say about whether or not IP2 is in depth-two TC^0.

SAT, computable as a threshold of thresholds...? Man.