首页    期刊浏览 2024年09月12日 星期四
登录注册

文章基本信息

  • 标题:A moment ratio bound for polynomials and
  • 本地全文:下载
  • 作者:Naomi Kirshner ; Alex Samorodnitsky
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2019
  • 卷号:2019
  • 页码:1-69
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    Let p 2 . We improve the bound f 2 f p ( p − 1 ) s 2 for a polynomial f of degree s on the boolean cube 0 1 n , which comes from hypercontractivity, replacing the right hand side of this inequality by an explicit bivariate function of p and s , which is smaller than ( p − 1 ) s 2 for any 2"> p 2 and 0"> s 0 . We show the new bound to be tight, within a smaller order factor, for the Krawchouk polynomial of degree s .This implies several nearly-extremal properties of Krawchouk polynomials and Hamming spheres (equivalently, Hamming balls). In particular, Krawchouk polynomials have (almost) the heaviest tails among all polynomials of the same degree and 2 norm (this has to be interpreted with some care). The Hamming spheres have the following approximate edge-isoperimetric property: For all 1 s 2 n , and for all even distances 0 i n 2 s ( n − s ) , the Hamming sphere of radius s contains, up to a multiplicative factor of O ( i ) , as many pairs of points at distance i as possible, among sets of the same size (there is a similar, but slightly weaker and somewhat more complicated claim for general distances). This also implies that Hamming spheres are (almost) stablest with respect to noise among sets of the same size. In coding theory terms this means that a Hamming sphere (equivalently a Hamming ball) has the maximal probability of undetected error, among all binary codes of the same rate.We also describe a family of hypercontractive inequalities for functions on 0 1 n , which improve on the `usual' `` q 2 " inequality by taking into account the concentration of a function (expressed as the ratio between its r norms), and which are nearly tight for characteristic functions of Hamming spheres.

国家哲学社会科学文献中心版权所有