Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > FIXED-POLYNOMIAL LOWER BOUNDS:
Reports tagged with fixed-polynomial lower bounds:
TR13-037 | 15th March 2013
Alexander Knop

Circuit Lower Bounds for Heuristic MA

Revisions: 2

Santhanam (2007) proved that MA/1 does not have circuits of size $n^k$. We translate his result to the heuristic setting by proving that there is a constant $a$ such that for any $k$, there is a language in HeurMA that cannot be solved by circuits of size $n^k$ on more ... more >>>




ISSN 1433-8092 | Imprint