61 citations · 83 across the 10 of their papers we have counts for
14 papers
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…
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…
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 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…
Explicit two-deletion codes with redundancy matching the existential bound
Venkatesan Guruswami, Johan Håstad
We give an explicit construction of length- binary codes capable of correcting the deletion of two bits that have size . This matches up to lower order terms the…
-Galvin families
Johan Håstad, Guillaume Lagarde, Joseph Swernofsky
The Galvin problem asks for the minimum size of a family with the property that, for any set of size , there is a set $S \in…
Quantum algorithms for computing short discrete logarithms and factoring RSA integers
Martin Ekerå, Johan Håstad
In this paper we generalize the quantum algorithm for computing short discrete logarithms previously introduced by Ekerå so as to allow for various tradeoffs between the number of…
An improved bound on the fraction of correctable deletions
Boris Bukh, Venkatesan Guruswami, Johan Håstad
We consider codes over fixed alphabets against worst-case symbol deletions. For any fixed , we construct a family of codes over alphabet of size with positive rate, wh…
Super-polylogarithmic hypergraph coloring hardness via low-degree long codes
Venkatesan Guruswami, Johan Hastad, Prahladh Harsha +2
We prove improved inapproximability results for hypergraph coloring using the low-degree polynomial code (aka, the 'short code' of Barak et. al. [FOCS 2012]) and the techniques pro…
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…
On the Usefulness of Predicates
Per Austrin, Johan Håstad
Motivated by the pervasiveness of strong inapproximability results for Max-CSPs, we introduce a relaxed notion of an approximate solution of a Max-CSP. In this relaxed version, loo…
Making the long code shorter, with applications to the Unique Games Conjecture
Boaz Barak, Parikshit Gopalan, Johan Hastad +3
The long code is a central tool in hardness of approximation, especially in questions related to the unique games conjecture. We construct a new code that is exponentially more eff…
On the List-Decodability of Random Linear Codes
Venkatesan Guruswami, Johan Hastad, Swastik Kopparty
For every fixed finite field $\F_q$, and , we prove that with high probability a random subspace of $\F_q^n$ of dimension has the proper…
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…