Abstract
Restrictions are a means of simplifying circuits by assigning values to a subset of input variables. This talk will present an overview of lower bounds based on restrictions, especially random restrictions. This includes a review Hastad’s classic switching lemma for p-random restrictions and a discussion of recent extensions which have led to #SAT algorithms and bounds on the Fourier spectrum of AC^0 functions. We will also discuss other types of random restrictions (projections and affine restrictions) which have been instrumental in recent breakthroughs in circuit complexity and proof complexity.