Photo of Sofya Raskhodnikova

Sofya Raskhodnikova

Adjunct Professor

Affiliation(s):

  • School of Electrical Engineering and Computer Science

W314 Information Sciences and Technology Building

sxr48@psu.edu

814-863-0608

Research Areas:

Interest Areas:

Theoretical computer science: sublinear-time algorithms (in particular, property testing), private data analysis, approximation algorithms, randomized algorithms and complexity theory.

 
 

 

Education

  • BS, Mathematics with Computer Science, Massachusetts Institute of Technology, 1997
  • MS, Computer Science, Massachusetts Institute of Technology, 1999
  • Ph D, Computer Science, Massachusetts Institute of Technology, 2003

Publications

Book, Chapters

  • Sofya Raskhodnikova, 2010, Transitive-Closure Spanners: A Survey, pp. 167–196

Journal Articles

  • Rayan Chikhi, Paul Medvedev, Martin Milanic and Sofya Raskhodnikova, 2016, "On the Readability of Overlap Diagraphs", Discrete Applied Mathematics, 205, pp. 35-44
  • Pranjal Awasthi, Madhav Jha, Marco Molinaro and Sofya Raskhodnikova, 2016, "Testing Lipschitz Functions on Hypergrid Domains", Algorithmica, 74, (3), pp. 1055–1081
  • Pranjal Awasthi, Madhav Jha, Marco Molinaro and Sofya Raskhodnikova, 2014, "Limitations of Local Filters of Lipschitz and Monotone Functions", ACM Transactions on Computation Theory, 7, (1), pp. 2
  • Piotr Berman and Sofya Raskhodnikova, 2014, "Approximation Algorithms for Min-Max Generalization Problems", ACM Transactions on Algorithms, 11, (1), pp. 5
  • Vishesh Karwa, Sofya Raskhodnikova, Adam D Smith and Grigory Yaroslavtsev, 2014, "Private Analysis of Graph Structure", ACM Trans. Database Syst., 39, (3), pp. 22
  • Piotr Berman, Arnab Bhattacharyya, Elena Grigorescu, Sofya Raskhodnikova, David P. Woodruff and Grigory Yaroslavtsev*, 2014, "Steiner transitive-closure spanners of low-dimensional posets", Combinatorica, 34, (3), pp. 255–277
  • Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld and Adam D Smith, 2013, "Sublinear Algorithms for Approximating String Compressibility", Algorithmica, 65, (3), pp. 685–709
  • Piotr Berman, Arnab Bhattacharyya, Konstantin Makarychev, Sofya Raskhodnikova and Grigory Yaroslavtsev, 2013, "Approximation algorithms for spanner problems and Directed SteinerForest", Information and Computation (ICALP 2011 Special Issue), 222, pp. 93–107
  • Madhav Jha and Sofya Raskhodnikova, 2013, "Testing and Reconstruction of Lipschitz Functions with Applicationsto Data Privacy", SIAM Journal on Computing, 42, (2), pp. 700–731
  • Arnab Bhattacharyya, Elena Grigorescu, Madhav Jha*, Kyomin Jung, Sofya Raskhodnikova and David P. Woodruff, 2012, "Lower Bounds for Local Monotonicity Reconstruction from Transitive-ClosureSpanners", SIAM Journal on Discrete Mathematics, 26, (2), pp. 618–646
  • Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova and David P. Woodruff, 2012, "Transitive-Closure Spanners", SIAM Journal on Computing, 41, (6), pp. 1380–1425
  • Shiva Prasad Kasiviswanathan*, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova and Adam D Smith, 2011, "What Can We Learn Privately?", SIAM Journal on Computing, 40, (3), pp. 793–826
  • Sofya Raskhodnikova, Dana Ron, Amir Shpilka and Adam D Smith, 2009, "Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem", SIAM Journal on Computing, 39, (3), pp. 813–842
  • Eli Ben-Sasson, Prahladh Harsha and Sofya Raskhodnikova, 2005, "Some 3CNF Properties Are Hard to Test", SIAM Journal on Computing, 35, (1), pp. 1–21

Conference Proceedings

  • Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova and Nithin Varma, 2017, "Parameterized Property Testing of Functions"
  • Piotr Berman, Meiram Murzabulatov and Sofya Raskhodnikova, 2016, "The Power and Limitations of Uniform Samples in Testing Properties of Figures"
  • Sofya Raskhodnikova and Adam D Smith, 2016, "Lipschitz Extensions for Node-Private Graph Statistics and the Generalized Exponential Mechanism"
  • Kashyap Dixit, Sofya Raskhodnikova, Abhradeep Thakurta and Nithin Varma, 2016, "Erasure-Resilient Property Testing"
  • Piotr Berman, Meiram Murzabulatov and Sofya Raskhodnikova, 2016, "Tolerant Testers of Image Properties"
  • Piotr Berman, M. Murzabulatov and Sofya Raskhodnikova, 2016, "Testing Convexity of Figures Under the Uniform Distribution"
  • Rayan Chikhi, Paul Medvedev, Martin Milanic and Sofya Raskhodnikova, 2015, "On the Readability of Overlap Digraphs", pp. 124–137
  • Eric Blais, Sofya Raskhodnikova and Grigory Yaroslavtsev, 2014, "Lower Bounds for Testing Properties of Functions over Hypergrid Domains", IEEE, pp. 309–320
  • Piotr Berman, Sofya Raskhodnikova and Grigory Yaroslavtsev, 2014, "L_p-testing", ACM, pp. 164–173
  • Shiva Prasad Kasiviswanathan, Kobbi Nissim, Sofya Raskhodnikova and Adam D Smith, 2013, "Analyzing Graphs with Node Differential Privacy", pp. 457–476
  • Kashyap Dixit, Madhav Jha, Sofya Raskhodnikova and Abhradeep Thakurta, 2013, "Testing the Lipschitz Property over Product Distributions with Applicationsto Data Privacy", pp. 418–436
  • Sofya Raskhodnikova and Grigory Yaroslavtsev, 2013, "Learning pseudo-Boolean k-DNF and submodular functions", pp. 1356–1368
  • Pranjal Awasthi, Madhav Jha*, Marco Molinaro and Sofya Raskhodnikova, 2012, "Limitations of Local Filters of Lipschitz and Monotone Functions", pp. 374–386
  • Pranjal Awasthi, Madhav Jha*, Marco Molinaro and Sofya Raskhodnikova, 2012, "Testing Lipschitz Functions on Hypergrid Domains", pp. 387–398
  • Madhav Jha* and Sofya Raskhodnikova, 2011, "Testing and Reconstruction of Lipschitz Functions with Applicationsto Data Privacy", pp. 433–442
  • Vishesh Karwa, Sofya Raskhodnikova, Adam D Smith and Grigory Yaroslavtsev*, 2011, "Private Analysis of Graph Structure", 4, (11), pp. 1146–1157
  • Piotr Berman, Arnab Bhattacharyya, Konstantin Makarychev, Sofya Raskhodnikova and Grigory Yaroslavtsev*, 2011, "Improved Approximation for the Directed Spanner Problem", pp. 1–12
  • Piotr Berman, Arnab Bhattacharyya, Elena Grigorescu, Sofya Raskhodnikova, David P. Woodruff and Grigory Yaroslavtsev*, 2011, "Steiner Transitive-Closure Spanners of Low-Dimensional Posets", pp. 760–772
  • Piotr Berman, Sofya Raskhodnikova and Ge Ruan*, 2010, "Finding Sparser Directed Spanners", pp. 424–435
  • Arnab Bhattacharyya, Elena Grigorescu, Madhav Jha*, Kyomin Jung, Sofya Raskhodnikova and David P. Woodruff, 2010, "Lower Bounds for Local Monotonicity Reconstruction from Transitive-ClosureSpanners", pp. 448–461
  • Piotr Berman and Sofya Raskhodnikova, 2010, "Approximation Algorithms for Min-Max Generalization Problems", pp. 53–66
  • Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova and David P. Woodruff, 2009, "Transitive-closure spanners", pp. 932–941
  • Shiva Prasad Kasiviswanathan*, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova and Adam D Smith, 2008, "What Can We Learn Privately?", pp. 531–540
  • Sofya Raskhodnikova, Dana Ron, Amir Shpilka and Adam D Smith, 2007, "Strong Lower Bounds for Approximating Distribution Support Size andthe Distinct Elements Problem", pp. 559–569
  • Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld and Adam D Smith, 2007, "Sublinear Algorithms for Approximating String Compressibility", pp. 609–623
  • Kobbi Nissim, Sofya Raskhodnikova and Adam D Smith, 2007, "Smooth sensitivity and sampling in private data analysis", pp. 75–84
  • Sofya Raskhodnikova, 2003, "Approximate Testing of Visual Properties", pp. 370–381
  • Eli Ben-Sasson, Prahladh Harsha and Sofya Raskhodnikova, 2003, "Some 3CNF properties are hard to test", pp. 345–354
  • Tugkan Batu, Funda Ergün, Joe Kilian, Avner Magen, Sofya Raskhodnikova, Ronitt Rubinfeld and Rahul Sami, 2003, "A sublinear algorithm for weakly approximating edit distance", pp. 316–324
  • Alexandr Andoni, Michel Deza, Anupam Gupta, Piotr Indyk and Sofya Raskhodnikova, 2003, "Lower bounds for embedding edit distance into normed spaces", pp. 523–526
  • Eldar Fischer, Eric Lehman, Ilan Newman, Sofya Raskhodnikova, Ronitt Rubinfeld and Alex Samorodnitsky, 2002, "Monotonicity testing over general poset domains", pp. 474–483
  • Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron and Alex Samorodnitsky, 1999, "Improved Testing Algorithms for Monotonicity", pp. 97–108

Technical Reports

  • Sofya Raskhodnikova and Adam D Smith, 2015, "Efficient Lipschitz Extensions for High-Dimensional Graph Statisticsand Node Private Degree Distributions", CoRR, abs/1504.07912
  • Rayan Chikhi, Paul Medvedev, Martin Milanic and Sofya Raskhodnikova, 2015, "On the readability of overlap digraphs", CoRR, abs/1504.04616
  • Piotr Berman, Meiram Murzabulatov and Sofya Raskhodnikova, 2015, "Constant-Time Testing and Learning of Image Properties", CoRR, abs/1503.01363
  • Pranjal Awasthi, Madhav Jha, Marco Molinaro and Sofya Raskhodnikova, 2012, "Testing Lipschitz Functions on Hypergrid Domains", pp. 22
  • Pranjal Awasthi, Madhav Jha*, Marco Molinaro and Sofya Raskhodnikova, 2012, "Limitations of Local Filters of Lipschitz and Monotone Functions", pp. 16
  • Sofya Raskhodnikova and Grigory Yaroslavtsev, 2012, "Learning pseudo-Boolean k-DNF and Submodular Functions", CoRR, abs/1208.2294
  • Madhav Jha and Sofya Raskhodnikova, 2011, "Testing and Reconstruction of Lipschitz Functions with Applicationsto Data Privacy", pp. 26
  • Piotr Berman, Sofya Raskhodnikova and G. Yaroslavtsev*, 2010, "Approximation for Directed Spanners"
  • Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova and Adam D Smith, 2010, "What Can We Learn Privately?", CORR, pp. 35
  • Piotr Berman, Arnab Bhattacharyya, Elena Grigorescu, Sofya Raskhodnikova, David P. Woodruff and Grigory Yaroslavtsev*, 2010, "Steiner Transitive-Closure Spanners of d-Dimensional Posets", CoRR, abs/1011.6100
  • Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova and David P. Woodruff, 2009, "Transitive-Closure Spanners of the Hypercube and the Hypergrid", Electronic Colloquium on Computational Complexity. TR09-046., pp. 20
  • Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova and David P. Woodruff, 2008, "Transitive-Closure Spanners", CoRR, abs/0808.1787, pp. 33
  • Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova and Adam D Smith, 2008, "What Can We Learn Privately?", CoRR, abs/0803.0924
  • Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld and Adam D Smith, 2007, "Sublinear Algorithms for Approximating String Compressibility", CoRR, abs/0706.1084, pp. 25
  • Sofya Raskhodnikova and Adam D Smith, 2006, "A Note on Adaptivity in Testing Properties of Bounded Degree Graphs", Electronic Colloquium on Computational Complexity (ECCC), 13, (089), pp. 6
  • Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Amir Shpilka and Adam D Smith, 2005, "Sublinear Algorithms for Approximating String Compressibility andthe Distribution Support Size", Electronic Colloquium on Computational Complexity. TR05-125., pp. 38
  • Eli Ben-Sasson, Prahladh Harsha and Sofya Raskhodnikova, 2003, "3CNF Properties are Hard to Test", Electronic Colloquium on Computational Complexity. TR03-006., 10, (006), pp. 23
  • Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron and Alex Samorodnitsky, 1999, "Improved Testing Algorithms for Monotonicity", Electronic Colloquium on Computational Complexity. TR99-017., 6, (17), pp. 19

Encyclopedia Entries

  • Sofya Raskhodnikova and Adam D Smith, 2016, "Differentially Private Analysis of Graphs",, Encyclopedia of Algorithms 2016,
  • Sofya Raskhodnikova and Ronitt Rubinfeld, 2016, "Linearity Testing/Testing Hadamard Codes",, Encyclopedia of Algorithms 2016,
  • Sofya Raskhodnik andva, , 2016, "Testing if an Array Is Sorted",, Encyclopedia of Algorithms 2016,

Other

  • Sofya Raskhodnikova and Ola Svensson, 2015, "Special Issue: APPROX-RANDOM 2013: Guest Editors’ Foreword", Theory of Computing, 11, pp. 237–239
  • Eric Blais, Sofya Raskhodnikova and Grigory Yaroslavtsev, 2013, "Lower Bounds for Testing Properties of Functions over Hypergrid Domains", pp. 14

Research Projects

Honors and Awards

  • Computer Science Faculty Marshall, Penn State, CSE Department, May 2016
  • CSE Department Teaching Award, Penn State, CSE Department, 2010
  • Computer Science Faculty Marshall, Penn State, CSE Department, May 2010
  • NSF CAREER Award, National Science Foundation, 2009
  • Ruth and Joel Spira Award for Teaching Excellence, 2007
  • Lady Davis Postdoctoral Fellowship, 2003
  • Award for Excellent Work at RSA, 1999
  • NY Governor's Citation for Academic Excellence, 1994
  • First Place in Belorussian Republican Math Olympiad, 1992

Service

Service to Penn State:

  • Chairperson, Colloquium Committee, August 2016 - July 2017
  • Committee Member, Outreach committee, August 2016 - July 2017
  • Co-Chairperson, Colloquium Committee, August 2015 - July 2016
  • Co-Chairperson, Data Structures and Algorithms Exam, January 2016 - May 2016
  • Co-Chairperson, Data Structures and Algorithms Exam, August 2016 - December 2016
  • Co-Chairperson, Data Structures and Algorithms Exam, August 2015 - December 2015
  • Member, Graduate Committee, August 2007 - July 2013
  • Member, Publications Committee, August 2009 - July 2013
  • Member, Curriculum/ABET Committee, August 2011 - July 2013
  • Member, Sustainability Committee, August 2012 - July 2013
  • Co-Chairperson, Data Structures and Algorithms Exam, January 2012 - May 2012
  • Co-Chairperson, Data Structures and Algorithms Exam, January 2012 - May 2012
  • Co-Chairperson, Data Structures and Algorithms Exam, August 2011 - December 2011
  • Chairperson, Theory Lab Equipment Committee, August 2009 - July 2010
  • Organizer, Junior Faculty Lunches, August 2009 - August 2010
  • Co-Chairperson, Data Structures and Algorithms Exam, August 2009 - December 2009
  • Co-Chairperson, Data Structures and Algorithms Exam, January 2008 - May 2008
  • Co-Chairperson, Data Structures and Algorithms Exam, January 2007 - May 2007
  • Member, Promotion and Tenure Committee, August 2014
  • Advisor, Association of Women in Computing at Penn State, 2011

Service to External Organizations:

  • Organizer, SUBLINEAR 2016, Johns Hopkins University, 2015 - January 2016
  • Member, Program Committee, 2015 - June 2016
  • Co-Organizer, Special Privacy Year (2013-2014), 2013 - 2014
  • Co-Organizer, May 2014
  • Co-Organizer, Sublinear Algorithms 2014, May 2014
  • Co-Organizer, MIT, Mike Fest, October 2014
  • Chairperson, Program Committee, August 2013
  • Member, Program Committee, July 2012
  • Member, Program Committee, October 2012
  • Member, Program Committee, December 2009 - October 2010
  • Member, Program Committee, December 2009 - September 2010
  • Member, Program Committee, January 2010
  • Member, Program Committee, August 2007
 


 

About

The School of Electrical Engineering and Computer Science was created in the spring of 2015 to allow greater access to courses offered by both departments for undergraduate and graduate students in exciting collaborative research in fields.

We offer B.S. degrees in electrical engineering, computer science, computer engineering and data science and graduate degrees (master's degrees and Ph.D.'s) in electrical engineering and computer science and engineering. EECS focuses on the convergence of technologies and disciplines to meet today’s industrial demands.

School of Electrical Engineering and Computer Science

The Pennsylvania State University

207 Electrical Engineering West

University Park, PA 16802

814-863-6740

Department of Computer Science and Engineering

814-865-9505

Department of Electrical Engineering

814-865-7667