Sofya Raskhodnikova

My research interests include sublinear-time algorithms (in particular, property testing), private data analysis, approximation algorithms, randomized algorithms, computational geometry, coding theory and complexity theory. I got my PhD from MIT in 2003. From the fall of 2003 to 2006, I worked at the Hebrew University of Jerusalem, the Weizmann Institute of Science and the Institute for Pure and Applied Mathematics. If you are interested in joining our CSE graduate program, please look at http://www.cse.psu.edu/academics/graduate/ for information on admission and a description of the program. Research assistanships are available for strong candidates interested in working in theory.

Courses

• CMPSC 464 Introduction to the Theory of Computation, Fall 2008
• CSE 598B Theory of Computation, Spring 2008
• CSE 565 Algorithm Design and Analysis, Fall 2007
• CSE 597A Theory Seminar can now be taken and repeated for credit, Fall 2007
• CSE 465 Data Structures and Algorithms, Spring 2007
• Sublinear Algorithms Course, Weizmann Institute, Spring 2005. (The web page has been disactivated.)

Professional activities

• program Committee for RANDOM 2007 (August 20--22, 2007, Princeton University).

Publications

• Transitive-Closure Spanners, Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David Woodruff, accepted to SODA09.
• What Can We Learn Privately? Shiva Kasiviswanathan, Homin Lee, Kobbi Nissim, Sofya Raskhodnikova, Adam Smith, accepted to FOCS08.
• Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem, Sofya Raskhodnikova, Dana Ron, Amir Shpilka, Adam Smith, Proceedings of the 48th IEEE FOCS, 559--569, 2007. (PDF)
• Smooth sensitivity and sampling in private data analysis, Kobbi Nissim, Sofya Raskhodnikova, Adam Smith, Proceedings of the 39th ACM STOC, 75--84, 2007. (PDF) Slides
• Sublinear Algorithms for Approximating String Compressibility, Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Adam Smith, Proceedings of the 11th RANDOM, 609--623, 2007. (PDF) Slides
• A Note on Adaptivity in Testing Properties of Bounded Degree Graphs, Sofya Raskhodnikova and Adam Smith, Electronic Colloquium on Computational Complexity, TR06--089, 2006. (PDF)
• Sublinear Algorithms for Approximating String Compressibility and the Distribution Support Size, Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Amir Shpilka, and Adam Smith, Electronic Colloquium on Computational Complexity, TR05--125, 2005. (PDF)
• Some 3CNF Properties are Hard to Test, Eli Ben-Sasson, Prahladh Harsha, Sofya Raskhodnikova, SIAM Journal on Computing, 35(1):1--21, 2005. (PDF). Preliminary version (PDF) appeared in Proceedings of the 35th ACM STOC, 345--354, 2003. Slides
• Property Testing: Theory and Applications, PhD Thesis, Massachusetts Institute of Technology, Cambridge, MA, 2003. (PDF)
• Approximate Testing of Visual Properties, Sofya Raskhodnikova, Proceedings of the 7th RANDOM, Springer-Verlag, 370--381, 2003. (PDF) Slides
• A Sublinear Algorithm for Weakly Approximating Edit Distance, Tugkan Batu, Funda Ergun, Joe Kilian, Avner Magen, Sofya Raskhodnikova, Ronitt Rubinfeld, and Rahul Sami, Proceedings of the 35th ACM STOC, 316--324, 2003. (PDF)
• Lower Bounds for Embedding of Edit Distance into Normed Spaces, Alexandr Andoni, Michael Deza, Anupam Gupta, Piotr Indyk, and Sofya Raskhodnikova, Proceedings of the 14th ACM-SIAM SODA, 523--526, 2003. (PDF)
• Monotonicity Testing Over General Poset Domains, Eldar Fischer, Eric Lehman, Ilan Newman, Sofya Raskhodnikova, Ronitt Rubinfeld, and Alex Samorodnitsky, Proceedings of the 34th ACM STOC, 474--483, 2002. (PDF)
• Improved Testing Algorithms for Monotonicity, Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, and Alex Samorodnitsky, Proceedings of the 3rd RANDOM conference, 97--108, 1999. (PDF) Slides
• Monotonicity Testing, Master's Thesis, Massachusetts Institute of Technology, Cambridge, MA, 1999. (PDF)

Contact Information

• Email: first-name "at" cse.psu.edu
• Office telephone: +1-814-863-0608

• Department of Computer Science and Engineering
  The Pennsylvania State University
  343F Information Sciences and Technology Building
  University Park, PA 16803
  

How To Pronounce My Name

• Sofya: There are two syllables.
  • The first one sounds like Soft without the last sound.
  • The second, ya, sounds like German "yes".
  The stress is on the first syllable. Sophia is not a correct pronounciation of my name. (There are both versions in Russian, Sofya and Sophia, but my name is not Sophia.)
• Raskhodnikova: The only tricky part is that the first "k" is silent.
  • Ras
  • hod (stressed, the first sound as in "hat")
  • ni
  • ka
  • va