Speaker:Suprovat Ghoshal

Title

On New Synergies between Constraint Satisfaction and Graph Expansion

Abstract

Approximation algorithms are a natural way of dealing with the intractability barrier faced by many fundamental computational problems in discrete and continuous optimization. The past couple of decades have resulted in vast progress in this area, culminating in unified theories of algorithms and hardness for several fundamental classes of problems. However, a similarly complete understanding of many fundamental generalizations of these classes is still yet to be realized, and in particular, the challenges in this direction represent some of the central open questions in the theory of algorithms and hardness.

In this talk, I will present some recent results which make progress on some of these questions by developing new connections between Constraint Satisfaction Problems (CSPs) and expansion profile in graphs. Firstly, I will discuss some exciting implications of the Small-Set Expansion Hypothesis (SSEH) to the question of approximating CSPs with Global Constraints, a class of problems that vastly generalize Max-CSPs. I will also describe some recent developments on the question of approximating Vertex Expansion in graphs and its connection to fundamental problems such as the Strong Unique Games and Max Independent Set. I will conclude by describing some exciting new open directions that follow from these developments.

About Suprovat Ghoshal

Suprovat Ghoshal is a postdoc at Northwestern University and Toyota Technological Institute at Chicago, hosted by Konstantin Makarychev and Yury Makarychev. Before this, he was a postdoc at the University of Michigan, hosted by Euiwoong Lee. He received his Ph.D. from the Indian Institute of Science (IISc), advised by Arnab Bhattacharyya and Siddharth Barman. His thesis received an honorable mention at the ACM India Doctoral Dissertation Award and a Best Alumni Thesis Award from IISc. His primary research interests are approximation algorithms and hardness of approximation, focusing on problems revolving around Constraint Satisfaction and various notions of graph expansion.