License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2019.13
URN: urn:nbn:de:0030-drops-101066
URL: http://drops.dagstuhl.de/opus/volltexte/2018/10106/
Go to the corresponding LIPIcs Volume Portal


Bhrushundi, Abhishek ; Hosseini, Kaave ; Lovett, Shachar ; Rao, Sankeerth

Torus Polynomials: An Algebraic Approach to ACC Lower Bounds

pdf-format:
LIPIcs-ITCS-2019-13.pdf (0.5 MB)


Abstract

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.

BibTeX - Entry

@InProceedings{bhrushundi_et_al:LIPIcs:2018:10106,
  author =	{Abhishek Bhrushundi and Kaave Hosseini and Shachar Lovett and Sankeerth Rao},
  title =	{{Torus Polynomials: An Algebraic Approach to ACC Lower Bounds}},
  booktitle =	{10th Innovations in Theoretical Computer Science  Conference (ITCS 2019)},
  pages =	{13:1--13:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-095-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{124},
  editor =	{Avrim Blum},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/10106},
  URN =		{urn:nbn:de:0030-drops-101066},
  doi =		{10.4230/LIPIcs.ITCS.2019.13},
  annote =	{Keywords: Circuit complexity, ACC, lower bounds, polynomials}
}

Keywords: Circuit complexity, ACC, lower bounds, polynomials
Seminar: 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Issue Date: 2018
Date of publication: 21.12.2018


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI