# About a symmetric rank decomposition of a SYM◦SYM circuit's truth table matrix

New algorithms and lower bounds for circuits with linear threshold gates.
Ryan Williams. Submitted, 2013.

I study this paper and have difficulty with understanding the proof of Lemma 2.2 in section 2.
My questions are the three below.

① In the proof, we can find this sentence.

Let f : {0,1,...,s} → {0,1} be the symmetric function of gate g′: for all a ∈ {0,1,...,s}, f(a) = b if and only if a true inputs make g′ output b.

Since f : {0,1,...,s} → {0,1} and f(a) = b, I thought b ∈ {0,1}.
Is my assumption correct?

② We can find the constants a and b also in the next paragraph.

For every pair (a,b)∈{0,1,...,t}2 such that a+bt, let Sa,b ⊆ {g1,...,gs} denote the subset of gates gj such that a+b true inputs makes gate gj output 1.

Do these a and b correspond to the previous ones?

③ To understand how every pair (a,b) is constructed, I made a simple SYM◦SYM circuit and tried to enumerate every pair.

In this example, I know the constants below will be
n = 2, s = 2, a ∈ {0,1,2},
but I'm not sure about the value of t(the number of wires), b and the subset Sa,b.
So, please tell me the value of constant t, every pair (a,b) and its Sa,b in this example.

P.S.(2019/05/03)

The concept of the pair (a,b) and the subset Sa,b are used in the following context to construct the truth table of a symmetric circuit.

(Since I'm not so good at English and not an expert of this field, I'd be sorry if there's any inappropriate expressions or mistakes.)

• The usual rule is one question per post. May 2, 2019 at 18:00

The fact that the same letter is used twice doesn't mean that it signifies the same thing. In particular, in your first question, clearly $$a \in \{0,\ldots,s\}$$ and $$b \in \{0,1\}$$, whereas in the second question, it is explicitly stated that $$a,b \in \{0,\ldots,t\}$$. From your excerpts, it seems that the second $$a,b$$ are of the same "type" as the $$a$$ in your first question.
Your third question is unanswerable given your excerpts. It could be that the construction is instantiated with several different values of $$t$$. In any case, I would look at the place in which the construction is invoked to find out what the value of $$t$$ should be.