A threshold function on n bits is a function that can be represented as the sign of a linear function of its inputs, i.e. f(x) = sign(w_1 x_1 + ... w_n x_n + c)
It is easy to show that there is a threshold function that requires weights at least 2^(n/2). We will start off the talk by seeing a simple proof of this.
In 1994, Johan Håstad showed that the known upper bound of 2^O(n logn) is tight by exhibiting a function that matched it. The rest of the talk would be a presentation of this result, building on the simple proof.
This result is from the paper "On the size of weights for threshold gates".
