Publications

2021
Shunhua Jiang, Zhao Song, Omri Weinstein, and Hengjie Zhang. 6/15/2021. “A faster algorithm for solving general LPs”. Publisher's Version
Jan van den Brand, Binghui Peng, Zhao Song, and Omri Weinstein. 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, edited by James R. Lee, 185: Pp. 63:1–63:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. Publisher's Version
2020
Young Kun-Ko and Omri Weinstein. 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. Publisher's Version
Kasper Green Larsen, Omri Weinstein, and Huacheng Yu. 2020. “Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds.” SIAM J. Comput., 49, 5. Publisher's Version
Moran Feldman, Moshe Tennenholtz, and Omri Weinstein. 2020. “Distributed Signaling Games.” ACM Trans. Economics and Comput., 8, 2, Pp. 7:1–7:26. Publisher's Version
Shunhua Jiang, Zhao Song, Omri Weinstein, and Hengjie Zhang. 2020. “Faster Dynamic Matrix Inverse for Faster LPs.” CoRR, abs/2004.07470. Publisher's Version
Emanuele Viola, Omri Weinstein, and Huacheng Yu. 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, edited by Shuchi Chawla, Pp. 426–445. SIAM. Publisher's Version
Kasper Green Larsen, Tal Malkin, Omri Weinstein, and Kevin Yeo. 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, edited by Shuchi Chawla, Pp. 1116–1134. SIAM. Publisher's Version
Alexander Golovnev, Gleb Posobin, Oded Regev, and Omri Weinstein. 2020. “Polynomial Data Structure Lower Bounds in the Group Model.” Electron. Colloquium Comput. Complex., 27, Pp. 57. Publisher's Version
Alexander Golovnev, Gleb Posobin, Oded Regev, and Omri Weinstein. 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. Publisher's Version
Victor Lecomte and Omri Weinstein. 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), edited by Fabrizio Grandoni, Grzegorz Herman, and Peter Sanders, 173: Pp. 68:1–68:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. Publisher's Version
Jan van den Brand, Binghui Peng, Zhao Song, and Omri Weinstein. 2020. “Training (Overparametrized) Neural Networks in Near-Linear Time.” CoRR, abs/2006.11648. Publisher's Version
2019
Young Ko and Omri Weinstein. 2019. “An Adaptive Step Toward the Multiphase Conjecture.” Electron. Colloquium Comput. Complex., 26, Pp. 144. Publisher's Version
Young Kun-Ko and Omri Weinstein. 2019. “An Adaptive Step Toward the Multiphase Conjecture.” CoRR, abs/1910.13543. Publisher's Version
Emanuele Viola, Omri Weinstein, and Huacheng Yu. 2019. “How to Store a Random Walk.” CoRR, abs/1907.10874. Publisher's Version
Sandip Sinha and Omri Weinstein. 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, edited by Moses Charikar and Edith Cohen, Pp. 744–755. ACM. Publisher's Version
Kasper Green Larsen, Tal Malkin, Omri Weinstein, and Kevin Yeo. 2019. “Lower Bounds for Oblivious Near-Neighbor Search.” IACR Cryptol. ePrint Arch., 2019, Pp. 377. Publisher's Version
Kasper Green Larsen, Tal Malkin, Omri Weinstein, and Kevin Yeo. 2019. “Lower Bounds for Oblivious Near-Neighbor Search.” Electron. Colloquium Comput. Complex., 26, Pp. 55. Publisher's Version
Kasper Green Larsen, Tal Malkin, Omri Weinstein, and Kevin Yeo. 2019. “Lower Bounds for Oblivious Near-Neighbor Search.” CoRR, abs/1904.04828. Publisher's Version
Sepehr Assadi, Xiaorui Sun, and Omri Weinstein. 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, edited by Peter Robinson and Faith Ellen, Pp. 461–470. ACM. Publisher's Version