文章基本信息

标题：Noise Stable Halfspaces are Close to Very Small Juntas
本地全文：下载
作者：Ilias Diakonikolas ; Ragesh Jaiswal ; Rocco A. Servedio 等
期刊名称：Chicago Journal of Theoretical Computer Science
印刷版ISSN：1073-0486
出版年度：2015
卷号：2015
出版社：MIT Press ; University of Chicago, Department of Computer Science
摘要：Bourgain showed that any noise stable Boolean function $f$ can be well-approximated by a junta. In this note we give an exponential sharpening of the parameters of Bourgain's result under the additional assumption that $f$ is a halfspace