I'm trying to understand this claim. I see that if there are $S$ vertices, then we can identify each vertex using $\log S$ bits. Now each vertex can be connected to, let's say, $S$ other ones (is there some sort of restriction to the fan-out that I'm unaware of?). If we use an adjacency list, then for each vertex, we wold need to store up to $S \log S$ bits. Doesn't this lead to $S^2 \log S$ bits, since we need a list for each vertex? And where does the $9$ come from?

  • $\begingroup$ Some models of circuits have restrictions on the fan-in of gates. $\endgroup$ Nov 9, 2018 at 15:50
  • $\begingroup$ Where have you seen this claim? $\endgroup$ Nov 9, 2018 at 15:50
  • $\begingroup$ This is in Arora and Barak's "Computational Complexity". There is indeed a restriction on the fan-in (2 or less), but not on the fan-out, as far as I can tell. $\endgroup$
    – theQman
    Nov 9, 2018 at 15:52
  • $\begingroup$ A restriction on the fan-in is all you need. $\endgroup$ Nov 9, 2018 at 15:53
  • $\begingroup$ Because then for each vertex we list the incoming vertices, rather than the outgoing ones? Then I think we can represent the circuit with $2S \log S$ bits, but why the $9$ in the claim? $\endgroup$
    – theQman
    Nov 9, 2018 at 15:57


Your Answer

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

Browse other questions tagged or ask your own question.