Talks
Fall 2018
![](https://old.simons.berkeley.edu/sites/default/files/styles/workshop_main/public/complexity9-01.png?itok=iJsfZae-)
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 |
---|---|
![]() | 3.96 MB |