Loading Events

« All Events

  • This event has passed.

CSE Colloquium: Amey Bhangale

April 29, 2019 @ 11:00 am - 12:00 pm UTC-5

Speaker: Amey Bhangale

Date: Monday, April 29

Time: 11-12pm

Location: HBL 1947 Room

 

Title: Unique Games with value half and its applications. 

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 about 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. 

Based on joint work with Subhash Khot. 

Details

Date:
April 29, 2019
Time:
11:00 am - 12:00 pm UTC-5
Event Category:

Venue

HBL Class of 1947 Conference Room
UConn Library, 369 Fairfield Way, Unit 1005
Storrs, CT 06269 United States
+ Google Map
Phone:
(860) 486-2518
Website:
https://lib.uconn.edu/

Connect With Us