4 papers
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 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 bounded depth proofs for Tseitin formulas on the grid; revisited
Johan HÃ¥stad, Kilian Risse
We study Frege proofs using depth- Boolean formulas for the Tseitin contradiction on grids. We prove that if each line in the proof is of size then the number o…
A logarithmic approximation of linearly ordered colourings
Johan Håstad, Björn Martinsson, Tamio-Vesa Nakajima +1
A linearly ordered (LO) -colouring of a hypergraph assigns to each vertex a colour from the set in such a way that each hyperedge has a unique maximum eleme…