BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:Improved NP-inapproximability for 2-variable Linear Equations
DTSTART:20150217T160000
DTEND:20150217T170000
DTSTAMP:20260406T184713Z
UID:5c9bf8b49cb153cabc5b28f729521504d48ceea4981fa591a557b5a4
CATEGORIES:Conferences - Seminars
DESCRIPTION:Sangxia Huang (KTH Royal Institute of Technology)\nAn instance
  of the E2-Lin(2) problem is a system of equations of the form "x_i + x_j 
 = b (mod 2)". Given such a system in which it is possible to satisfy all b
 ut an epsilon fraction of the equations\, we would like to find an assignm
 ent that violates as few equations as possible. In this paper\, we show th
 at it is NP-hard to satisfy all but a C*epsilon fraction of the equations\
 , for any C < 11/8 and 0 < epsilon <= 1/8. Our result holds also for the s
 pecial case of Max-Cut. The previous best NP-hardness result\, standing fo
 r over 15 years\, had 5/4 in place of 11/8.\nOur proof is by a modified ga
 dget reduction from a predicate that supports a pairwise independent distr
 ibution. We also show an inherent limitation to this type of gadget reduct
 ion. In particular\, we show that no such reduction can establish a hardne
 ss factor C greater than ~2.54.\nJoint work with Johan Håstad\, Rajsekar 
 Manokaran\, Ryan O'Donnell\, John Wright.
LOCATION:BC 420 https://plan.epfl.ch/?room==BC%20420
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR