Time-Space Lowerbound for SAT

Speaker:

Prerona Chatterjee

Organiser:

Varun Narayanan

Date:

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

Venue:

A-201 (STCS Seminar Room)

Category:

STCS Student Seminar

event.ics Print

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.