DIMACS Theory of Computing Seminar

Title: Supercritical Space-Width Trade-offs for Resolution

Speaker: Jakob Nordstrom, KTH Stockholm

Date: Wednesday, October 12, 2016 11:00am-12:00pm

Location: CoRE Bldg, Room 301, Rutgers University, Busch Campus, Piscataway, NJ


We show that there are CNF formulas which can be refuted in resolution in both small space and small width, but for which any small-width resolution proof must have space exceeding by far the linear worst-case upper bound. This significantly strengthens the space-width trade-offs in [Ben-Sasson '09], and provides one more example of trade-offs in the "supercritical" regime above worst case recently identified by [Razborov '16]. We obtain our results by using Razborov's new hardness condensation technique and combining it with the space lower bounds in [Ben-Sasson and Nordström '08].

This is joint work with Christoph Berkholz.

See: http://www.math.rutgers.edu/~sk1233/theory-seminar/F16/