Sofya Raskhodnikova

My research interests include sublinear-time algorithms (in particular, property testing), private data analysis, approximation algorithms, randomized algorithms, coding theory and complexity theory. I am a member of the theory group. 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 algorithms and theory. Make sure to indicate "algorithms" or "theoretical computer science" or the name of a faculty member you are interested in working with if you want our group to consider you. Our department receives many applications, and I cannot review all of them personally.

New! If you are interested in a postdoc position, email me.

Courses

• CMPSC 464 Introduction to the Theory of Computation, Fall 2008 and 2009
• 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 and 2009
• 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 memeber for
  • RANDOM 2007 (August 20--22, 2007, Princeton University)
  • SODA 2010 (January 17--19, 2010, Austin,Texas)

Current Students

• Madhav Jha, Ph.D. in progress
• Huiwen Yu, Ph.D. in progress

Alumni

• Olena Melnychenko, research assistant, B.S. '09

Awards

• NSF CAREER Award, 2009
• Ruth and Joel Spira Excellence in Teaching Award, 2007
• Lady Davis Postdoctoral Fellowship, 2003
• Award for Excellent Work at RAS, 1999
• NY Governor's Citation for Academic Excellence, 1994
• 1st place in Belorussian Republican Math Olympiad, 1992

Publications

• Transitive-Closure Spanners of the Hypercube and the Hypergrid, Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David Woodruff, Electronic Colloquium on Computational Complexity, TR09--046, 2009.
• Transitive-Closure Spanners, Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David Woodruff, Proceedings of the 20th ACM-SIAM SODA, 531--540, 2009. Preliminary full version. Slides
• What Can We Learn Privately? Shiva Kasiviswanathan, Homin Lee, Kobbi Nissim, Sofya Raskhodnikova, Adam Smith, Proceedings of the 49th IEEE FOCS, 559--569,2008. Invited to SIAM Journal on Computing (FOCS special issue). Preliminary full version.
• 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). Full version accepted to SIAM Journal on Computing. Preliminary full version.
• 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