1 citations · 1 across the 4 of their papers we have counts for
4 papers
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…
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…