Event calendar file
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)
at A-201 (STCS Seminar Room)
| Description |
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". |
