Search filters

List of works by Johan Håstad

A New Way of Using Semidefinite Programming with Applications to Linear Equations mod p

A Slight Sharpening of LMN

A Smaller Sleeping Bag for a Baby Snake

article by Johan Håstad et al published July 2007 in Discrete and Computational Geometry

A Smaller Sleeping Bag for a Baby Snake

article by Johan Håstad et al published January 2001 in Discrete and Computational Geometry

A simple lower bound for monotone clique using a communication game

article by Mikael Goldmann & Johan Håstad published March 1992 in Information Processing Letters

A well-characterized approximation problem

An Efficient Parallel Repetition Theorem

Approximating Linear Threshold Predicates

Approximating Linear Threshold Predicates

Circuit Bottom Fan-in and Computational Power

Clique is hard to approximate within n/sup 1-ε/

article

Clique is hard to approximate within n1−ε

scientific article published in Acta Mathematica in 1999

Complexity Theory, Proofs and Approximation

article

Erratum: Polynomial Time Algorithms for Finding Integer Relations Among Real Numbers

scholarly article published in SIAM Journal on Computing

Every 2-csp Allows Nontrivial Approximation

Fitting points on the real line and its application to RH mapping

Hardness of Approximate Hypergraph Coloring

Linear-Consistency Testing

Making the Long Code Shorter

Monotone Circuits for Connectivity Have Depth (log n)2-o(1)

On DNF Approximators for Monotone Boolean Functions

On Lower Bounds for Selecting the Median

On average time hierarchies

On bounded occurrence constraint satisfaction

On the Approximation Resistance of a Random Predicate

On the Correlation of Parity and Small-Depth Circuits

On the NP-Hardness of Max-Not-2

On the NP-Hardness of Max-Not-2

On the advantage over a random assignment

scholarly article by Johan Håstad & S. Venkatesh published 23 June 2004 in Random Structures and Algorithms

On the complexity of interactive proofs with bounded communication

On the power of many one-bit provers

On the shrinkage exponent for read-once formulae

On the usefulness of predicates

Polynomial Time Algorithms for Finding Integer Relations among Real Numbers

1989 journal article

Practical Construction and Analysis of Pseudo-Randomness Primitives

Randomly supported independence and resistance

article published in 2009

Satisfying Degree-d Equations over GF[2] n

Simple Constructions of Almost k-wise Independent Random Variables

scholarly article by Noga Alon et al published 1992 in Random Structures and Algorithms

Simple analysis of graph tests for linearity and PCP

scholarly article by Johan Håstad & Avi Wigderson published 6 January 2003 in Random Structures and Algorithms

Some optimal inapproximability results

scientific article published in 2001

Special Issue “Conference on Computational Complexity 2009” Guest Editor’s Foreword

Super-polylogarithmic hypergraph coloring hardness via low-degree long codes

Switching lemma

Tensor rank is NP-complete

article by Johan Håstad published December 1990 in Journal of Algorithms

The discrete logarithm modulo a composite hides 0(n) Bits

article published in 1993

The random oracle hypothesis is false

The security of all RSA and discrete log bits

The square lattice shuffle

scholarly article by Johan Håstad published 2006 in Random Structures and Algorithms

The square lattice shuffle, correction

Tight Bounds for Searching a Sorted Array of Strings