Fall 2015

Satisfiability Algorithms I

Monday, Aug. 31, 2015 9:30 am10:30 am PDT

Add to Calendar


Calvin Lab Auditorium 

The second session of this talk will take place on Monday, August 31 from 11:00 am – 12:00 pm; the third session of this talk will take place on Monday, August 31 from 1:30 pm – 2:30 pm.

I will survey the satisfiability algorithms for k-CNF and extensions and explore the connections to lower bounds for depth-3 circuits. I will also provide motivation for ETH and SETH and discuss the Sparsification Lemma.

PDF icon Satisfiability Algorithms I486.54 KB