Sofya Raskhodnikova

Orcid: 0000-0002-4902-050X

Affiliations:
  • Boston University, USA
  • Pennsylvania State University, University Park, USA (former)


According to our database1, Sofya Raskhodnikova authored at least 70 papers between 1999 and 2024.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
The Role of Local Algorithms in Privacy (Invited Talk).
Proceedings of the 41st International Symposium on Theoretical Aspects of Computer Science, 2024

Property Testing with Online Adversaries.
Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

2023
Local Lipschitz Filters for Bounded-Range Functions.
CoRR, 2023

Node-Differentially Private Estimation of the Number of Connected Components.
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.
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.
Proceedings of the International Conference on Machine Learning, 2023

Triangle Counting with Local Edge Differential Privacy.
Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

Testing Connectedness of Images.
Proceedings of the Approximation, 2023

2022
Tolerant Testers of Image Properties.
ACM Trans. Algorithms, 2022

Sublinear-Time Computation in the Presence of Online Erasures.
Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

Differential Privacy from Locally Adjustable Graph Algorithms: k-Core Decomposition, Low Out-Degree Ordering, and Densest Subgraphs.
Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

2021
Differentially Private Sampling from Distributions.
Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

2020
Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps.
Theory Comput., 2020

Bipartite graphs of small readability.
Theor. Comput. Sci., 2020

Special Section on the Fifty-Eighth Annual IEEE Symposium on Foundations of Computer Science (FOCS 2017).
SIAM J. Comput., 2020

Erasure-Resilient Sublinear-Time Graph Algorithms.
Electron. Colloquium Comput. Complex., 2020

Isoperimetric Inequalities for Real-Valued Functions with Applications to Monotonicity Testing.
Electron. Colloquium Comput. Complex., 2020

2019
Testing convexity of figures under the uniform distribution.
Random Struct. Algorithms, 2019

Approximating the Distance to Monotonicity of Boolean Functions.
Electron. Colloquium Comput. Complex., 2019

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

Erasures vs. Errors in Local Decoding and Property Testing.
Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

2018
Erasure-Resilient Property Testing.
SIAM J. Comput., 2018

Erasures versus Errors in Local Decoding and Property Testing.
Electron. Colloquium Comput. Complex., 2018

Brief Announcement: Erasure-Resilience Versus Tolerance to Errors.
Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

2017
Parameterized Property Testing of Functions.
Electron. Colloquium Comput. Complex., 2017

A Lower Bound for Nonadaptive, One-Sided Error Testing of Unateness of Boolean Functions over the Hypercube.
Electron. Colloquium Comput. Complex., 2017

2016
Differentially Private Analysis of Graphs.
Encyclopedia of Algorithms, 2016

Linearity Testing/Testing Hadamard Codes.
Encyclopedia of Algorithms, 2016

Testing if an Array Is Sorted.
Encyclopedia of Algorithms, 2016

On the readability of overlap digraphs.
Discret. Appl. Math., 2016

Testing Unateness of Real-Valued Functions.
CoRR, 2016

Testing Lipschitz Functions on Hypergrid Domains.
Algorithmica, 2016

Lipschitz Extensions for Node-Private Graph Statistics and the Generalized Exponential Mechanism.
Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

2015
Special Issue: APPROX-RANDOM 2013: Guest Editors' Foreword.
Theory Comput., 2015

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

Constant-Time Testing and Learning of Image Properties.
CoRR, 2015

2014
Approximation Algorithms for Min-Max Generalization Problems.
ACM Trans. Algorithms, 2014

Steiner transitive-closure spanners of low-dimensional posets.
Comb., 2014

L<sub>p</sub>-testing.
Proceedings of the Symposium on Theory of Computing, 2014

Lower Bounds for Testing Properties of Functions over Hypergrid Domains.
Proceedings of the IEEE 29th Conference on Computational Complexity, 2014

2013
Approximation algorithms for spanner problems and Directed Steiner Forest.
Inf. Comput., 2013

Lower Bounds for Testing Properties of Functions on Hypergrid Domains.
Electron. Colloquium Comput. Complex., 2013

Sublinear Algorithms for Approximating String Compressibility.
Algorithmica, 2013

Analyzing Graphs with Node Differential Privacy.
Proceedings of the Theory of Cryptography - 10th Theory of Cryptography Conference, 2013

Testing the Lipschitz Property over Product Distributions with Applications to Data Privacy.
Proceedings of the Theory of Cryptography - 10th Theory of Cryptography Conference, 2013

Learning pseudo-Boolean <i>k</i>-DNF and submodular functions.
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

2012
Lower Bounds for Local Monotonicity Reconstruction from Transitive-Closure Spanners.
SIAM J. Discret. Math., 2012

Transitive-Closure Spanners.
SIAM J. Comput., 2012

Limitations of Local Filters of Lipschitz and Monotone Functions.
Electron. Colloquium Comput. Complex., 2012

Learning pseudo-Boolean k-DNF and Submodular Functions
CoRR, 2012

2011
What Can We Learn Privately?
SIAM J. Comput., 2011

Private Analysis of Graph Structure.
Proc. VLDB Endow., 2011

Testing and Reconstruction of Lipschitz Functions with Applications to Data Privacy.
Electron. Colloquium Comput. Complex., 2011

Improved Approximation for the Directed Spanner Problem.
Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

2010
Steiner Transitive-Closure Spanners of d-Dimensional Posets
CoRR, 2010

Transitive-Closure Spanners: A Survey.
Proceedings of the Property Testing - Current Research and Surveys, 2010

Finding Sparser Directed Spanners.
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.
SIAM J. Comput., 2009

Transitive-Closure Spanners of the Hypercube and the Hypergrid.
Electron. Colloquium Comput. Complex., 2009

2007
Smooth sensitivity and sampling in private data analysis.
Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

2006
A Note on Adaptivity in Testing Properties of Bounded Degree Graphs.
Electron. Colloquium Comput. Complex., 2006

2005
Some 3CNF Properties Are Hard to Test.
SIAM J. Comput., 2005

Sublinear Algorithms for Approximating String Compressibility and the Distribution Support Size
Electron. Colloquium Comput. Complex., 2005

2003
Property testing: theory and applications.
PhD thesis, 2003

3CNF Properties are Hard to Test
Electron. Colloquium Comput. Complex., 2003

A sublinear algorithm for weakly approximating edit distance.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

Lower bounds for embedding edit distance into normed spaces.
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Approximate Testing of Visual Properties.
Proceedings of the Approximation, 2003

2002
Monotonicity testing over general poset domains.
Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

1999
Improved Testing Algorithms for Monotonicity.
Electron. Colloquium Comput. Complex., 1999


  Loading...