Sharad Malik and members of his 2001 lab group won the DAC’s Most Influential Paper Award for developing an algorithm and a software tool to efficiently solve a class of equations that are foundational to many applications in cryptography, artificial intelligence, and hardware, software and network security and verification.
Malik, the George van Ness Lothrop Professor in Engineering, and his group introduced in a 2001 paper an algorithm and a software tool capable of solving complex logic puzzles, known as Boolean Satisfiability problems, enabling more efficient computer chip design and impacting a wide range of other fields. An example of one of these problems, referred to as SATs, is the conundrum of seating 10 people at a dinner party where guest A wants to sit with guest B or C, but B is friends with D, who does not like guest C… When the number of guests increases, the problem becomes exponentially more difficult to solve. Problems in many fields and businesses can be represented as these kinds of puzzles. One of the most prominent influences of Malik’s program is in the chip industry, where SAT problems are used to determine whether or not the computer chip will work correctly in billions of situations, before the chip is built. The project was pioneered as part of the senior thesis project of two undergraduates working in Malik’s group, Conor Madigan and Matthew Moskewitz, both class of 2000. They named the tool Chaff and teamed up with Malik and graduate students Ying Zhao and Lintao Yang to further develop the program and publish the paper.
The publication was selected as the most influential paper of the decade spanning 2000-2010 by the Design Automation Conference (DAC), which is sponsored by the Association for Computing and Machinery and the Institute for Electrical and Electronics Engineers. The award is known as a “test of time award” because it recognizes work that has made a substantial, lasting impact on industry and academia. It is the oldest conference in the field of electronic design automation, and has given an award to one paper for each decade since the 1960s.
Malik joined Princeton faculty in 1991 after earning his doctorate at the University of California Berkeley. He served as the Chair of the Department of Electrical and Computer Engineering at Princeton from 2012-2021 and the Director of Princeton’s Keller Center for Innovation in Engineering Education from 2006-2011.
