Improved NP-inapproximability for 2-variable Linear Equations
Event details
| Date | 17.02.2015 |
| Hour | 16:00 › 17:00 |
| Speaker | Sangxia Huang (KTH Royal Institute of Technology) |
| Location | |
| Category | Conferences - Seminars |
An 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 but an epsilon fraction of the equations, we would like to find an assignment that violates as few equations as possible. In this paper, we show that 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 special case of Max-Cut. The previous best NP-hardness result, standing for over 15 years, had 5/4 in place of 11/8.
Our proof is by a modified gadget reduction from a predicate that supports a pairwise independent distribution. We also show an inherent limitation to this type of gadget reduction. In particular, we show that no such reduction can establish a hardness factor C greater than ~2.54.
Joint work with Johan Håstad, Rajsekar Manokaran, Ryan O'Donnell, John Wright.
Our proof is by a modified gadget reduction from a predicate that supports a pairwise independent distribution. We also show an inherent limitation to this type of gadget reduction. In particular, we show that no such reduction can establish a hardness factor C greater than ~2.54.
Joint work with Johan Håstad, Rajsekar Manokaran, Ryan O'Donnell, John Wright.
Practical information
- Informed public
- Free
Organizer
- Ola Svensson