# Is nonuniform $\mathsf{TC^0}$ equal to the composition closure of $\mathsf{AC^0}$ and Majority?

D.A.M. Barrington, N. Immerman and H. Straubing show in their 1990 paper "On Uniformity Within $$\mathsf{NC^1}$$" that the uniform $$\mathsf{TC^0}$$ is equal to $$\mathsf{FOM}$$ ($$\mathsf{FO}$$ plus Majority quantifiers).

Is a similar result known for the nonuniform case? I.e. is it known that any $$\mathsf{TC^0}$$ function can be obtained by composing Majority and (nonuniform) $$\mathsf{AC^0}$$ functions?

It seems this should be true since $$\mathsf{AC^0}$$ is closed under restrictions of inputs (replacing an input with $$0$$ or $$1$$) and the evaluation problem for $$\mathsf{TC^0_d}$$ circuits is in (uniform) $$\mathsf{TC^0}$$.

### Clarification and Motivation:

By composing I mean the usual composition of functions, i.e. the composition of $$g(\vec{y})$$ and $$\vec{f}(\vec{x})$$ is $$h(\vec{x})=g(\vec{f}(\vec{x}))$$.

Consider the smallest set of functions containing the Majority function and $$\mathsf{AC^0}$$ which is closed under composition. In the uniform case this gives uniform $$\mathsf{TC^0}$$.

If I am not making a mistake, the evaluation problem for $$\mathsf{TC^0_d}$$ circuits ($$\mathsf{TC^0_d}$$-Eval) is in uniform $$\mathsf{TC^0}$$ and therefore in this set by [BIS88]. I think this is enough since we can get any function in $$C\in\mathsf{TC^0_d}$$ by composing a simple $$\mathsf{AC^0}$$ function with $$\mathsf{TC^0_d}$$-Eval: given input $$\vec{x}$$ the $$\mathsf{AC^0}$$ function computes $$(\vec{x}, \langle C \rangle)$$, where $$\langle C \rangle$$ is a fixed string encoding the circuit $$C$$. This $$\mathsf{AC^0}$$ function composed with $$\mathsf{TC^0}$$-Eval computes the same function that $$C$$ does.

But this argument uses [BIS88] and I feel that the nonuniform case should have an easier well-known direct proof.

The reason this is interesting is that $$\mathsf{TC^0}$$ is not known to have any complete problem w.r.t. many-one $$\mathsf{AC^0}$$ reductions. But for many purposes this characterization of $$\mathsf{TC^0}$$ as the composition closure of Majority+$$\mathsf{AC^0}$$ (if correct) seems to be as good as having a complete problem w.r.t. many-one $$\mathsf{AC^0}$$ reductions.

• Can you explain what do you mean by "composing Majority and non-uniform $\mathsf{AC^0}$ functions"? It is well-known that threshold gates can be simulated by majority gates, but I'm not sure that that's enough for your purposes. – Yuval Filmus Jul 7 '13 at 4:31
• @Yuval, I added a clarification. – Kaveh Jul 7 '13 at 8:15
• If I understand your definition correctly, all circuit families obtained by composing majority and $\mathsf{AC^0}$ circuit families have a constant number of majority gates. This is probably not as powerful as $\mathsf{TC^0}$ circuit families, which can have polynomially many majority gates. Even worse, all majority gates have constant fan-in, and so can be eliminated. So you actually get $\mathsf{AC^0}$. – Yuval Filmus Jul 7 '13 at 8:19
• In the uniform setting, if you have nested majority quantifiers (even nested within another quantifier) then when you convert the formula to a circuit you get a super-constant number of majority gates. It's not clear how to express this in the non-uniform setting, other than just having polysize bounded-depth circuits with majority gates, which we already know are the same class as $\mathsf{TC^0}$. – Yuval Filmus Jul 7 '13 at 8:33
• Can you formally state the new version of the question? (Including your earlier comment on circuits with multiple inputs.) – Yuval Filmus Jul 7 '13 at 14:59