首页    期刊浏览 2024年11月30日 星期六
登录注册

文章基本信息

  • 标题:Approximate Degree-Weight and Indistinguishability
  • 本地全文:下载
  • 作者:Xuangui Huang ; Emanuele Viola
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2019
  • 卷号:2019
  • 页码:1-20
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    We prove that the OR function on n bits can be point-wise approximated with error by a polynomial of degree O ( k ) and weight 2 O n \logeps k , for any k n log 1 . This result is tight for k = ( 1 − (1)) n . Previous results were either not tight or had = (1) . In general we obtain a tight approximation result for any symmetric function. Building on this we also obtain an approximation result for bounded-width CNF. For these two classes no such result was known.One motivation for such results comes from the study of indistinguishability. Two distributions P , Q over n -bit strings are ( k ) -indistinguishable if their projections on any k bits have statistical distance at most . The above approximations give values of ( k ) that suffice to fool OR, symmetric functions and bounded-width CNF, and the first result is tight for all k while the second result is tight for k = ( 1 − (1)) n . Finally, we show that any two ( k ) -indistinguishable distributions are O ( n ) k 2 -close to two distributions that are ( k 0 ) -indistinguishable, improving the previous bound of O ( n ) k .

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