Search

# Hardness of Approximation between P and NP

Wednesday, November 30, 2016
12:00 PM - 1:00 PM
Location: Baxter B125
Aviad Rubenstein, Computer Science PhD Candidate, UC Berkeley

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!" Rubenstein will discuss recent progress towards understanding the complexity of those problems.

Series: Linde Institute/Social and Information Sciences Laboratory Seminar Series (SISL)