Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR21-031 | 3rd March 2021 10:44

Upper Bound for Torus Polynomials

RSS-Feed




TR21-031
Authors: Vaibhav Krishan
Publication: 5th March 2021 16:14
Downloads: 747
Keywords: 


Abstract:

We prove that all functions that have low degree torus polynomials approximating them with small error also have $MidBit^+$ circuits computing them. This serves as a partial converse to the result that all $ACC$ functions have low degree torus polynomials approximating them with small error, by Bhrushundi, Hosseini, Lovett and Rao (ITCS 2019).



ISSN 1433-8092 | Imprint