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

About the Study

Conference: IEEE Symposium on Security and Privacy, presented May 22-25, 2022, San Francisco.

Title: Differential Privacy and Swapping: Examining De-Identication’s Impact on Minority Representation and Privacy Preservation in the U.S. Census.

Authors: Miranda Christ (Columbia University), Sarah Radway (Tufts University- formerly Columbia University), Steven M. Bellovin (Columbia University)

This research was supported in part by the U.S. Department of Energy (DOE), Office of Science, Office of Advanced Scientific Computing Research under award number DE-SC-0001234, a Google Faculty Grant, NSF grants CNS-1923528 and CCF-2107187, a grant from the Columbia-IBM center for Blockchain and Data Transparency, a grant from JPMorgan Chase & Co., and a grant from LexisNexis Risk Solutions.

COI: The authors declare no financial or other conflicts of interest.

Self-awareness in robots

The work is part of Lipson’s decades-long quest to find ways to grant robots some form of self-awareness. “Self-modeling is a primitive form of self-awareness,” he explained. “If a robot, animal, or human has an accurate self-model, it can function better in the world, it can make better decisions, and it has an evolutionary advantage.”

The researchers are aware of the limits, risks, and controversies surrounding granting machines greater autonomy through self-awareness. Lipson is quick to admit that the kind of self-awareness demonstrated in this study is, as he noted, “trivial compared to that of humans, but you have to start somewhere. We have to go slowly and carefully, so we can reap the benefits while minimizing the risks.”

About the Study

Title: Full-Body Visual Self-Modeling of Robot Morphologies

Authors: Boyuan Chen, Robert Kwiatkowski, Carl Vondrick, Hod Lipson

The study was supported by DARPA MTO Lifelong Learning Machines (L2M) Program W911NF-21-2-0071, NSF NRI Award 1925157, NSF AI Institute for Dynamical Systems 2112085, NSF CAREER Award 2046910, and gifts from Facebook Research and Northrop Grumman.

COI: The authors declare no financial or other conflicts of interest.

Researchers at Columbia Engineering have demonstrated a highly dexterous robot hand, one that combines an advanced sense of touch with motor learning algorithms in order to achieve a high level of dexterity. 

As a demonstration of skill, the team chose a difficult manipulation task: executing an arbitrarily large rotation of an unevenly shaped grasped object in hand while always maintaining the object in a stable, secure hold. This is a very difficult task because it requires constant repositioning of a subset of fingers, while the other fingers have to keep the object stable. Not only was the hand able to perform this task, but it also did it without any visual feedback whatsoever, based solely on touch sensing. 

In addition to the new levels of dexterity, the hand worked without any external cameras, so it's immune to lighting, occlusion, or similar issues. And the fact that the hand does not rely on vision to manipulate objects means that it can do so in very difficult lighting conditions that would confuse vision-based algorithms--it can even operate in the dark.

“While our demonstration was on a proof-of-concept task, meant to illustrate the capabilities of the hand, we believe that this level of dexterity will open up entirely new applications for robotic manipulation in the real world,” said Matei Ciocarlie, associate professor in the Departments of Mechanical Engineering and Computer Science. “Some of the more immediate uses might be in logistics and material handling, helping ease up supply chain problems like the ones that have plagued our economy in recent years, and in advanced manufacturing and assembly in factories.”

Leveraging optics-based tactile fingers

Image

In earlier work, Ciocarlie’s group collaborated with Ioannis Kymissis, professor of electrical engineering, to develop a new generation of optics-based tactile robot fingers. These were the first robot fingers to achieve contact localization with sub-millimeter precision while providing complete coverage of a complex multi-curved surface. In addition, the compact packaging and low wire count of the fingers allowed for easy integration into complete robot hands. 

Teaching the hand to perform complex tasks

Image

For this new work, led by CIocarlie’s doctoral researcher, Gagan Khandate, the researchers designed and built a robot hand with five fingers and 15 independently actuated joints--each finger was equipped with the team’s touch-sensing technology. The next step was to test the ability of the tactile hand to perform complex manipulation tasks. To do this, they used new methods for motor learning, or the ability of a robot to learn new physical tasks via practice. In particular, they used a method called deep reinforcement learning, augmented with new algorithms that they developed for effective exploration of possible motor strategies. 

Robot completed approximately one year of practice in only hours of real-time

The input to the motor learning algorithms consisted exclusively of the team’s tactile and proprioceptive data, without any vision. Using simulation as a training ground, the robot completed approximately one year of practice in only hours of real-time, thanks to modern physics simulators and highly parallel processors. The researchers then transferred this manipulation skill trained in simulation to the real robot hand, which was able to achieve the level of dexterity the team was hoping for. Ciocarlie noted that “the directional goal for the field remains assistive robotics in the home, the ultimate proving ground for real dexterity. In this study, we've shown that robot hands can also be highly dexterous based on touch sensing alone. Once we also add visual feedback into the mix along with touch, we hope to be able to achieve even more dexterity, and one day start approaching the replication of the human hand.”

Ultimate goal: joining abstract intelligence with embodied intelligence

Ultimately, Ciocarlie observed, a physical robot being useful in the real world needs both abstract, semantic intelligence (to understand conceptually how the world works), and embodied intelligence (the skill to physically interact with the world). Large language models such as OpenAI’s GPT-4 or Google’s PALM aim to provide the former, while dexterity in manipulation as achieved in this study represents complementary advances in the latter.

For instance, when asked how to make a sandwich, ChatGPT will type out a step-by-step plan in response, but it takes a dexterous robot to take that plan and actually make the sandwich. In the same way, researchers hope that physically skilled robots will be able to take semantic intelligence out of the purely virtual world of the Internet, and put it to good use on real-world physical tasks, perhaps even in our homes.

The paper has been accepted for publication at the Robotics: Science and Systems Conference (Daegu, Korea, July 10-14, 2023), and is currently available as a preprint.

ABOUT THE STUDY

CONFERENCE: Science and Systems Conference (Daegu, Korea, July 10-14, 2023)

STUDY: "Sampling-based Exploration for Reinforcement Learning of Dexterous Manipulation”

AUTHORS: Authors are all from Columbia Engineering: Gagan Khandate and Tristan Luca Saidi (Computer Science), Siqi Shang, Eric Chang, Johnson Adams, and Matei Ciocarlie (Mechanical Engineering). The tactile sensors were developed in collaboration with Ioannis Kymissis (Electrical Engineering).

FUNDING: This work was supported in part by the Office of Naval Research grant N00014-21-1-4010 and the National Science Foundation grant CMMI-2037101.

The authors declare no financial or other conflicts of interest.