Please note: This is a beta version of the new dblp website.
You can find the classic dblp view of this page here.
You can find the classic dblp view of this page here.
Sofya Raskhodnikova
2010 – today
- 2013
[j9]Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Adam 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)
- [c23]Sofya Raskhodnikova, Grigory Yaroslavtsev: Learning pseudo-Boolean k-DNF and submodular functions. SODA 2013: 1356-1368
- [c22]Kashyap Dixit, Madhav Jha, Sofya Raskhodnikova, Abhradeep Thakurta: Testing the Lipschitz Property over Product Distributions with Applications to Data Privacy. TCC 2013: 418-436
- [c21]Shiva Prasad Kasiviswanathan, Kobbi Nissim, Sofya Raskhodnikova, Adam Smith: Analyzing Graphs with Node Differential Privacy. TCC 2013: 457-476
- [i14]Eric Blais, Sofya Raskhodnikova, Grigory Yaroslavtsev: Lower Bounds for Testing Properties of Functions on Hypergrid Domains. Electronic Colloquium on Computational Complexity (ECCC) 20: 36 (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. Discrete Math. 26(2): 618-646 (2012)
- [c20]Pranjal Awasthi, Madhav Jha, Marco Molinaro, Sofya Raskhodnikova: Limitations of Local Filters of Lipschitz and Monotone Functions. APPROX-RANDOM 2012: 374-386
- [c19]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. Electronic Colloquium on Computational Complexity (ECCC) 19: 75 (2012)
- [i11]Pranjal Awasthi, Madhav Jha, Marco Molinaro, Sofya Raskhodnikova: Testing Lipschitz Functions on Hypergrid Domains. Electronic Colloquium on Computational Complexity (ECCC) 19: 76 (2012)
- 2011
- [j4]Vishesh Karwa, Sofya Raskhodnikova, Adam Smith, Grigory Yaroslavtsev: Private Analysis of Graph Structure. PVLDB 4(11): 1146-1157 (2011)
- [j3]Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, Adam Smith: What Can We Learn Privately? SIAM J. Comput. 40(3): 793-826 (2011)
- [c18]Madhav Jha, Sofya Raskhodnikova: Testing and Reconstruction of Lipschitz Functions with Applications to Data Privacy. FOCS 2011: 433-442
- [c17]Piotr Berman, Arnab Bhattacharyya, Konstantin Makarychev, Sofya Raskhodnikova, Grigory Yaroslavtsev: Improved Approximation for the Directed Spanner Problem. ICALP (1) 2011: 1-12
- [c16]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. Electronic Colloquium on Computational Complexity (ECCC) 18: 57 (2011)
- 2010
- [c15]Piotr Berman, Sofya Raskhodnikova: Approximation Algorithms for Min-Max Generalization Problems. APPROX-RANDOM 2010: 53-66
- [c14]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
- [c13]
- [c12]
- [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 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. Electronic Colloquium on Computational Complexity (ECCC) 16: 46 (2009)
- 2008
- [c10]Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, Adam Smith: What Can We Learn Privately? FOCS 2008: 531-540
- [i7]Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, Adam 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 Smith: Sublinear Algorithms for Approximating String Compressibility. APPROX-RANDOM 2007: 609-623
- [c8]Sofya Raskhodnikova, Dana Ron, Amir Shpilka, Adam Smith: Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem. FOCS 2007: 559-569
- [c7]Kobbi Nissim, Sofya Raskhodnikova, Adam Smith: Smooth sensitivity and sampling in private data analysis. STOC 2007: 75-84
- [i5]Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Adam Smith: Sublinear Algorithms for Approximating String Compressibility. CoRR abs/0706.1084 (2007)
- 2006
- [i4]Sofya Raskhodnikova, Adam Smith: A Note on Adaptivity in Testing Properties of Bounded Degree Graphs. Electronic Colloquium on Computational Complexity (ECCC) 13(089) (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 Smith: Sublinear Algorithms for Approximating String Compressibility and the Distribution Support Size. Electronic Colloquium on Computational Complexity (ECCC)(125) (2005)
- 2003
- [c6]
- [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. Electronic Colloquium on Computational Complexity (ECCC) 10(006) (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. Electronic Colloquium on Computational Complexity (ECCC) 6(17) (1999)
Coauthor Index
data released under the ODC-BY 1.0 license. See also our legal information page
last updated on 2013-06-05 21:32 CEST by the dblp team