William M. Hoza

A Technique for Hardness Amplification Against $$\textsf{AC}^0$$

Abstract To show that a function h is hard to approximate for $$\textsf{AC}^0$$ AC 0 circuits, one method is to (a) design some distribution over random restrictions or random projections, (b) show that $$\textsf{AC}^0$$ AC 0 circuits simplify to shallow decision trees under thes...