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