Location: CoRE 301
Date & time: Wednesday, 12 October 2016 at 11:00AM -
"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.
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.
 |
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 |
