Timeline for An inequality concerning formulas and Boolean functions
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 27, 2017 at 14:38 | history | edited | fedja | CC BY-SA 3.0 |
added 214 characters in body
|
| Mar 27, 2017 at 14:34 | comment | added | fedja | @EmilJeřábek Argh! You don't allow branching wires!!! You are right then. Of course, I thought of circuits rather than formulas. Thanks for the clarification (once I see the word "gate", I immediately think of a circuit somehow). Thanks again! :-) | |
| Mar 27, 2017 at 13:56 | comment | added | Emil Jeřábek | Again: these are formulas, not circuits. Each gate can be fed as input to another gate only once. So, each time the output of the multiplication formula is used, it has to be recomputed. Likewise, the Legendre symbol has polynomial circuits, but likely not formulas. A useful equivalent is that a function has poly-size formulas iff it has (bounded fan-in) circuits of logarithmic depth. | |
| Mar 27, 2017 at 13:52 | comment | added | fedja | @EmilJeřábek What do you mean? Once we have the output of the multiplication ($n$ outgoing wires), we just feed them as inputs of $\varphi$. Also, Legendre symbol is polynomial ($a^{(p-1)/2}\mod p$ computed via the squaring technique), but this requires much more than one multiplication, that's why the dogma. | |
| Mar 27, 2017 at 13:10 | comment | added | Emil Jeřábek | No, wait a minute. This doesn't work. We are talking formula complexity, not circuit complexity. Thus, the "composite formula" is $\varphi$ with every occurrence of a variable replaced with a separate copy of the appropriate multiplication formula. The total size is roughly the product of the two formula sizes, not their sum. | |
| Mar 27, 2017 at 10:23 | comment | added | Emil Jeřábek | This is a great counterexample. Indeed, iterated multiplication modulo $p$ has polynomial-size formulas (being computable in uniform $\mathrm{TC^0}$), whereas this is very unlikely to be true for the Legendre symbol. | |
| Mar 27, 2017 at 1:42 | history | answered | fedja | CC BY-SA 3.0 |