School of Technology and Computer Science Seminars

Time-Space Lowerbound for SAT

Name: Time-Space Lowerbound for SAT
Start: 2017-05-19T17:15:00+05:30
End: 2017-05-19T18:15:00+05:30
Location: No location set

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

Friday 19 May 2017, 17:15 → 18:15 Asia/Kolkata

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.