Rocco A. Servedio


S.W. Mudd
Mail Code 0401

Tel(212) 939-7065
Fax(212) 666-0140

Rocco A. Servedio is a theoretical computer scientist whose work aims at elucidating the boundary between computationally tractable and intractable problems. 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.  

Research Interests

Theoretical computer science, computational complexity theory, computational learning theory, randomness in computation

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. 


  • Visiting fellow, Princeton University (sabbatical visit), 2009-2010
  • NSF postdoctoral fellow, Harvard University, 2001-2002


  • Professor of computer science, Columbia University, 2017–
  • Vice-chair of computer science, 2012-
  • Interim chair of computer science, Fall 2015
  • Associate professor of computer science, Columbia University, 2007-2016
  • Assistant professor of computer science, Columbia University, 2003-2006


  • Association for Computing Machinery, Special Interest Group on Algorithms and Computation Theory (SIGACT


  • Best Paper Award, 32nd Conference on Computational Complexity (CCC), 2017
  • Best Paper Award, 56th IEEE Symposium on Foundations of Computer Science (FOCS), 2015
  • Presidential Teaching Award, Columbia University, 2013
  • Alfred P. Sloan Foundation Fellowship, 2005
  • NSF CAREER Award, 2004
  • Best Paper Award, 18nd Conference on Computational Complexity (CCC), 2003


  • Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten and Jinyu Xie.  “Settling the query complexity of non-adaptive junta testing,” 32nd Conference on Computational Complexity (CCC), 2017.
  • Toniann Pitassi, Benjamin Rossman, Rocco A. Servedio and Li-Yang Tan.  “Poly-logarithmic Frege depth lower bounds via an expander switching lemma,” 48th ACM Symposium on Theory of Computing (STOC), pp. 644-657 (2016).
  • Benjamin Rossman, Rocco A. Servedio and Li-Yang Tan.  “An average-case depth hierarchy theorem for Boolean circuits,” 56th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 1030-1048 (2015).
  • Clement Canonne, Dana Ron, and Rocco A. Servedio.  “Testing probability distributions using conditional samples,” SIAM Journal on Computing, 44(3), pp. 540-616 (2015). 
  • Philip M. Long and Rocco A. Servedio.  “On the weight of halfspaces over Hamming balls,” SIAM Journal on Discrete Mathematics, 28(3), pp. 1035-1061 (2014).
  • Anindya De, Ilias Diakonikolas, Vitaly Feldman and Rocco A. Servedio.  “Nearly optimal solutions for the Chow Parameters Problem and low-weight approximation of halfspaces,” Journal of the ACM, 61(2), Article 11 (2014).
  • Anindya De and Rocco A. Servedio.  “Efficient deterministic approximate counting for low-degree polynomial threshold functions,” 46th ACM Symposium on Theory of Computing (STOC), pp. 832-841 (2014).
  • Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco A. Servedio and Emanuele Viola.  “Bounded independence fools halfspaces,” SIAM Journal on Computing, 39(8), pp. 3441-3462 (2010).
  • Philip M. Long and Rocco A. Servedio.  “Random classification noise defeats all convex potential boosters,” Machine Learning Journal, 78(3), pp. 287-304 (2010).
  • Adam R. Klivans and Rocco A. Servedio.  “Learning DNF in time 2O(n^(1/3)”, Journal of Computer and System Sciences, 68(2), pp. 303-318 (2003).