Photo of Sofya Raskhodnikova

Sofya Raskhodnikova

Adjunct Professor of Computer Science and Engineering

Affiliation(s):

  • School of Electrical Engineering and Computer Science

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

Service

Service to Penn State:

Service to External Organizations:

 


 

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