Publications

2021
Shunhua Jiang, Song, Zhao , Weinstein, Omri , and Zhang, Hengjie . 6/15/2021. “A Faster Algorithm For Solving General Lps”. . Publisher's Version
Jan van den Brand, Peng, Binghui , Song, Zhao , and Weinstein, Omri . 2021. “Training (Overparametrized) Neural Networks In Near-Linear Time”. In 12Th Innovations In Theoretical Computer Science Conference, Itcs 2021, January 6-8, 2021, Virtual Conference, 185:Pp. 63:1–63:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ITCS.2021.63. Publisher's Version
2020
Young Kun-Ko and Weinstein, Omri . 2020. “An Adaptive Step Toward The Multiphase Conjecture”. In 61St Ieee Annual Symposium On Foundations Of Computer Science, Focs 2020, Durham, Nc, Usa, November 16-19, 2020, Pp. 752–761. IEEE. doi:10.1109/FOCS46700.2020.00075. Publisher's Version
Kasper Green Larsen, Weinstein, Omri , and Yu, Huacheng . 2020. “Crossing The Logarithmic Barrier For Dynamic Boolean Data Structure Lower Bounds”. Siam J. Comput., 49, 5. doi:10.1137/18M1198429. Publisher's Version
Moran Feldman, Tennenholtz, Moshe , and Weinstein, Omri . 2020. “Distributed Signaling Games”. Acm Trans. Economics And Comput., 8, 2, Pp. 7:1–7:26. doi:10.1145/3381529. Publisher's Version
Shunhua Jiang, Song, Zhao , Weinstein, Omri , and Zhang, Hengjie . 2020. “Faster Dynamic Matrix Inverse For Faster Lps”. Corr, abs/2004.07470. . Publisher's Version
Emanuele Viola, Weinstein, Omri , and Yu, Huacheng . 2020. “How To Store A Random Walk”. In Proceedings Of The 2020 Acm-Siam Symposium On Discrete Algorithms, Soda 2020, Salt Lake City, Ut, Usa, January 5-8, 2020, Pp. 426–445. SIAM. doi:10.1137/1.9781611975994.26. Publisher's Version
Kasper Green Larsen, Malkin, Tal , Weinstein, Omri , and Yeo, Kevin . 2020. “Lower Bounds For Oblivious Near-Neighbor Search”. In Proceedings Of The 2020 Acm-Siam Symposium On Discrete Algorithms, Soda 2020, Salt Lake City, Ut, Usa, January 5-8, 2020, Pp. 1116–1134. SIAM. doi:10.1137/1.9781611975994.68. Publisher's Version
Alexander Golovnev, Posobin, Gleb , Regev, Oded , and Weinstein, Omri . 2020. “Polynomial Data Structure Lower Bounds In The Group Model”. In 61St Ieee Annual Symposium On Foundations Of Computer Science, Focs 2020, Durham, Nc, Usa, November 16-19, 2020, Pp. 740–751. IEEE. doi:10.1109/FOCS46700.2020.00074. Publisher's Version
Alexander Golovnev, Posobin, Gleb , Regev, Oded , and Weinstein, Omri . 2020. “Polynomial Data Structure Lower Bounds In The Group Model”. Electron. Colloquium Comput. Complex., 27, Pp. 57. . Publisher's Version
Victor Lecomte and Weinstein, Omri . 2020. “Settling The Relationship Between Wilber's Bounds For Dynamic Optimality”. In 28Th Annual European Symposium On Algorithms, Esa 2020, September 7-9, 2020, Pisa, Italy (Virtual Conference), 173:Pp. 68:1–68:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ESA.2020.68. Publisher's Version
Jan van den Brand, Peng, Binghui , Song, Zhao , and Weinstein, Omri . 2020. “Training (Overparametrized) Neural Networks In Near-Linear Time”. Corr, abs/2006.11648. . Publisher's Version
2019
Young Ko and Weinstein, Omri . 2019. “An Adaptive Step Toward The Multiphase Conjecture”. Electron. Colloquium Comput. Complex., 26, Pp. 144. . Publisher's Version
Young Kun-Ko and Weinstein, Omri . 2019. “An Adaptive Step Toward The Multiphase Conjecture”. Corr, abs/1910.13543. . Publisher's Version
Emanuele Viola, Weinstein, Omri , and Yu, Huacheng . 2019. “How To Store A Random Walk”. Corr, abs/1907.10874. . Publisher's Version
Sandip Sinha and Weinstein, Omri . 2019. “Local Decodability Of The Burrows-Wheeler Transform”. In Proceedings Of The 51St Annual Acm Sigact Symposium On Theory Of Computing, Stoc 2019, Phoenix, Az, Usa, June 23-26, 2019, Pp. 744–755. ACM. doi:10.1145/3313276.3316317. Publisher's Version
Kasper Green Larsen, Malkin, Tal , Weinstein, Omri , and Yeo, Kevin . 2019. “Lower Bounds For Oblivious Near-Neighbor Search”. Corr, abs/1904.04828. . Publisher's Version
Kasper Green Larsen, Malkin, Tal , Weinstein, Omri , and Yeo, Kevin . 2019. “Lower Bounds For Oblivious Near-Neighbor Search”. Electron. Colloquium Comput. Complex., 26, Pp. 55. . Publisher's Version
Kasper Green Larsen, Malkin, Tal , Weinstein, Omri , and Yeo, Kevin . 2019. “Lower Bounds For Oblivious Near-Neighbor Search”. Iacr Cryptol. Eprint Arch., 2019, Pp. 377. . Publisher's Version
Sepehr Assadi, Sun, Xiaorui , and Weinstein, Omri . 2019. “Massively Parallel Algorithms For Finding Well-Connected Components In Sparse Graphs”. In Proceedings Of The 2019 Acm Symposium On Principles Of Distributed Computing, Podc 2019, Toronto, On, Canada, July 29 - August 2, 2019, Pp. 461–470. ACM. doi:10.1145/3293611.3331596. Publisher's Version