Sofya Raskhodnikova

ORCID

Publication Activity (10 Years)

Years Active: 1999-2024
Publications (10 Years): 66

Top Venues

CoRR

Electron. Colloquium Comput. Complex.

ICALP

ITCS

Massachusetts Institute of Technology, Cambridge, MA, USA (PHD)

Education History

Massachusetts Institute of Technology, Cambridge, MA, USA

PHD

Publications

Omri Ben-Eliezer, Esty Kelman, Uri Meir, Sofya Raskhodnikova
Property Testing with Online Adversaries. ITCS (2024)
Sofya Raskhodnikova
The Role of Local Algorithms in Privacy (Invited Talk). STACS (2024)
Jane Lange, Ephraim Linder, Sofya Raskhodnikova, Arsen Vasilyan
Local Lipschitz Filters for Bounded-Range Functions. CoRR (2023)
Piotr Berman, Meiram Murzabulatov, Sofya Raskhodnikova, Dragos-Florian Ristache
Testing Connectedness of Images. CoRR (2023)
Piotr Berman, Meiram Murzabulatov, Sofya Raskhodnikova, Dragos Ristache
Testing Connectedness of Images. APPROX/RANDOM (2023)
Hadley Black, Iden Kalemaj, Sofya Raskhodnikova
Isoperimetric Inequalities for Real-Valued Functions with Applications to Monotonicity Testing. ICALP (2023)
Palak Jain, Iden Kalemaj, Sofya Raskhodnikova, Satchit Sivakumar, Adam D. Smith
Counting Distinct Elements in the Turnstile Model with Differential Privacy under Continual Observation. NeurIPS (2023)
Iden Kalemaj, Sofya Raskhodnikova, Adam D. Smith, Charalampos E. Tsourakakis
Node-Differentially Private Estimation of the Number of Connected Components. PODS (2023)
Palak Jain, Iden Kalemaj, Sofya Raskhodnikova, Satchit Sivakumar, Adam D. Smith
Counting Distinct Elements in the Turnstile Model with Differential Privacy under Continual Observation. CoRR (2023)
Talya Eden, Quanquan C. Liu, Sofya Raskhodnikova, Adam D. Smith
Triangle Counting with Local Edge Differential Privacy. CoRR (2023)
Omri Ben-Eliezer, Esty Kelman, Uri Meir, Sofya Raskhodnikova
Property Testing with Online Adversaries. CoRR (2023)
Iden Kalemaj, Sofya Raskhodnikova, Adam D. Smith, Charalampos E. Tsourakakis
Node-Differentially Private Estimation of the Number of Connected Components. CoRR (2023)
Palak Jain, Sofya Raskhodnikova, Satchit Sivakumar, Adam D. Smith
The Price of Differential Privacy under Continual Observation. ICML (2023)
Talya Eden, Quanquan C. Liu, Sofya Raskhodnikova, Adam D. Smith
Triangle Counting with Local Edge Differential Privacy. ICALP (2023)
Laxman Dhulipala, Quanquan C. Liu, Sofya Raskhodnikova, Jessica Shi, Julian Shun, Shangdi Yu
Differential Privacy from Locally Adjustable Graph Algorithms: k-Core Decomposition, Low Out-Degree Ordering, and Densest Subgraphs. CoRR (2022)
Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Erik Waingarten
Approximating the distance to monotonicity of Boolean functions. Random Struct. Algorithms 60 (2) (2022)
Iden Kalemaj, Sofya Raskhodnikova, Nithin Varma
Sublinear-Time Computation in the Presence of Online Erasures. ITCS (2022)
Laxman Dhulipala, Quanquan C. Liu, Sofya Raskhodnikova, Jessica Shi, Julian Shun, Shangdi Yu
Differential Privacy from Locally Adjustable Graph Algorithms: k-Core Decomposition, Low Out-Degree Ordering, and Densest Subgraphs. FOCS (2022)
Piotr Berman, Meiram Murzabulatov, Sofya Raskhodnikova
Tolerant Testers of Image Properties. ACM Trans. Algorithms 18 (4) (2022)
Amit Levi, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma
Erasure-Resilient Sublinear-Time Graph Algorithms. ACM Trans. Comput. Theory 14 (1) (2022)
Sofya Raskhodnikova, Satchit Sivakumar, Adam D. Smith, Marika Swanberg
Differentially Private Sampling from Distributions. CoRR (2022)
Sofya Raskhodnikova, Satchit Sivakumar, Adam D. Smith, Marika Swanberg
Differentially Private Sampling from Distributions. NeurIPS (2021)
Amit Levi, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma
Erasure-Resilient Sublinear-Time Graph Algorithms. ITCS (2021)
Iden Kalemaj, Sofya Raskhodnikova, Nithin Varma
Sublinear-Time Computation in the Presence of Online Erasures. CoRR (2021)
Palak Jain, Sofya Raskhodnikova, Satchit Sivakumar, Adam D. Smith
The Price of Differential Privacy under Continual Observation. CoRR (2021)
Sofya Raskhodnikova, Noga Ron-Zewi, Nithin Varma
Erasures versus errors in local decoding and property testing. Random Struct. Algorithms 59 (4) (2021)
Valentine Kabanets, Sofya Raskhodnikova, Chaitanya Swamy
Special Section on the Fifty-Eighth Annual IEEE Symposium on Foundations of Computer Science (FOCS 2017). SIAM J. Comput. 49 (4) (2020)
Amit Levi, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma
Erasure-Resilient Sublinear-Time Graph Algorithms. Electron. Colloquium Comput. Complex. 27 (2020)
Hadley Black, Iden Kalemaj, Sofya Raskhodnikova
Isoperimetric Inequalities for Real-Valued Functions with Applications to Monotonicity Testing. Electron. Colloquium Comput. Complex. 27 (2020)
Amit Levi, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma
Erasure-Resilient Sublinear-Time Graph Algorithms. CoRR (2020)
Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Erik Waingarten
Approximating the Distance to Monotonicity of Boolean Functions. SODA (2020)
Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, C. Seshadhri
Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps. Theory Comput. 16 (2020)
Hadley Black, Iden Kalemaj, Sofya Raskhodnikova
Isoperimetric Inequalities for Real-Valued Functions with Applications to Monotonicity Testing. CoRR (2020)
Rayan Chikhi, Vladan Jovicic, Stefan Kratsch, Paul Medvedev, Martin Milanic, Sofya Raskhodnikova, Nithin Varma
Bipartite graphs of small readability. Theor. Comput. Sci. 806 (2020)
Sofya Raskhodnikova, Noga Ron-Zewi, Nithin Varma
Erasures vs. Errors in Local Decoding and Property Testing. ITCS (2019)
Piotr Berman, Meiram Murzabulatov, Sofya Raskhodnikova
The Power and Limitations of Uniform Samples in Testing Properties of Figures. Algorithmica 81 (3) (2019)
Piotr Berman, Meiram Murzabulatov, Sofya Raskhodnikova
Testing convexity of figures under the uniform distribution. Random Struct. Algorithms 54 (3) (2019)
Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Erik Waingarten
Approximating the Distance to Monotonicity of Boolean Functions. CoRR (2019)
Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Erik Waingarten
Approximating the Distance to Monotonicity of Boolean Functions. Electron. Colloquium Comput. Complex. 26 (2019)
Kashyap Dixit, Sofya Raskhodnikova, Abhradeep Thakurta, Nithin Varma
Erasure-Resilient Property Testing. SIAM J. Comput. 47 (2) (2018)
Sofya Raskhodnikova, Noga Ron-Zewi, Nithin Varma
Erasures versus Errors in Local Decoding and Property Testing. Electron. Colloquium Comput. Complex. 25 (2018)
Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma
Parameterized Property Testing of Functions. ACM Trans. Comput. Theory 9 (4) (2018)
Sofya Raskhodnikova, Nithin Varma
Brief Announcement: Erasure-Resilience Versus Tolerance to Errors. ICALP (2018)
Rayan Chikhi, Vladan Jovicic, Stefan Kratsch, Paul Medvedev, Martin Milanic, Sofya Raskhodnikova, Nithin Varma
Bipartite Graphs of Small Readability. COCOON (2018)
Rayan Chikhi, Vladan Jovicic, Stefan Kratsch, Paul Medvedev, Martin Milanic, Sofya Raskhodnikova, Nithin Varma
Bipartite Graphs of Small Readability. CoRR (2018)
Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma
Parameterized Property Testing of Functions. Electron. Colloquium Comput. Complex. 24 (2017)
Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma
Parameterized Property Testing of Functions. ITCS (2017)
Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, C. Seshadhri
A Lower Bound for Nonadaptive, One-Sided Error Testing of Unateness of Boolean Functions over the Hypercube. Electron. Colloquium Comput. Complex. 24 (2017)
Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, C. Seshadhri
Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps. ICALP (2017)
Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, C. Seshadhri
A Lower Bound for Nonadaptive, One-Sided Error Testing of Unateness of Boolean Functions over the Hypercube. CoRR (2017)
Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, C. Seshadhri
Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps. CoRR (2017)
Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, C. Seshadhri
Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps. Electron. Colloquium Comput. Complex. 24 (2017)
Pranjal Awasthi, Madhav Jha, Marco Molinaro, Sofya Raskhodnikova
Testing Lipschitz Functions on Hypergrid Domains. Algorithmica 74 (3) (2016)
Roksana Baleshzar, Meiram Murzabulatov, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova
Testing Unateness of Real-Valued Functions. CoRR (2016)
Sofya Raskhodnikova, Adam D. Smith
Lipschitz Extensions for Node-Private Graph Statistics and the Generalized Exponential Mechanism. FOCS (2016)
Piotr Berman, Meiram Murzabulatov, Sofya Raskhodnikova
The Power and Limitations of Uniform Samples in Testing Properties of Figures. FSTTCS (2016)
Piotr Berman, Meiram Murzabulatov, Sofya Raskhodnikova
Testing Convexity of Figures Under the Uniform Distribution. SoCG (2016)
Piotr Berman, Meiram Murzabulatov, Sofya Raskhodnikova
Tolerant Testers of Image Properties. ICALP (2016)
Kashyap Dixit, Sofya Raskhodnikova, Abhradeep Thakurta, Nithin Varma
Erasure-Resilient Property Testing. CoRR (2016)
Kashyap Dixit, Sofya Raskhodnikova, Abhradeep Thakurta, Nithin Varma
Erasure-Resilient Property Testing. ICALP (2016)
Rayan Chikhi, Paul Medvedev, Martin Milanic, Sofya Raskhodnikova
On the readability of overlap digraphs. Discret. Appl. Math. 205 (2016)
Rayan Chikhi, Paul Medvedev, Martin Milanic, Sofya Raskhodnikova
On the readability of overlap digraphs. CoRR (2015)
Rayan Chikhi, Paul Medvedev, Martin Milanic, Sofya Raskhodnikova
On the Readability of Overlap Digraphs. CPM (2015)
Piotr Berman, Meiram Murzabulatov, Sofya Raskhodnikova
Constant-Time Testing and Learning of Image Properties. CoRR (2015)
Sofya Raskhodnikova, Adam D. Smith
Efficient Lipschitz Extensions for High-Dimensional Graph Statistics and Node Private Degree Distributions. CoRR (2015)
Sofya Raskhodnikova, Ola Svensson
Special Issue: APPROX-RANDOM 2013: Guest Editors' Foreword. Theory Comput. 11 (2015)
Vishesh Karwa, Sofya Raskhodnikova, Adam D. Smith, Grigory Yaroslavtsev
Private Analysis of Graph Structure. ACM Trans. Database Syst. 39 (3) (2014)
Piotr Berman, Sofya Raskhodnikova
Approximation Algorithms for Min-Max Generalization Problems. ACM Trans. Algorithms 11 (1) (2014)
Piotr Berman, Sofya Raskhodnikova, Grigory Yaroslavtsev
-testing. STOC (2014)
Piotr Berman, Arnab Bhattacharyya, Elena Grigorescu, Sofya Raskhodnikova, David P. Woodruff, Grigory Yaroslavtsev
Steiner transitive-closure spanners of low-dimensional posets. Comb. 34 (3) (2014)
Eric Blais, Sofya Raskhodnikova, Grigory Yaroslavtsev
Lower Bounds for Testing Properties of Functions over Hypergrid Domains. Computational Complexity Conference (2014)
Pranjal Awasthi, Madhav Jha, Marco Molinaro, Sofya Raskhodnikova
Limitations of Local Filters of Lipschitz and Monotone Functions. ACM Trans. Comput. Theory 7 (1) (2014)
Sofya Raskhodnikova, Grigory Yaroslavtsev
-DNF and submodular functions. SODA (2013)
Madhav Jha, Sofya Raskhodnikova
Testing and Reconstruction of Lipschitz Functions with Applications to Data Privacy. SIAM J. Comput. 42 (2) (2013)
Piotr Berman, Arnab Bhattacharyya, Konstantin Makarychev, Sofya Raskhodnikova, Grigory Yaroslavtsev
Approximation algorithms for spanner problems and Directed Steiner Forest. Inf. Comput. 222 (2013)
Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Adam D. Smith
Sublinear Algorithms for Approximating String Compressibility. Algorithmica 65 (3) (2013)
Eric Blais, Sofya Raskhodnikova, Grigory Yaroslavtsev
Lower Bounds for Testing Properties of Functions on Hypergrid Domains. Electron. Colloquium Comput. Complex. 20 (2013)
Shiva Prasad Kasiviswanathan, Kobbi Nissim, Sofya Raskhodnikova, Adam D. Smith
Analyzing Graphs with Node Differential Privacy. TCC (2013)
Kashyap Dixit, Madhav Jha, Sofya Raskhodnikova, Abhradeep Thakurta
Testing the Lipschitz Property over Product Distributions with Applications to Data Privacy. TCC (2013)
Pranjal Awasthi, Madhav Jha, Marco Molinaro, Sofya Raskhodnikova
Limitations of Local Filters of Lipschitz and Monotone Functions. Electron. Colloquium Comput. Complex. 19 (2012)
Arnab Bhattacharyya, Elena Grigorescu, Madhav Jha, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff
Lower Bounds for Local Monotonicity Reconstruction from Transitive-Closure Spanners. SIAM J. Discret. Math. 26 (2) (2012)
Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff
Transitive-Closure Spanners. SIAM J. Comput. 41 (6) (2012)
Pranjal Awasthi, Madhav Jha, Marco Molinaro, Sofya Raskhodnikova
Testing Lipschitz Functions on Hypergrid Domains. Electron. Colloquium Comput. Complex. 19 (2012)
Sofya Raskhodnikova, Grigory Yaroslavtsev
Learning pseudo-Boolean k-DNF and Submodular Functions CoRR (2012)
Pranjal Awasthi, Madhav Jha, Marco Molinaro, Sofya Raskhodnikova
Testing Lipschitz Functions on Hypergrid Domains. APPROX-RANDOM (2012)
Pranjal Awasthi, Madhav Jha, Marco Molinaro, Sofya Raskhodnikova
Limitations of Local Filters of Lipschitz and Monotone Functions. APPROX-RANDOM (2012)
Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, Adam D. Smith
What Can We Learn Privately? SIAM J. Comput. 40 (3) (2011)
Madhav Jha, Sofya Raskhodnikova
Testing and Reconstruction of Lipschitz Functions with Applications to Data Privacy. FOCS (2011)
Piotr Berman, Arnab Bhattacharyya, Elena Grigorescu, Sofya Raskhodnikova, David P. Woodruff, Grigory Yaroslavtsev
Steiner Transitive-Closure Spanners of Low-Dimensional Posets. ICALP (1) (2011)
Piotr Berman, Arnab Bhattacharyya, Konstantin Makarychev, Sofya Raskhodnikova, Grigory Yaroslavtsev
Improved Approximation for the Directed Spanner Problem. ICALP (1) (2011)
Vishesh Karwa, Sofya Raskhodnikova, Adam D. Smith, Grigory Yaroslavtsev
Private Analysis of Graph Structure. Proc. VLDB Endow. 4 (11) (2011)
Madhav Jha, Sofya Raskhodnikova
Testing and Reconstruction of Lipschitz Functions with Applications to Data Privacy. Electron. Colloquium Comput. Complex. 18 (2011)
Arnab Bhattacharyya, Elena Grigorescu, Madhav Jha, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff
Lower Bounds for Local Monotonicity Reconstruction from Transitive-Closure Spanners. APPROX-RANDOM (2010)
Piotr Berman, Sofya Raskhodnikova
Approximation Algorithms for Min-Max Generalization Problems. APPROX-RANDOM (2010)
Piotr Berman, Arnab Bhattacharyya, Elena Grigorescu, Sofya Raskhodnikova, David P. Woodruff, Grigory Yaroslavtsev
Steiner Transitive-Closure Spanners of d-Dimensional Posets CoRR (2010)
Piotr Berman, Sofya Raskhodnikova, Ge Ruan
Finding Sparser Directed Spanners. FSTTCS (2010)
Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff
Transitive-Closure Spanners of the Hypercube and the Hypergrid. Electron. Colloquium Comput. Complex. 16 (2009)
Sofya Raskhodnikova, Dana Ron, Amir Shpilka, Adam D. Smith
Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem. SIAM J. Comput. 39 (3) (2009)
Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff
Transitive-closure spanners. SODA (2009)
Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, Adam D. Smith
What Can We Learn Privately? CoRR (2008)

Sofya Raskhodnikova.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Sofya Raskhodnikova