Some lower bounds in parameterized ${\mathrm{AC}}^0$

Yijia Chen, Joerg Flum

We demonstrate some lower bounds for parameterized problems via parameterized classes corresponding to the classical ${\mathrm{AC}}^0$. Among others, we derive such a lower bound for al…