Institute for Interdisciplinary Information Sciences (IIIS)

home>Events>Upcoming Events>Institute Seminars

Beating the random ordering is hard: Approximation resistance of Max Acyclic Su

Speaker: Venkatesan Guruswami Carnegie Mellon University
Time: 2009-06-17 14:00-2009-06-17 15:00
Venue: FIT Building 4-603, Tsinghua University

Abstract:

Given a directed acyclic graph, it is easy to "topological sort" its vertices such that all directed edges go forward in the ordering. But what if there is some noise and the graph is only nearly acyclic, say 1% of the edges need to be reversed to make it acyclic. Simply picking a random ordering gets an expected fraction 1/2 of edges going forward, but it was a longstanding open question if one could efficiently find an ordering of the vertices of such a graph with even 51% of forward edges.

We prove that finding such an ordering is hard. Specifically, for any constant eps > 0, given a directed graph G that has an acyclic subgraph consisting of a fraction (1-eps) of its edges, finding an acyclic subgraph of G with more than (1/2+eps) of its edges is Unique-Games hard. This immediately implies a super-constant factor inapproximability result for the Feedback Arc Set problem.

More generally, we prove that every ordering problem with constraints on the local ordering of subsets of up to 3 elements (such as the "Betweenness" problem which has constraints of the form "j is placed between i and k"), is approximation resistant: it is UG-hard to outperform the trivial approximation ratio achieved by a random ordering.

Based on joint works [G.-Manokaran-Raghavendra'08] and [Charikar-G.-Manokaran'09].

Short Bio:

Venkatesan Guruswami received his Bachelor's degree from the Indian Institute of Technology at Madras in 1997 and his Ph.D. from the Massachusetts Institute of Technology in 2001. He will be an Associate Professor in the Computer Science Department at Carnegie Mellon University starting July 2009. Prior to this, he was a faculty member in the Department of Computer Science and Engineering at the University of Washington. Dr. Guruswami was a Miller Research Fellow at the University of California, Berkeley during 2001-02, and was on leave at the School of mathematics, Institute for Advanced Study during 2007-08.

Dr. Guruswami's research interests span a broad array of topITCS including the theory of error-correcting codes, approximation algorithms and non-approximability results for NP-hard optimization problems, explicit combinatorial constructions and pseudorandomness, probabilistically checkable proofs, computational complexity theory, and algebraic algorithms. He is especially well known for his contributions to the area of list error-correction, parts of which have been featured by NSF and Science magazine.

Dr. Guruswami is a recipient of several awards including the David and Lucile Packard Foundation Fellowship (2005), Alfred P. Sloan Foundation Fellowship (2005), NSF CAREER award (2004), ACM's Doctoral Dissertation Award (2002), and the IEEE Information Theory Society Paper Award (2000).