Sofya Raskhodnikova

According to our database, Sofya Raskhodnikova authored at least 72 papers between 1999 and 2025.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2025

Local Lipschitz Filters for Bounded-Range Functions with Applications to Arbitrary Real-Valued Functions.

Jane Lange, Ephraim Linder, Sofya Raskhodnikova, Arsen Vasilyan

Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, 2025

2024

Testing Connectedness of Images.

Piotr Berman, Meiram Murzabulatov, Sofya Raskhodnikova, Dragos-Florian Ristache

Algorithmica, November, 2024

Online versus Offline Adversaries in Property Testing.

Esty Kelman, Ephraim Linder, Sofya Raskhodnikova

CoRR, 2024

The Role of Local Algorithms in Privacy (Invited Talk).

Sofya Raskhodnikova

Proceedings of the 41st International Symposium on Theoretical Aspects of Computer Science, 2024

Property Testing with Online Adversaries.

Omri Ben-Eliezer, Esty Kelman, Uri Meir, Sofya Raskhodnikova

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

2023

Sublinear-Time Computation in the Presence of Online Erasures.

Iden Kalemaj, Sofya Raskhodnikova, Nithin Varma

Theory Comput., 2023

Local Lipschitz Filters for Bounded-Range Functions.

Jane Lange, Ephraim Linder, Sofya Raskhodnikova, Arsen Vasilyan

CoRR, 2023

Node-Differentially Private Estimation of the Number of Connected Components.

Iden Kalemaj, Sofya Raskhodnikova, Adam D. Smith, Charalampos E. Tsourakakis

Proceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2023

Counting Distinct Elements in the Turnstile Model with Differential Privacy under Continual Observation.

Palak Jain, Iden Kalemaj, Sofya Raskhodnikova, Satchit Sivakumar, Adam D. Smith

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

The Price of Differential Privacy under Continual Observation.

Palak Jain, Sofya Raskhodnikova, Satchit Sivakumar, Adam D. Smith

Proceedings of the International Conference on Machine Learning, 2023

Triangle Counting with Local Edge Differential Privacy.

Talya Eden, Quanquan C. Liu, Sofya Raskhodnikova, Adam D. Smith

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

2022

Tolerant Testers of Image Properties.

Piotr Berman, Meiram Murzabulatov, Sofya Raskhodnikova

ACM Trans. Algorithms, 2022

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, Julian Shun, Shangdi Yu

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

2021

Differentially Private Sampling from Distributions.

Sofya Raskhodnikova, Satchit Sivakumar, Adam D. Smith, Marika Swanberg

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

2020

Bipartite graphs of small readability.

Rayan Chikhi, Vladan Jovicic, Stefan Kratsch, Paul Medvedev, Martin Milanic, Sofya Raskhodnikova, Nithin Varma

Theor. Comput. Sci., 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

Erasure-Resilient Sublinear-Time Graph Algorithms.

Amit Levi, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma

Electron. Colloquium Comput. Complex., 2020

Isoperimetric Inequalities for Real-Valued Functions with Applications to Monotonicity Testing.

Hadley Black, Iden Kalemaj, Sofya Raskhodnikova

Electron. Colloquium Comput. Complex., 2020

2019

Testing convexity of figures under the uniform distribution.

Piotr Berman, Meiram Murzabulatov, Sofya Raskhodnikova

Random Struct. Algorithms, 2019

Approximating the Distance to Monotonicity of Boolean Functions.

Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Erik Waingarten

Electron. Colloquium Comput. Complex., 2019

The Power and Limitations of Uniform Samples in Testing Properties of Figures.

Piotr Berman, Meiram Murzabulatov, Sofya Raskhodnikova

Algorithmica, 2019

Erasures vs. Errors in Local Decoding and Property Testing.

Sofya Raskhodnikova, Noga Ron-Zewi, Nithin Varma

Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

2018

Erasure-Resilient Property Testing.

Kashyap Dixit, Sofya Raskhodnikova, Abhradeep Thakurta, Nithin Varma

SIAM J. Comput., 2018

Erasures versus Errors in Local Decoding and Property Testing.

Sofya Raskhodnikova, Noga Ron-Zewi, Nithin Varma

Electron. Colloquium Comput. Complex., 2018

Brief Announcement: Erasure-Resilience Versus Tolerance to Errors.

Sofya Raskhodnikova, Nithin Varma

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

2017

Parameterized Property Testing of Functions.

Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma

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

Electron. Colloquium Comput. Complex., 2017

Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps.

Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, C. Seshadhri

Electron. Colloquium Comput. Complex., 2017

2016

Differentially Private Analysis of Graphs.

Sofya Raskhodnikova, Adam D. Smith

Encyclopedia of Algorithms, 2016

Linearity Testing/Testing Hadamard Codes.

Sofya Raskhodnikova, Ronitt Rubinfeld

Encyclopedia of Algorithms, 2016

Testing if an Array Is Sorted.

Sofya Raskhodnikova

Encyclopedia of Algorithms, 2016

On the readability of overlap digraphs.

Rayan Chikhi, Paul Medvedev, Martin Milanic, Sofya Raskhodnikova

Discret. Appl. Math., 2016

Testing Unateness of Real-Valued Functions.

Roksana Baleshzar, Meiram Murzabulatov, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova

CoRR, 2016

Lipschitz Extensions for Node-Private Graph Statistics and the Generalized Exponential Mechanism.

Sofya Raskhodnikova, Adam D. Smith

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

2015

Special Issue: APPROX-RANDOM 2013: Guest Editors' Foreword.

Sofya Raskhodnikova, Ola Svensson

Theory Comput., 2015

Efficient Lipschitz Extensions for High-Dimensional Graph Statistics and Node Private Degree Distributions.

Sofya Raskhodnikova, Adam D. Smith

CoRR, 2015

Constant-Time Testing and Learning of Image Properties.

Piotr Berman, Meiram Murzabulatov, Sofya Raskhodnikova

CoRR, 2015

2014

Approximation Algorithms for Min-Max Generalization Problems.

Piotr Berman, Sofya Raskhodnikova

ACM Trans. Algorithms, 2014

Steiner transitive-closure spanners of low-dimensional posets.

Piotr Berman, Arnab Bhattacharyya, Elena Grigorescu, Sofya Raskhodnikova, David P. Woodruff, Grigory Yaroslavtsev

Comb., 2014

L_p-testing.

Piotr Berman, Sofya Raskhodnikova, Grigory Yaroslavtsev

Proceedings of the Symposium on Theory of Computing, 2014

Lower Bounds for Testing Properties of Functions over Hypergrid Domains.

Eric Blais, Sofya Raskhodnikova, Grigory Yaroslavtsev

Proceedings of the IEEE 29th Conference on Computational Complexity, 2014

2013

Testing and Reconstruction of Lipschitz Functions with Applications to Data Privacy.

Madhav Jha, Sofya Raskhodnikova

SIAM J. Comput., 2013

Approximation algorithms for spanner problems and Directed Steiner Forest.

Piotr Berman, Arnab Bhattacharyya, Konstantin Makarychev, Sofya Raskhodnikova, Grigory Yaroslavtsev

Inf. Comput., 2013

Lower Bounds for Testing Properties of Functions on Hypergrid Domains.

Eric Blais, Sofya Raskhodnikova, Grigory Yaroslavtsev

Electron. Colloquium Comput. Complex., 2013

Sublinear Algorithms for Approximating String Compressibility.

Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Adam D. Smith

Algorithmica, 2013

Analyzing Graphs with Node Differential Privacy.

Shiva Prasad Kasiviswanathan, Kobbi Nissim, Sofya Raskhodnikova, Adam D. Smith

Proceedings of the Theory of Cryptography - 10th Theory of Cryptography Conference, 2013

Testing the Lipschitz Property over Product Distributions with Applications to Data Privacy.

Kashyap Dixit, Madhav Jha, Sofya Raskhodnikova, Abhradeep Thakurta

Proceedings of the Theory of Cryptography - 10th Theory of Cryptography Conference, 2013

Learning pseudo-Boolean <i>k</i>-DNF and submodular functions.

Sofya Raskhodnikova, Grigory Yaroslavtsev

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

2012

Lower Bounds for Local Monotonicity Reconstruction from Transitive-Closure Spanners.

Arnab Bhattacharyya, Elena Grigorescu, Madhav Jha, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff

SIAM J. Discret. Math., 2012

Transitive-Closure Spanners.

Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff

SIAM J. Comput., 2012

Testing Lipschitz Functions on Hypergrid Domains.

Pranjal Awasthi, Madhav Jha, Marco Molinaro, Sofya Raskhodnikova

Electron. Colloquium Comput. Complex., 2012

Limitations of Local Filters of Lipschitz and Monotone Functions.

Pranjal Awasthi, Madhav Jha, Marco Molinaro, Sofya Raskhodnikova

Electron. Colloquium Comput. Complex., 2012

Learning pseudo-Boolean k-DNF and Submodular Functions

Sofya Raskhodnikova, Grigory Yaroslavtsev

CoRR, 2012

2011

What Can We Learn Privately?

Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, Adam D. Smith

SIAM J. Comput., 2011

Private Analysis of Graph Structure.

Vishesh Karwa, Sofya Raskhodnikova, Adam D. Smith, Grigory Yaroslavtsev

Proc. VLDB Endow., 2011

Improved Approximation for the Directed Spanner Problem.

Piotr Berman, Arnab Bhattacharyya, Konstantin Makarychev, Sofya Raskhodnikova, Grigory Yaroslavtsev

Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

2010

Steiner Transitive-Closure Spanners of d-Dimensional Posets

Piotr Berman, Arnab Bhattacharyya, Elena Grigorescu, Sofya Raskhodnikova, David P. Woodruff, Grigory Yaroslavtsev

CoRR, 2010

Transitive-Closure Spanners: A Survey.

Sofya Raskhodnikova

Proceedings of the Property Testing - Current Research and Surveys, 2010

Finding Sparser Directed Spanners.

Piotr Berman, Sofya Raskhodnikova, Ge Ruan

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2010

2009

Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem.

Sofya Raskhodnikova, Dana Ron, Amir Shpilka, Adam D. Smith

SIAM J. Comput., 2009

Transitive-Closure Spanners of the Hypercube and the Hypergrid.

Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff

Electron. Colloquium Comput. Complex., 2009

2007

Smooth sensitivity and sampling in private data analysis.

Kobbi Nissim, Sofya Raskhodnikova, Adam D. Smith

Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

2006

A Note on Adaptivity in Testing Properties of Bounded Degree Graphs.

Sofya Raskhodnikova, Adam D. Smith

Electron. Colloquium Comput. Complex., 2006

2005

Some 3CNF Properties Are Hard to Test.

Eli Ben-Sasson, Prahladh Harsha, Sofya Raskhodnikova

SIAM J. Comput., 2005

Sublinear Algorithms for Approximating String Compressibility and the Distribution Support Size

Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Amir Shpilka, Adam D. Smith

Electron. Colloquium Comput. Complex., 2005

2003

Property testing: theory and applications.

Sofya Raskhodnikova

PhD thesis, 2003

3CNF Properties are Hard to Test

Eli Ben-Sasson, Prahladh Harsha, Sofya Raskhodnikova

Electron. Colloquium Comput. Complex., 2003

A sublinear algorithm for weakly approximating edit distance.

Tugkan Batu, Funda Ergün, Joe Kilian, Avner Magen, Sofya Raskhodnikova, Ronitt Rubinfeld, Rahul Sami

Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

Lower bounds for embedding edit distance into normed spaces.

Alexandr Andoni, Michel Deza, Anupam Gupta, Piotr Indyk, Sofya Raskhodnikova

Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Approximate Testing of Visual Properties.

Sofya Raskhodnikova

Proceedings of the Approximation, 2003

2002

Monotonicity testing over general poset domains.

Eldar Fischer, Eric Lehman, Ilan Newman, Sofya Raskhodnikova, Ronitt Rubinfeld, Alex Samorodnitsky

Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

1999

Improved Testing Algorithms for Monotonicity.

Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, Alex Samorodnitsky

Electron. Colloquium Comput. Complex., 1999