Omri Weinstein

Publication Activity (10 Years)

Years Active: 2011-2023
Publications (10 Years): 62

Top Topics

Fourier Transform

Universal Relation

Spectral Graph Theory

Top Venues

Electron. Colloquium Comput. Complex.

Publications

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