☰

Rafail Ostrovsky - Publications

Affiliations: 
Computer Science University of California, Los Angeles, Los Angeles, CA 
Area:
theory of computation; cryptography and security; distributed algorithms; high-dimensional search; routing and flow control in communication networks
Tree Info Similar researchers PubMed Report error

59 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 Bunn P, Ostrovsky R. Oblivious Sampling with Applications to Two-Party k-Means Clustering Journal of Cryptology. 33: 1362-1403. DOI: 10.1007/S00145-020-09349-W  0.758
2019 Gonczarowski YA, Nisan N, Ostrovsky R, Rosenbaum W. A stable marriage requires communication Games and Economic Behavior. 118: 626-647. DOI: 10.1016/J.Geb.2018.10.013  0.381
2018 Alter G, Falk BH, Lu S, Ostrovsky R. Computing Statistics from Private Data Data Science Journal. 17. DOI: 10.5334/Dsj-2018-031  0.738
2017 Braverman M, Gelles R, Mao J, Ostrovsky R. Coding for Interactive Communication Correcting Insertions and Deletions Ieee Transactions On Information Theory. 63: 6256-6270. DOI: 10.1109/Tit.2017.2734881  0.759
2017 Hemenway B, Ostrovsky R. Efficient robust secret sharing from expander graphs Cryptography and Communications. 10: 79-99. DOI: 10.1007/S12095-017-0215-Z  0.779
2016 Khamsemanan N, Ostrovsky R, Skeith WE. On the black-box use of somewhat homomorphic encryption in noninteractive two-party protocols Siam Journal On Discrete Mathematics. 30: 266-295. DOI: 10.1137/110858835  0.781
2015 Braverman V, Ostrovsky R, Roytman A. Zero-one laws for sliding windows and universal sketches Leibniz International Proceedings in Informatics, Lipics. 40: 573-590. DOI: 10.4230/LIPIcs.APPROX-RANDOM.2015.573  0.649
2015 Franklin M, Gelles R, Ostrovsky R, Schulman LJ. Optimal coding for streaming authentication and interactive communication Ieee Transactions On Information Theory. 61: 133-145. DOI: 10.1109/Tit.2014.2367094  0.754
2015 Braverman V, Ostrovsky R, Vorsanger G. Weighted sampling without replacement from data streams Information Processing Letters. 115: 923-926. DOI: 10.1016/J.Ipl.2015.07.007  0.697
2015 Hemenway B, Ostrovsky R, Wootters M. Local correctability of expander codes Information and Computation. 243: 178-190. DOI: 10.1016/J.Ic.2014.12.013  0.758
2015 Chandran N, Garay JA, Ostrovsky R. Almost-Everywhere Secure Computation with Edge Corruptions Journal of Cryptology. 28: 745-768. DOI: 10.1007/S00145-013-9176-3  0.779
2015 Ostrovsky R, Richelson S, Scafuro A. Round-optimal black-box two-party computation Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 9216: 339-358. DOI: 10.1007/978-3-662-48000-7_17  0.3
2015 Chase M, Ostrovsky R, Visconti I. Executable proofs, input-size hiding secure computation and a new ideal world Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 9057: 532-560. DOI: 10.1007/978-3-662-46803-6_18  0.302
2014 He D, Furlotte NA, Hormozdiari F, Joo JW, Wadia A, Ostrovsky R, Sahai A, Eskin E. Identifying genetic relatives without compromising privacy. Genome Research. 24: 664-72. PMID 24614977 DOI: 10.1101/Gr.153346.112  0.748
2014 Chandran N, Kanukurthi B, Ostrovsky R, Reyzin L. Privacy amplification with asymptotically optimal entropy loss Journal of the Acm. 61. DOI: 10.1145/2630064  0.782
2014 Barenboim L, Dolev S, Ostrovsky R. Deterministic and energy-optimal wireless synchronization Acm Transactions On Sensor Networks. 11. DOI: 10.1145/2629493  0.346
2014 Buhrma H, Chandran N, Fehr S, Gelles R, Goyal V, Ostrovsky R, Schaffner C. Position-based quantum cryptography:Impossibility and constructions Siam Journal On Computing. 43: 150-178. DOI: 10.1137/130913687  0.738
2014 Chandran N, Goyal V, Moriarty R, Ostrovsky R. Position-based cryptography Siam Journal On Computing. 43: 1291-1341. DOI: 10.1137/100805005  0.751
2014 Garay J, Givens C, Ostrovsky R. Secure message transmission with small public discussion Ieee Transactions On Information Theory. 60: 2373-2390. DOI: 10.1109/Tit.2014.2307309  0.33
2014 Baron J, Ishai Y, Ostrovsky R. On linear-size pseudorandom generators and hardcore functions Theoretical Computer Science. 554: 50-63. DOI: 10.1016/J.Tcs.2014.06.013  0.766
2014 Braverman V, Gelles R, Ostrovsky R. How to catch L2-heavy-hitters on sliding windows Theoretical Computer Science. 554: 82-94. DOI: 10.1016/J.Tcs.2014.06.008  0.757
2014 Groth J, Ostrovsky R. Cryptography in the multi-string model Journal of Cryptology. 27: 506-543. DOI: 10.1007/S00145-013-9152-Y  0.409
2014 Chung KM, Ostrovsky R, Pass R, Venkitasubramaniam M, Visconti I. 4-round resettably-sound zero knowledge Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 8349: 192-216. DOI: 10.1007/978-3-642-54242-8_9  0.5
2014 Lampkins J, Ostrovsky R. Communication-efficient MPC for general adversary structures Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 8642: 155-174.  0.31
2013 Baron J, El Defrawy K, Minkovich K, Ostrovsky R, Tressler E. 5PM: Secure pattern matching Journal of Computer Security. 21: 601-625. DOI: 10.3233/Jcs-130481  0.779
2013 Chung KM, Ostrovsky R, Pass R, Visconti I. Simultaneous resettability from one-way functions Proceedings - Annual Ieee Symposium On Foundations of Computer Science, Focs. 60-69. DOI: 10.1109/FOCS.2013.15  0.453
2013 Lu S, Ostrovsky R, Sahai A, Shacham H, Waters B. Sequential aggregate signatures, multisignatures, and verifiably encrypted signatures without random oracles Journal of Cryptology. 26: 340-373. DOI: 10.1007/S00145-012-9126-5  0.74
2013 Braverman V, Ostrovsky R. Generalizing the layering method of indyk and Woodruff: Recursive sketches for frequency-based vectors on streams Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 8096: 58-70. DOI: 10.1007/978-3-642-40328-6_5  0.649
2013 Braverman V, Ostrovsky R. Approximating large frequency moments with pick-and-drop sampling Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 8096: 42-57. DOI: 10.1007/978-3-642-40328-6_4  0.676
2013 Braverman V, Ostrovsky R, Vilenchik D. How hard is counting triangles in the streaming model? Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 7965: 244-254. DOI: 10.1007/978-3-642-39206-1_21  0.689
2013 Braverman V, Gelles R, Ostrovsky R. How to catch l 2-heavy-hitters on sliding windows Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 7936: 638-650. DOI: 10.1007/978-3-642-38768-5_56  0.688
2013 Bitansky N, Chiesa A, Ishai Y, Paneth O, Ostrovsky R. Succinct non-interactive arguments via linear interactive proofs Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 7785: 315-333. DOI: 10.1007/978-3-642-36594-2_18  0.449
2012 Groth J, Ostrovsky R, Sahai A. New techniques for noninteractive zero-knowledge Journal of the Acm. 59. DOI: 10.1145/2220357.2220358  0.35
2012 Bradonjić M, Kohler E, Ostrovsky R. Near-optimal radio use for wireless network synchronization Theoretical Computer Science. 453: 14-28. DOI: 10.1016/J.Tcs.2011.09.026  0.346
2012 Braverman V, Ostrovsky R, Zaniolo C. Optimal sampling from sliding windows Journal of Computer and System Sciences. 78: 260-272. DOI: 10.1016/J.Jcss.2011.04.004  0.712
2011 Curtmola R, Garay J, Kamara S, Ostrovsky R. Searchable symmetric encryption: Improved definitions and efficient constructions Journal of Computer Security. 19: 895-934. DOI: 10.3233/Jcs-2011-0426  0.413
2011 Braverman V, Meyerson A, Ostrovsky R, Roytman A, Shindler M, Tagiku B. Streaming k-means on well-clusterable data Proceedings of the Annual Acm-Siam Symposium On Discrete Algorithms. 26-40.  0.646
2010 Braverman V, Ostrovsky R. Effective Computations on Sliding Windows Siam Journal On Computing. 39: 2113-2131. DOI: 10.1137/090749281  0.727
2009 Katz J, Ostrovsky R, Yung M. Efficient and secure authenticated key exchange using weak passwords Journal of the Acm. 57: 1-39. DOI: 10.1145/1613676.1613679  0.41
2009 Ishai Y, Kushilevitz E, Ostrovsky R, Sahai A. Zero-Knowledge Proofs from Secure Multiparty Computation Siam Journal On Computing. 39: 1121-1152. DOI: 10.1137/080725398  0.416
2009 Ostrovsky R, Rabani Y, Schulman LJ. Error-correcting codes for automatic control Ieee Transactions On Information Theory. 55: 2931-2941. DOI: 10.1109/Tit.2009.2021303  0.306
2009 Lu S, Manchala D, Ostrovsky R. Visual cryptography on graphs Journal of Combinatorial Optimization. 21: 47-66. DOI: 10.1007/S10878-009-9241-X  0.727
2008 Chandran N, Moriarty R, Ostrovsky R, Pandey O, Safari MA, Sahai A. Improved algorithms for optimal embeddings Acm Transactions On Algorithms. 4. DOI: 10.1145/1383369.1383376  0.718
2008 Dodis Y, Ostrovsky R, Reyzin L, Smith A. Fuzzy extractors: How to generate strong keys from biometrics and other noisy data Siam Journal On Computing. 38: 97-139. DOI: 10.1137/060651380  0.675
2007 Ostrovsky R, Rabani Y. Low distortion embeddings for edit distance Journal of the Acm. 54: 23. DOI: 10.1145/1284320.1284322  0.316
2007 Ostrovsky R, Skeith WE. Private Searching on Streaming Data Journal of Cryptology. 20: 397-430. DOI: 10.1007/S00145-007-0565-3  0.769
2005 Fitzi M, Garay JA, Maurer U, Ostrovsky R. Minimal complete primitives for secure multi-party computation Journal of Cryptology. 18: 37-61. DOI: 10.1007/S00145-004-0150-Y  0.408
2004 Borodin A, Ostrovsky R, Rabani Y. Subquadratic Approximation Algorithms for Clustering Problems in High Dimensional Spaces Machine Learning. 56: 153-167. DOI: 10.1023/B:Mach.0000033118.09057.80  0.314
2003 Kushilevitz E, Ostrovsky R, Rosén A. Amortizing Randomness in Private Multiparty Computations Siam Journal On Discrete Mathematics. 16: 533-544. DOI: 10.1137/S089548010135274X  0.366
2002 Ostrovsky R, Rabani Y. Polynomial-time approximation schemes for geometric min-sum median clustering Journal of the Acm (Jacm). 49: 139-156. DOI: 10.1145/506147.506149  0.336
2002 Mayer A, Ostrovsky R, Ofek Y, Yung M. Self-Stabilizing Symmetry Breaking in Constant Space Siam Journal On Computing. 31: 1571-1595. DOI: 10.1137/S0097539798285997  0.321
2001 Chuzhoy J, Ostrovsky R, Rabani Y. Approximation algorithms for the job interval selection problem and related scheduling problems Annual Symposium On Foundations of Computer Science - Proceedings. 348-356. DOI: 10.1287/Moor.1060.0218  0.319
2001 Di Crescenzo G, Ishai Y, Ostrovsky R. Universal Service-Providers for Private Information Retrieval Journal of Cryptology. 14: 37-74. DOI: 10.1007/S001450010008  0.319
2000 Kushilevitz E, Ostrovsky R, Rabani Y. Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces Siam Journal On Computing. 30: 457-474. DOI: 10.1137/S0097539798347177  0.345
2000 Kilian J, Kushilevitz E, Micali S, Ostrovsky R. Reducibility and Completeness in Private Computations Siam Journal On Computing. 29: 1189-1208. DOI: 10.1137/S0097539797321742  0.709
2000 Canetti R, Kushilevitz E, Ostrovsky R, Rosén A. Randomness versus Fault-Tolerance Journal of Cryptology. 13: 107-142. DOI: 10.1007/S001459910005  0.336
2000 Kutten S, Ostrovsky R, Patt-Shamir B. The Las-Vegas Processor Identity Problem (How and When to Be Unique) Journal of Algorithms. 37: 468-494. DOI: 10.1006/Jagm.2000.1110  0.374
1999 Kushilevitz E, Ostrovsky R, Rosén A. Characterizing Linear Size Circuits in Terms of Privacy Journal of Computer and System Sciences. 58: 129-136. DOI: 10.1006/Jcss.1997.1544  0.337
1998 Kushilevitz E, Ostrovsky R, Rosén A. Log-Space Polynomial End-to-End Communication Siam Journal On Computing. 27: 1531-1549. DOI: 10.1137/S0097539795296760  0.353
Show low-probability matches.