- 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.
Randomized Algorithms, Computational Complexity, Private Data Analysis
- 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.
- 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)
- 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.
- 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.
- 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.