Xi Chen Wins Both 2021 Gödel Prize and Fulkerson Prize

Xi Chen, associate professor of computer science, is one of a small number of researchers to be awarded two highly prestigious honors—the 2021 Gödel Prize and the 2021 Fulkerson Prize—in one year. He and his long-time collaborator Jin-Yi Cai, a professor at the University of Wisconsin–Madison, won the prizes for their paper, Complexity of Counting CSP with Complex Weights.

Chen works on complexity theory, which classifies and compares the difficulty of problems or how efficiently they can be solved by algorithms and helps determine the limits of what a computer can and cannot do: the problems that computers can solve efficiently are considered easy, while others that cannot be solved efficiently are hard. For example, suppose you have two gigantic numbers, each one so enormous that it would take a full page to just write down. A modern computer can multiply those two numbers in a fraction of a second because multiplication is an “easy” problem—computer scientists have efficient methods, called algorithms, to do the multiplication.

But suppose you are given a gigantic number and the problem is to factor the number, i.e. figure out whether it can be expressed by multiplying together two smaller numbers and if so find those smaller numbers. Even if all of the world’s fastest computers were put to work on this problem, they could not solve this problem in millions of years, if ever—factoring seems to be an extremely hard problem for which researchers do not yet have efficient algorithms. In fact, computer science (CS) theorists do not believe they exist. Complexity theorists like Chen study this kind of phenomenon, sometimes spending years looking for solutions.

But, says Chen, “Sometimes a ‘Eureka moment’ occurs during a walk or when I am relaxing. That is when I know that I am close to finding the solution to a research problem.”

Chen had a major Eureka moment about a decade ago which led to two CS theory awards this past year for his work on complexity theory. For the groundbreaking paper, Complexity of Counting CSP with Complex Weights, Chen and his long-time collaborator Jin-Yi Cai, a professor at the University of Wisconsin–Madison, were awarded the 2021 Gödel Prize and the 2021 Fulkerson Prize.

“It’s a tremendous badge of honor to receive either one of these awards,” said Rocco Servedio, a CS professor who also works with Chen in the department’s Theory Group. CS and CS theory at Columbia are on a roll—the department’s theory group is now in U.S. News & World Report’s  top 10. The group, which has grown a good deal in recent years, includes a broad and deep group of faculty across many branches of CS theory, along with a very strong cohort of graduate students and postdocs.

“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.