Sofya Raskhodnikova

According to our database1, Sofya Raskhodnikova authored at least 56 papers between 1999 and 2020.

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

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

On csauthors.net:

Bibliography

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

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

Approximating the Distance to Monotonicity of Boolean Functions.
Electronic Colloquium on Computational Complexity (ECCC), 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.
Electronic Colloquium on Computational Complexity (ECCC), 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.
Electronic Colloquium on Computational Complexity (ECCC), 2017

A Lower Bound for Nonadaptive, One-Sided Error Testing of Unateness of Boolean Functions over the Hypercube.
Electronic Colloquium on Computational Complexity (ECCC), 2017

Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps.
Electronic Colloquium on Computational Complexity (ECCC), 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

Tolerant Testers of Image Properties.
Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 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 of Computing, 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.
Combinatorica, 2014

Lp-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.
Electronic Colloquium on Computational Complexity (ECCC), 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 k-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. Discrete Math., 2012

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

Limitations of Local Filters of Lipschitz and Monotone Functions.
Electronic Colloquium on Computational Complexity (ECCC), 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.
PVLDB, 2011

Testing and Reconstruction of Lipschitz Functions with Applications to Data Privacy.
Electronic Colloquium on Computational Complexity (ECCC), 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.
Electronic Colloquium on Computational Complexity (ECCC), 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.
Electronic Colloquium on Computational Complexity (ECCC), 2006

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

Sublinear Algorithms for Approximating String Compressibility and the Distribution Support Size
Electronic Colloquium on Computational Complexity (ECCC), 2005

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

3CNF Properties are Hard to Test
Electronic Colloquium on Computational Complexity (ECCC), 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.
Electronic Colloquium on Computational Complexity (ECCC), 1999


  Loading...