Abstract: What underlying mathematical structure (or lack thereof) in a computational problem governs its efficient solvability (or dictates its hardness)? In the realm of constraint satisfaction problems (CSPs), the algebraic dichotomy theorem gives a definitive answer: a polynomial time algorithm exists precisely when the problem admits non-trivial operations called polymorphisms that combine solutions to the problem to yield new solutions. Inspired and emboldened by this, one might speculate a broader polymorphic principle: if there are interesting ways to combine solutions to get more solutions, then the problem ought to be tractable (with the meanings of "interesting" and "tractable” being heavily context dependent).
Beginning with some background on the polymorphic approach to understanding the complexity of constraint satisfaction, the talk will discuss some extensions beyond CSPs where the polymorphic principle seems highly promising (yet far from understood). Specifically, we will discuss promise CSPs where one is allowed to satisfy a relaxed version of the constraints (a framework that includes important problems like approximate graph coloring and discrepancy minimization), and the potential and challenges in applying the polymorphic framework to them. Another interesting direction is fine-grained complexity, where partial polymorphisms govern the runtime of fast exponential-time algorithms. Our inquiries into these directions also reveal some interesting connections to optimization, such as algorithms to solve LPs over different rings (like integers adjoined with sqrt{2}), and a random-walk based algorithm interpolating between 0-1 and linear programming, generalizing Schöning's famous (4/3)^n time algorithm for 3-SAT.
Based on a body of work with Joshua Brakensiek.
Bio: Venkatesan Guruswami received his Bachelor's degree in Computer Science from the Indian Institute of Technology at Madras in 1997 and his Ph.D. in Computer Science from the Massachusetts Institute of Technology in 2001. He is currently a Professor in the Computer Science Department at Carnegie Mellon University. Earlier, during 2002-09, he was a faculty member at the University of Washington. Dr. Guruswami was a Miller Research Fellow at the UC Berkeley during 2001-02, and was a member in the School of Mathematics, Institute for Advanced Study during 2007-08.
Dr. Guruswami's research interests span several topics in theoretical computer science such as the theory of error-correcting codes, approximability of fundamental optimization problems, explicit combinatorial constructions and pseudorandomness, probabilistically checkable proofs, computational complexity theory, and algebraic algorithms.
Dr. Guruswami currently serves on the editorial boards of the SIAM Journal on Computing and the ACM Transactions on Computation Theory, and as the program committee chair for the 2015 FOCS conference. Previously, he was on editorial board of the IEEE Transactions on Information Theory and was program committee chair for the 2012 Computational Complexity conference. He was an invited speaker at the 2010 International Congress of Mathematicians. Dr. Guruswami is a recipient of the Presburger Award (2012), Packard Fellowship (2005), Sloan Fellowship (2005), NSF CAREER award (2004), the ACM Doctoral Dissertation Award (2002), and the IEEE Information Theory Society Paper Award (2000).
