Sofya Raskhodnikova

144 papers A* 28A 9B 3Misc 2Journal 85Unranked 11

Year	Rank	Type	Title / Venue / Authors
2026	A*	`conf`	Computational Complexity in Property Testing. SODA Renato Ferreira Pinto Jr., Diptaksho Palit, Sofya Raskhodnikova
2026	J	`jnl`	Local Node Differential Privacy. CoRR Sofya Raskhodnikova, Adam D. Smith, Connor Wagaman, Anatoly Zavyalov
2026	J	`jnl`	Node-Differentially Private Estimation of the Number of Connected Components. ACM Trans. Algorithms Iden Kalemaj, Sofya Raskhodnikova, Adam D. Smith, Charalampos E. Tsourakakis
2026	J	`jnl`	Property Testing with Online Adversaries. ACM Trans. Comput. Theory Omri Ben-Eliezer, Esty Kelman, Uri Meir, Sofya Raskhodnikova
2025	J	`jnl`	Computational Complexity in Property Testing. CoRR Renato Ferreira Pinto Jr., Diptaksho Palit, Sofya Raskhodnikova
2025	J	`jnl`	Computational Complexity in Property Testing. Electron. Colloquium Comput. Complex. Renato Ferreira Pinto Jr., Diptaksho Palit, Sofya Raskhodnikova
2025	J	`jnl`	Differentially Private Sampling from Distributions. SIAM J. Comput. Sofya Raskhodnikova, Satchit Sivakumar, Adam Smith, Marika Swanberg
2025	J	`jnl`	Fast Agnostic Learners in the Plane. CoRR Talya Eden, Ludmila Glinskih, Sofya Raskhodnikova
2025	J	`jnl`	Fully Dynamic Algorithms for Graph Databases with Edge Differential Privacy. Proc. ACM Manag. Data Sofya Raskhodnikova, Teresa Anna Steiner
2025	J	`jnl`	Homomorphism Testing with Resilience to Online Manipulations. CoRR Esty Kelman, Uri Meir, Debanuj Nayak, Sofya Raskhodnikova
2025	A*	`conf`	Local Lipschitz Filters for Bounded-Range Functions with Applications to Arbitrary Real-Valued Functions. SODA Jane Lange, Ephraim Linder, Sofya Raskhodnikova, Arsen Vasilyan
2025	A	`conf`	Online Versus Offline Adversaries in Property Testing. ITCS Esty Kelman, Ephraim Linder, Sofya Raskhodnikova
2025	A*	`conf`	Privately Evaluating Untrusted Black-Box Functions. STOC Ephraim Linder, Sofya Raskhodnikova, Adam Smith, Thomas Steinke
2025	J	`jnl`	Privately Evaluating Untrusted Black-Box Functions. CoRR Ephraim Linder, Sofya Raskhodnikova, Adam Smith, Thomas Steinke
2025	J	`jnl`	Triangle Counting With Local Edge Differential Privacy. Random Struct. Algorithms Talya Eden, Quanquan C. Liu, Sofya Raskhodnikova, Adam D. Smith
2024	J	`jnl`	Fully Dynamic Graph Algorithms with Edge Differential Privacy. CoRR Sofya Raskhodnikova, Teresa Anna Steiner
2024	J	`jnl`	Isoperimetric inequalities for real-valued functions with applications to monotonicity testing. Random Struct. Algorithms Hadley Black, Iden Kalemaj, Sofya Raskhodnikova
2024	J	`jnl`	Online versus Offline Adversaries in Property Testing. CoRR Esty Kelman, Ephraim Linder, Sofya Raskhodnikova
2024	A	`conf`	Property Testing with Online Adversaries. ITCS Omri Ben-Eliezer, Esty Kelman, Uri Meir, Sofya Raskhodnikova
2024	J	`jnl`	Testing Connectedness of Images. Algorithmica Piotr Berman, Meiram Murzabulatov, Sofya Raskhodnikova, Dragos-Florian Ristache
2024	A	`conf`	The Role of Local Algorithms in Privacy (Invited Talk). STACS Sofya Raskhodnikova
2023	A*	`conf`	Counting Distinct Elements in the Turnstile Model with Differential Privacy under Continual Observation. NeurIPS Palak Jain, Iden Kalemaj, Sofya Raskhodnikova, Satchit Sivakumar, Adam Smith
2023	J	`jnl`	Counting Distinct Elements in the Turnstile Model with Differential Privacy under Continual Observation. CoRR Palak Jain, Iden Kalemaj, Sofya Raskhodnikova, Satchit Sivakumar, Adam D. Smith
2023	A*	`conf`	Isoperimetric Inequalities for Real-Valued Functions with Applications to Monotonicity Testing. ICALP Hadley Black, Iden Kalemaj, Sofya Raskhodnikova
2023	J	`jnl`	Local Lipschitz Filters for Bounded-Range Functions. CoRR Jane Lange, Ephraim Linder, Sofya Raskhodnikova, Arsen Vasilyan
2023	A*	`conf`	Node-Differentially Private Estimation of the Number of Connected Components. PODS Iden Kalemaj, Sofya Raskhodnikova, Adam D. Smith, Charalampos E. Tsourakakis
2023	J	`jnl`	Node-Differentially Private Estimation of the Number of Connected Components. CoRR Iden Kalemaj, Sofya Raskhodnikova, Adam D. Smith, Charalampos E. Tsourakakis
2023	J	`jnl`	Property Testing with Online Adversaries. CoRR Omri Ben-Eliezer, Esty Kelman, Uri Meir, Sofya Raskhodnikova
2023	J	`jnl`	Sublinear-Time Computation in the Presence of Online Erasures. Theory Comput. Iden Kalemaj, Sofya Raskhodnikova, Nithin Varma
2023	A	`conf`	Testing Connectedness of Images. APPROX/RANDOM Piotr Berman, Meiram Murzabulatov, Sofya Raskhodnikova, Dragos Ristache
2023	J	`jnl`	Testing Connectedness of Images. CoRR Piotr Berman, Meiram Murzabulatov, Sofya Raskhodnikova, Dragos-Florian Ristache
2023	A*	`conf`	The Price of Differential Privacy under Continual Observation. ICML Palak Jain, Sofya Raskhodnikova, Satchit Sivakumar, Adam D. Smith
2023	A*	`conf`	Triangle Counting with Local Edge Differential Privacy. ICALP Talya Eden, Quanquan C. Liu, Sofya Raskhodnikova, Adam Smith
2023	J	`jnl`	Triangle Counting with Local Edge Differential Privacy. CoRR Talya Eden, Quanquan C. Liu, Sofya Raskhodnikova, Adam D. Smith
2022	J	`jnl`	Approximating the distance to monotonicity of Boolean functions. Random Struct. Algorithms Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Erik Waingarten
2022	Misc	`ed.`	Computer Science - Theory and Applications - 17th International Computer Science Symposium in Russia, CSR 2022, Virtual Event, June 29 - July 1, 2022, Proceedings CSR Alexander S. Kulikov, Sofya Raskhodnikova
2022	A*	`conf`	Differential Privacy from Locally Adjustable Graph Algorithms: k-Core Decomposition, Low Out-Degree Ordering, and Densest Subgraphs. FOCS Laxman Dhulipala, Quanquan C. Liu, Sofya Raskhodnikova, Jessica Shi, Julian Shun, Shangdi Yu
2022	J	`jnl`	Differential Privacy from Locally Adjustable Graph Algorithms: k-Core Decomposition, Low Out-Degree Ordering, and Densest Subgraphs. CoRR Laxman Dhulipala, Quanquan C. Liu, Sofya Raskhodnikova, Jessica Shi, Julian Shun, Shangdi Yu
2022	J	`jnl`	Differentially Private Sampling from Distributions. CoRR Sofya Raskhodnikova, Satchit Sivakumar, Adam D. Smith, Marika Swanberg
2022	J	`jnl`	Erasure-Resilient Sublinear-Time Graph Algorithms. ACM Trans. Comput. Theory Amit Levi, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma
2022	A	`conf`	Sublinear-Time Computation in the Presence of Online Erasures. ITCS Iden Kalemaj, Sofya Raskhodnikova, Nithin Varma
2022	J	`jnl`	Tolerant Testers of Image Properties. ACM Trans. Algorithms Piotr Berman, Meiram Murzabulatov, Sofya Raskhodnikova
2021	A*	`conf`	Differentially Private Sampling from Distributions. NeurIPS Sofya Raskhodnikova, Satchit Sivakumar, Adam D. Smith, Marika Swanberg
2021	A	`conf`	Erasure-Resilient Sublinear-Time Graph Algorithms. ITCS Amit Levi, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma
2021	J	`jnl`	Erasures versus errors in local decoding and property testing. Random Struct. Algorithms Sofya Raskhodnikova, Noga Ron-Zewi, Nithin Varma
2021	J	`jnl`	Sublinear-Time Computation in the Presence of Online Erasures. CoRR Iden Kalemaj, Sofya Raskhodnikova, Nithin Varma
2021	J	`jnl`	The Price of Differential Privacy under Continual Observation. CoRR Palak Jain, Sofya Raskhodnikova, Satchit Sivakumar, Adam Smith
2020	A*	`conf`	Approximating the Distance to Monotonicity of Boolean Functions. SODA Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Erik Waingarten
2020	J	`jnl`	Bipartite graphs of small readability. Theor. Comput. Sci. Rayan Chikhi, Vladan Jovicic, Stefan Kratsch, Paul Medvedev, Martin Milanic, Sofya Raskhodnikova, Nithin Varma
2020	J	`jnl`	Erasure-Resilient Sublinear-Time Graph Algorithms. CoRR Amit Levi, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma
2020	J	`jnl`	Erasure-Resilient Sublinear-Time Graph Algorithms. Electron. Colloquium Comput. Complex. Amit Levi, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma
2020	J	`jnl`	Isoperimetric Inequalities for Real-Valued Functions with Applications to Monotonicity Testing. CoRR Hadley Black, Iden Kalemaj, Sofya Raskhodnikova
2020	J	`jnl`	Isoperimetric Inequalities for Real-Valued Functions with Applications to Monotonicity Testing. Electron. Colloquium Comput. Complex. Hadley Black, Iden Kalemaj, Sofya Raskhodnikova
2020	J	`jnl`	Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps. Theory Comput. Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, C. Seshadhri
2020	J	`jnl`	Special Section on the Fifty-Eighth Annual IEEE Symposium on Foundations of Computer Science (FOCS 2017). SIAM J. Comput. Valentine Kabanets, Sofya Raskhodnikova, Chaitanya Swamy
2019	J	`jnl`	Approximating the Distance to Monotonicity of Boolean Functions. CoRR Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Erik Waingarten
2019	J	`jnl`	Approximating the Distance to Monotonicity of Boolean Functions. Electron. Colloquium Comput. Complex. Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Erik Waingarten
2019	A	`conf`	Erasures vs. Errors in Local Decoding and Property Testing. ITCS Sofya Raskhodnikova, Noga Ron-Zewi, Nithin Varma
2019	J	`jnl`	Testing convexity of figures under the uniform distribution. Random Struct. Algorithms Piotr Berman, Meiram Murzabulatov, Sofya Raskhodnikova
2019	J	`jnl`	The Power and Limitations of Uniform Samples in Testing Properties of Figures. Algorithmica Piotr Berman, Meiram Murzabulatov, Sofya Raskhodnikova
2018	Misc	`conf`	Bipartite Graphs of Small Readability. COCOON Rayan Chikhi, Vladan Jovicic, Stefan Kratsch, Paul Medvedev, Martin Milanic, Sofya Raskhodnikova, Nithin Varma
2018	J	`jnl`	Bipartite Graphs of Small Readability. CoRR Rayan Chikhi, Vladan Jovicic, Stefan Kratsch, Paul Medvedev, Martin Milanic, Sofya Raskhodnikova, Nithin Varma
2018	A*	`conf`	Brief Announcement: Erasure-Resilience Versus Tolerance to Errors. ICALP Sofya Raskhodnikova, Nithin Varma
2018	J	`jnl`	Erasure-Resilient Property Testing. SIAM J. Comput. Kashyap Dixit, Sofya Raskhodnikova, Abhradeep Thakurta, Nithin Varma
2018	J	`jnl`	Erasures versus Errors in Local Decoding and Property Testing. Electron. Colloquium Comput. Complex. Sofya Raskhodnikova, Noga Ron-Zewi, Nithin Varma
2018	J	`jnl`	Parameterized Property Testing of Functions. ACM Trans. Comput. Theory Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma
2017	J	`jnl`	A Lower Bound for Nonadaptive, One-Sided Error Testing of Unateness of Boolean Functions over the Hypercube. CoRR Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, C. Seshadhri
2017	J	`jnl`	A Lower Bound for Nonadaptive, One-Sided Error Testing of Unateness of Boolean Functions over the Hypercube. Electron. Colloquium Comput. Complex. Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, C. Seshadhri
2017	A*	`conf`	Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps. ICALP Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, C. Seshadhri
2017	J	`jnl`	Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps. CoRR Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, C. Seshadhri
2017	J	`jnl`	Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps. Electron. Colloquium Comput. Complex. Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, C. Seshadhri
2017	A	`conf`	Parameterized Property Testing of Functions. ITCS Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma
2017	J	`jnl`	Parameterized Property Testing of Functions. Electron. Colloquium Comput. Complex. Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma
2016	—	`ch.`	Differentially Private Analysis of Graphs. Encyclopedia of Algorithms Sofya Raskhodnikova, Adam D. Smith
2016	A*	`conf`	Erasure-Resilient Property Testing. ICALP Kashyap Dixit, Sofya Raskhodnikova, Abhradeep Thakurta, Nithin Varma
2016	J	`jnl`	Erasure-Resilient Property Testing. CoRR Kashyap Dixit, Sofya Raskhodnikova, Abhradeep Thakurta, Nithin Varma
2016	—	`ch.`	Linearity Testing/Testing Hadamard Codes. Encyclopedia of Algorithms Sofya Raskhodnikova, Ronitt Rubinfeld
2016	A*	`conf`	Lipschitz Extensions for Node-Private Graph Statistics and the Generalized Exponential Mechanism. FOCS Sofya Raskhodnikova, Adam D. Smith
2016	J	`jnl`	On the readability of overlap digraphs. Discret. Appl. Math. Rayan Chikhi, Paul Medvedev, Martin Milanic, Sofya Raskhodnikova
2016	A*	`conf`	Testing Convexity of Figures Under the Uniform Distribution. SoCG Piotr Berman, Meiram Murzabulatov, Sofya Raskhodnikova
2016	J	`jnl`	Testing Lipschitz Functions on Hypergrid Domains. Algorithmica Pranjal Awasthi, Madhav Jha, Marco Molinaro, Sofya Raskhodnikova
2016	J	`jnl`	Testing Unateness of Real-Valued Functions. CoRR Roksana Baleshzar, Meiram Murzabulatov, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova
2016	—	`ch.`	Testing if an Array Is Sorted. Encyclopedia of Algorithms Sofya Raskhodnikova
2016	—	`conf`	The Power and Limitations of Uniform Samples in Testing Properties of Figures. FSTTCS Piotr Berman, Meiram Murzabulatov, Sofya Raskhodnikova
2016	A*	`conf`	Tolerant Testers of Image Properties. ICALP Piotr Berman, Meiram Murzabulatov, Sofya Raskhodnikova
2015	J	`jnl`	Constant-Time Testing and Learning of Image Properties. CoRR Piotr Berman, Meiram Murzabulatov, Sofya Raskhodnikova
2015	J	`jnl`	Efficient Lipschitz Extensions for High-Dimensional Graph Statistics and Node Private Degree Distributions. CoRR Sofya Raskhodnikova, Adam D. Smith
2015	B	`conf`	On the Readability of Overlap Digraphs. CPM Rayan Chikhi, Paul Medvedev, Martin Milanic, Sofya Raskhodnikova
2015	J	`jnl`	On the readability of overlap digraphs. CoRR Rayan Chikhi, Paul Medvedev, Martin Milanic, Sofya Raskhodnikova
2015	J	`jnl`	Special Issue: APPROX-RANDOM 2013: Guest Editors' Foreword. Theory Comput. Sofya Raskhodnikova, Ola Svensson
2014	J	`jnl`	Approximation Algorithms for Min-Max Generalization Problems. ACM Trans. Algorithms Piotr Berman, Sofya Raskhodnikova
2014	A*	`conf`	L STOC Piotr Berman, Sofya Raskhodnikova, Grigory Yaroslavtsev
2014	J	`jnl`	Limitations of Local Filters of Lipschitz and Monotone Functions. ACM Trans. Comput. Theory Pranjal Awasthi, Madhav Jha, Marco Molinaro, Sofya Raskhodnikova
2014	A	`conf`	Lower Bounds for Testing Properties of Functions over Hypergrid Domains. CCC Eric Blais, Sofya Raskhodnikova, Grigory Yaroslavtsev
2014	J	`jnl`	Private Analysis of Graph Structure. ACM Trans. Database Syst. Vishesh Karwa, Sofya Raskhodnikova, Adam D. Smith, Grigory Yaroslavtsev
2014	J	`jnl`	Steiner transitive-closure spanners of low-dimensional posets. Comb. Piotr Berman, Arnab Bhattacharyya, Elena Grigorescu, Sofya Raskhodnikova, David P. Woodruff, Grigory Yaroslavtsev
2013	B	`conf`	Analyzing Graphs with Node Differential Privacy. TCC Shiva Prasad Kasiviswanathan, Kobbi Nissim, Sofya Raskhodnikova, Adam D. Smith
2013	J	`jnl`	Approximation algorithms for spanner problems and Directed Steiner Forest. Inf. Comput. Piotr Berman, Arnab Bhattacharyya, Konstantin Makarychev, Sofya Raskhodnikova, Grigory Yaroslavtsev
2013	—	`ed.`	Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 16th International Workshop, APPROX 2013, and 17th International Workshop, RANDOM 2013, Berkeley, CA, USA, August 21-23, 2013. Proceedings APPROX-RANDOM Prasad Raghavendra, Sofya Raskhodnikova, Klaus Jansen, José D. P. Rolim
2013	A*	`conf`	Learning pseudo-Boolean SODA Sofya Raskhodnikova, Grigory Yaroslavtsev
2013	J	`jnl`	Lower Bounds for Testing Properties of Functions on Hypergrid Domains. Electron. Colloquium Comput. Complex. Eric Blais, Sofya Raskhodnikova, Grigory Yaroslavtsev
2013	J	`jnl`	Sublinear Algorithms for Approximating String Compressibility. Algorithmica Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Adam D. Smith
2013	J	`jnl`	Testing and Reconstruction of Lipschitz Functions with Applications to Data Privacy. SIAM J. Comput. Madhav Jha, Sofya Raskhodnikova
2013	B	`conf`	Testing the Lipschitz Property over Product Distributions with Applications to Data Privacy. TCC Kashyap Dixit, Madhav Jha, Sofya Raskhodnikova, Abhradeep Thakurta
2012	J	`jnl`	Learning pseudo-Boolean k-DNF and Submodular Functions CoRR Sofya Raskhodnikova, Grigory Yaroslavtsev
2012	—	`conf`	Limitations of Local Filters of Lipschitz and Monotone Functions. APPROX-RANDOM Pranjal Awasthi, Madhav Jha, Marco Molinaro, Sofya Raskhodnikova
2012	J	`jnl`	Limitations of Local Filters of Lipschitz and Monotone Functions. Electron. Colloquium Comput. Complex. Pranjal Awasthi, Madhav Jha, Marco Molinaro, Sofya Raskhodnikova
2012	J	`jnl`	Lower Bounds for Local Monotonicity Reconstruction from Transitive-Closure Spanners. SIAM J. Discret. Math. Arnab Bhattacharyya, Elena Grigorescu, Madhav Jha, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff
2012	—	`conf`	Testing Lipschitz Functions on Hypergrid Domains. APPROX-RANDOM Pranjal Awasthi, Madhav Jha, Marco Molinaro, Sofya Raskhodnikova
2012	J	`jnl`	Testing Lipschitz Functions on Hypergrid Domains. Electron. Colloquium Comput. Complex. Pranjal Awasthi, Madhav Jha, Marco Molinaro, Sofya Raskhodnikova
2012	J	`jnl`	Transitive-Closure Spanners. SIAM J. Comput. Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff
2011	—	`conf`	Improved Approximation for the Directed Spanner Problem. ICALP (1) Piotr Berman, Arnab Bhattacharyya, Konstantin Makarychev, Sofya Raskhodnikova, Grigory Yaroslavtsev
2011	J	`jnl`	Private Analysis of Graph Structure. Proc. VLDB Endow. Vishesh Karwa, Sofya Raskhodnikova, Adam D. Smith, Grigory Yaroslavtsev
2011	—	`conf`	Steiner Transitive-Closure Spanners of Low-Dimensional Posets. ICALP (1) Piotr Berman, Arnab Bhattacharyya, Elena Grigorescu, Sofya Raskhodnikova, David P. Woodruff, Grigory Yaroslavtsev
2011	A*	`conf`	Testing and Reconstruction of Lipschitz Functions with Applications to Data Privacy. FOCS Madhav Jha, Sofya Raskhodnikova
2011	J	`jnl`	Testing and Reconstruction of Lipschitz Functions with Applications to Data Privacy. Electron. Colloquium Comput. Complex. Madhav Jha, Sofya Raskhodnikova
2011	J	`jnl`	What Can We Learn Privately? SIAM J. Comput. Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, Adam D. Smith
2010	—	`conf`	Approximation Algorithms for Min-Max Generalization Problems. APPROX-RANDOM Piotr Berman, Sofya Raskhodnikova
2010	—	`conf`	Finding Sparser Directed Spanners. FSTTCS Piotr Berman, Sofya Raskhodnikova, Ge Ruan
2010	—	`conf`	Lower Bounds for Local Monotonicity Reconstruction from Transitive-Closure Spanners. APPROX-RANDOM Arnab Bhattacharyya, Elena Grigorescu, Madhav Jha, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff
2010	J	`jnl`	Steiner Transitive-Closure Spanners of d-Dimensional Posets CoRR Piotr Berman, Arnab Bhattacharyya, Elena Grigorescu, Sofya Raskhodnikova, David P. Woodruff, Grigory Yaroslavtsev
2010	—	`ch.`	Transitive-Closure Spanners: A Survey. Property Testing Sofya Raskhodnikova
2009	J	`jnl`	Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem. SIAM J. Comput. Sofya Raskhodnikova, Dana Ron, Amir Shpilka, Adam D. Smith
2009	J	`jnl`	Transitive-Closure Spanners of the Hypercube and the Hypergrid. Electron. Colloquium Comput. Complex. Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff
2009	A*	`conf`	Transitive-closure spanners. SODA Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff
2008	J	`jnl`	Transitive-Closure Spanners CoRR Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff
2008	A*	`conf`	What Can We Learn Privately? FOCS Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, Adam D. Smith
2008	J	`jnl`	What Can We Learn Privately? CoRR Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, Adam D. Smith
2007	A*	`conf`	Smooth sensitivity and sampling in private data analysis. STOC Kobbi Nissim, Sofya Raskhodnikova, Adam D. Smith
2007	A*	`conf`	Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem. FOCS Sofya Raskhodnikova, Dana Ron, Amir Shpilka, Adam D. Smith
2007	J	`jnl`	Sublinear Algorithms for Approximating String Compressibility CoRR Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Adam D. Smith
2007	—	`conf`	Sublinear Algorithms for Approximating String Compressibility. APPROX-RANDOM Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Adam D. Smith
2006	J	`jnl`	A Note on Adaptivity in Testing Properties of Bounded Degree Graphs. Electron. Colloquium Comput. Complex. Sofya Raskhodnikova, Adam D. Smith
2005	J	`jnl`	Some 3CNF Properties Are Hard to Test. SIAM J. Comput. Eli Ben-Sasson, Prahladh Harsha, Sofya Raskhodnikova
2005	J	`jnl`	Sublinear Algorithms for Approximating String Compressibility and the Distribution Support Size Electron. Colloquium Comput. Complex. Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Amir Shpilka, Adam D. Smith
2003	J	`jnl`	3CNF Properties are Hard to Test Electron. Colloquium Comput. Complex. Eli Ben-Sasson, Prahladh Harsha, Sofya Raskhodnikova
2003	A*	`conf`	A sublinear algorithm for weakly approximating edit distance. STOC Tugkan Batu, Funda Ergün, Joe Kilian, Avner Magen, Sofya Raskhodnikova, Ronitt Rubinfeld, Rahul Sami
2003	—	`conf`	Approximate Testing of Visual Properties. RANDOM-APPROX Sofya Raskhodnikova
2003	A*	`conf`	Lower bounds for embedding edit distance into normed spaces. SODA Alexandr Andoni, Michel Deza, Anupam Gupta, Piotr Indyk, Sofya Raskhodnikova
2003	—	`—`	Property testing: theory and applications. Sofya Raskhodnikova
2003	A*	`conf`	Some 3CNF properties are hard to test. STOC Eli Ben-Sasson, Prahladh Harsha, Sofya Raskhodnikova
2002	A*	`conf`	Monotonicity testing over general poset domains. STOC Eldar Fischer, Eric Lehman, Ilan Newman, Sofya Raskhodnikova, Ronitt Rubinfeld, Alex Samorodnitsky
1999	—	`conf`	Improved Testing Algorithms for Monotonicity. RANDOM-APPROX Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, Alex Samorodnitsky
1999	J	`jnl`	Improved Testing Algorithms for Monotonicity. Electron. Colloquium Comput. Complex. Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, Alex Samorodnitsky