1 citations · 1 across the 5 of their papers we have counts for
4 papers · 1 filter
On the Usefulness of Promises
Per Austrin, Johan Håstad, Björn Martinsson
A Boolean predicate is defined to be promise-useful if is tractable for some non-trivial and otherwise it is promise-useless. We initiate investi…
On Small-depth Frege Proofs for PHP
Johan Håstad
We study Frege proofs for the one-to-one graph Pigeon Hole Principle defined on the grid where is odd. We are interested in the case where each formula in the proof…
On the Power of Many One-Bit Provers
Per Austrin, Johan Håstad, Rafael Pass
We study the class of languages, denoted by $\MIP[k, 1-ε, s]$, which have -prover games where each prover just sends a \emph{single} bit, with completeness and soundness e…
Towards an Optimal Separation of Space and Length in Resolution
Jakob Nordström, Johan Håstad
Most state-of-the-art satisfiability algorithms today are variants of the DPLL procedure augmented with clause learning. The main bottleneck for such algorithms, other than the obv…