Speaker: |
Suhail Sherif |

Organiser: |
Gowtham Raghunath Kurri |

Date: |
Friday, 28 Jul 2017, 17:15 to 18:15 |

Venue: |
A-201 (STCS Seminar Room) |

(Scan to add to calendar)

As a model of computation, we look at polynomials with integer coefficients which accept an input if the polynomial evaluates to at least 1, and rejects if the polynomial evaluates to at most 0. (A more rad term for such a model of computation is a 'perceptron') Perceptrons of degree d are closely related to query algorithms with at most d queries.

We prove that any perceptron computing the function either has large degree (at least n^{1/3}) or large coefficients (at least 2^n^{1/4}).

The proof I will present is adapted from Nikolai Vereshchagin's original proof of the result in his paper "Lower Bounds for Perceptrons Solving some Separation Problems and Oracle Separation of AM from PP". The adaptation is inspired by a proof of Thomas Watson in his paper "Quadratic Simulations of Arthur-Merlin Games".