Tata Institute of Fundamental Research

Time-Space Lowerbound for SAT

STCS Student Seminar
Speaker: Prerona Chatterjee
Organiser: Varun Narayanan
Date: Friday, 19 May 2017, 17:15 to 18:15
Venue: A-201 (STCS Seminar Room)

(Scan to add to calendar)
Abstract:  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.