A Lower Bound for Perceptrons that Compute Some Separation Problem

We look at the boolean function in which the input is a boolean matrix with the promise that either 2/3rd of its rows contain a 1 or 2/3rd of its rows do not contain a 1. The output is 1 if the matrix is of the former kind and 0 if it is of the latter kind.

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