3 ms·
I spent some time searching for an algebraic expression or straight forward recursive formula for dedekind numbers in the past because such a formula would make
by nullc 3y ago
I spent some time searching for an algebraic expression or straight forward recursive formula for dedekind numbers in the past because such a formula would make it easy to construct an efficient encoding function that maps a monotone boolean function to an integer optimally.
Why was I interested in optimally encoding monotone boolean functions? Because they're exactly equivalent to the set of credible multi-party signing policies. So, for example you have some N parties that can participate in signing to control some Bitcoin-- which combinations of them should be allowed? People commonly use thresholds, M of N, but sometimes not all participants are equal. The full set of policies you could possibly have is the monotone functions (since it doesn't make sense to have a policy that says a party CANT participate, since a party could always refrain to satisfy the policy).
Knowing the next dedekind number, even if not through a an efficient expression provides extra information that could help understand the structure of the problem.
For my application though having an optimal encoding isn't strictly necessary (and in any case may not be possible, given the amount of thought that has gone into solving the problem finding the dedekind numbers)-- though it would be neat.
The naive encoding is to just express it as a boolean function, which takes 2^n bits, but already at 9 inputs an optimal encoding of monotone functions would be 26.8% of the size and the gap will increase as the number of inputs increases.
More interesting to me would be an encoding that efficiently (if not optimally) expressed the monotone functions in terms of how many bits were allowed to be false, because I'd come up with a commitment scheme that allows the policy setter to set the policy as a single hash (which has a hidden bound on he number of missing parties), while the signers can collaboratively produce a signature of size proportional to the number of missing parties. In the case that the policy is a simple threshold, this construct alone is enough, but if it isn't additional information for which missing-sets aren't allowed is needed and to maximize policy privacy it would be best if he information was hierarchically encoded. E.g. if none are missing then no information is needed, if 1 is missing which parties are it not allowed to be, if 2 are missing which pairs, and so on. (this structure also has more promise for an efficient encoding, since its easy to optimally encode an n choose m selection).
For these more generalized encoding questions, particularly if they don't seek to encode optimally the next dedekind number is less useful, but exploration of it could still yield helpful insights towards more efficient, if not optimal encodings or somewhat efficient encodings with special properties like the hierarchical one I wanted above.