We learn from our alumni in this interaction series, often technically, sometimes semi-technically.

Venkatesan Guruswami Berkeley

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 Chancellor's Professor, Department of EECS, Berkeley. He has been associated with several top universities such as CMU, University of Washington, and Institute for Advanced Study. 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 as the Editor-in-Chief of the Journal of the ACM, Editor of TheoretiCS, and Vice chair of the IEEE Technical Committee on Mathematical Foundations of Computing. Previously, he was on editorial board of several journals such as SIAM Journal on Computing, the ACM Transactions on Computation Theory, IEEE Transactions on Information Theory and was program committee chair for ISIT 2018, FOCS 2015 and 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). He has graduated 11 PhDs so far, including two award-winning PhDs. Dr. Guruswami is chosen as a Distinguished Alumnus of IIT Madras this year.

Computational problems exhibit a diverse range of behaviors in terms of how quickly and effectively they can be solved. What underlying mathematical structure (or lack thereof) in a computational problem leads to an efficient algorithm for solving it (or dictates its intractability)? Given the vast landscape of problems and algorithmic approaches, it would be simplistic to hope for a universal theory explaining the underpinnings of easiness/hardness. Yet, in the realm of constraint satisfaction problems, 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 polymorphic principle in more general contexts, with symmetries in the solution space being the genesis of efficient algorithms.

Beginning with some background on constraint satisfaction problems (CSP) and the polymorphic approach to understanding their complexity, the talk will discuss some extensions beyond CSP where the polymorphic principle seems promising (yet far from understood). In particular, we will discuss ``promise CSP'' 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). We will also point out some of the many challenges that remain, and touch upon broader connections to complexity and optimization.

Organizers