School of Technology and Computer Science Seminars

Necessarily Heavy Functions

by Suhail Sherif (School of Technology and Computer Science, TIFR)

Friday, April 13, 2018 from to (Asia/Kolkata)
at A-201 (STCS Seminar Room)
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".