9 citations · 12 across the 3 of their papers we have counts for
3 papers · 1 filter
Hardness of Approximation in PSPACE and Separation Results for Pebble Games
Siu Man Chan, Massimo Lauria, Jakob Nordström +1
We consider the pebble game on DAGs with bounded fan-in introduced in [Paterson and Hewitt '70] and the reversible version of this game in [Bennett '89], and study the question of…
From Small Space to Small Width in Resolution
Yuval Filmus, Massimo Lauria, Mladen Mikša +2
In 2003, Atserias and Dalmau resolved a major open question about the resolution proof system by establishing that the space complexity of CNF formulas is always an upper bound on…
Narrow Proofs May Be Maximally Long
Albert Atserias, Massimo Lauria, Jakob Nordström
We prove that there are 3-CNF formulas over n variables that can be refuted in resolution in width w but require resolution proofs of size n^Omega(w). This shows that the simple co…