<p>D.A.M. Barrington, N. Immerman and H. Straubing show in their 1990 paper
&quot;<a href="http://www.cs.umass.edu/%7Eimmerman/pub/bis.pdf" rel="nofollow noreferrer">On Uniformity Within <span class="math-container">$\mathsf{NC^1}$</span></a>&quot; that
the uniform <span class="math-container">$\mathsf{TC^0}$</span> is equal to <span class="math-container">$\mathsf{FOM}$</span>
(<a href="https://en.wikipedia.org/wiki/FO_%28complexity%29" rel="nofollow noreferrer"><span class="math-container">$\mathsf{FO}$</span></a> plus Majority quantifiers).</p>
<blockquote>
<p>Is a similar result known for the nonuniform case?
I.e. is it known that any <span class="math-container">$\mathsf{TC^0}$</span> function can be obtained by composing Majority and (nonuniform) <span class="math-container">$\mathsf{AC^0}$</span> functions?</p>
</blockquote>
<p>It seems this should be true since <span class="math-container">$\mathsf{AC^0}$</span> is closed under restrictions of inputs (replacing an input with <span class="math-container">$0$</span> or <span class="math-container">$1$</span>) and the evaluation problem for <span class="math-container">$\mathsf{TC^0_d}$</span> circuits is in (uniform) <span class="math-container">$\mathsf{TC^0}$</span>.</p>
<hr />
<h3>Clarification and Motivation:</h3>
<p>By composing I mean the usual composition of functions,
i.e. the composition of <span class="math-container">$g(\vec{y})$</span> and <span class="math-container">$\vec{f}(\vec{x})$</span> is
<span class="math-container">$h(\vec{x})=g(\vec{f}(\vec{x}))$</span>.</p>
<p>Consider the smallest set of functions containing the Majority function and <span class="math-container">$\mathsf{AC^0}$</span> which is closed under composition.
In the uniform case this gives uniform <span class="math-container">$\mathsf{TC^0}$</span>.</p>
<p>If I am not making a mistake,
the evaluation problem for <span class="math-container">$\mathsf{TC^0_d}$</span> circuits (<span class="math-container">$\mathsf{TC^0_d}$</span>-Eval) is in uniform <span class="math-container">$\mathsf{TC^0}$</span> and
therefore in this set by [BIS88].
I think this is enough since
we can get any function in <span class="math-container">$C\in\mathsf{TC^0_d}$</span>
by composing a simple <span class="math-container">$\mathsf{AC^0}$</span> function with <span class="math-container">$\mathsf{TC^0_d}$</span>-Eval:
given input <span class="math-container">$\vec{x}$</span> the <span class="math-container">$\mathsf{AC^0}$</span> function computes
<span class="math-container">$(\vec{x}, \langle C \rangle)$</span>,
where <span class="math-container">$\langle C \rangle$</span> is a fixed string encoding the circuit <span class="math-container">$C$</span>.
This <span class="math-container">$\mathsf{AC^0}$</span> function composed with <span class="math-container">$\mathsf{TC^0}$</span>-Eval
computes the same function that <span class="math-container">$C$</span> does.</p>
<p>But this argument uses [BIS88] and
I feel that the nonuniform case should have an easier well-known direct proof.</p>
<p>The reason this is interesting is that <span class="math-container">$\mathsf{TC^0}$</span> is not known
to have any complete problem w.r.t. many-one <span class="math-container">$\mathsf{AC^0}$</span> reductions.
But for many purposes this characterization of <span class="math-container">$\mathsf{TC^0}$</span>
as the composition closure of Majority+<span class="math-container">$\mathsf{AC^0}$</span> (if correct)
seems to be as good as
having a complete problem w.r.t. many-one <span class="math-container">$\mathsf{AC^0}$</span> reductions.</p>

CC BY-SA 3.0
2013-07-07T04:31:20.163Z
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
CC BY-SA 3.0
2013-07-07T08:15:04.603Z
@Yuval, I added a clarification.
Kaveh
CC BY-SA 3.0
2013-07-07T08:19:17.413Z
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
CC BY-SA 3.0
2013-07-07T08:22:57.257Z
In short, the problem is that objects in $\mathsf{AC^0}$ are sequences of functions rather than a single function, and so your definition isn't clear. It makes more sense in the uniform setting.
Yuval Filmus
CC BY-SA 3.0
2013-07-07T08:27:51.827Z
@Yuval, you are right. The issue is that people usually don't preciously define what they mean by a circuit with multiple inputs, e.g. take multiplication: given two binary numbers we want to compute their multiplication. But how do you distinguish between the bits for the first number and second number? One can say use some encoding of pairs but that is not how people really do it. If we deal with this (which is not difficult to do, we just have to consider families of circuits with multiple indices, one for the size of each input) then things would work as they do in uniform setting.
Kaveh
CC BY-SA 3.0
2013-07-07T08:30:12.680Z
@Yuval, for the other point, i.e. if what the closure characterization is correct then any $\mathsf{TC^0}$ circuit can be computed by a circuit which uses only a fixed number of Majority gates. That might look surprising, however if it is true in the uniform case (which seems to be the case) then it would not be very surprising if it is also true in the nonuniform case.
Kaveh
CC BY-SA 3.0
2013-07-07T08:33:14.713Z
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
CC BY-SA 3.0
2013-07-07T08:52:04.210Z
@Yuval, it seems that one can get around that issue by using a two dimensional version of the majority function which takes a matrix and returns the majority of each row. The reason this works is that with $\mathsf{FOM}$ we don't get arbitrary children, they are all the result of the same function and are obtained by changing a single input over a range. The argument with Majority replaced with this two-dimensional Majority seems to work (I don't see how to compute this function with a constant number of majority gates so this should address your point).
Kaveh
CC BY-SA 3.0
2013-07-07T14:59:58.027Z
Can you formally state the new version of the question? (Including your earlier comment on circuits with multiple inputs.)
Yuval Filmus
<cc.complexity-theory><reference-request><circuit-complexity><advice-and-nonuniformity><bounded-depth>
Is nonuniform $\mathsf{TC^0}$ equal to the composition closure of $\mathsf{AC^0}$ and Majority?
Kaveh
# Is nonuniform $\mathsf{TC^0}$ equal to the composition closure of $\mathsf{AC^0}$ and Majority?

(Asked by: username_0 on 2013-07-06)

D.A.M. Barrington, N. Immerman and H. Straubing show in their 1990 paper
"[On Uniformity Within $\mathsf{NC^1}$](http://www.cs.umass.edu/%7Eimmerman/pub/bis.pdf)" that
the uniform $\mathsf{TC^0}$ is equal to $\mathsf{FOM}$
([$\mathsf{FO}$](https://en.wikipedia.org/wiki/FO_%28complexity%29) 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.

**Tags:** cc.complexity-theory, reference-request, circuit-complexity, advice-and-nonuniformity, bounded-depth
> **Comments:**
> **username_1**: 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.  
> **username_0**: @Yuval, I added a clarification.  
> **username_1**: 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}$.  
> **username_1**: In short, the problem is that objects in $\mathsf{AC^0}$ are sequences of functions rather than a single function, and so your definition isn't clear. It makes more sense in the uniform setting.  
> **username_0**: @Yuval, you are right. The issue is that people usually don't preciously define what they mean by a circuit with multiple inputs, e.g. take multiplication: given two binary numbers we want to compute their multiplication. But how do you distinguish between the bits for the first number and second number? One can say use some encoding of pairs but that is not how people really do it. If we deal with this (which is not difficult to do, we just have to consider families of circuits with multiple indices, one for the size of each input) then things would work as they do in uniform setting.  
> **username_0**: @Yuval, for the other point, i.e. if what the closure characterization is correct then any $\mathsf{TC^0}$ circuit can be computed by a circuit which uses only a fixed number of Majority gates. That might look surprising, however if it is true in the uniform case (which seems to be the case) then it would not be very surprising if it is also true in the nonuniform case.  
> **username_1**: 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}$.  
> **username_0**: @Yuval, it seems that one can get around that issue by using a two dimensional version of the majority function which takes a matrix and returns the majority of each row. The reason this works is that with $\mathsf{FOM}$ we don't get arbitrary children, they are all the result of the same function and are obtained by changing a single input over a range. The argument with Majority replaced with this two-dimensional Majority seems to work (I don't see how to compute this function with a constant number of majority gates so this should address your point).  
> **username_1**: Can you formally state the new version of the question? (Including your earlier comment on circuits with multiple inputs.)  

---

## 0 answers

