Loading...
Please wait, while we are loading the content...
Similar Documents
The Average Sensitivity of an Intersection of Half Spaces
| Content Provider | arXiv |
|---|---|
| Author | Kane, Daniel M. |
| Date of Submission | 2015-01-26 |
| Abstract | We prove new bounds on the average sensitivity of the indicator function of an intersection of $k$ halfspaces. In particular, we prove the optimal bound of $O(\sqrt{n\log(k)})$. This generalizes a result of Nazarov, who proved the analogous result in the Gaussian case, and improves upon a result of Harsha, Klivans and Meka. Furthermore, our result has implications for the runtime required to learn intersections of halfspaces. |
| Related Links | https://arxiv.org/pdf/1309.2987.pdf |
| arXiv | 1309.2987 |
| Language | English |
| Access Restriction | Open |
| Subject Keyword | Computer Science - Computational Complexity Mathematics - Combinatorics Mathematics - Metric Geometry Computer Science Mathematics |
| Content Type | Text |
| Resource Type | Article |
| Subject | Mathematics |
