I 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.
As 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.
Because 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.
Great, 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.
It'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 by @ColinWright points out, that is not a monotone property … unless `n = 0`!)
Thank 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!
