Dept Banner
Dept Banner


Download as iCal file

DIMACS Theory of Computing Seminar

Supercritical Space-Width Trade-offs for Resolution

Location:  CoRE 301
Date & time: Wednesday, 12 October 2016 at 11:00AM -

Jakob Nordstrom, KTH Stockholm

"Supercritical Space-Widths Trade-offs for Resolution"

Location: CoRE 301

Time: 11:00 AM

Abstract:  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.

Special Note to All Travelers

Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.

Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.

Contact Us

HillCenter small

Department of Mathematics

Department of Mathematics
Rutgers University
Hill Center - Busch Campus
110 Frelinghuysen Road
Piscataway, NJ 08854-8019, USA

Phone: +1.848.445.2390
Fax: +1.732.445.5530