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$
$\endgroup$
7
-
$\begingroup$ Some models of circuits have restrictions on the fan-in of gates. $\endgroup$– Yuval FilmusCommented Nov 9, 2018 at 15:50
-
$\begingroup$ Where have you seen this claim? $\endgroup$– Yuval FilmusCommented 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$– theQmanCommented Nov 9, 2018 at 15:52
-
$\begingroup$ A restriction on the fan-in is all you need. $\endgroup$– Yuval FilmusCommented 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$– theQmanCommented Nov 9, 2018 at 15:57
|
Show 2 more comments