9 citations · 13 across the 8 of their papers we have counts for
Showing 2014Show all
2 papers · 1 filter
cs.CC2014★ 9 cited
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…
cs.CC2014★ 3 cited
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…