Hacker Newsnew | past | comments | ask | show | jobs | submit | johnb556677's commentslogin

The Nevanlinna Prize was also awarded. This is the award mathematicians give to theoretical computer scientists. This year the winner is Subhash Khot from NYU. His main result is the Unique Games Conjecture (UGC) and how it can be used to obtain hardness of approximation results for algorithmic problems. For example, it is used to show that MaxCut cannot be approximated better than a factor of 0.878.. unless UGC does not hold. Remarkably this exact approximation factor is achievable by the breakthrough SDP algorithm of Goemans and Williamson. It is not currently clear if UGC is true and the opinions of theoreticians are split.


Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: