Tata Institute of Fundamental Research
Necessarily Heavy Functions
STCS Student Seminar
Speaker:
Suhail Sherif
Organiser:
Siddharth Bhandari
Date:
Friday, 13 Apr 2018, 16:00 to 17:00
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
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".
| Speaker: | Suhail Sherif |
| Organiser: | Siddharth Bhandari |
| Date: | Friday, 13 Apr 2018, 16:00 to 17:00 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
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".
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".