Rocco Anthony Servedio

Computer Science

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.  

  • 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).