All reports by Author Johan Håstad:

__
TR23-042
| 3rd April 2023
__

Johan Håstad#### On small-depth Frege proofs for PHP

__
TR19-151
| 5th November 2019
__

Per Austrin, Jonah Brown-Cohen, Johan Håstad#### Optimal Inapproximability with Universal Factor Graphs

__
TR17-142
| 21st September 2017
__

Johan Håstad#### On small-depth Frege proofs for Tseitin for grids

Revisions: 1

__
TR16-102
| 4th July 2016
__

Ravi Boppana, Johan Håstad, Chin Ho Lee, Emanuele Viola#### Bounded independence vs. moduli

Revisions: 1

__
TR16-041
| 17th March 2016
__

Johan Håstad#### An average-case depth hierarchy theorem for higher depth

__
TR13-167
| 28th November 2013
__

Venkatesan Guruswami, Prahladh Harsha, Johan Håstad, Srikanth Srinivasan, Girish Varma#### Super-polylogarithmic hypergraph coloring hardness via low-degree long codes

__
TR13-159
| 20th November 2013
__

Per Austrin, Venkatesan Guruswami, Johan Håstad#### $(2+\epsilon)$-SAT is NP-hard

Revisions: 2

__
TR12-137
| 1st November 2012
__

Johan Håstad#### On the correlation of parity and small-depth circuits

Revisions: 1

__
TR11-142
| 2nd November 2011
__

Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra, David Steurer#### Making the long code shorter, with applications to the Unique Games Conjecture

Revisions: 1

__
TR11-027
| 28th February 2011
__

Venkatesan Guruswami, Johan Håstad, Rajsekar Manokaran, Prasad Raghavendra, Moses Charikar#### Beating the Random Ordering is Hard: Every ordering CSP is approximation resistant

__
TR10-132
| 18th August 2010
__

Mahdi Cheraghchi, Johan Håstad, Marcus Isaksson, Ola Svensson#### Approximating Linear Threshold Predicates

__
TR10-003
| 6th January 2010
__

Venkatesan Guruswami, Johan Håstad, Swastik Kopparty#### On the List-Decodability of Random Linear Codes

__
TR08-026
| 28th February 2008
__

Jakob Nordström, Johan Håstad#### Towards an Optimal Separation of Space and Length in Resolution

__
TR00-062
| 25th August 2000
__

Venkatesan Guruswami, Johan Håstad, Madhu Sudan#### Hardness of approximate hypergraph coloring

__
TR99-039
| 24th September 1999
__

Johan Håstad#### On approximating CSP-B

__
TR99-037
| 27th August 1999
__

Johan Håstad, Mats Näslund#### The Security of all RSA and Discrete Log Bits

__
TR99-025
| 2nd July 1999
__

Yonatan Aumann, Johan Håstad, Michael O. Rabin, Madhu Sudan#### Linear Consistency Testing

__
TR96-018
| 23rd February 1996
__

Oded Goldreich, Johan Håstad#### On the Message Complexity of Interactive Proof Systems

Revisions: 2

Johan Håstad

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 ...
more >>>

Per Austrin, Jonah Brown-Cohen, Johan Håstad

The factor graph of an instance of a constraint satisfaction problem (CSP) is the bipartite graph indicating which variables appear in each constraint. An instance of the CSP is given by the factor graph together with a list of which predicate is applied for each constraint. We establish that many ... more >>>

Johan Håstad

We prove that a small-depth Frege refutation of the Tseitin contradiction

on the grid requires subexponential size.

We conclude that polynomial size Frege refutations

of the Tseitin contradiction must use formulas of almost

logarithmic depth.

Ravi Boppana, Johan Håstad, Chin Ho Lee, Emanuele Viola

Let $k=k(n)$ be the largest integer such that there

exists a $k$-wise uniform distribution over $\zo^n$ that

is supported on the set $S_m := \{x \in \zo^n : \sum_i

x_i \equiv 0 \bmod m\}$, where $m$ is any integer. We

show that $\Omega(n/m^2 \log m) \le k \le 2n/m + ...
more >>>

Johan Håstad

We extend the recent hierarchy results of Rossman, Servedio and

Tan \cite{rst15} to any $d \leq \frac {c \log n}{\log {\log n}}$

for an explicit constant $c$.

To be more precise, we prove that for any such $d$ there is a function

$F_d$ that is computable by a read-once formula ...
more >>>

Venkatesan Guruswami, Prahladh Harsha, Johan Håstad, Srikanth Srinivasan, Girish Varma

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 proposed by Dinur and Guruswami [FOCS 2013] to incorporate this code for inapproximability results.

In particular, we prove quasi-NP-hardness of the following problems on ... more >>>

Per Austrin, Venkatesan Guruswami, Johan Håstad

We prove the following hardness result for a natural promise variant of the classical CNF-satisfiability problem: Given a CNF-formula where each clause has width $w$ and the guarantee that there exists an assignment satisfying at least $g = \lceil \frac{w}{2}\rceil -1$ literals in each clause, it is NP-hard to find ... more >>>

Johan Håstad

We prove that the correlation of a depth-$d$

unbounded fanin circuit of size $S$ with parity

of $n$ variables is at most $2^{-\Omega(n/(\log S)^{d-1})}$.

Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra, David Steurer

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 ecient, but can still be used in many of these applications.

Using the new code we obtain exponential improvements over several ...
more >>>

Venkatesan Guruswami, Johan Håstad, Rajsekar Manokaran, Prasad Raghavendra, Moses Charikar

We prove that, assuming the Unique Games Conjecture (UGC), every problem in the class of ordering constraint satisfaction problems (OCSP) where each constraint has constant arity is approximation

resistant. In other words, we show that if $\rho$ is the expected fraction of constraints satisfied by a random ordering, then obtaining ...
more >>>

Mahdi Cheraghchi, Johan Håstad, Marcus Isaksson, Ola Svensson

We study constraint satisfaction problems on the domain $\{-1,1\}$, where the given constraints are homogeneous linear threshold predicates. That is, predicates of the form $\mathrm{sgn}(w_1 x_1 + \cdots + w_n x_n)$ for some positive integer weights $w_1, \dots, w_n$. Despite their simplicity, current techniques fall short of providing a classification ... more >>>

Venkatesan Guruswami, Johan Håstad, Swastik Kopparty

For every fixed finite field $\F_q$, $p \in (0,1-1/q)$ and $\varepsilon >

0$, we prove that with high probability a random subspace $C$ of

$\F_q^n$ of dimension $(1-H_q(p)-\varepsilon)n$ has the

property that every Hamming ball of radius $pn$ has at most

$O(1/\varepsilon)$ codewords.

This ... more >>>

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 obvious one of time, is the amount

of memory used. In the field of proof complexity, the resources of

time and memory correspond to the length ...
more >>>

Venkatesan Guruswami, Johan Håstad, Madhu Sudan

We introduce the notion of covering complexity of a probabilistic

verifier. The covering complexity of a verifier on a given input is

the minimum number of proofs needed to ``satisfy'' the verifier on

every random string, i.e., on every random string, at least one of the

given proofs must be ...
more >>>

Johan Håstad

We prove that any constraint satisfaction problem

where each variable appears a bounded number of

times admits a nontrivial polynomial time approximation

algorithm.

Johan Håstad, Mats Näslund

We study the security of individual bits in an

RSA encrypted message $E_N(x)$. We show that given $E_N(x)$,

predicting any single bit in $x$ with only a non-negligible

advantage over the trivial guessing strategy, is (through a

polynomial time reduction) as hard as breaking ...
more >>>

Yonatan Aumann, Johan Håstad, Michael O. Rabin, Madhu Sudan

We extend the notion of linearity testing to the task of checking

linear-consistency of multiple functions. Informally, functions

are ``linear'' if their graphs form straight lines on the plane.

Two such functions are ``consistent'' if the lines have the same

slope. We propose a variant of a test of ...
more >>>

Oded Goldreich, Johan Håstad

We investigate the computational complexity of languages

which have interactive proof systems of bounded message complexity.

In particular, we show that

(1) If $L$ has an interactive proof in which the total

communication is bounded by $c(n)$ bits

then $L$ can be recognized a probabilitic machine

in time ...
more >>>