Computing Assistant Professors Nick Feamster and Adam Kalai Win Sloan Fellowships

February 25, 2008

Two School of Computer Science faculty members, Nick Feamster in the Networking and Telecommunications Group and GTISC, and Adam Kalai in the Theory Group and ARC ThinkTank, have been awarded the prestigious Alfred P. Sloan fellowships for 2008. Sloan Research Fellowships are awarded by the Alfred P. Sloan Foundation to encourage the work of the very best young faculty members in diverse fields such as Computer Science, Mathematics, Physics, Chemistry, Molecular Biology, Economics, and Neuroscience. The awardees are chosen on the basis of their prior research accomplishments and outstanding promise of making fundamental contributions to their research areas. Thirty-five Sloan Fellows have won Nobel Prizes later in their careers.

Two areas in which Dr. Kalai has made strong contributions are online algorithms and machine learning. In online algorithms, he has contributed a new proof of a stock market strategy called the Universal Portfolio which has led to a polytime algorithm using a biased random walk - a new tool for online algorithms. In the past few years, Adam’s work on the online decision problem has changed the course of the field. Adam discovered an algorithm for the general problem of online linear optimization where costs add up over the sequence: maintain the best solution on the past, on a randomly perturbed version of the data so far. Adam’s proof is so transparent that it has lead to many follow-up papers in a short time. In learning theory, he found a new algorithm for learning parity functions in the presence of random noise. This settles a theoretical question about the power of statistical learning and remains the best-known algorithm for this central problem in learning theory. His algorithm also has a direct application to the classic question of finding the shortest vector in a lattice.

Dr. Feamster’s research agenda is in the area of network operations. He interprets the scope of this research to encompass questions regarding network connectivity such as how to make it robust and how to incentivize it within the context of Internet economics. His research also considers network security as an operational primitive and is concerned with how network monitoring can be used to enhance security. Within these broad research areas, Nick has several important and highly creative research contributions including work on a routing configuration compiler that incorporates program analysis techniques to analyze complex router configurations in a network to predict their behavior; a technique for detecting spam through network traffic monitoring that relies on understanding the network-level behavior of spam and using that signature to detect spam as it is being carried over the network; and an architecture for network virtualization that can provide robust and flexible network connectivity, an idea first proposed by Dr. Feamster as the basis of a future Internet design.

Assistant professors Feamster and Kalai are among the 16 recipients of the award for Computer Science this year. The award carries a two-year, $50,000 grant for the faculty to spend on their respective research interests. Previous recipients of the fellowship at the College of Computing include distinguished professor Santosh Vempala, assistant professor Subhash Khot, associate professor Beth Mynatt, and associate professor Dana Randall.

About Nick Feamster:

About Adam Kalai:

About Sloan Fellowships:

List of this year's awardees: