☰

Sofya Raskhodnikova - Publications

Affiliations: 
Computer Science and Engineering Pennsylvania State University, State College, PA, United States 
Area:
Computer Science, Theoretical Mathematics
Tree Info Similar researchers PubMed Report error

30 high-probability publications. We are testing a new system for linking publications to authors. You can help! If you notice any inaccuracies, please sign in and mark papers as correct or incorrect matches. If you identify any major omissions or other inaccuracies in the publication list, please let us know.

Year Citation  Score
2020 Chikhi R, Jovičić V, Kratsch S, Medvedev P, Milanič M, Raskhodnikova S, Varma N. Bipartite graphs of small readability Theoretical Computer Science. 806: 402-415. DOI: 10.1016/J.Tcs.2019.07.022  0.494
2019 Berman P, Murzabulatov M, Raskhodnikova S. The Power and Limitations of Uniform Samples in Testing Properties of Figures Algorithmica. 81: 1247-1266. DOI: 10.1007/S00453-018-0467-9  0.338
2018 Dixit K, Raskhodnikova S, Thakurta A, Varma NM. Erasure-Resilient Property Testing Siam Journal On Computing. 47: 295-329. DOI: 10.1137/16M1075661  0.419
2017 Pallavoor RKS, Raskhodnikova S, Varma N. Parameterized Property Testing of Functions Acm Transactions On Computation Theory. 9: 17. DOI: 10.1145/3155296  0.428
2016 Chikhi R, Medvedev P, Milanič M, Raskhodnikova S. On the readability of overlap digraphs Discrete Applied Mathematics. 205: 35-44. DOI: 10.1016/J.Dam.2015.12.009  0.482
2016 Awasthi P, Jha M, Molinaro M, Raskhodnikova S. Testing Lipschitz Functions on Hypergrid Domains Algorithmica. 74: 1055-1081. DOI: 10.1007/S00453-015-9984-Y  0.607
2015 Chikhi R, Medvedev P, Milanič M, Raskhodnikova S. On the readability of overlap digraphs Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 9133: 124-137. DOI: 10.1007/978-3-319-19929-0_11  0.391
2014 Awasthi P, Jha M, Molinaro M, Raskhodnikova S. Limitations of local filters of lipschitz and monotone functions Acm Transactions On Computation Theory. 7. DOI: 10.1145/2692372.2692373  0.565
2014 Berman P, Raskhodnikova S. Approximation Algorithms for Min-Max Generalization Problems Acm Transactions On Algorithms. 11: 5. DOI: 10.1145/2636920  0.433
2014 Berman P, Raskhodnikova S, Yaroslavtsev G. Lp-testing Proceedings of the Annual Acm Symposium On Theory of Computing. 164-173. DOI: 10.1145/2591796.2591887  0.702
2014 Blais E, Raskhodnikova S, Yaroslavtsev G. Lower bounds for testing properties of functions over hypergrid domains Proceedings of the Annual Ieee Conference On Computational Complexity. 309-320. DOI: 10.1109/CCC.2014.38  0.7
2014 Berman P, Bhattacharyya A, Grigorescu E, Raskhodnikova S, Woodruff DP, Yaroslavtsev G. Steiner transitive-closure spanners of low-dimensional posets Combinatorica. 34: 255-277. DOI: 10.1007/S00493-014-2833-9  0.749
2013 Jha M, Raskhodnikova S. Testing and reconstruction of lipschitz functions with applications to data privacy Siam Journal On Computing. 42: 700-731. DOI: 10.1137/110840741  0.591
2013 Berman P, Bhattacharyya A, Makarychev K, Raskhodnikova S, Yaroslavtsev G. Approximation algorithms for spanner problems and Directed Steiner Forest Information and Computation. 222: 93-107. DOI: 10.1016/J.Ic.2012.10.007  0.744
2013 Raskhodnikova S, Ron D, Rubinfeld R, Smith A. Sublinear algorithms for approximating string compressibility Algorithmica. 65: 685-709. DOI: 10.1007/S00453-012-9618-6  0.361
2013 Dixit K, Jha M, Raskhodnikova S, Thakurta A. Testing the Lipschitz property over product distributions with applications to data privacy Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 7785: 418-436. DOI: 10.1007/978-3-642-36594-2_24  0.316
2013 Raskhodnikova S, Yaroslavtsev G. Learning pseudo-Boolean k-DNF and submodular functions Proceedings of the Annual Acm-Siam Symposium On Discrete Algorithms. 1356-1368.  0.721
2012 Bhattacharyya A, Grigorescu E, Jung K, Raskhodnikova S, Woodruff DP. Transitive-Closure Spanners Siam Journal On Computing. 41: 1380-1425. DOI: 10.1137/110826655  0.569
2011 Karwa V, Raskhodnikova S, Smith A, Yaroslavtsev G. Private analysis of graph structure Proceedings of the Vldb Endowment. 4: 1146-1157. DOI: 10.1145/2611523  0.751
2011 Kasiviswanathan SP, Lee OK, Nissim K, Raskhodnikova S, Smith A. What can we learn privately? Siam Journal On Computing. 40: 793-826. DOI: 10.1137/090756090  0.331
2011 Berman P, Bhattacharyya A, Grigorescu E, Raskhodnikova S, Woodruff DP, Yaroslavtsev G. Steiner transitive-closure spanners of low-dimensional posets Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 6755: 760-772. DOI: 10.1007/978-3-642-22006-7_64  0.741
2011 Berman P, Bhattacharyya A, Makarychev K, Raskhodnikova S, Yaroslavtsev G. Improved approximation for the directed spanner problem Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 6755: 1-12. DOI: 10.1007/978-3-642-22006-7_1  0.757
2010 Berman P, Raskhodnikova S, Ruan G. Finding sparser directed spanners Leibniz International Proceedings in Informatics, Lipics. 8: 424-435. DOI: 10.4230/LIPIcs.FSTTCS.2010.424  0.466
2010 Bhattacharyya A, Grigorescu E, Jha M, Jung K, Raskhodnikova S, Woodruff DP. Lower bounds for local monotonicity reconstruction from transitive-closure spanners Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 6302: 448-461. DOI: 10.1137/100808186  0.708
2010 Raskhodnikova S. Transitive-closure spanners: A survey Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 6390: 167-196. DOI: 10.1007/978-3-642-16367-8_10  0.479
2010 Berman P, Raskhodnikova S. Approximation algorithms for min-max generalization problems Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 6302: 53-66. DOI: 10.1007/978-3-642-15369-3_5  0.356
2009 Raskhodnikova S, Ron D, Shpilka A, Smith A. Strong lower bounds for approximating distribution support size and the distinct elements problem Siam Journal On Computing. 39: 813-842. DOI: 10.1137/070701649  0.402
2006 Ben-Sasson E, Harsha P, Raskhodnikova S. Some 3CNF properties are hard to test Siam Journal On Computing. 35: 1-21. DOI: 10.1137/S0097539704445445  0.396
2002 Fischer E, Lehman E, Newman I, Raskhodnikova S, Rubinfeld R, Samorodnitsky A. Monotonicity testing over general poset domains Conference Proceedings of the Annual Acm Symposium On Theory of Computing. 474-483.  0.434
1999 Dodis Y, Goldreich O, Lehman E, Raskhodnikova S, Ron D, Samorodnitsky A. Improved testing algorithms for monotonicity Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 1671: 97-108. DOI: 10.1007/978-3-540-48413-4_10  0.339
Show low-probability matches.