Login
Talks & Seminars
Title: Unique Games with value half and its applications
Dr. Amey Bhangale, Weizmann Institute of Science, Israel
Date & Time: April 1, 2019 10:35
Venue: Dept. of CSE, Room No. 109, 1st Floor, New CSE/CC Bldg.
Abstract:
PCP Theorem characterizes the class NP and gives hardness of approximation for many optimization problems. Despite this, several tight hardness of approximation results remain elusive via the PCP theorem. In 2002, Khot proposed the Unique Games Conjecture. Since the formulation of the conjecture, it has found interesting connections to the tight hardness of approximation results for many optimization problems. In this talk, I will discuss recent developments on the Unique Games Conjecture. The 2-to-2 Games Theorem implies that it is NP-hard to distinguish between Unique Games instances with assignment satisfying at least 1/2 fraction of the constraints vs. no assignment satisfying more than \eps fraction of the constraints, for every constant \eps>0. We show that the reduction can be transformed in a non-trivial way to give a stronger guarantee on the Unique Games instance and use this guarantee to convert the known Unique Games-hardness results to NP-hardness for several optimization problems.
Speaker Profile:
Amey Bhangale is currently a post-doctoral fellow at Weizmann Institute of Science hosted by Irit Dinur. He recently (2017) graduated from Rutgers University. His details are available at : http://paul.rutgers.edu/~arb182/
List of Talks

Webmail

Username:
Password:
Faculty CSE IT
Forgot Password
    [+] Sitemap     Feedback