Approximating the Influence of Monotone Boolean Functions in $O( sqrt{n})$ Query Complexity. - Dana Ron; Ronitt Rubinfeld; Muli Safra; Omri Weinstein (APPROX-RANDOM, 2011)

Approximating the Influence of a monotone Boolean function in O( sqrt{n}) query complexity - Dana Ron; Ronitt Rubinfeld; Muli Safra; Omri Weinstein (CoRR, 2011)

On the Furthest Hyperplane Problem and Maximal Margin Clustering - Edo Liberty; Shachar Lovett; Omri Weinstein (CoRR, 2011)

A discrepancy lower bound for information complexity. - Mark Braverman; Omri Weinstein (Electron. Colloquium Comput. Complex., 2011)

Unsupervised SVMs: On the Complexity of the Furthest Hyperplane Problem. - Zohar Shay Karnin; Edo Liberty; Shachar Lovett; Roy Schwartz 002; Omri Weinstein (COLT, 2012)

From Information to Exact Communication. - Mark Braverman; Ankit Garg; Denis Pankratov; Omri Weinstein (Electron. Colloquium Comput. Complex., 2012)

Information lower bounds via self-reducibility. - Mark Braverman; Ankit Garg; Denis Pankratov; Omri Weinstein (Electron. Colloquium Comput. Complex., 2012)

Direct Products in Communication Complexity. - Mark Braverman; Anup Rao 001; Omri Weinstein; Amir Yehudayoff (Electron. Colloquium Comput. Complex., 2012)

Approximating the Influence of Monotone Boolean Functions in O(√n) Query Complexity. - Dana Ron; Ronitt Rubinfeld; Muli Safra; Alex Samorodnitsky; Omri Weinstein (ACM Trans. Comput. Theory, 2012)

Direct product via round-preserving compression. - Mark Braverman; Anup Rao 001; Omri Weinstein; Amir Yehudayoff (Electron. Colloquium Comput. Complex., 2013)

Toward Better Formula Lower Bounds: An Information Complexity Approach to the KRW Composition Conjecture. - Dmitry Gavinsky; Or Meir; Omri Weinstein; Avi Wigderson (Electron. Colloquium Comput. Complex., 2013)

Display Advertising with Information Mediators. - Moran Feldman; Moshe Tennenholtz; Omri Weinstein (CoRR, 2014)

Approximating the best Nash Equilibrium in no(log n)-time breaks the Exponential Time Hypothesis. - Mark Braverman; Young Kun-Ko; Omri Weinstein (Electron. Colloquium Comput. Complex., 2014)

An Interactive Information Odometer with Applications. - Mark Braverman; Omri Weinstein (Electron. Colloquium Comput. Complex., 2014)

Approximating the best Nash Equilibrium in no(log n)-time breaks the Exponential Time Hypothesis. - Mark Braverman; Young Kun-Ko; Omri Weinstein (SODA, 2015)

An Interactive Information Odometer and Applications. - Mark Braverman; Omri Weinstein (STOC, 2015)

Welfare and Revenue Guarantees for Competitive Bundling Equilibrium. - Shahar Dobzinski; Michal Feldman; Inbal Talgam-Cohen; Omri Weinstein (WINE, 2015)

ETH Hardness for Densest-$k$-Subgraph with Perfect Completeness. - Mark Braverman; Young Kun-Ko; Aviad Rubinstein; Omri Weinstein (CoRR, 2015)

Information Complexity and the Quest for Interactive Compression (A Survey). - Omri Weinstein (CoRR, 2015)

Welfare Maximization with Limited Interaction. - Noga Alon; Noam Nisan; Ran Raz; Omri Weinstein (Electron. Colloquium Comput. Complex., 2015)

ETH Hardness for Densest-k-Subgraph with Perfect Completeness. - Mark Braverman; Young Kun-Ko; Aviad Rubinstein; Omri Weinstein (Electron. Colloquium Comput. Complex., 2015)

Dictatorship is the Most Informative Balanced Function at the Extremes. - Or Ordentlich; Ofer Shayevitz; Omri Weinstein (Electron. Colloquium Comput. Complex., 2015)

The Simultaneous Communication of Disjointness with Applications to Data Streams. - Omri Weinstein; David P. Woodruff (Electron. Colloquium Comput. Complex., 2015)

Information Complexity and the Quest for Interactive Compression. - Omri Weinstein (SIGACT News, 2015)

Interactive Information Complexity and Applications - Omri Weinstein (2015)

An improved upper bound for the most informative boolean function conjecture. - Or Ordentlich; Ofer Shayevitz; Omri Weinstein (ISIT, 2016)

The Minrank of Random Graphs. - Alexander Golovnev; Oded Regev 001; Omri Weinstein (Electron. Colloquium Comput. Complex., 2016)

On the Communication Complexity of Approximate Fixed Points. - Tim Roughgarden; Omri Weinstein (Electron. Colloquium Comput. Complex., 2016)

Amortized Dynamic Cell-Probe Lower Bounds from Four-Party Communication. - Omri Weinstein; Huacheng Yu (Electron. Colloquium Comput. Complex., 2016)

Coding with asymmetric prior knowledge. - Alexandr Andoni; Javad Ghaderi; Daniel J. Hsu; Dan Rubenstein; Omri Weinstein (CoRR, 2017)

Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation. - Dmitry Gavinsky; Or Meir; Omri Weinstein; Avi Wigderson (SIAM J. Comput., 2017)

Static Data Structure Lower Bounds Imply Rigidity. - Zeev Dvir; Alexander Golovnev; Omri Weinstein (Electron. Colloquium Comput. Complex., 2018)

Local Decodability of the Burrows-Wheeler Transform. - Sandip Sinha; Omri Weinstein (Electron. Colloquium Comput. Complex., 2018)

Massively Parallel Algorithms for Finding Well-Connected Components in Sparse Graphs. - Sepehr Assadi; Xiaorui Sun; Omri Weinstein (PODC, 2019)

An Adaptive Step Toward the Multiphase Conjecture. - Young Ko; Omri Weinstein (Electron. Colloquium Comput. Complex., 2019)

Lower Bounds for Oblivious Near-Neighbor Search. - Kasper Green Larsen; Tal Malkin; Omri Weinstein; Kevin Yeo (Electron. Colloquium Comput. Complex., 2019)

Settling the Relationship Between Wilber's Bounds for Dynamic Optimality. - Victor Lecomte; Omri Weinstein (ESA, 2020)

An Adaptive Step Toward the Multiphase Conjecture. - Young Kun-Ko; Omri Weinstein (FOCS, 2020)

How to Store a Random Walk. - Emanuele Viola; Omri Weinstein; Huacheng Yu (SODA, 2020)

Faster Dynamic Matrix Inverse for Faster LPs. - Shunhua Jiang; Zhao Song 002; Omri Weinstein; Hengjie Zhang (CoRR, 2020)

Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds. - Kasper Green Larsen; Omri Weinstein; Huacheng Yu (SIAM J. Comput., 2020)

Distributed Signaling Games. - Moran Feldman; Moshe Tennenholtz; Omri Weinstein (ACM Trans. Economics and Comput., 2020)

Training (Overparametrized) Neural Networks in Near-Linear Time. - Jan van den Brand; Binghui Peng; Zhao Song 002; Omri Weinstein (ITCS, 2021)

A faster algorithm for solving general LPs. - Shunhua Jiang; Zhao Song 002; Omri Weinstein; Hengjie Zhang (STOC, 2021)

Fast Distance Oracles for Any Symmetric Norm. - Yichuan Deng 002; Zhao Song 002; Omri Weinstein; Ruizhe Zhang 001 (NeurIPS, 2022)

Dynamic Least-Squares Regression. - Shunhua Jiang; Binghui Peng; Omri Weinstein (CoRR, 2022)

A Dynamic Fast Gaussian Transform. - Baihe Huang; Zhao Song 002; Omri Weinstein; Hengjie Zhang; Ruizhe Zhang 001 (CoRR, 2022)

Sparse Fourier Transform over Lattices: A Unified Approach to Signal Reconstruction. - Zhao Song 002; Baocheng Sun 002; Omri Weinstein; Ruizhe Zhang 001 (CoRR, 2022)

Training Overparametrized Neural Networks in Sublinear Time. - Hang Hu 014; Zhao Song 002; Omri Weinstein; Danyang Zhuo (CoRR, 2022)

Discrepancy Minimization in Input-Sparsity Time. - Yichuan Deng 002; Zhao Song 002; Omri Weinstein (CoRR, 2022)

Dynamic Kernel Sparsifiers. - Yichuan Deng 002; Wenyu Jin 001; Zhao Song 002; Xiaorui Sun; Omri Weinstein (CoRR, 2022)

Quartic Samples Suffice for Fourier Interpolation. - Zhao Song 002; Baocheng Sun 002; Omri Weinstein; Ruizhe Zhang 001 (FOCS, 2023)

The Complexity of Dynamic Least-Squares Regression. - Shunhua Jiang; Binghui Peng; Omri Weinstein (FOCS, 2023)

Infinite Lewis Weights in Spectral Graph Theory. - Amit Suliman; Omri Weinstein (CoRR, 2023)

A Faster Interior-Point Method for Sum-of-Squares Optimization. - Shunhua Jiang; Bento Natura; Omri Weinstein (Algorithmica, 2023)

Hardness Amplification for Dynamic Binary Search Trees. - Shunhua Jiang; Victor Lecomte; Omri Weinstein; Sorrachai Yingchareonthawornchai (ISAAC, 2024)

Polynomial Data Structure Lower Bounds in the Group Model. - Alexander Golovnev; Gleb Posobin; Oded Regev 001; Omri Weinstein (SIAM J. Comput., 2024)

A Framework for Building Data Structures from Communication Protocols. - Alexandr Andoni; Shunhua Jiang; Omri Weinstein (STOC, 2025)

Approximating the Held-Karp Bound for Metric TSP in Nearly Linear Work and Polylogarithmic Depth. - Zhuan Khye Koh; Omri Weinstein; Sorrachai Yingchareonthawornchai (STOC, 2025)

Proofs of Useful Work from Arbitrary Matrix Multiplication. - Ilan Komargodski; Itamar Schen; Omri Weinstein (IACR Cryptol. ePrint Arch., 2025)

Changing Base Without Losing Pace: A GPU-Efficient Alternative to MatMul in DNNs. - Nir Ailon; Akhiad Bercovich; Omri Weinstein (CoRR, 2025)

Proof of Work With External Utilities. - Yogev Bar-On; Ilan Komargodski; Omri Weinstein (CoRR, 2025)