| Title | : | The polymorphic gateway between structure and algorithms: Constraint Satisfaction and Beyond |
| Speaker | : | Venkatesan Guruswami (CMU, USA) |
| Details | : | Tue, 26 Mar, 2019 4:00 PM @ A M Turing Hall |
| 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 when there are non-trivial local operations called polymorphisms under which the solution space is closed; otherwise the problem is NP-complete. 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 context dependent interpretations of interesting and tractable). 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 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önings famous ( 4/3)^n time algorithm for 3-SAT.
Based on a body of work with Joshua Brakensiek (former CMU undergrad, currently in the PhD program at Stanford). About the Speaker: Venkatesan Guruswami (Venkat) is a Professor in the Computer Science Department at Carnegie Mellon University. He received his B. Tech. degree from IIT Madras in 1997 and his Ph.D. in Computer Science from the Massachusetts Institute of Technology in 2001. Venkat is a theoretical computer scientist with broad interests spanning several topics including error-correcting codes and information theory, approximate optimization, constraint satisfaction, and computational complexity. Venkat currently serves as the Editor-in-Chief of the ACM Transactions on Computation Theory and on the editorial board of the Journal of the ACM. He served as the program committee chair for the 2012 Computational Complexity Conference (CCC), the 2015 IEEE Symposium on Foundations of Computer Science (FOCS), and a Technical Program co-chair of the 2018 IEEE International Symposium on Information Theory (ISIT). Venkat is currently President of the Computational Complexity Foundation, and a co-moderator for arXiv/cs.IT. Venkat was an invited speaker at the 2010 International Congress of Mathematicians on the topic of Mathematical Aspects of Computer Science. Venkat is an ACM Fellow as well as an IEEE Fellow. His other honors include the EATCS Presburger Award, Packard and Sloan Fellowships, a Google Faculty Research Award, the ACM Doctoral Dissertation Award, and the IEEE Information Theory Society Paper Award. This is the 8th Talk in the TCS-IITM Computer Science and Engineering Colloquium Series. |
