We say that a first-order formula A(x_1,\dots,x_n) over \mathbb{R} defines a Boolean function f:\{0,1\}^n\rightarrow\{0,1\}, if for every x_1,\dots,x_n\in\{0,1\}, A(x_1,\dots,x_n) is true iff f(x_1,\dots,x_n)=1. We show that:
(i) every f can be defined by a formula of size O(n),
(ii) if A is required to have at most k\geq 1 ...
more >>>
A secret-sharing scheme allows to distribute a secret s among n parties such that only some predefined ``authorized'' sets of parties can reconstruct the secret, and all other ``unauthorized'' sets learn nothing about s. For over 30 years, it was known that any (monotone) collection of authorized sets can be ... more >>>