Sofya Raskhodnikova

My research interests include sublinear-time algorithms (in particular, property testing), private data analysis, approximation algorithms, randomized algorithms 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 assistantships 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 starting from Spring or Fall 2012, email me. We are looking for strong candidates interested in data privacy. The position can be at Penn State only or joint with CMU, co-mentored with Sesa Slavkovic (PSU), Adam Smith (PSU) and/or Steve Fienberg (CMU).

Courses

• CSE 598A Sublinear Algorithms, Spring 2012
• CSE 565 Algorithm Design and Analysis, Fall 2007 and 2011
• CMPSC 464 Introduction to the Theory of Computation, Fall 2008, 2009 and 2010
• CSE 598A Algorithmic Aspects of Data Privacy, Spring 2010
• CSE 598B Theory of Computation, Spring 2008
• CSE 597A Theory Seminar can 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

• Lecturer for 2011 Program for Women and Mathematics (Institute for Advanced Study), a course on sublinear algorithms
  Slides: Lecture 1, Lecture 2, Lecture 3, Lecture 4
• Program committee member for
  • FOCS 2012
  • SWAT 2012 (submission deadline: February 24, 2012, conference: July 4 -6, 2012, Helsinki, Finland)
    Note: This year, sublinear algorithms are explicitly in the call for papers.
  • FOCS 2010 (October 23-26, 2010, Las Vegas, Nevada)
  • RANDOM 2010 (September 1-3, 2010, Barcelona)
  • SODA 2010 (January 17--19, 2010, Austin,Texas)
  • RANDOM 2007 (August 20--22, 2007, Princeton University)

Current Ph.D. Students

• Madhav Jha (also M.S. '10)
• Grigory Yaroslavtsev

First-year Graduate Adviser for

• Ramesh T. Krishnamachari (M.S. '11, supervised by Piotr Berman)
• Ge Ruan
• Huiwen Yu (now Ph.D. student supervised by Martin Furer)

Alumni

• Ishan Behoora, research intern, Spring 2010 (now Ph.D. student supervised by Piotr Berman)
• Olena Melnychenko, research assistant, B.S. '09

Honors and Awards

• Selected as Computer Science faculty marshal by Thomas Conkling, Computer Science student marshal, 2010 (Centre Daily Times article about Tom)
• CSE Department Teaching Award, 2010
• NSF CAREER Award, 2009
• Ruth and Joel Spira Excellence in Teaching Award, 2007
• Lady Davis Postdoctoral Fellowship, 2003
• Award for Excellent Work at RSA, 1999
• NY Governor's Citation for Academic Excellence, 1994
• 1st place in Belorussian Republican Math Olympiad, 1992

Publications

• Testing and Reconstruction of Lipschitz Functions with Applications to Data Privacy, Madhav Jha and Sofya Raskhodnikova. Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2011.
  Preliminary version appeared in Electronic Colloquium on Computational Complexity, TR11-057, 2011. Slides
• What Can We Learn Privately? Shiva Kasiviswanathan, Homin Lee, Kobbi Nissim, Sofya Raskhodnikova, Adam Smith. SIAM Journal on Computing, 40(3), pp. 793-826, 2011 (FOCS 2008 special issue).
  Preliminary version appeared in Proceedings of the 49th IEEE FOCS, 531--540, 2008.
• Private Analysis of Graph Structure, Vishesh Karwa, Sofya Raskhodnikova, Adam Smith, Grigory Yaroslavtsev. Proceedings of the Thirty-Seventh International Conference on Very Large Data Bases (VLDB), 1146--1157, 2011.
• Improved Approximation for the Directed Spanner Problem, Piotr Berman, Arnab Bhattacharyya, Konstantin Makarychev, Sofya Raskhodnikova, Grigory Yaroslavtsev. Invited to Information and Computation (ICALP 2011 special issue).
  Preliminary version appeared in Proceedings of the 38th International Colloquium on Automata, Languages and Programming (ICALP), 1--12, 2011.
• Steiner Transitive-Closure Spanners of Low-Dimensional Posets, Piotr Berman, Arnab Bhattacharyya, Elena Grigorescu, Sofya Raskhodnikova, David Woodruff, Grigory Yaroslavtsev. Proceedings of the 38th International Colloquium on Automata, Languages and Programming (ICALP), 760--772, 2011. Preliminary full version.
• Transitive-Closure Spanners: a Survey, Sofya Raskhodnikova. In O. Goldreich, editor, Property Testing, LNCS 6390, LNCS State-of-the-Art Surveys, Springer, Heidelberg, 167--196, 2010. Slides
• Finding Sparser Directed Spanners, Piotr Berman, Sofya Raskhodnikova, Ge Ruan. Proceedings of the 30th Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 424--435, 2010.
• Lower Bounds for Local Monotonicity Reconstruction from Transitive-Closure Spanners, Arnab Bhattacharyya, Elena Grigorescu, Madhav Jha, Kyomin Jung, Sofya Raskhodnikova, David Woodruff. Proceedings of the 14th RANDOM, Springer-Verlag, 448--461, 2010. Preliminary full version.
• Approximation Algorithms for Min-Max Generalization Problems, Piotr Berman and Sofya Raskhodnikova, Proceedings of the 13th APPROX, Springer-Verlag, 53--66, 2010.
  Preliminary full version. Slides
• Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem, Sofya Raskhodnikova, Dana Ron, Amir Shpilka, Adam Smith, SIAM Journal on Computing, 39(3):813--842, 2009.
  Preliminary version appeared in Proceedings of the 48th IEEE FOCS, 559--569, 2007.
• 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
• Smooth sensitivity and sampling in private data analysis, Kobbi Nissim, Sofya Raskhodnikova, Adam Smith, Proceedings of the 39th ACM STOC, 75--84, 2007. Slides
• Sublinear Algorithms for Approximating String Compressibility, Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Adam Smith, Proceedings of the 11th RANDOM, Springer-Verlag, 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 (unstressed o is pronounced as a in Russian)
  • va