---
abstract: 'The *threshold degree* of a function $f\colon\zoon\to\moo$ is the least degree of a real polynomial $p$ with $f(x)\equiv\sign p(x).$ We prove that the intersection of two halfspaces on $\zoon$ has threshold degree $\Omega(n),$ which matches the trivial upper bound and completely answers a question due to Klivans (2002). The best previous lower bound was $\Omega(\sqrt n).$ Our result shows that the intersection of two halfspaces on $\zoon$ only admits a trivial $2^{\Theta(n)}$-time learning algorithm based on sign-representation by polynomials, unlike the advances achieved in PAC learning DNF formulas and read-once Boolean formulas. The proof introduces a new technique of independent interest, based on Fourier analysis and matrix theory.'
author:
- 'Alexander A. Sherstov$^*$'
bibliography:
- |
    %
    /Users/sasha/bib/general.bib
- |
    %
    /Users/sasha/bib/fourier.bib
- |
    %
    /Users/sasha/bib/cc.bib
- |
    %
    /Users/sasha/bib/learn.bib
- |
    %
    /Users/sasha/bib/my.bib
title: |
    Optimal Bounds for Sign-Representing the Intersection\
    of Two Halfspaces by Polynomials
---

[^1]

Introduction {#sec:intro}
============

A well-studied notion in computational learning theory is that of a *perceptron*. This term stands for the representation of a given Boolean function $f\colon\zoon\to\moo$ in the form $
f(x) \equiv \sign p(x)
$ for a real polynomial $p$ of some degree $d.$ The least degree $d$ 