Speaker:

Suhail Sherif, TIFR

## Time:

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

## Venue:

- A-201 (STCS Seminar Room)

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