Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR18-076 | 1st March 2019 00:18

Torus polynomials: an algebraic approach to ACC lower bounds

RSS-Feed




Revision #2
Authors: Abhishek Bhrushundi, Kaave Hosseini, Shachar Lovett, Sankeerth Rao Karingula
Accepted on: 1st March 2019 00:18
Downloads: 715
Keywords: 


Abstract:

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.



Changes to previous version:

Extended introduction; final version that appears in the proceedings of ITCS 2019


Revision #1 to TR18-076 | 23rd April 2018 22:31

Torus polynomials: an algebraic approach to ACC lower bounds





Revision #1
Authors: Abhishek Bhrushundi, Kaave Hosseini, Shachar Lovett, Sankeerth Rao Karingula
Accepted on: 23rd April 2018 22:31
Downloads: 1343
Keywords: 


Abstract:

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.



Changes to previous version:

Fixed minor typos.


Paper:

TR18-076 | 22nd April 2018 20:25

Torus polynomials: an algebraic approach to ACC lower bounds


Abstract:

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.



ISSN 1433-8092 | Imprint