The hardest halfspace
The hardest halfspace
复制标题
DOI：
10.1007/s00037-021-00211-4
复制
发表时间：
2019-02
影响因子：
1.4
通讯作者：
Alexander A. Sherstov
中科院分区：
文献类型：
--
作者：
Alexander A. Sherstov
我们通过任意给定次数的多项式和有理函数来研究无穷范数中半空间的近似。我们的主要结果是“最难”半空间的显式构造，为此我们证明了与所有半空间可实现的平凡上限相匹配的多项式和有理逼近下界。这完成了由 Myhill 和 Kautz (1961) 开始的一系列漫长的工作。作为一个应用程序，我们构建了一个通信问题，该问题本质上实现了符号秩和差异之间最大可能的分离（O(n)vs）。同样，我们的问题展示了无界与弱无界误差的通信复杂性之间的对数与对数差距，在以前的构造上进行了二次改进，并完成了 Babai、Frankl 和 Simon 开始的一系列工作（FOCS 1986）。我们的结果进一步推广到 k 方额头数字模型，在该模型中，我们获得了 logn 与无界与弱无界误差通信的显式分离。
We study the approximation of halfspacesin the infinity norm by polynomials and rational functions of any given degree. Our main result is an explicit construction of the “hardest” halfspace, for which we prove polynomial and rational approximation lower bounds that match the trivial upper bounds achievable for all halfspaces. This completes a lengthy line of work started by Myhill and Kautz (1961). As an application, we construct a communication problem that achieves essentially the largest possible separation, ofO(n)versus, between the sign-rank and discrepancy. Equivalently, our problem exhibits a gap of lognversusbetween the communication complexity withunboundedversusweakly unboundederror, improving quadratically on previous constructions and completing a line of work started by Babai, Frankl, and Simon (FOCS 1986). Our results further generalize to thek-party number-on-the-forehead model, where we obtain an explicit separation of lognversusfor communication with unbounded versus weakly unbounded error.