Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR23-111 | 29th July 2023 06:17

$\mathit{MidBit}^+$, Torus Polynomials and Non-classical Polynomials: Equivalences for $\mathit{ACC}$ Lower Bounds

RSS-Feed




TR23-111
Authors: Vaibhav Krishan
Publication: 29th July 2023 06:55
Downloads: 255
Keywords: 


Abstract:

We give a conversion from non-classical polynomials to $\mathit{MidBit}^+$ circuits and vice-versa. This conversion, along with previously known results, shows that torus polynomials, non-classical polynomials and $\mathit{MidBit}^+$ circuits can all be converted to each other. Therefore lower bounds against any of these models lead to lower bounds against all three of them. Each of these three models capture the power of $\mathit{ACC}$ circuits, which are circuits composed of $\mathit{AND}$, $\mathit{OR}$, $\mathit{MOD}_m$ gates for some constant natural number m. Hence lower bounds against any of these models lead to comparable lower bounds against ACC.



ISSN 1433-8092 | Imprint