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.
a SYM◦SYM circuit example
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.


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. Symmetric rank and Lemma 2.2

(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.)

  • 1
    $\begingroup$ The usual rule is one question per post. $\endgroup$ May 2, 2019 at 18:00

1 Answer 1


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.

  • $\begingroup$ I appreciate for your very kind explanation. Now I understand the same letter can be used in the different places while they have nothing to do with each other. So my first and secend questions are solved by you. About my third question, I added a postscript in the last of my question. I hope this will help you to see which place the construction is invoked. And if you figure out how the construction is done, please teach me. $\endgroup$
    May 3, 2019 at 4:30
  • $\begingroup$ I suggest you move your third question to a different post. The usual rule is one question per post. $\endgroup$ May 3, 2019 at 4:49
  • $\begingroup$ I'm sorry, I'll do so. Thank you for telling me the rule. $\endgroup$
    May 3, 2019 at 4:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.