Speaker: Prof. Venkatesan Guruswami
Time: 2017-06-09 14:00-2017-06-09 15:00
Venue: FIT 1-222

Abstract:

Given a k-SAT instance with the promise that there is an assignment satisfying at least t out of k literals in each clause, can one efficiently find a satisfying assignment (setting at least one literal to true in every clause)?

Extensions of some 2-SAT algorithms solve this problem when t >= k/2. We prove that for t < k/2, the problem is NP-hard (joint work with P. Austrin and J. Hastad). Thus, SAT becomes hard when the promised density of true literals falls below 1/2. One might thus say that the transition from easy to hard in 2-SAT vs. 3-SAT takes place just after two and not just before three.

The talk will sketch the proof of this hardness result, which proceeds by characterizing functions passing the natural "dictatorship test” as   "juntas" depending on few variables.  We will then elucidate a broader principle based on the paucity of "weak polymorphisms” (generalizing the universal-algebraic approach to study constraint satisfaction via polymorphisms), which seems to govern the intractability of promise constraint satisfaction problems (PCSPs), a rich class that includes the above example among many other fundamental problems. We will touch upon on a body of work (with J. Brakensiek) that shows that the complexity of a PCSP is precisely captured by its associated weak polymorphisms, and applies this framework to prove new hardness results for approximate graph coloring and establish a complexity dichotomy for the case of Boolean symmetric PCSP.

Short Bio:

Venkatesan Guruswami  is a computer scientist at Carnegie Mellon University in Pittsburgh, United States. He did his schooling at Padma Seshadri Bala Bhavan in Chennai, India. He completed his undergraduate in Computer Science from IIT Madras and his doctorate from Massachusetts Institute of Technology under the supervision of Madhu Sudan in 2001 [1]. After receiving his PhD, he spent a year at UC Berkeley as a Miller Fellow, and then was a member of the faculty at the University of Washington from 2002 to 2009. His primary area of research is computer science, and in particular on error-correcting codes. Following 2007, he was on leave from University of Washington. During 2007-2008, he visited the Institute for Advanced Study as a Member of School of Mathematics. He also visited SCS at Carnegie Mellon University during 2008-09 as a Visiting Faculty. In July 2009, he joined the School of Computer Science at Carnegie Mellon University as Associate Professor in the Computer Science Department. Guruswami was one of two winners of the 2012 Presburger Award, given by the European Association for Theoretical Computer Science for outstanding contributions by a young theoretical computer scientist.