School of Technology and Computer Science Seminars

Time-Space Lowerbound for SAT

by Prerona Chatterjee (School of Technology and Computer Science, TIFR)

Friday, May 19, 2017 from to (Asia/Kolkata)
at A-201 (STCS Seminar Room)
Description
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.