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. |

- CSE 597B Theory Seminar can be taken and repeated for credit, Fall 2007 and 2009, Spring 2013
- CMPSC 464 Introduction to the Theory of Computation, Fall 2008, 2009, 2010 and 2012
- CSE 598A Sublinear Algorithms, Spring 2012
- CSE 565 Algorithm Design and Analysis, Fall 2007 and 2011
- 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.)

- RANDOM 2013 (August 21-23 2013, UC Berkeley, California)

- FOCS 2012 (October 20-23, 2012, New Brunswick, New Jersey)
- SWAT 2012 (July 4-6, 2012, Helsinki, Finland)
- 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)

- Meiram Murzabulatov

- Edward Lu

- Madhav Jha (M.S. '10, Ph.D. '13, now a postdoc at Sandia National Labs)
- Grigory Yaroslavtsev (Ph.D. '14, now a postdoc at Brown University)
- Ishan Behoora, research intern, Spring '10
- Olena Melnychenko, research assistant, B.S. '09

- 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

**L**, Piotr Berman, Sofya Raskhodnikova and Grigory Yaroslavtsev. Proceedings of 46th ACM Symposium on the Theory of Computing (STOC), 2014._{p}-testing**Lower Bounds for Testing Properties of Functions on Hypergrid Domains**, Eric Blais, Sofya Raskhodnikova and Grigory Yaroslavtsev. Proceedings of the 29th IEEE Conference on Computational Complexity (CCC), 2014.

Preliminary version appeared in ECCC, TR13-036, 2013.**Analyzing Graphs with Node Differential Privacy**, Shiva Kasiviswanathan, Kobbi Nissim, Sofya Raskhodnikova and Adam Smith. Proceedings of the 10th Theory of Cryptography Conference (TCC), 457-476, 2013.**Slides****Testing the Lipschitz Property over Product Distributions with Applications to Data Privacy**, Kashyap Dixit, Madhav Jha, Sofya Raskhodnikova and Abhradeep Thakurta. Proceedings of the 10th Theory of Cryptography Conference (TCC), 418-436, 2013.**Learning Pseudo-Boolean k-DNF and Submodular Functions**, Sofya Raskhodnikova and Grigory Yaroslavtsev. Proceedings of the 24th ACM-SIAM SODA, 1356-1368, 2013.-
**Testing Lipschitz Functions on Hypergrid Domains**, Pranjal Awasthi, Madhav Jha, Marco Molinaro, Sofya Raskhodnikova. Proceedings of the 15th RANDOM, Springer-Verlag, 387-398, 2012.

Preliminary version appeared in*Electronic Colloquium on Computational Complexity*, TR12-076, 2012. -
**Limitations of Local Filters of Lipschitz and Monotone Functions**, Pranjal Awasthi, Madhav Jha, Marco Molinaro, Sofya Raskhodnikova. Proceedings of the 15th RANDOM, Springer-Verlag, 374-386, 2012.

Preliminary version appeared in*Electronic Colloquium on Computational Complexity*, TR12-075, 2012. -
Testing and Reconstruction of Lipschitz Functions with Applications to Data Privacy, Madhav Jha and Sofya Raskhodnikova.
*SIAM Journal on Computing,*42(2), 700-731, 2013.

Preliminary version appeared in Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), 433-442, 2011.**Slides** **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.**Approximation Algorithms for Spanner Problems and Directed Steiner Forest**, Piotr Berman, Arnab Bhattacharyya, Konstantin Makarychev, Sofya Raskhodnikova, Grigory Yaroslavtsev.*Information and Computation,*222, 93-107, 2013. (ICALP 2011 special issue).

Preliminary version entitled**"Improved Approximation for the Directed Spanner Problem"**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.*SIAM J. Discrete Math.,*26(2), 618-646, 2012.

Preliminary version appeared in Proceedings of the 14th RANDOM, Springer-Verlag, 448-461, 2010. -
**Approximation Algorithms for Min-Max Generalization Problems**, Piotr Berman and Sofya Raskhodnikova, to appear in ACM Transactions on Algorithms.

Preliminary version in Proceedings of the 13th APPROX, Springer-Verlag, 53-66, 2010.**Slides** -
**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,*SIAM Journal on Computing,*41(6), pp. 1380-1425, 2012.

Preliminary version appeared in Proceedings of the 20th ACM-SIAM SODA, 531-540, 2009.

**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. -
**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. -
**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, Algorithmica, Volume 65, Issue 3, pp 685-709, 2013.

Preliminary version appeared in Proceedings of the 11th RANDOM, Springer-Verlag, 609-623, 2007.**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)-
**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)

**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

**Sofya:**There are two syllables.- The first one sounds like
*Soft*without the last sound. - The second,
*ya*, sounds like German "yes".

*Sophia*is not a correct pronounciation of my name. (There are both versions in Russian, Sofya and Sophia, but my name is not Sophia.)- The first one sounds like
**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*