Talks
Fall 2015

Sparsification Lemma and ETH

Monday, August 31st, 2015 1:30 pm2:30 pm

Add to Calendar

Location: 

Calvin Lab Auditorium 

The first session of this talk will take place on Monday, August 31 from 9:30 am – 10:30 am; the second session of this talk will take place on Monday, August 31 from 11:00 am – 12:00 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.

AttachmentSize
PDF icon Sparsification Lemma and ETH557.81 KB