“Chen, in particular, works across a really wide and impressive range of topics within theoretical computer science and does superb work as evidenced by his winning both of these prestigious awards,” Servedio adds. “The Gödel Prize is given to a small number of papers each year, and the Fulkerson Prize is awarded only every three years. Just a handful of people can proudly claim to receive both awards in the same year!”

Chen and Cai proved a deep and difficult result that provides the definitive word on an important class of problems in complexity theory, namely counting constraint satisfaction problems. In trying to answer the central question of whether the computational problem is easy or hard, Chen and Cai proved a dichotomy theorem, giving a particularly complete and thorough answer by characterizing every problem in the class of problems under consideration as either easy or hard. Their paper is the capstone of a major intellectual body of work that has been conducted by many top researchers over the course of 20 years.

Columbia Engineering sat down with Chen to find out more about the award-winning paper and his research process.

What are the things that you look for before deciding to pursue a research project?

The project needs to be well-motivated, either by real-world applications or connections with other theoretical problems people care about. You should also feel deeply attached to the problem. A good sign to me is that whenever the brain is idle (during a walk or when you are waiting for something), it is the first thing that jumps out.

What is your process when it comes to research?

I would start by digesting existing techniques, understanding their strengths and weaknesses. After internalizing them in my own language, the hope is to come up with conjectures to attack the problem. Usually conjectures during the first few (or many) rounds would be disproved, which in the process could help inform the formulation of new conjectures that lead to new lines of attack on the problem. 

What do you like most about research?

I guess it has to be the Eureka moment. However, such moments are rare and they build on many hours of discussions and hard work. For some projects, they may never arrive.

What is your paper about? How would you describe it? 

Imagine there is a big island full of flowers. Jin-Yi Cai and I set out to prove that every flower on this island is either red or yellow. 

We were interested in a general family of counting problems where the two colors correspond to the two cases when a problem is either efficiently solvable (in polynomial time) or intractable. 

Just like some flowers are neither red nor yellow in the world, we know there are problems that do not fall in any of these two cases (under standard complexity assumptions). However, it turns out that for this particular #CSP island, every problem can be classified into one of these two cases (either efficiently solvable or intractable).

How did you come up with the research? 

We just finished working on a dichotomy theorem for the family of counting graph homomorphisms with complex weights (which can be viewed as special cases of #CSP with a single symmetric binary constraint). Jin-Yi and I believed that some of the techniques we developed in the graph homomorphism paper (jointly with my other long-time collaborator Pinyan Lu) for dealing with complex weights might help advance the line of work on #CSP from Boolean weights to complex weights. So, we looked at the research that has been done and figured out how we can advance it. In hindsight, I feel that my training in this area is mainly based on the writing of this very long (over 100 pages) graph homomorphism paper.

What do you hope to contribute to the field of complexity theory?

The paper, together with the other two papers that received the 2021 Gödel Prize, is the culmination of a large body of work on the complexity classification of #CSPs. Constraint satisfaction problems are of central importance in computer science. Our work gives a dichotomy theorem for the most general setting of their counting versions with complex weights. It covers a broad range of problems studied in not only computer science but also other sciences including statistical physics.