2026-07-22T03:56:51Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10106 2024-03-06T10:45:23Z ddc:004 open_access

Torus Polynomials: An Algebraic Approach to ACC Lower Bounds Bhrushundi, Abhishek Hosseini, Kaave Lovett, Shachar Rao, Sankeerth Circuit complexity ACC lower bounds polynomials We propose an algebraic approach to proving circuit lower bounds for ACC^0 by defining and studying the notion of torus polynomials. We show how currently known polynomial-based approximation results for AC^0 and ACC^0 can be reformulated in this framework, implying that ACC^0 can be approximated by low-degree torus polynomials. Furthermore, as a step towards proving ACC^0 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Abhishek Bhrushundi and Kaave Hosseini and Shachar Lovett and Sankeerth Rao 2019 Is Part Of LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2019.13 urn:nbn:de:0030-drops-101066 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.13 eng https://creativecommons.org/licenses/by/3.0/legalcode