From Small Space to Small Width in Resolution
Authors: Yuval Filmus, Massimo Lauria, Mladen Miksa, Jakob Nordström and Marc Vinyals
Paper Information
| Title: | From Small Space to Small Width in Resolution |
| Authors: | Yuval Filmus, Massimo Lauria, Mladen Miksa, Jakob Nordström and Marc Vinyals |
| Proceedings: | PC 2014 Abstracts |
| Editors: | Jan Johannsen and Olaf Beyersdorff |
| Keywords: | proof complexity, resolution, width, space, polynomial calculus, PCR |
| Abstract: | ABSTRACT. In 2003, Atserias and Dalmau established that the space complexity of formulas in resolution is an upper bound on the width needed to refute them. Their proof is beautiful but somewhat mysterious in that it relies on tools from finite model theory. We give an alternative proof that works by simple syntactic manipulations of resolution refutations. As a by-product, we develop a "black-box" technique for proving space lower bounds. |
| Pages: | 0 |
| Talk: | Jul 13 12:30 |
| Paper: |  |