Talks
Fall 2018
Restriction-based Methods I
Monday, August 20th, 2018, 2:00 pm–3:00 pm
Speaker:
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.
Attachment | Size |
---|---|
Restriction-based Methods | 3.96 MB |