Omri Weinstein

114 papers A* 26A 3B 2Misc 2Journal 74Unranked 6
YearRankTypeTitle / Venue / Authors
2026 J jnl
Improved Sparse Recovery for Approximate Matrix Multiplication.
CoRR
Yahel Uffenheimer, Omri Weinstein
2025 J jnl
(Approximate) Matrix Multiplication via Convolutions.
CoRR
Kevin Pratt, Yahel Uffenheimer, Omri Weinstein
2025 A* conf
A Framework for Building Data Structures from Communication Protocols.
STOC
Alexandr Andoni, Shunhua Jiang, Omri Weinstein
2025 J jnl
A Framework for Building Data Structures from Communication Protocols.
CoRR
Alexandr Andoni, Shunhua Jiang, Omri Weinstein
2025 A* conf
Approximating the Held-Karp Bound for Metric TSP in Nearly Linear Work and Polylogarithmic Depth.
STOC
Zhuan Khye Koh, Omri Weinstein, Sorrachai Yingchareonthawornchai
2025 J jnl
Changing Base Without Losing Pace: A GPU-Efficient Alternative to MatMul in DNNs.
CoRR
Nir Ailon, Akhiad Bercovich, Omri Weinstein
2025 A* conf
Discrepancy Minimization in Input-Sparsity Time.
ICML
Yichuan Deng, Xiaoyu Li, Zhao Song, Omri Weinstein
2025 J jnl
Proof of Work With External Utilities.
CoRR
Yogev Bar-On, Ilan Komargodski, Omri Weinstein
2025 J jnl
Proofs of Useful Work from Arbitrary Matrix Multiplication.
CoRR
Ilan Komargodski, Itamar Schen, Omri Weinstein
2025 J jnl
Proofs of Useful Work from Arbitrary Matrix Multiplication.
IACR Cryptol. ePrint Arch.
Ilan Komargodski, Itamar Schen, Omri Weinstein
2024 J jnl
Approximating the Held-Karp Bound for Metric TSP in Nearly Linear Work and Polylogarithmic Depth.
CoRR
Zhuan Khye Koh, Omri Weinstein, Sorrachai Yingchareonthawornchai
2024 B conf
Hardness Amplification for Dynamic Binary Search Trees.
ISAAC
Shunhua Jiang, Victor Lecomte, Omri Weinstein, Sorrachai Yingchareonthawornchai
2024 J jnl
Hardness Amplification for Dynamic Binary Search Trees.
CoRR
Shunhua Jiang, Victor Lecomte, Omri Weinstein, Sorrachai Yingchareonthawornchai
2024 J jnl
Polynomial Data Structure Lower Bounds in the Group Model.
SIAM J. Comput.
Alexander Golovnev, Gleb Posobin, Oded Regev, Omri Weinstein
2023 J jnl
A Faster Interior-Point Method for Sum-of-Squares Optimization.
Algorithmica
Shunhua Jiang, Bento Natura, Omri Weinstein
2023 J jnl
Infinite Lewis Weights in Spectral Graph Theory.
CoRR
Amit Suliman, Omri Weinstein
2023 A* conf
Quartic Samples Suffice for Fourier Interpolation.
FOCS
Zhao Song, Baocheng Sun, Omri Weinstein, Ruizhe Zhang
2023 A* conf
The Complexity of Dynamic Least-Squares Regression.
FOCS
Shunhua Jiang, Binghui Peng, Omri Weinstein
2022 J jnl
A Dynamic Fast Gaussian Transform.
CoRR
Baihe Huang, Zhao Song, Omri Weinstein, Hengjie Zhang, Ruizhe Zhang
2022 A* conf
A Faster Interior-Point Method for Sum-Of-Squares Optimization.
ICALP
Shunhua Jiang, Bento Natura, Omri Weinstein
2022 J jnl
A Faster Interior-Point Method for Sum-of-Squares Optimization.
CoRR
Shunhua Jiang, Bento Natura, Omri Weinstein
2022 J jnl
Discrepancy Minimization in Input-Sparsity Time.
CoRR
Yichuan Deng, Zhao Song, Omri Weinstein
2022 J jnl
Dynamic Kernel Sparsifiers.
CoRR
Yichuan Deng, Wenyu Jin, Zhao Song, Xiaorui Sun, Omri Weinstein
2022 J jnl
Dynamic Least-Squares Regression.
CoRR
Shunhua Jiang, Binghui Peng, Omri Weinstein
2022 A* conf
Fast Distance Oracles for Any Symmetric Norm.
NeurIPS
Yichuan Deng, Zhao Song, Omri Weinstein, Ruizhe Zhang
2022 J jnl
Fast Distance Oracles for Any Symmetric Norm.
CoRR
Yichuan Deng, Zhao Song, Omri Weinstein, Ruizhe Zhang
2022 J jnl
Quartic Samples Suffice for Fourier Interpolation.
CoRR
Zhao Song, Baocheng Sun, Omri Weinstein, Ruizhe Zhang
2022 J jnl
Sparse Fourier Transform over Lattices: A Unified Approach to Signal Reconstruction.
CoRR
Zhao Song, Baocheng Sun, Omri Weinstein, Ruizhe Zhang
2022 J jnl
Training Overparametrized Neural Networks in Sublinear Time.
CoRR
Hang Hu, Zhao Song, Omri Weinstein, Danyang Zhuo
2021 A* conf
A faster algorithm for solving general LPs.
STOC
Shunhua Jiang, Zhao Song, Omri Weinstein, Hengjie Zhang
2021 A conf
Training (Overparametrized) Neural Networks in Near-Linear Time.
ITCS
Jan van den Brand, Binghui Peng, Zhao Song, Omri Weinstein
2020 A* conf
An Adaptive Step Toward the Multiphase Conjecture.
FOCS
Young Kun-Ko, Omri Weinstein
2020 J jnl
Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds.
SIAM J. Comput.
Kasper Green Larsen, Omri Weinstein, Huacheng Yu
2020 J jnl
Distributed Signaling Games.
ACM Trans. Economics and Comput.
Moran Feldman, Moshe Tennenholtz, Omri Weinstein
2020 J jnl
Faster Dynamic Matrix Inverse for Faster LPs.
CoRR
Shunhua Jiang, Zhao Song, Omri Weinstein, Hengjie Zhang
2020 A* conf
How to Store a Random Walk.
SODA
Emanuele Viola, Omri Weinstein, Huacheng Yu
2020 A* conf
Lower Bounds for Oblivious Near-Neighbor Search.
SODA
Kasper Green Larsen, Tal Malkin, Omri Weinstein, Kevin Yeo
2020 A* conf
Polynomial Data Structure Lower Bounds in the Group Model.
FOCS
Alexander Golovnev, Gleb Posobin, Oded Regev, Omri Weinstein
2020 J jnl
Polynomial Data Structure Lower Bounds in the Group Model.
Electron. Colloquium Comput. Complex.
Alexander Golovnev, Gleb Posobin, Oded Regev, Omri Weinstein
2020 A conf
Settling the Relationship Between Wilber's Bounds for Dynamic Optimality.
ESA
Victor Lecomte, Omri Weinstein
2020 J jnl
Training (Overparametrized) Neural Networks in Near-Linear Time.
CoRR
Jan van den Brand, Binghui Peng, Zhao Song, Omri Weinstein
2019 J jnl
An Adaptive Step Toward the Multiphase Conjecture.
CoRR
Young Kun-Ko, Omri Weinstein
2019 J jnl
An Adaptive Step Toward the Multiphase Conjecture.
Electron. Colloquium Comput. Complex.
Young Ko, Omri Weinstein
2019 J jnl
How to Store a Random Walk.
CoRR
Emanuele Viola, Omri Weinstein, Huacheng Yu
2019 A* conf
Local decodability of the Burrows-Wheeler transform.
STOC
Sandip Sinha, Omri Weinstein
2019 J jnl
Lower Bounds for Oblivious Near-Neighbor Search.
CoRR
Kasper Green Larsen, Tal Malkin, Omri Weinstein, Kevin Yeo
2019 J jnl
Lower Bounds for Oblivious Near-Neighbor Search.
Electron. Colloquium Comput. Complex.
Kasper Green Larsen, Tal Malkin, Omri Weinstein, Kevin Yeo
2019 J jnl
Lower Bounds for Oblivious Near-Neighbor Search.
IACR Cryptol. ePrint Arch.
Kasper Green Larsen, Tal Malkin, Omri Weinstein, Kevin Yeo
2019 A* conf
Massively Parallel Algorithms for Finding Well-Connected Components in Sparse Graphs.
PODC
Sepehr Assadi, Xiaorui Sun, Omri Weinstein
2019 J jnl
Settling the relationship between Wilber's bounds for dynamic optimality.
CoRR
Victor Lecomte, Omri Weinstein
2019 A* conf
Static data structure lower bounds imply rigidity.
STOC
Zeev Dvir, Alexander Golovnev, Omri Weinstein
2018 Misc conf
Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds.
ITA
Kasper Green Larsen, Omri Weinstein, Huacheng Yu
2018 A* conf
Crossing the logarithmic barrier for dynamic Boolean data structure lower bounds.
STOC
Kasper Green Larsen, Omri Weinstein, Huacheng Yu
2018 J jnl
Local Decodability of the Burrows-Wheeler Transform.
CoRR
Sandip Sinha, Omri Weinstein
2018 J jnl
Local Decodability of the Burrows-Wheeler Transform.
Electron. Colloquium Comput. Complex.
Sandip Sinha, Omri Weinstein
2018 J jnl
Massively Parallel Algorithms for Finding Well-Connected Components in Sparse Graphs.
CoRR
Sepehr Assadi, Xiaorui Sun, Omri Weinstein
2018 J jnl
Static Data Structure Lower Bounds Imply Rigidity.
CoRR
Zeev Dvir, Alexander Golovnev, Omri Weinstein
2018 J jnl
Static Data Structure Lower Bounds Imply Rigidity.
Electron. Colloquium Comput. Complex.
Zeev Dvir, Alexander Golovnev, Omri Weinstein
2018 J jnl
The Minrank of Random Graphs.
IEEE Trans. Inf. Theory
Alexander Golovnev, Oded Regev, Omri Weinstein
2017 J jnl
Coding with asymmetric prior knowledge.
CoRR
Alexandr Andoni, Javad Ghaderi, Daniel J. Hsu, Dan Rubenstein, Omri Weinstein
2017 J jnl
Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds.
CoRR
Kasper Green Larsen, Omri Weinstein, Huacheng Yu
2017 J jnl
Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds.
Electron. Colloquium Comput. Complex.
Kasper Green Larsen, Omri Weinstein, Huacheng Yu
2017 A* conf
ETH Hardness for Densest-
SODA
Mark Braverman, Young Kun-Ko, Aviad Rubinstein, Omri Weinstein
2017 — conf
The Minrank of Random Graphs.
APPROX-RANDOM
Alexander Golovnev, Oded Regev, Omri Weinstein
2017 J jnl
Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation.
SIAM J. Comput.
Dmitry Gavinsky, Or Meir, Omri Weinstein, Avi Wigderson
2016 J jnl
A Discrepancy Lower Bound for Information Complexity.
Algorithmica
Mark Braverman, Omri Weinstein
2016 A* conf
Amortized Dynamic Cell-Probe Lower Bounds from Four-Party Communication.
FOCS
Omri Weinstein, Huacheng Yu
2016 J jnl
Amortized Dynamic Cell-Probe Lower Bounds from Four-Party Communication.
CoRR
Omri Weinstein, Huacheng Yu
2016 J jnl
Amortized Dynamic Cell-Probe Lower Bounds from Four-Party Communication.
Electron. Colloquium Comput. Complex.
Omri Weinstein, Huacheng Yu
2016 B conf
An improved upper bound for the most informative boolean function conjecture.
ISIT
Or Ordentlich, Ofer Shayevitz, Omri Weinstein
2016 A conf
Distributed Signaling Games.
ESA
Moran Feldman, Moshe Tennenholtz, Omri Weinstein
2016 J jnl
Information Lower Bounds via Self-Reducibility.
Theory Comput. Syst.
Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein
2016 A* conf
On the Communication Complexity of Approximate Fixed Points.
FOCS
Tim Roughgarden, Omri Weinstein
2016 J jnl
On the Communication Complexity of Approximate Fixed Points.
Electron. Colloquium Comput. Complex.
Tim Roughgarden, Omri Weinstein
2016 J jnl
The Minrank of Random Graphs.
CoRR
Alexander Golovnev, Oded Regev, Omri Weinstein
2016 J jnl
The Minrank of Random Graphs.
Electron. Colloquium Comput. Complex.
Alexander Golovnev, Oded Regev, Omri Weinstein
2015 A* conf
An Interactive Information Odometer and Applications.
STOC
Mark Braverman, Omri Weinstein
2015 A* conf
Approximating the best Nash Equilibrium in
SODA
Mark Braverman, Young Kun-Ko, Omri Weinstein
2015 J jnl
Dictatorship is the Most Informative Balanced Function at the Extremes.
CoRR
Or Ordentlich, Ofer Shayevitz, Omri Weinstein
2015 J jnl
Dictatorship is the Most Informative Balanced Function at the Extremes.
Electron. Colloquium Comput. Complex.
Or Ordentlich, Ofer Shayevitz, Omri Weinstein
2015 J jnl
ETH Hardness for Densest-
Electron. Colloquium Comput. Complex.
Mark Braverman, Young Kun-Ko, Aviad Rubinstein, Omri Weinstein
2015 J jnl
ETH Hardness for Densest-$k$-Subgraph with Perfect Completeness.
CoRR
Mark Braverman, Young Kun-Ko, Aviad Rubinstein, Omri Weinstein
2015 J jnl
Information Complexity and the Quest for Interactive Compression (A Survey).
CoRR
Omri Weinstein
2015 J jnl
Information Complexity and the Quest for Interactive Compression.
Electron. Colloquium Comput. Complex.
Omri Weinstein
2015 J jnl
Information Complexity and the Quest for Interactive Compression.
SIGACT News
Omri Weinstein
2015 — —
Interactive Information Complexity and Applications
Omri Weinstein
2015 — conf
The Simultaneous Communication of Disjointness with Applications to Data Streams.
ICALP (1)
Omri Weinstein, David P. Woodruff
2015 J jnl
The Simultaneous Communication of Disjointness with Applications to Data Streams.
Electron. Colloquium Comput. Complex.
Omri Weinstein, David P. Woodruff
2015 A* conf
Welfare Maximization with Limited Interaction.
FOCS
Noga Alon, Noam Nisan, Ran Raz, Omri Weinstein
2015 J jnl
Welfare Maximization with Limited Interaction.
CoRR
Noga Alon, Noam Nisan, Ran Raz, Omri Weinstein
2015 J jnl
Welfare Maximization with Limited Interaction.
Electron. Colloquium Comput. Complex.
Noga Alon, Noam Nisan, Ran Raz, Omri Weinstein
2015 — conf
Welfare and Revenue Guarantees for Competitive Bundling Equilibrium.
WINE
Shahar Dobzinski, Michal Feldman, Inbal Talgam-Cohen, Omri Weinstein
2014 J jnl
An Interactive Information Odometer with Applications.
Electron. Colloquium Comput. Complex.
Mark Braverman, Omri Weinstein
2014 J jnl
Approximating the best Nash Equilibrium in n
Electron. Colloquium Comput. Complex.
Mark Braverman, Young Kun-Ko, Omri Weinstein
2014 J jnl
Display Advertising with Information Mediators.
CoRR
Moran Feldman, Moshe Tennenholtz, Omri Weinstein
2014 A* conf
Toward better formula lower bounds: an information complexity approach to the KRW composition conjecture.
STOC
Dmitry Gavinsky, Or Meir, Omri Weinstein, Avi Wigderson
2014 J jnl
Welfare and Revenue Guarantees for Competitive Bundling Equilibrium.
CoRR
Shahar Dobzinski, Michal Feldman, Inbal Talgam-Cohen, Omri Weinstein
2013 — conf
Direct Product via Round-Preserving Compression.
ICALP (1)
Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff
2013 A* conf
Direct Products in Communication Complexity.
FOCS
Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff
2013 J jnl
Direct product via round-preserving compression.
Electron. Colloquium Comput. Complex.
Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff
2013 A* conf
From information to exact communication.
STOC
Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein
2013 Misc conf
Information Lower Bounds via Self-reducibility.
CSR
Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein
2013 J jnl
Toward Better Formula Lower Bounds: An Information Complexity Approach to the KRW Composition Conjecture.
Electron. Colloquium Comput. Complex.
Dmitry Gavinsky, Or Meir, Omri Weinstein, Avi Wigderson
2012 — conf
A Discrepancy Lower Bound for Information Complexity.
APPROX-RANDOM
Mark Braverman, Omri Weinstein
2012 J jnl
Approximating the Influence of Monotone Boolean Functions in O(√n) Query Complexity.
ACM Trans. Comput. Theory
Dana Ron, Ronitt Rubinfeld, Muli Safra, Alex Samorodnitsky, Omri Weinstein
2012 J jnl
Direct Products in Communication Complexity.
Electron. Colloquium Comput. Complex.
Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff
2012 J jnl
From Information to Exact Communication.
Electron. Colloquium Comput. Complex.
Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein
2012 J jnl
Information lower bounds via self-reducibility.
Electron. Colloquium Comput. Complex.
Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein
2012 A* conf
Unsupervised SVMs: On the Complexity of the Furthest Hyperplane Problem.
COLT
Zohar Shay Karnin, Edo Liberty, Shachar Lovett, Roy Schwartz, Omri Weinstein
2011 J jnl
A discrepancy lower bound for information complexity
CoRR
Mark Braverman, Omri Weinstein
2011 J jnl
A discrepancy lower bound for information complexity.
Electron. Colloquium Comput. Complex.
Mark Braverman, Omri Weinstein
2011 — conf
Approximating the Influence of Monotone Boolean Functions in $O(\sqrt{n})$ Query Complexity.
APPROX-RANDOM
Dana Ron, Ronitt Rubinfeld, Muli Safra, Omri Weinstein
2011 J jnl
Approximating the Influence of a monotone Boolean function in O(\sqrt{n}) query complexity
CoRR
Dana Ron, Ronitt Rubinfeld, Muli Safra, Omri Weinstein
2011 J jnl
On the Furthest Hyperplane Problem and Maximal Margin Clustering
CoRR
Edo Liberty, Shachar Lovett, Omri Weinstein