Improved Testing Algorithms for Monotonicity. - Yevgeniy Dodis; Oded Goldreich 001; Eric Lehman; Sofya Raskhodnikova; Dana Ron; Alex Samorodnitsky (Electron. Colloquium Comput. Complex., 1999)

Monotonicity testing over general poset domains. - Eldar Fischer; Eric Lehman; Ilan Newman; Sofya Raskhodnikova; Ronitt Rubinfeld; Alex Samorodnitsky (STOC, 2002)

Approximate Testing of Visual Properties. - Sofya Raskhodnikova (RANDOM-APPROX, 2003)

Lower bounds for embedding edit distance into normed spaces. - Alexandr Andoni; Michel Deza; Anupam Gupta 001; Piotr Indyk; Sofya Raskhodnikova (SODA, 2003)

A sublinear algorithm for weakly approximating edit distance. - Tugkan Batu; Funda Ergün; Joe Kilian; Avner Magen; Sofya Raskhodnikova; Ronitt Rubinfeld; Rahul Sami (STOC, 2003)

3CNF Properties are Hard to Test - Eli Ben-Sasson; Prahladh Harsha; Sofya Raskhodnikova (Electron. Colloquium Comput. Complex., 2003)

Property testing: theory and applications. - Sofya Raskhodnikova (2003)

Sublinear Algorithms for Approximating String Compressibility and the Distribution Support Size - Sofya Raskhodnikova; Dana Ron; Ronitt Rubinfeld; Amir Shpilka; Adam D. Smith 001 (Electron. Colloquium Comput. Complex., 2005)

Some 3CNF Properties Are Hard to Test. - Eli Ben-Sasson; Prahladh Harsha; Sofya Raskhodnikova (SIAM J. Comput., 2005)

A Note on Adaptivity in Testing Properties of Bounded Degree Graphs. - Sofya Raskhodnikova; Adam D. Smith 001 (Electron. Colloquium Comput. Complex., 2006)

Smooth sensitivity and sampling in private data analysis. - Kobbi Nissim; Sofya Raskhodnikova; Adam D. Smith 001 (STOC, 2007)

Transitive-Closure Spanners of the Hypercube and the Hypergrid. - Arnab Bhattacharyya 001; Elena Grigorescu; Kyomin Jung; Sofya Raskhodnikova; David P. Woodruff (Electron. Colloquium Comput. Complex., 2009)

Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem. - Sofya Raskhodnikova; Dana Ron; Amir Shpilka; Adam D. Smith 001 (SIAM J. Comput., 2009)

Finding Sparser Directed Spanners. - Piotr Berman; Sofya Raskhodnikova; Ge Ruan (FSTTCS, 2010)

Transitive-Closure Spanners: A Survey. - Sofya Raskhodnikova (Property Testing, 2010)

Steiner Transitive-Closure Spanners of d-Dimensional Posets - Piotr Berman; Arnab Bhattacharyya 001; Elena Grigorescu; Sofya Raskhodnikova; David P. Woodruff; Grigory Yaroslavtsev (CoRR, 2010)

Improved Approximation for the Directed Spanner Problem. - Piotr Berman; Arnab Bhattacharyya 001; Konstantin Makarychev; Sofya Raskhodnikova; Grigory Yaroslavtsev (ICALP (1), 2011)

Private Analysis of Graph Structure. - Vishesh Karwa; Sofya Raskhodnikova; Adam D. Smith 001; Grigory Yaroslavtsev (Proc. VLDB Endow., 2011)

What Can We Learn Privately? - Shiva Prasad Kasiviswanathan; Homin K. Lee; Kobbi Nissim; Sofya Raskhodnikova; Adam D. Smith 001 (SIAM J. Comput., 2011)

Learning pseudo-Boolean k-DNF and Submodular Functions - Sofya Raskhodnikova; Grigory Yaroslavtsev (CoRR, 2012)

Limitations of Local Filters of Lipschitz and Monotone Functions. - Pranjal Awasthi; Madhav Jha; Marco Molinaro 001; Sofya Raskhodnikova (Electron. Colloquium Comput. Complex., 2012)

Testing Lipschitz Functions on Hypergrid Domains. - Pranjal Awasthi; Madhav Jha; Marco Molinaro 001; Sofya Raskhodnikova (Electron. Colloquium Comput. Complex., 2012)

Transitive-Closure Spanners. - Arnab Bhattacharyya 001; Elena Grigorescu; Kyomin Jung; Sofya Raskhodnikova; David P. Woodruff (SIAM J. Comput., 2012)

Lower Bounds for Local Monotonicity Reconstruction from Transitive-Closure Spanners. - Arnab Bhattacharyya 001; Elena Grigorescu; Madhav Jha; Kyomin Jung; Sofya Raskhodnikova; David P. Woodruff (SIAM J. Discret. Math., 2012)

Learning pseudo-Boolean k-DNF and submodular functions. - Sofya Raskhodnikova; Grigory Yaroslavtsev (SODA, 2013)

Testing the Lipschitz Property over Product Distributions with Applications to Data Privacy. - Kashyap Dixit; Madhav Jha; Sofya Raskhodnikova; Abhradeep Thakurta (TCC, 2013)

Analyzing Graphs with Node Differential Privacy. - Shiva Prasad Kasiviswanathan; Kobbi Nissim; Sofya Raskhodnikova; Adam D. Smith 001 (TCC, 2013)

Sublinear Algorithms for Approximating String Compressibility. - Sofya Raskhodnikova; Dana Ron; Ronitt Rubinfeld; Adam D. Smith 001 (Algorithmica, 2013)

Lower Bounds for Testing Properties of Functions on Hypergrid Domains. - Eric Blais; Sofya Raskhodnikova; Grigory Yaroslavtsev (Electron. Colloquium Comput. Complex., 2013)

Approximation algorithms for spanner problems and Directed Steiner Forest. - Piotr Berman; Arnab Bhattacharyya 001; Konstantin Makarychev; Sofya Raskhodnikova; Grigory Yaroslavtsev (Inf. Comput., 2013)

Testing and Reconstruction of Lipschitz Functions with Applications to Data Privacy. - Madhav Jha; Sofya Raskhodnikova (SIAM J. Comput., 2013)

Lower Bounds for Testing Properties of Functions over Hypergrid Domains. - Eric Blais; Sofya Raskhodnikova; Grigory Yaroslavtsev (CCC, 2014)

Lp-testing. - Piotr Berman; Sofya Raskhodnikova; Grigory Yaroslavtsev (STOC, 2014)

Steiner transitive-closure spanners of low-dimensional posets. - Piotr Berman; Arnab Bhattacharyya 001; Elena Grigorescu; Sofya Raskhodnikova; David P. Woodruff; Grigory Yaroslavtsev (Comb., 2014)

Approximation Algorithms for Min-Max Generalization Problems. - Piotr Berman; Sofya Raskhodnikova (ACM Trans. Algorithms, 2014)

Constant-Time Testing and Learning of Image Properties. - Piotr Berman; Meiram Murzabulatov; Sofya Raskhodnikova (CoRR, 2015)

Efficient Lipschitz Extensions for High-Dimensional Graph Statistics and Node Private Degree Distributions. - Sofya Raskhodnikova; Adam D. Smith 001 (CoRR, 2015)

Special Issue: APPROX-RANDOM 2013: Guest Editors' Foreword. - Sofya Raskhodnikova; Ola Svensson (Theory Comput., 2015)

Lipschitz Extensions for Node-Private Graph Statistics and the Generalized Exponential Mechanism. - Sofya Raskhodnikova; Adam D. Smith 001 (FOCS, 2016)

Testing Unateness of Real-Valued Functions. - Roksana Baleshzar; Meiram Murzabulatov; Ramesh Krishnan S. Pallavoor; Sofya Raskhodnikova (CoRR, 2016)

On the readability of overlap digraphs. - Rayan Chikhi; Paul Medvedev; Martin Milanic; Sofya Raskhodnikova (Discret. Appl. Math., 2016)

Testing if an Array Is Sorted. - Sofya Raskhodnikova (Encyclopedia of Algorithms, 2016)

Linearity Testing/Testing Hadamard Codes. - Sofya Raskhodnikova; Ronitt Rubinfeld (Encyclopedia of Algorithms, 2016)

Differentially Private Analysis of Graphs. - Sofya Raskhodnikova; Adam D. Smith 001 (Encyclopedia of Algorithms, 2016)

Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps. - Roksana Baleshzar; Deeparnab Chakrabarty; Ramesh Krishnan S. Pallavoor; Sofya Raskhodnikova; C. Seshadhri 001 (Electron. Colloquium Comput. Complex., 2017)

A Lower Bound for Nonadaptive, One-Sided Error Testing of Unateness of Boolean Functions over the Hypercube. - Roksana Baleshzar; Deeparnab Chakrabarty; Ramesh Krishnan S. Pallavoor; Sofya Raskhodnikova; C. Seshadhri 001 (Electron. Colloquium Comput. Complex., 2017)

Parameterized Property Testing of Functions. - Ramesh Krishnan S. Pallavoor; Sofya Raskhodnikova; Nithin Varma 001 (Electron. Colloquium Comput. Complex., 2017)

Brief Announcement: Erasure-Resilience Versus Tolerance to Errors. - Sofya Raskhodnikova; Nithin Varma 001 (ICALP, 2018)

Erasures versus Errors in Local Decoding and Property Testing. - Sofya Raskhodnikova; Noga Ron-Zewi; Nithin Varma 001 (Electron. Colloquium Comput. Complex., 2018)

Erasure-Resilient Property Testing. - Kashyap Dixit; Sofya Raskhodnikova; Abhradeep Thakurta; Nithin Varma 001 (SIAM J. Comput., 2018)

Erasures vs. Errors in Local Decoding and Property Testing. - Sofya Raskhodnikova; Noga Ron-Zewi; Nithin Varma 001 (ITCS, 2019)

The Power and Limitations of Uniform Samples in Testing Properties of Figures. - Piotr Berman; Meiram Murzabulatov; Sofya Raskhodnikova (Algorithmica, 2019)

Approximating the Distance to Monotonicity of Boolean Functions. - Ramesh Krishnan S. Pallavoor; Sofya Raskhodnikova; Erik Waingarten (Electron. Colloquium Comput. Complex., 2019)

Testing convexity of figures under the uniform distribution. - Piotr Berman; Meiram Murzabulatov; Sofya Raskhodnikova (Random Struct. Algorithms, 2019)

Isoperimetric Inequalities for Real-Valued Functions with Applications to Monotonicity Testing. - Hadley Black; Iden Kalemaj; Sofya Raskhodnikova (Electron. Colloquium Comput. Complex., 2020)

Erasure-Resilient Sublinear-Time Graph Algorithms. - Amit Levi; Ramesh Krishnan S. Pallavoor; Sofya Raskhodnikova; Nithin Varma 001 (Electron. Colloquium Comput. Complex., 2020)

Special Section on the Fifty-Eighth Annual IEEE Symposium on Foundations of Computer Science (FOCS 2017). - Valentine Kabanets; Sofya Raskhodnikova; Chaitanya Swamy (SIAM J. Comput., 2020)

Bipartite graphs of small readability. - Rayan Chikhi; Vladan Jovicic; Stefan Kratsch; Paul Medvedev; Martin Milanic; Sofya Raskhodnikova; Nithin Varma 001 (Theor. Comput. Sci., 2020)

Differential Privacy from Locally Adjustable Graph Algorithms: k-Core Decomposition, Low Out-Degree Ordering, and Densest Subgraphs. - Laxman Dhulipala; Quanquan C. Liu; Sofya Raskhodnikova; Jessica Shi 001; Julian Shun; Shangdi Yu (FOCS, 2022)

Tolerant Testers of Image Properties. - Piotr Berman; Meiram Murzabulatov; Sofya Raskhodnikova (ACM Trans. Algorithms, 2022)

The Price of Differential Privacy under Continual Observation. - Palak Jain 004; Sofya Raskhodnikova; Satchit Sivakumar; Adam D. Smith 001 (ICML, 2023)

Counting Distinct Elements in the Turnstile Model with Differential Privacy under Continual Observation. - Palak Jain 004; Iden Kalemaj; Sofya Raskhodnikova; Satchit Sivakumar; Adam Smith 006 (NeurIPS, 2023)

Node-Differentially Private Estimation of the Number of Connected Components. - Iden Kalemaj; Sofya Raskhodnikova; Adam D. Smith 001; Charalampos E. Tsourakakis (PODS, 2023)

Local Lipschitz Filters for Bounded-Range Functions. - Jane Lange; Ephraim Linder; Sofya Raskhodnikova; Arsen Vasilyan (CoRR, 2023)

Sublinear-Time Computation in the Presence of Online Erasures. - Iden Kalemaj; Sofya Raskhodnikova; Nithin Varma 001 (Theory Comput., 2023)

Property Testing with Online Adversaries. - Omri Ben-Eliezer; Esty Kelman; Uri Meir; Sofya Raskhodnikova (ITCS, 2024)

The Role of Local Algorithms in Privacy (Invited Talk). - Sofya Raskhodnikova (STACS, 2024)

Fully Dynamic Graph Algorithms with Edge Differential Privacy. - Sofya Raskhodnikova; Teresa Anna Steiner (CoRR, 2024)

Testing Connectedness of Images. - Piotr Berman; Meiram Murzabulatov; Sofya Raskhodnikova; Dragos-Florian Ristache (Algorithmica, 2024)

Online Versus Offline Adversaries in Property Testing. - Esty Kelman; Ephraim Linder; Sofya Raskhodnikova (ITCS, 2025)

Local Lipschitz Filters for Bounded-Range Functions with Applications to Arbitrary Real-Valued Functions. - Jane Lange; Ephraim Linder; Sofya Raskhodnikova; Arsen Vasilyan (SODA, 2025)

Privately Evaluating Untrusted Black-Box Functions. - Ephraim Linder; Sofya Raskhodnikova; Adam Smith 006; Thomas Steinke 002 (STOC, 2025)

Triangle Counting With Local Edge Differential Privacy. - Talya Eden; Quanquan C. Liu; Sofya Raskhodnikova; Adam D. Smith 001 (Random Struct. Algorithms, 2025)

Differentially Private Sampling from Distributions. - Sofya Raskhodnikova; Satchit Sivakumar; Adam Smith 006; Marika Swanberg (SIAM J. Comput., 2025)

Fully Dynamic Algorithms for Graph Databases with Edge Differential Privacy. - Sofya Raskhodnikova; Teresa Anna Steiner (Proc. ACM Manag. Data, 2025)