Time-Space Lowerbound for SAT

Speaker: 

Time: 

Friday, 19 May 2017, 17:15 to 18:15

Venue: 

  • A-201 (STCS Seminar Room)

Organisers: 

In this talk, we look at a $n^1.6616$ lower bound for SAT on $n^{o(n)}$ space machines. The result is taken from the 2006 paper by Ryan Williams.