Johan Håstad: Some of my interests and (old) results
Time: Tue 2020-11-10 11.15
Lecturer: Johan Håstad, KTH
Location: Zoom and KTH, F11
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 .