Timeline for Every circuit of size at most $S$ can be representd as a string of $9S \log S$ bits
Current License: CC BY-SA 4.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 9, 2018 at 16:03 | comment | added | theQman | Yes, I have been coming to terms with this, but sometimes these constants seem absurdly arbitrary... | |
| Nov 9, 2018 at 16:01 | comment | added | Yuval Filmus | Right, that’s the idea. The constant 9 is probably an arbitrary constant that works, but could be reduced. We usually don’t care much about such constants. | |
| Nov 9, 2018 at 15:57 | comment | added | theQman | 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? | |
| Nov 9, 2018 at 15:57 | history | edited | xskxzr | CC BY-SA 4.0 |
edited title
|
| Nov 9, 2018 at 15:53 | comment | added | Yuval Filmus | A restriction on the fan-in is all you need. | |
| Nov 9, 2018 at 15:52 | comment | added | theQman | 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. | |
| Nov 9, 2018 at 15:50 | comment | added | Yuval Filmus | Where have you seen this claim? | |
| Nov 9, 2018 at 15:50 | comment | added | Yuval Filmus | Some models of circuits have restrictions on the fan-in of gates. | |
| Nov 9, 2018 at 15:29 | history | asked | theQman | CC BY-SA 4.0 |