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.

  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Jul 7 '13 at 4:31
  • $\begingroup$ @Yuval, I added a clarification. $\endgroup$ – Kaveh Jul 7 '13 at 8:15
  • $\begingroup$ 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}$. $\endgroup$ – Yuval Filmus Jul 7 '13 at 8:19
  • 1
    $\begingroup$ 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}$. $\endgroup$ – Yuval Filmus Jul 7 '13 at 8:33
  • 1
    $\begingroup$ Can you formally state the new version of the question? (Including your earlier comment on circuits with multiple inputs.) $\endgroup$ – Yuval Filmus Jul 7 '13 at 14:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.