Seminar Details
Torus Polynomials: an Algebraic Approach to ACC Lower Bounds
- Start Date: January 30, 2019
- Event Start Time: 11:00 AM
- Event End Time: 12:00 PM
- Seminar Series: Theoretical Computer Science Seminar
- Presenter(s): Abhishek Bhrushundi - Rutgers University
- Event Location: Conference Room 301 | Rutgers University | CoRE Building | 96 Frelinghuysen Road
- Presentation Type: Stand Alone Presentation
- 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.
Joint work with Kaave Hosseini, Shachar Lovett, and Sankeerth Rao.