Publications

2019
Victor Lecomte and Weinstein, Omri . 2019. “Settling The Relationship Between Wilber's Bounds For Dynamic Optimality”. Corr, abs/1912.02858. . Publisher's Version
Zeev Dvir, Golovnev, Alexander , and Weinstein, Omri . 2019. “Static Data Structure Lower Bounds Imply Rigidity”. In Proceedings Of The 51St Annual Acm Sigact Symposium On Theory Of Computing, Stoc 2019, Phoenix, Az, Usa, June 23-26, 2019, Pp. 967–978. ACM. doi:10.1145/3313276.3316348. Publisher's Version
2018
Kasper Green Larsen, Weinstein, Omri , and Yu, Huacheng . 2018. “Crossing The Logarithmic Barrier For Dynamic Boolean Data Structure Lower Bounds”. In 2018 Information Theory And Applications Workshop, Ita 2018, San Diego, Ca, Usa, February 11-16, 2018, Pp. 1–40. IEEE. doi:10.1109/ITA.2018.8503262. Publisher's Version
Kasper Green Larsen, Weinstein, Omri , and Yu, Huacheng . 2018. “Crossing The Logarithmic Barrier For Dynamic Boolean Data Structure Lower Bounds”. In Proceedings Of The 50Th Annual Acm Sigact Symposium On Theory Of Computing, Stoc 2018, Los Angeles, Ca, Usa, June 25-29, 2018, Pp. 978–989. ACM. doi:10.1145/3188745.3188790. Publisher's Version
Sandip Sinha and Weinstein, Omri . 2018. “Local Decodability Of The Burrows-Wheeler Transform”. Corr, abs/1808.03978. . Publisher's Version
Sandip Sinha and Weinstein, Omri . 2018. “Local Decodability Of The Burrows-Wheeler Transform”. Electron. Colloquium Comput. Complex., 25, Pp. 141. . Publisher's Version
Sepehr Assadi, Sun, Xiaorui , and Weinstein, Omri . 2018. “Massively Parallel Algorithms For Finding Well-Connected Components In Sparse Graphs”. Corr, abs/1805.02974. . Publisher's Version
Alexander Golovnev, Regev, Oded , and Weinstein, Omri . 2018. “The Minrank Of Random Graphs”. Ieee Trans. Inf. Theory, 64, 11, Pp. 6990–6995. doi:10.1109/TIT.2018.2810384. Publisher's Version
Zeev Dvir, Golovnev, Alexander , and Weinstein, Omri . 2018. “Static Data Structure Lower Bounds Imply Rigidity”. Corr, abs/1811.02725. . Publisher's Version
Zeev Dvir, Golovnev, Alexander , and Weinstein, Omri . 2018. “Static Data Structure Lower Bounds Imply Rigidity”. Electron. Colloquium Comput. Complex., 25, Pp. 188. . Publisher's Version
2017
Alexandr Andoni, Ghaderi, Javad , Hsu, Daniel J. , Rubenstein, Dan , and Weinstein, Omri . 2017. “Coding With Asymmetric Prior Knowledge”. Corr, abs/1707.04875. . Publisher's Version
Kasper Green Larsen, Weinstein, Omri , and Yu, Huacheng . 2017. “Crossing The Logarithmic Barrier For Dynamic Boolean Data Structure Lower Bounds”. Corr, abs/1703.03575. . Publisher's Version
Kasper Green Larsen, Weinstein, Omri , and Yu, Huacheng . 2017. “Crossing The Logarithmic Barrier For Dynamic Boolean Data Structure Lower Bounds”. Electron. Colloquium Comput. Complex., 24, Pp. 47. . Publisher's Version
Mark Braverman, Kun-Ko, Young , Rubinstein, Aviad , and Weinstein, Omri . 2017. “Eth Hardness For Densest-\Emphk-Subgraph With Perfect Completeness”. In Proceedings Of The Twenty-Eighth Annual Acm-Siam Symposium On Discrete Algorithms, Soda 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, Pp. 1326–1341. SIAM. doi:10.1137/1.9781611974782.86. Publisher's Version
Alexander Golovnev, Regev, Oded , and Weinstein, Omri . 2017. “The Minrank Of Random Graphs”. In Approximation, Randomization, And Combinatorial Optimization. Algorithms And Techniques, Approx/Random 2017, August 16-18, 2017, Berkeley, Ca, Usa, 81:Pp. 46:1–46:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.APPROX-RANDOM.2017.46. Publisher's Version
Dmitry Gavinsky, Meir, Or , Weinstein, Omri , and Wigderson, Avi . 2017. “Toward Better Formula Lower Bounds: The Composition Of A Function And A Universal Relation”. Siam J. Comput., 46, 1, Pp. 114–131. doi:10.1137/15M1018319. Publisher's Version
2016
Omri Weinstein and Yu, Huacheng . 2016. “Amortized Dynamic Cell-Probe Lower Bounds From Four-Party Communication”. In Ieee 57Th Annual Symposium On Foundations Of Computer Science, Focs 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, Usa, Pp. 305–314. IEEE Computer Society. doi:10.1109/FOCS.2016.41. Publisher's Version
Omri Weinstein and Yu, Huacheng . 2016. “Amortized Dynamic Cell-Probe Lower Bounds From Four-Party Communication”. Corr, abs/1604.03030. . Publisher's Version
Omri Weinstein and Yu, Huacheng . 2016. “Amortized Dynamic Cell-Probe Lower Bounds From Four-Party Communication”. Electron. Colloquium Comput. Complex., 23, Pp. 54. . Publisher's Version
Tim Roughgarden and Weinstein, Omri . 2016. “On The Communication Complexity Of Approximate Fixed Points”. In Ieee 57Th Annual Symposium On Foundations Of Computer Science, Focs 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, Usa, Pp. 229–238. IEEE Computer Society. doi:10.1109/FOCS.2016.32. Publisher's Version