Source author record

Johan Håstad

Johan Håstad appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Computational Complexity Discrete Mathematics Information Theory math.IT Data Structures and Algorithms math.CO

Catalog footprint

What is connected

5works

6topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2025arXiv

On Small-depth Frege Proofs for PHP

We study Frege proofs for the one-to-one graph Pigeon Hole Principle defined on the $n\times n$ grid where $n$ is odd. We are interested in the case where each formula in the proof is a depth $d$ formula in the basis given by $\land$, $\lor$, and $\neg$. We prove that in this situation the proof needs to be of size exponential in $n^{Ω(1/d)}$. If we restrict the size of each line in the proof to be of size $M$ then the number of lines needed is exponential in $n/(\log M)^{O(d)}$. The main technical component of the proofs is to design a new family of random restrictions and to prove the appropriate switching lemmas.

preprint2020arXiv

Explicit two-deletion codes with redundancy matching the existential bound

We give an explicit construction of length-$n$ binary codes capable of correcting the deletion of two bits that have size $2^n/n^{4+o(1)}$. This matches up to lower order terms the existential result, based on an inefficient greedy choice of codewords, that guarantees such codes of size $Ω(2^n/n^4)$. Our construction is based on augmenting the classic Varshamov-Tenengolts construction of single deletion codes with additional check equations. We also give an explicit construction of binary codes of size $Ω(2^n/n^{3+o(1)})$ that can be list decoded from two deletions using lists of size two. Previously, even the existence of such codes was not clear.

preprint2016arXiv

An improved bound on the fraction of correctable deletions

We consider codes over fixed alphabets against worst-case symbol deletions. For any fixed $k \ge 2$, we construct a family of codes over alphabet of size $k$ with positive rate, which allow efficient recovery from a worst-case deletion fraction approaching $1-\frac{2}{k+\sqrt k}$. In particular, for binary codes, we are able to recover a fraction of deletions approaching $1/(\sqrt 2 +1)=\sqrt 2-1 \approx 0.414$. Previously, even non-constructively the largest deletion fraction known to be correctable with positive rate was $1-Θ(1/\sqrt{k})$, and around $0.17$ for the binary case. Our result pins down the largest fraction of correctable deletions for $k$-ary codes as $1-Θ(1/k)$, since $1-1/k$ is an upper bound even for the simpler model of erasures where the locations of the missing symbols are known. Closing the gap between $(\sqrt 2 -1)$ and $1/2$ for the limit of worst-case deletions correctable by binary codes remains a tantalizing open question.

preprint2013arXiv

On the Power of Many One-Bit Provers

We study the class of languages, denoted by $\MIP[k, 1-ε, s]$, which have $k$-prover games where each prover just sends a \emph{single} bit, with completeness $1-ε$ and soundness error $s$. For the case that $k=1$ (i.e., for the case of interactive proofs), Goldreich, Vadhan and Wigderson ({\em Computational Complexity'02}) demonstrate that $\SZK$ exactly characterizes languages having 1-bit proof systems with"non-trivial" soundness (i.e., $1/2 < s \leq 1-2ε$). We demonstrate that for the case that $k\geq 2$, 1-bit $k$-prover games exhibit a significantly richer structure: + (Folklore) When $s \leq \frac{1}{2^k} - ε$, $\MIP[k, 1-ε, s] = \BPP$; + When $\frac{1}{2^k} + ε\leq s < \frac{2}{2^k}-ε$, $\MIP[k, 1-ε, s] = \SZK$; + When $s \ge \frac{2}{2^k} + ε$, $\AM \subseteq \MIP[k, 1-ε, s]$; + For $s \le 0.62 k/2^k$ and sufficiently large $k$, $\MIP[k, 1-ε, s] \subseteq \EXP$; + For $s \ge 2k/2^{k}$, $\MIP[k, 1, 1-ε, s] = \NEXP$. As such, 1-bit $k$-prover games yield a natural "quantitative" approach to relating complexity classes such as $\BPP$,$\SZK$,$\AM$, $\EXP$, and $\NEXP$. We leave open the question of whether a more fine-grained hierarchy (between $\AM$ and $\NEXP$) can be established for the case when $s \geq \frac{2}{2^k} + ε$.

preprint2012arXiv

On the Usefulness of Predicates

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, loosely speaking, the algorithm is allowed to replace the constraints of an instance by some other (possibly real-valued) constraints, and then only needs to satisfy as many of the new constraints as possible. To be more precise, we introduce the following notion of a predicate $P$ being \emph{useful} for a (real-valued) objective $Q$: given an almost satisfiable Max-$P$ instance, there is an algorithm that beats a random assignment on the corresponding Max-$Q$ instance applied to the same sets of literals. The standard notion of a nontrivial approximation algorithm for a Max-CSP with predicate $P$ is exactly the same as saying that $P$ is useful for $P$ itself. We say that $P$ is useless if it is not useful for any $Q$. This turns out to be equivalent to the following pseudo-randomness property: given an almost satisfiable instance of Max-$P$ it is hard to find an assignment such that the induced distribution on $k$-bit strings defined by the instance is not essentially uniform. Under the Unique Games Conjecture, we give a complete and simple characterization of useful Max-CSPs defined by a predicate: such a Max-CSP is useless if and only if there is a pairwise independent distribution supported on the satisfying assignments of the predicate. It is natural to also consider the case when no negations are allowed in the CSP instance, and we derive a similar complete characterization (under the UGC) there as well. Finally, we also include some results and examples shedding additional light on the approximability of certain Max-CSPs.