Stop the war!Остановите войну!
for scientists:
default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDSofya Raskhodnikova
Person information
- affiliation: Boston University, USA
- affiliation (former): Pennsylvania State University, University Park, USA
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2023
[c45]Piotr Berman, Meiram Murzabulatov, Sofya Raskhodnikova, Dragos Ristache:
Testing Connectedness of Images. APPROX/RANDOM 2023: 66:1-66:15- [c44]Hadley Black, Iden Kalemaj, Sofya Raskhodnikova:
Isoperimetric Inequalities for Real-Valued Functions with Applications to Monotonicity Testing. ICALP 2023: 25:1-25:20 - [c43]Talya Eden, Quanquan C. Liu, Sofya Raskhodnikova, Adam D. Smith:
Triangle Counting with Local Edge Differential Privacy. ICALP 2023: 52:1-52:21 - [c42]Palak Jain, Sofya Raskhodnikova, Satchit Sivakumar, Adam D. Smith:
The Price of Differential Privacy under Continual Observation. ICML 2023: 14654-14678 - [c41]Iden Kalemaj
, Sofya Raskhodnikova, Adam D. Smith, Charalampos E. Tsourakakis:
Node-Differentially Private Estimation of the Number of Connected Components. PODS 2023: 183-194 - [i40]Iden Kalemaj, Sofya Raskhodnikova, Adam D. Smith, Charalampos E. Tsourakakis:
Node-Differentially Private Estimation of the Number of Connected Components. CoRR abs/2304.05890 (2023) - [i39]Talya Eden, Quanquan C. Liu, Sofya Raskhodnikova, Adam D. Smith:
Triangle Counting with Local Edge Differential Privacy. CoRR abs/2305.02263 (2023) - [i38]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 abs/2306.06723 (2023) - [i37]Jane Lange, Ephraim Linder, Sofya Raskhodnikova, Arsen Vasilyan:
Local Lipschitz Filters for Bounded-Range Functions. CoRR abs/2308.14716 (2023) - 2022
- [j27]Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Erik Waingarten:
Approximating the distance to monotonicity of Boolean functions. Random Struct. Algorithms 60(2): 233-260 (2022) - [j26]Piotr Berman, Meiram Murzabulatov, Sofya Raskhodnikova:
Tolerant Testers of Image Properties. ACM Trans. Algorithms 18(4): 37:1-37:39 (2022) - [j25]Amit Levi, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma:
Erasure-Resilient Sublinear-Time Graph Algorithms. ACM Trans. Comput. Theory 14(1): 1:1-1:22 (2022) - [c40]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: 754-765 - [c39]Iden Kalemaj, Sofya Raskhodnikova, Nithin Varma:
Sublinear-Time Computation in the Presence of Online Erasures. ITCS 2022: 90:1-90:25 - [e2]Alexander S. Kulikov, Sofya Raskhodnikova:
Computer Science - Theory and Applications - 17th International Computer Science Symposium in Russia, CSR 2022, Virtual Event, June 29 - July 1, 2022, Proceedings. Lecture Notes in Computer Science 13296, Springer 2022, ISBN 978-3-031-09573-3 [contents] - [i36]Sofya Raskhodnikova, Satchit Sivakumar, Adam D. Smith, Marika Swanberg:
Differentially Private Sampling from Distributions. CoRR abs/2211.08193 (2022) - [i35]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 abs/2211.10887 (2022) - 2021
- [j24]Sofya Raskhodnikova, Noga Ron-Zewi, Nithin Varma:
Erasures versus errors in local decoding and property testing. Random Struct. Algorithms 59(4): 640-670 (2021) - [c38]Amit Levi, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma:
Erasure-Resilient Sublinear-Time Graph Algorithms. ITCS 2021: 80:1-80:20 - [c37]Sofya Raskhodnikova, Satchit Sivakumar, Adam D. Smith, Marika Swanberg:
Differentially Private Sampling from Distributions. NeurIPS 2021: 28983-28994 - [i34]Iden Kalemaj, Sofya Raskhodnikova, Nithin Varma:
Sublinear-Time Computation in the Presence of Online Erasures. CoRR abs/2109.08745 (2021) - [i33]Palak Jain, Sofya Raskhodnikova, Satchit Sivakumar, Adam D. Smith:
The Price of Differential Privacy under Continual Observation. CoRR abs/2112.00828 (2021) - 2020
- [j23]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) - [j22]Rayan Chikhi, Vladan Jovicic, Stefan Kratsch, Paul Medvedev, Martin Milanic, Sofya Raskhodnikova, Nithin Varma:
Bipartite graphs of small readability. Theor. Comput. Sci. 806: 402-415 (2020) - [j21]Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, C. Seshadhri:
Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps. Theory Comput. 16: 1-36 (2020) - [c36]Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Erik Waingarten:
Approximating the Distance to Monotonicity of Boolean Functions. SODA 2020: 1995-2009 - [i32]Hadley Black, Iden Kalemaj, Sofya Raskhodnikova:
Isoperimetric Inequalities for Real-Valued Functions with Applications to Monotonicity Testing. CoRR abs/2011.09441 (2020) - [i31]Amit Levi, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma:
Erasure-Resilient Sublinear-Time Graph Algorithms. CoRR abs/2011.14291 (2020) - [i30]Hadley Black, Iden Kalemaj, Sofya Raskhodnikova:
Isoperimetric Inequalities for Real-Valued Functions with Applications to Monotonicity Testing. Electron. Colloquium Comput. Complex. TR20 (2020) - [i29]Amit Levi, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma:
Erasure-Resilient Sublinear-Time Graph Algorithms. Electron. Colloquium Comput. Complex. TR20 (2020)
2010 – 2019
- 2019
- [j20]Piotr Berman, Meiram Murzabulatov, Sofya Raskhodnikova:
The Power and Limitations of Uniform Samples in Testing Properties of Figures. Algorithmica 81(3): 1247-1266 (2019) - [j19]Piotr Berman, Meiram Murzabulatov, Sofya Raskhodnikova:
Testing convexity of figures under the uniform distribution. Random Struct. Algorithms 54(3): 413-443 (2019) - [c35]Sofya Raskhodnikova, Noga Ron-Zewi, Nithin Varma:
Erasures vs. Errors in Local Decoding and Property Testing. ITCS 2019: 63:1-63:21 - [i28]Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Erik Waingarten:
Approximating the Distance to Monotonicity of Boolean Functions. CoRR abs/1911.06924 (2019) - [i27]Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Erik Waingarten:
Approximating the Distance to Monotonicity of Boolean Functions. Electron. Colloquium Comput. Complex. TR19 (2019) - 2018
- [j18]Kashyap Dixit, Sofya Raskhodnikova, Abhradeep Thakurta, Nithin Varma:
Erasure-Resilient Property Testing. SIAM J. Comput. 47(2): 295-329 (2018) - [j17]Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma:
Parameterized Property Testing of Functions. ACM Trans. Comput. Theory 9(4): 17:1-17:19 (2018) - [c34]Rayan Chikhi, Vladan Jovicic, Stefan Kratsch, Paul Medvedev, Martin Milanic, Sofya Raskhodnikova, Nithin Varma:
Bipartite Graphs of Small Readability. COCOON 2018: 467-479 - [c33]Sofya Raskhodnikova, Nithin Varma:
Brief Announcement: Erasure-Resilience Versus Tolerance to Errors. ICALP 2018: 111:1-111:3 - [i26]Rayan Chikhi, Vladan Jovicic, Stefan Kratsch, Paul Medvedev, Martin Milanic, Sofya Raskhodnikova, Nithin Varma:
Bipartite Graphs of Small Readability. CoRR abs/1805.04765 (2018) - [i25]Sofya Raskhodnikova, Noga Ron-Zewi, Nithin Varma:
Erasures versus Errors in Local Decoding and Property Testing. Electron. Colloquium Comput. Complex. TR18 (2018) - 2017
- [c32]Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, C. Seshadhri:
Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps. ICALP 2017: 5:1-5:14 - [c31]Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma:
Parameterized Property Testing of Functions. ITCS 2017: 12:1-12:17 - [i24]Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, C. Seshadhri:
Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps. CoRR abs/1703.05199 (2017) - [i23]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 abs/1706.00053 (2017) - [i22]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. TR17 (2017) - [i21]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. TR17 (2017) - [i20]Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma:
Parameterized Property Testing of Functions. Electron. Colloquium Comput. Complex. TR17 (2017) - 2016
- [j16]Pranjal Awasthi, Madhav Jha, Marco Molinaro, Sofya Raskhodnikova:
Testing Lipschitz Functions on Hypergrid Domains. Algorithmica 74(3): 1055-1081 (2016) - [j15]Rayan Chikhi, Paul Medvedev, Martin Milanic, Sofya Raskhodnikova:
On the readability of overlap digraphs. Discret. Appl. Math. 205: 35-44 (2016) - [c30]Piotr Berman, Meiram Murzabulatov, Sofya Raskhodnikova:
Testing Convexity of Figures Under the Uniform Distribution. SoCG 2016: 17:1-17:15 - [c29]Sofya Raskhodnikova, Adam D. Smith:
Lipschitz Extensions for Node-Private Graph Statistics and the Generalized Exponential Mechanism. FOCS 2016: 495-504 - [c28]Piotr Berman, Meiram Murzabulatov, Sofya Raskhodnikova:
The Power and Limitations of Uniform Samples in Testing Properties of Figures. FSTTCS 2016: 45:1-45:14 - [c27]Piotr Berman, Meiram Murzabulatov, Sofya Raskhodnikova:
Tolerant Testers of Image Properties. ICALP 2016: 90:1-90:14 - [c26]Kashyap Dixit, Sofya Raskhodnikova, Abhradeep Thakurta, Nithin Varma:
Erasure-Resilient Property Testing. ICALP 2016: 91:1-91:15 - [r3]Sofya Raskhodnikova, Adam D. Smith:
Differentially Private Analysis of Graphs. Encyclopedia of Algorithms 2016: 543-547 - [r2]Sofya Raskhodnikova, Ronitt Rubinfeld:
Linearity Testing/Testing Hadamard Codes. Encyclopedia of Algorithms 2016: 1107-1110 - [r1]Sofya Raskhodnikova:
Testing if an Array Is Sorted. Encyclopedia of Algorithms 2016: 2219-2222 - [i19]Kashyap Dixit, Sofya Raskhodnikova, Abhradeep Thakurta, Nithin Varma:
Erasure-Resilient Property Testing. CoRR abs/1607.05786 (2016) - [i18]Roksana Baleshzar, Meiram Murzabulatov, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova:
Testing Unateness of Real-Valued Functions. CoRR abs/1608.07652 (2016) - 2015
- [j14]Sofya Raskhodnikova, Ola Svensson:
Special Issue: APPROX-RANDOM 2013: Guest Editors' Foreword. Theory Comput. 11: 237-239 (2015) - [c25]Rayan Chikhi, Paul Medvedev, Martin Milanic, Sofya Raskhodnikova:
On the Readability of Overlap Digraphs. CPM 2015: 124-137 - [i17]Piotr Berman, Meiram Murzabulatov, Sofya Raskhodnikova:
Constant-Time Testing and Learning of Image Properties. CoRR abs/1503.01363 (2015) - [i16]Rayan Chikhi, Paul Medvedev, Martin Milanic, Sofya Raskhodnikova:
On the readability of overlap digraphs. CoRR abs/1504.04616 (2015) - [i15]Sofya Raskhodnikova, Adam D. Smith:
Efficient Lipschitz Extensions for High-Dimensional Graph Statistics and Node Private Degree Distributions. CoRR abs/1504.07912 (2015) - 2014
- [j13]Piotr Berman, Arnab Bhattacharyya, Elena Grigorescu, Sofya Raskhodnikova, David P. Woodruff, Grigory Yaroslavtsev:
Steiner transitive-closure spanners of low-dimensional posets. Comb. 34(3): 255-277 (2014) - [j12]Piotr Berman, Sofya Raskhodnikova:
Approximation Algorithms for Min-Max Generalization Problems. ACM Trans. Algorithms 11(1): 5:1-5:23 (2014) - [j11]Pranjal Awasthi, Madhav Jha, Marco Molinaro, Sofya Raskhodnikova:
Limitations of Local Filters of Lipschitz and Monotone Functions. ACM Trans. Comput. Theory 7(1): 2:1-2:16 (2014) - [j10]Vishesh Karwa, Sofya Raskhodnikova, Adam D. Smith, Grigory Yaroslavtsev:
Private Analysis of Graph Structure. ACM Trans. Database Syst. 39(3): 22:1-22:33 (2014) - [c24]Eric Blais, Sofya Raskhodnikova, Grigory Yaroslavtsev:
Lower Bounds for Testing Properties of Functions over Hypergrid Domains. CCC 2014: 309-320 - [c23]Piotr Berman, Sofya Raskhodnikova, Grigory Yaroslavtsev:
Lp-testing. STOC 2014: 164-173 - 2013
- [j9]Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Adam D. Smith:
Sublinear Algorithms for Approximating String Compressibility. Algorithmica 65(3): 685-709 (2013) - [j8]Piotr Berman, Arnab Bhattacharyya, Konstantin Makarychev, Sofya Raskhodnikova, Grigory Yaroslavtsev:
Approximation algorithms for spanner problems and Directed Steiner Forest. Inf. Comput. 222: 93-107 (2013) - [j7]Madhav Jha, Sofya Raskhodnikova:
Testing and Reconstruction of Lipschitz Functions with Applications to Data Privacy. SIAM J. Comput. 42(2): 700-731 (2013) - [c22]Sofya Raskhodnikova, Grigory Yaroslavtsev:
Learning pseudo-Boolean k-DNF and submodular functions. SODA 2013: 1356-1368 - [c21]Kashyap Dixit, Madhav Jha, Sofya Raskhodnikova, Abhradeep Thakurta:
Testing the Lipschitz Property over Product Distributions with Applications to Data Privacy. TCC 2013: 418-436 - [c20]Shiva Prasad Kasiviswanathan, Kobbi Nissim, Sofya Raskhodnikova, Adam D. Smith:
Analyzing Graphs with Node Differential Privacy. TCC 2013: 457-476 - [e1]Prasad Raghavendra, Sofya Raskhodnikova, Klaus Jansen, José D. P. Rolim:
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. Lecture Notes in Computer Science 8096, Springer 2013, ISBN 978-3-642-40327-9 [contents] - [i14]Eric Blais, Sofya Raskhodnikova, Grigory Yaroslavtsev:
Lower Bounds for Testing Properties of Functions on Hypergrid Domains. Electron. Colloquium Comput. Complex. TR13 (2013) - 2012
- [j6]Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff:
Transitive-Closure Spanners. SIAM J. Comput. 41(6): 1380-1425 (2012) - [j5]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): 618-646 (2012) - [c19]Pranjal Awasthi, Madhav Jha, Marco Molinaro, Sofya Raskhodnikova:
Limitations of Local Filters of Lipschitz and Monotone Functions. APPROX-RANDOM 2012: 374-386 - [c18]Pranjal Awasthi, Madhav Jha, Marco Molinaro, Sofya Raskhodnikova:
Testing Lipschitz Functions on Hypergrid Domains. APPROX-RANDOM 2012: 387-398 - [i13]Sofya Raskhodnikova, Grigory Yaroslavtsev:
Learning pseudo-Boolean k-DNF and Submodular Functions. CoRR abs/1208.2294 (2012) - [i12]Pranjal Awasthi, Madhav Jha, Marco Molinaro, Sofya Raskhodnikova:
Limitations of Local Filters of Lipschitz and Monotone Functions. Electron. Colloquium Comput. Complex. TR12 (2012) - [i11]Pranjal Awasthi, Madhav Jha, Marco Molinaro, Sofya Raskhodnikova:
Testing Lipschitz Functions on Hypergrid Domains. Electron. Colloquium Comput. Complex. TR12 (2012) - 2011
- [j4]Vishesh Karwa, Sofya Raskhodnikova, Adam D. Smith, Grigory Yaroslavtsev:
Private Analysis of Graph Structure. Proc. VLDB Endow. 4(11): 1146-1157 (2011) - [j3]Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, Adam D. Smith:
What Can We Learn Privately? SIAM J. Comput. 40(3): 793-826 (2011) - [c17]Madhav Jha, Sofya Raskhodnikova:
Testing and Reconstruction of Lipschitz Functions with Applications to Data Privacy. FOCS 2011: 433-442 - [c16]Piotr Berman, Arnab Bhattacharyya, Konstantin Makarychev, Sofya Raskhodnikova, Grigory Yaroslavtsev:
Improved Approximation for the Directed Spanner Problem. ICALP (1) 2011: 1-12 - [c15]Piotr Berman, Arnab Bhattacharyya, Elena Grigorescu, Sofya Raskhodnikova, David P. Woodruff, Grigory Yaroslavtsev:
Steiner Transitive-Closure Spanners of Low-Dimensional Posets. ICALP (1) 2011: 760-772 - [i10]Madhav Jha, Sofya Raskhodnikova:
Testing and Reconstruction of Lipschitz Functions with Applications to Data Privacy. Electron. Colloquium Comput. Complex. TR11 (2011) - 2010
- [c14]Piotr Berman, Sofya Raskhodnikova:
Approximation Algorithms for Min-Max Generalization Problems. APPROX-RANDOM 2010: 53-66 - [c13]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: 448-461 - [c12]Piotr Berman, Sofya Raskhodnikova, Ge Ruan:
Finding Sparser Directed Spanners. FSTTCS 2010: 424-435 - [p1]Sofya Raskhodnikova:
Transitive-Closure Spanners: A Survey. Property Testing 2010: 167-196 - [i9]Piotr Berman, Arnab Bhattacharyya, Elena Grigorescu, Sofya Raskhodnikova, David P. Woodruff, Grigory Yaroslavtsev:
Steiner Transitive-Closure Spanners of d-Dimensional Posets. CoRR abs/1011.6100 (2010)
2000 – 2009
- 2009
- [j2]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): 813-842 (2009) - [c11]Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff:
Transitive-closure spanners. SODA 2009: 932-941 - [i8]Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff:
Transitive-Closure Spanners of the Hypercube and the Hypergrid. Electron. Colloquium Comput. Complex. TR09 (2009) - 2008
- [c10]Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, Adam D. Smith:
What Can We Learn Privately? FOCS 2008: 531-540 - [i7]Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, Adam D. Smith:
What Can We Learn Privately? CoRR abs/0803.0924 (2008) - [i6]Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff:
Transitive-Closure Spanners. CoRR abs/0808.1787 (2008) - 2007
- [c9]Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Adam D. Smith:
Sublinear Algorithms for Approximating String Compressibility. APPROX-RANDOM 2007: 609-623 - [c8]Sofya Raskhodnikova, Dana Ron, Amir Shpilka, Adam D. Smith:
Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem. FOCS 2007: 559-569 - [c7]Kobbi Nissim, Sofya Raskhodnikova, Adam D. Smith:
Smooth sensitivity and sampling in private data analysis. STOC 2007: 75-84 - [i5]Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Adam D. Smith:
Sublinear Algorithms for Approximating String Compressibility. CoRR abs/0706.1084 (2007) - 2006
- [i4]Sofya Raskhodnikova, Adam D. Smith:
A Note on Adaptivity in Testing Properties of Bounded Degree Graphs. Electron. Colloquium Comput. Complex. TR06 (2006) - 2005
- [j1]Eli Ben-Sasson, Prahladh Harsha, Sofya Raskhodnikova:
Some 3CNF Properties Are Hard to Test. SIAM J. Comput. 35(1): 1-21 (2005) - [i3]Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Amir Shpilka, Adam D. Smith:
Sublinear Algorithms for Approximating String Compressibility and the Distribution Support Size. Electron. Colloquium Comput. Complex. TR05 (2005) - 2003
- [b1]Sofya Raskhodnikova:
Property testing: theory and applications. Massachusetts Institute of Technology, Cambridge, MA, USA, 2003 - [c6]Sofya Raskhodnikova:
Approximate Testing of Visual Properties. RANDOM-APPROX 2003: 370-381 - [c5]Alexandr Andoni, Michel Deza, Anupam Gupta, Piotr Indyk, Sofya Raskhodnikova:
Lower bounds for embedding edit distance into normed spaces. SODA 2003: 523-526 - [c4]Tugkan Batu, Funda Ergün, Joe Kilian, Avner Magen, Sofya Raskhodnikova, Ronitt Rubinfeld, Rahul Sami:
A sublinear algorithm for weakly approximating edit distance. STOC 2003: 316-324 - [c3]Eli Ben-Sasson, Prahladh Harsha, Sofya Raskhodnikova:
Some 3CNF properties are hard to test. STOC 2003: 345-354 - [i2]Eli Ben-Sasson, Prahladh Harsha, Sofya Raskhodnikova:
3CNF Properties are Hard to Test. Electron. Colloquium Comput. Complex. TR03 (2003) - 2002
- [c2]Eldar Fischer, Eric Lehman, Ilan Newman, Sofya Raskhodnikova, Ronitt Rubinfeld, Alex Samorodnitsky:
Monotonicity testing over general poset domains. STOC 2002: 474-483
1990 – 1999
- 1999
- [c1]Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, Alex Samorodnitsky:
Improved Testing Algorithms for Monotonicity. RANDOM-APPROX 1999: 97-108 - [i1]Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, Alex Samorodnitsky:
Improved Testing Algorithms for Monotonicity. Electron. Colloquium Comput. Complex. TR99 (1999)
Coauthor Index