CS Events

Computer Science Department Colloquium Towards a Unified Theory of Approximability of Globally Constrained CSPs
Export Event Save iCal Send to Google Calendar Send to Yahoo Calendar Send to Outlook Live Send to Microsoft Outlook Save iCal Preserve formatting in description (only supported in some calendar applications) Close Monday, March 04, 2024, 10:30am - 12:00pm

Speaker: Suprovat Ghoshal

Bio

Suprovat Ghoshal is currently 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), where he was 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. He is primarily interested in exploring the landscape of optimization problems using the theory of approximation algorithms and the hardness of approximation.

Location : CoRE 301

: 

Event Type: Computer Science Department Colloquium

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 seen vast progress in this area, culminating in unified theories of algorithms and hardness for several fundamental classes of problems, such as Maximum Constraint Satisfaction Problems (Max-CSPs). 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 that build towards a theory of optimal algorithms and hardness for Globally Constrained CSPs (Constraint Satisfaction Problems), a class of problems that vastly generalize Max-CSPs. These results are derived using recently emerging tools in the theory of approximation, such as the Small-Set Expansion Hypothesis and the Sum-of-Squares Hierarchy, and they yield the first nearly tight bounds for classical fundamental problems such as Densest-k-Subgraph and Densest-k-SubHypergraph, in the regime where k is linear in the number of vertices. I will conclude by describing this research program's broad, long-term goals, as well as some specific open questions that represent key bottlenecks towards its realization.

: 

Contact  Professor Mario Szegedy

Join Zoom Meeting
https://rutgers.zoom.us/j/2014444359?pwd=WW9ybFNCNVFrUWlycHowSHdNZjhzUT09
Meeting ID: 201 444 4359
Password: 550978