Rocco A. Servedio

He has developed algorithms and established lower bounds for learning many fundamental classes of Boolean functions and probability distributions as well as for property testing of such classes.  

His work in concrete computational complexity theory has yielded new lower bounds and state-of-the-art derandomization results for well-studied Boolean circuit models. A core goal that motivates and inspires much of Servedio’s work is to understand the structural properties of different types of Boolean functions using a range of analytic, algebraic, probabilistic, and combinatorial techniques. Beyond identifying and establishing such structural properties, Servedio leverages these properties both to develop efficient solutions to various algorithmic problems (such as computational learning and property testing) and to establish computational hardness (such as circuit lower bounds and pseudorandomness results). Servedio has given state-of-the-art algorithms and hardness results for learning, testing, and derandomizing well-studied Boolean function classes such as DNF formulas, monotone functions, functions with small Fourier sparsity and/or Fourier dimension, constant-depth circuits, linear separators, intersections of halfspaces, polynomial threshold functions, and juntas. His interests also include structural analysis and computational learning and testing of various classes of probability distributions, as well as other data analysis problems.

Servedio received an AB in mathematics summa cum laude from Harvard University in 1993 and a PhD in computer science from Harvard University in 2001.  He is a Sloan Foundation Fellow, a recipient of multiple Best Paper awards from leading conferences in theoretical computer science, and a 2013 recipient of the Columbia University Presidential Teaching Award. He joined the faculty of Columbia Engineering in 2003. 

Research Areas

• Applied and Theoretical Machine Learning
• Artificial Intelligence
• Theoretical Computer Science
• Algorithms
• Sublinear Computation
• Cryptography
• Complexity Theory