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

文章基本信息

  • 标题:Torus polynomials: an algebraic approach to ACC lower bounds
  • 本地全文:下载
  • 作者:Abhishek Bhrushundi ; Kaave Hosseini ; Shachar Lovett
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2018
  • 卷号:2018
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    We propose an algebraic approach to proving circuit lower bounds for ACC0 by defining and studying the notion of torus polynomials. We show how currently known polynomial-based approximation results for AC0 and ACC0 can be reformulated in this framework, implying that ACC0 can be approximated by low-degree torus polynomials. Furthermore, as a step towards proving ACC0 lower bounds for the majority function via our approach, we show that MAJORITY cannot be approximated by low-degree symmetric torus polynomials. We also pose several open problems related to our framework.

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