On Top-Down and Local Lower Bounds for $\mathrm{A}{\mathrm{C}}^0$ Circuits

Gülce Kardeş, Benjamin Rossman

Classical lower bounds for $\mathrm{A}{\mathrm{C}}^0$ circuits proceed bottom-up by simplifying or approximating gates beginning at the input layer. We introduce a complementary top-down mode…