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