Dissertation Talk: Hardness of approximation between P and NP

Seminar | April 19 | 10-11 a.m. | 380 Soda Hall

 Aviad Rubinstein, UC Berkeley

 Electrical Engineering and Computer Sciences (EECS)

The first question we computer scientists ask when facing a new algorithmic challenge is: is it NP-hard, or is it in P? Surprisingly, for many important problems, the answer is “neither!” I will discuss recent progress towards understanding the complexity of those problems.

 CA, aviad@eecs.berkeley.edu, 6822928423