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

Carlos Paz-Soldan, an associate professor of applied physics and applied mathematics, enraptured alumni attendees with a century of rising and falling interest and research in harnessable nuclear fusion—a promising frontier in the increasingly widespread conversation around energy—and Columbia’s continued role at the forefront.

The next day was an invigorating discussion on generative artificial intelligence tools like OpenAI’s ChatGPT, offered to a full-capacity audience of alumni and their families by Kathleen McKeown, Henry and Gertrude Rothschild Professor of Computer Science.

Finally, shedding light on how the landmark CHIPS Act is set to redefine the future of semiconductor technology, Harish Krishnaswamy, associate professor of electrical engineering, gave alumni an exclusive glimpse into the game-changing developments set to shape the world of technology as we know it.

Dean Chang’s State of the School Address

Image

On Saturday, Dean Chang gave a State of the School address to attendees with exciting new updates on the School and plans for the future. Highlights included recent faculty and alumni awards, a review of Class Day and Commencement, and funding wins for new multi-partner centers based at Columbia Engineering such as ARNI, the AI Institute for Artificial and Natural Intelligence. Dean Chang also unveiled Columbia+, a new lifelong learning online platform open to alumni that features online courses, live-streamed and recorded events, and podcasts from across Columbia’s schools and Global Centers. He closed with a look ahead at Columbia’s expansion into Manhattanville and plans for a new engineering building focused on advancing the Engineering for Humanity vision. 

Building Bridges

Milestone Class Gatherings

Image

Laughter, anecdotes, and a collective sense of Columbia pride reverberated across campus as alumni volunteers and staff brought former classmates together to celebrate their milestone graduation anniversaries. View class photos. 

Chelsea Piers Reception

Image

Back by popular demand for its second year, the Chelsea Piers Reception saw generations of alumni bring the dance floor to life. Enjoying floor-to-ceiling views of the New York City skyline, alumni of each of the undergraduate schools mingled and relished in an evening of celebration and connection. View photos.

Engineering Master's and Doctoral Alumni Reception

Image

Unique to Columbia Engineering, which offers world-renowned advanced degree programs in addition to its undergraduate degree programs, this first in-person gathering of its kind brought master’s and doctoral alumni together across a diverse range of industries and academic departments in the hallowed library at the Italian Academy. It was a full and lively room. Dean Chang gave remarks and mingled with alumni. View photos.