Fall 2018

Restriction-based Methods II

Monday, August 20th, 2018 3:30 pm4:30 pm

Add to Calendar

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.

PDF icon Restriction-based Methods3.96 MB