Personal tools
You are here: Home People Sofya Raskhodnikova
Sofya Raskhodnikova
Document Actions

Sofya Raskhodnikova

  • Associate Professor
343F IST Building
University Park, PA 16802
Phone: (814) 863-0608


  1. Ph.D., M.I.T.


Sofya Raskhodnikova completed all her university education at M.I.T. She received her Ph.D. in 2003 under the supervision of Michael Sipser. She was awarded a Lady Davis Fellowship at the Hebrew University of Jerusalem for 2003-2004, and then spent two years as a postdoctoral fellow at the Weizmann Institute of Science.

Sofya's areas of research are randomized algorithms and computational complexity. Her main interest is the design and analysis of sublinear-time algorithms for combinatorial problems. Sublinear algorithms produce approximate answers to a question after reading only a small portion of the input. Such algorithms are important for dealing with massive datasets. Sofya's research focus is two-fold: her work (1) gives algorithms and lower bounds for specific problems and (2) identifies classes of problems solvable by sublinear algorithms and problems that are not amenable to sublinear solutions. The specific problems include visual properties of discretized images, edit distance between strings, compressibility of strings and monotonicity of functions. Recently, Sofya also has been working on privacy-preserving methods for publishing aggregate statistical data.

Research Interests:

Randomized Algorithms, Computational Complexity, Private Data Analysis

Selected Publications:

  1. Bhattacharyya, A., E. Grigorescu, K. Jung, S. Raskhodnikova, D. Woodruff.  January 2009.  Transitive-Closure Spanners.  Proceedings of the Twentieth ACM-SIAM Symposium on Discrete Algorithms (SODA 2009).  pp. 531-540.  New York, NY.
  2. Kasiviswanath, S., H. Lee, K. Nissim, S. Raskhodnikova.  November 2008.  What Can We Learn Privately?  Proceedings of the Forty-Ninth Annual IEEE Symposium on Foundations of Computer Science (FOCS 2008).  pp. 559-569.  Atlanta, GA.  (Invited to SIAM Journal on Computing-FOCS Special Issue)
  3. Raskhodnikova, S., D. Ron, A. Shpilka, A. Smith. October 2007. Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem. Proceedings of the Forty-Eighth Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007). Providence, RI.
  4. Nissim, K., S. Raskhodnikova, A. Smith. June 2007. Smooth Sensitivity and Sampling in Private Data Analysis. Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing (STOC 2007). pp. 75-84. San Diego, CA.
  5. Batu, T., F. Ergun, J. Kilian, A. Magen, S. Raskhodnikova, R. Rubinfeld, R. Sami. January 2003. A Sublinear Algorithm for Weakly Approximating Edit Distance. Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing (STOC 2003). pp. 316-324. San Diego, CA.