9 citations · 9 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…
Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity
Susanna F. de Rezende, Or Meir, Jakob Nordström +3
We significantly strengthen and generalize the theorem lifting Nullstellensatz degree to monotone span program size by Pitassi and Robere (2018) so that it works for any gadget wit…
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…