Matthias Krause, Hans Ulrich Simon

This paper shows that the largest possible contrast C(k,n)

in a k-out-of-n secret sharing scheme is approximately

4^(-(k-1)). More precisely, we show that

4^(-(k-1)) <= C_{k,n} <= 4^(-(k-1))}n^k/(n(n-1)...(n-(k-1))).

This implies that the largest possible contrast equals

4^(-(k-1)) in the limit when n approaches ...
more >>>

Arkadev Chattopadhyay, Nikhil Mande

Proving super-polynomial lower bounds against depth-2 threshold circuits of the form THR of THR is a well-known open problem that represents a frontier of our understanding in boolean circuit complexity. By contrast, exponential lower bounds on the size of THR of MAJ circuits were shown by Razborov and Sherstov (SIAM ... more >>>