- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- BIRS Workshop Lecture Videos /
- The hardest halfspace
Open Collections
BIRS Workshop Lecture Videos
BIRS Workshop Lecture Videos
The hardest halfspace Sherstov, Alexander
Description
Pointwise (i.e., infinity-norm) approximation by polynomials has produced a treasure trove of efficient learning algorithms under arbitrary distributions for fundamental concept classes. A notable exception is the intersection of two halfspaces on {0,1}^n, shown 8 years ago (STOC 2010) to require a polynomial of the maximum possible degree, Omega(n), even for representation by sign (the weakest form of pointwise approximation). The proof was based on the probabilistic method, and the explicit construction of such an intersection of two halfspaces has remained an open problem. We solve this problem here, with an explicit construction of a halfspace h:{0,1}^n -> {-1,+1} such that the intersection of two copies of h cannot be represented by the sign of a polynomial of degree less than Omega(n). We further show that h by itself is the ``hardest'' of halfspaces for pointwise approximation by polynomials and rational functions, and determine the minimum error achievable by approximants of any given degree. This completes a line of work started by Myhill and Kautz (1961). We discuss applications to separating communication complexity classes. The proof features elements of approximation theory, random walks, and number theory. Our starting point is the construction, due to Ajtai et al. (1990), of a set of O(log m) of integers that are appear random modulo m in the sense of the discrete Fourier transform on Z/mZ.
Item Metadata
Title |
The hardest halfspace
|
Creator | |
Publisher |
Banff International Research Station for Mathematical Innovation and Discovery
|
Date Issued |
2018-08-14T12:34
|
Description |
Pointwise (i.e., infinity-norm) approximation by polynomials has produced a treasure trove of efficient
learning algorithms under arbitrary distributions for fundamental concept classes. A notable exception is the
intersection of two halfspaces on {0,1}^n, shown 8 years ago (STOC 2010) to require a polynomial of the
maximum possible degree, Omega(n), even for representation by sign (the weakest form of pointwise
approximation). The proof was based on the probabilistic method, and the explicit construction of such an intersection of two halfspaces has remained an open problem.
We solve this problem here, with an explicit construction of a halfspace h:{0,1}^n -> {-1,+1} such that the intersection of two copies of h cannot be represented by the sign of a polynomial of degree less than Omega(n). We further show that h by itself is the ``hardest'' of halfspaces for pointwise approximation by polynomials and rational functions, and determine
the minimum error achievable by approximants of any given degree. This completes a line of work started by
Myhill and Kautz (1961). We discuss applications to separating communication complexity classes.
The proof features elements of approximation theory, random walks, and number theory. Our starting point is
the construction, due to Ajtai et al. (1990), of a set of O(log m) of integers that are appear random modulo m in the sense of the discrete Fourier transform on Z/mZ.
|
Extent |
57.0
|
Subject | |
Type | |
File Format |
video/mp4
|
Language |
eng
|
Notes |
Author affiliation: UCLA
|
Series | |
Date Available |
2019-03-28
|
Provider |
Vancouver : University of British Columbia Library
|
Rights |
Attribution-NonCommercial-NoDerivatives 4.0 International
|
DOI |
10.14288/1.0377630
|
URI | |
Affiliation | |
Peer Review Status |
Unreviewed
|
Scholarly Level |
Researcher
|
Rights URI | |
Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
Rights
Attribution-NonCommercial-NoDerivatives 4.0 International