# Johan Håstad: Some of my interests and (old) results

**Time: **
Tue 2020-11-10 11.15

**Location: **
Zoom and KTH, F11

**Lecturer: **
Johan Håstad, KTH

### Abstract

I work in complexity theory and recently I have studied efficient approximability of NP-hard optimization problems. In particular I have been interested in constraint satisfaction problems (CSPs). In a CSP you are given a large number of constraints each only depending on a constant number of variables and the goal is to find an assignment to satisfy as many constraints as possible. Central examples are Max-3Sat and sets of linear equations over a finite field where each equation only depends on three variables. I will also briefly mention some problems in post-quantum cryptography.

**Notes:** The seminar will take place in F11 for **the first 18 people to arrive**. Overflow audience and those who are working from home can participate via Zoom with meeting ID
62586628413
.