All reports by Author Johan Hastad:

__
TR17-142
| 21st September 2017
__

Johan Hastad#### On small-depth Frege proofs for Tseitin for grids

Revisions: 1

__
TR16-041
| 17th March 2016
__

Johan Hastad#### An average-case depth hierarchy theorem for higher depth

__
TR12-137
| 1st November 2012
__

Johan Hastad#### On the correlation of parity and small-depth circuits

Revisions: 1

__
TR11-142
| 2nd November 2011
__

Boaz Barak, Parikshit Gopalan, Johan Hastad, 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 Hastad, 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 Hastad, Marcus Isaksson, Ola Svensson#### Approximating Linear Threshold Predicates

__
TR10-003
| 6th January 2010
__

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

__
TR08-026
| 28th February 2008
__

Jakob NordstrÃ¶m, Johan Hastad#### Towards an Optimal Separation of Space and Length in Resolution

__
TR00-062
| 25th August 2000
__

Venkatesan Guruswami, Johan Hastad, Madhu Sudan#### Hardness of approximate hypergraph coloring

__
TR99-039
| 24th September 1999
__

Johan Hastad#### On approximating CSP-B

__
TR99-037
| 27th August 1999
__

Johan Hastad, Mats NÃ¤slund#### The Security of all RSA and Discrete Log Bits

__
TR99-025
| 2nd July 1999
__

Yonatan Aumann, Johan Hastad, Michael O. Rabin, Madhu Sudan#### Linear Consistency Testing

__
TR96-018
| 23rd February 1996
__

Oded Goldreich, Johan Hastad#### On the Message Complexity of Interactive Proof Systems

Revisions: 2

Johan Hastad

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.

Johan Hastad

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

Johan Hastad

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 Hastad, 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 Hastad, 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 Hastad, 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 Hastad, 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 Hastad

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 Hastad, 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 Hastad

We prove that any constraint satisfaction problem

where each variable appears a bounded number of

times admits a nontrivial polynomial time approximation

algorithm.

Johan Hastad, 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 Hastad, 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 Hastad

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