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", pp. 45:1-45:14

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

Other

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

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

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

Service to Penn State:

Service to External Organizations: