ManuscriptsWe give an exposition of Smolensky’s fundamental paper on the polynomial method, a lower bound method in circuit complexity. Books usually contain a simpler argument which works only for parity, whereas Smolensky’s argument also works for majority (directly). Our exposition omits the step of approximating a constant depth circuit by a low-degree polynomial.
