Talk: New Approaches to Approximately Solving Constraint Satisfaction Problems

Live stream: https://uwmadison.zoom.us/j/96501408405?pwd=e7FY0iXMpLY6ZuG9x9rZexaYLj51hr.1 

Abstract: Constraint Satisfaction Problems (CSPs) are a fundamental framework for modeling combinatorial problems where the goal is to assign values to variables subject to local constraints. They unify diverse problems across AI, logic, and graph theory. CSPs are key to exploring the boundary between tractable and intractable problems, with rich structure captured via polymorphisms and algebraic methods.

In this talk, I will present some of my recent work on advances in approximately solving CSPs. In the quest for optimal approximation algorithms, several intriguing mathematical questions emerged. The talk will explore these connections and highlight applications of the developed techniques in areas such as complexity theory, property testing, and additive combinatorics. I will also present a new approximation algorithm for a class of CSPs that non-trivially combines two distinct algorithmic techniques: Gaussian elimination for solving a system of linear equations and semidefinite programming relaxation. I will conclude by outlining future directions toward resolving the central question of CSP approximability.

Bio: Amey Bhangale is an Assistant Professor in the Computer Science Department at the University of California, Riverside. He received his Ph.D. degree from Rutgers University under the guidance of Swastik Kopparty. Before joining UC Riverside, he spent two years in Israel where he was a postdoctoral fellow at the Weizmann Institute of Science, hosted by Irit Dinur. He also spent a semester as a research fellow at the Simons Institute for theory of computing, Berkeley. He is interested in approximation algorithms, hardness of approximation and the analysis of Boolean functions.