Necessarily Heavy Functions

Speaker: 

Time: 

Friday, 13 April 2018, 16:00 to 17:00

Venue: 

Organisers: 

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".