Johan Håstad
where else to find them
no profile links on file
what they talk about
where they keep going back
no series more than once — all 1 in the filters
on a stage with
never shared a talk
who talks about the same things
nobody close enough yet
| title | conference | date |
|---|---|---|
| Inapproximability of Constraint Satisfaction Problems I | Real Analysis Boot Camp 2013 | 2013-09-09 |
Claim: it is NP‑hard to beat 7/8 hardness for MAX‑3SAT. Proof outline: reduction from satisfiability via the PCP theorem, then parallel repetition to get a… | ||
| Inapproximability of Constraint Satisfaction Problems II | Real Analysis Boot Camp 2013 | 2013-09-09 |
Shows NP‑hardness of approximating Max‑3‑LIN/Max‑3‑SAT to within the usual constants (half+ε for 3‑LIN and approaching 7/8+ε for 3‑SAT) by starting from PCP… | ||
| Inapproximability of Constraint Satisfaction Problems III | Real Analysis Boot Camp 2013 | 2013-09-09 |
Reduction starts from label cover and encodes labels by long codes, analyzes Fourier coefficients and probabilistic labelings to turn a parity test into an… | ||
| Inapproximability of Constraint Satisfaction Problems IV | Real Analysis Boot Camp 2013 | 2013-09-09 |
Recap of concrete hardness techniques: starts from label cover with smooth label cover and uses long‑code style tests plus gadget reductions that introduce at… | ||
| Inapproximability of Constraint Satisfaction Problems V | Real Analysis Boot Camp 2013 | 2013-09-09 |
Argues that standard gadget/LP methods cannot prove NP-hardness for the sparse Hadamard predicate H7 and instead uses a construction that takes… | ||
| nothing matches | ||