4 ms·
Extremal Combinatorics With Applications in Computer Science
- jeffreyrogers 6y agoI wish the author would give some motivation for why I should attempt to understand monotone circuit lower bounds. I can probably follow the math, but math takes effort to read and I'm not generally willing to make the effort unless I get some hint as to what the payoff might be.
- xhkkffbf 6y agoTwo words: 3sat. In other words, answering whether P==NP or not.
- xenonite 6y agoDid someone get why "It cannot be that S has an even number of elements" (in the first subsection)?
- ColinWright 6y agoBecause if you just add one element to the set it no longer has the property, and hence the predicate is not monotone. In more detail ... He's talking about properties (or predicates) that are monotone. That means that if P(S) is true, and T contains S, then P(T) must also be true. But when P(X) is true if and only if X has an even number of elements, then P({a,b}) would be true, but P({a,b,c}) will not be true. Then P would not be monotone.
- xenonite 6y agoGreat, thank you very much for your explanation! I now get that the sentence describes a new example predicate that is not connected to the sentence before (“S includes at least half of the elements of [n]”). This makes sense. Thank you for your thoughts.
- JadeNB 6y agoIt's worded confusingly; it certainly can be that `S` has an even number of elements. (For a silly example, if `f(S) = 1` identically, then `f(∅) = 1` even though `∅` has an even number of elements.) What cannot be is that `f(S) = 1` is equivalent to `S` having an even number of elements (because, as the sibling thread https://news.ycombinator.com/item?id=23967766 https://news.ycombinator.com/item?id=23967766 by @ColinWright points out, that is not a monotone property … unless `n = 0`!)
- xenonite 6y agoThank you a lot for your answer with a further possible interpretation, even. Indeed the wording didn’t make it clear to me this is a second example. Now it is totally clear. Thank you, it’s great to follow your thoughts!
- bmc7505 6y agoPDF: http://bd.unsl.edu.ar/download.php?id=1638 http://bd.unsl.edu.ar/download.php?id=1638
- daviddaviddavid 6y agoAs a regular old non-theoretical-CS computer programmer, it amazes me that a fellow Buffalonian (Dr Ken Regan) pops up on HN and related sites so often for writings in the headiest areas of CS and chess, etc. Not too many internet celebrities in this city.