首页    期刊浏览 2024年10月06日 星期日
登录注册

文章基本信息

  • 标题:Approximating the AND-OR Tree
  • 本地全文:下载
  • 作者:Alexander A. Sherstov
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2013
  • 卷号:2013
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    The approximate degree of a Boolean function f is the least degree of a real polynomial that approximates f within 13 at every point. We prove that the function ni=1nj=1xij , known as the AND-OR tree, has approximate degree (n) This lower bound is tight and closes a line of research on the problem, the best previous bound being (n075). More generally, we prove that the function mi=1nj=1xij has approximate degree (mn) which is tight. The same lower bound was obtained independently by Bun and Thaler (2013) using related techniques.

  • 关键词:AND-OR tree; approximate degree; linear programming duality; polynomial approximation; Representations of Boolean functions by polynomials
国家哲学社会科学文献中心版权所有