Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > SUNDAR VISHWANATHAN:
All reports by Author Sundar Vishwanathan:

TR24-074 | 11th April 2024
Vaibhav Krishan, Sundar Vishwanathan

Towards ACC Lower Bounds using Torus Polynomials

The class $ACC$ consists of Boolean functions that can be computed by constant-depth circuits of polynomial size with $AND, NOT$ and $MOD_m$ gates, where $m$ is a natural number. At the frontier of our understanding lies a widely believed conjecture asserting that $MAJORITY$ does not belong to $ACC$. The Boolean ... more >>>




ISSN 1433-8092 | Imprint