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.
| 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.