Omri Weinstein

Affiliations:

The Hebrew University of Jerusalem, Israel
Columbia University, New York, NY, USA
Princeton University, USA (former)

According to our database¹, Omri Weinstein authored at least 55 papers between 2011 and 2023.

Collaborative distances:

Dijkstra number² of three.
Erdős number³ of two.

Timeline

Legend:

Book

In proceedings

Article

PhD thesis

Dataset

Other

Bibliography

2023

A Faster Interior-Point Method for Sum-of-Squares Optimization.

[BibT_eX]

[DOI]

Shunhua Jiang

Bento Natura

Omri Weinstein

Algorithmica, September, 2023

Infinite Lewis Weights in Spectral Graph Theory.

[BibT_eX]

[DOI]

Amit Suliman

Omri Weinstein

CoRR, 2023

The Complexity of Dynamic Least-Squares Regression.

[BibT_eX]

[DOI]

Shunhua Jiang

Binghui Peng

Omri Weinstein

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Quartic Samples Suffice for Fourier Interpolation.

[BibT_eX]

[DOI]

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

2022

Dynamic Kernel Sparsifiers.

[BibT_eX]

[DOI]

CoRR, 2022

Discrepancy Minimization in Input-Sparsity Time.

[BibT_eX]

[DOI]

Yichuan Deng

Zhao Song

Omri Weinstein

CoRR, 2022

Training Overparametrized Neural Networks in Sublinear Time.

[BibT_eX]

[DOI]

CoRR, 2022

Sparse Fourier Transform over Lattices: A Unified Approach to Signal Reconstruction.

[BibT_eX]

[DOI]

CoRR, 2022

A Dynamic Fast Gaussian Transform.

[BibT_eX]

[DOI]

CoRR, 2022

Dynamic Least-Squares Regression.

[BibT_eX]

[DOI]

Shunhua Jiang

Binghui Peng

Omri Weinstein

CoRR, 2022

Fast Distance Oracles for Any Symmetric Norm.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

2021

A faster algorithm for solving general LPs.

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Training (Overparametrized) Neural Networks in Near-Linear Time.

[BibT_eX]

[DOI]

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

2020

Distributed Signaling Games.

[BibT_eX]

[DOI]

Moran Feldman

Moshe Tennenholtz

Omri Weinstein

ACM Trans. Economics and Comput., 2020

Polynomial Data Structure Lower Bounds in the Group Model.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2020

Faster Dynamic Matrix Inverse for Faster LPs.

[BibT_eX]

[DOI]

CoRR, 2020

How to Store a Random Walk.

[BibT_eX]

[DOI]

Emanuele Viola

Omri Weinstein

Huacheng Yu

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

An Adaptive Step Toward the Multiphase Conjecture.

[BibT_eX]

[DOI]

Young Kun-Ko

Omri Weinstein

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Settling the Relationship Between Wilber's Bounds for Dynamic Optimality.

[BibT_eX]

[DOI]

Victor Lecomte

Omri Weinstein

Proceedings of the 28th Annual European Symposium on Algorithms, 2020

2019

Lower Bounds for Oblivious Near-Neighbor Search.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2019

An Adaptive Step Toward the Multiphase Conjecture.

[BibT_eX]

[DOI]

Young Ko

Omri Weinstein

Electron. Colloquium Comput. Complex., 2019

Massively Parallel Algorithms for Finding Well-Connected Components in Sparse Graphs.

[BibT_eX]

[DOI]

Sepehr Assadi

Xiaorui Sun

Omri Weinstein

Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, 2019

2018

Local Decodability of the Burrows-Wheeler Transform.

[BibT_eX]

[DOI]

Sandip Sinha

Omri Weinstein

Electron. Colloquium Comput. Complex., 2018

Static Data Structure Lower Bounds Imply Rigidity.

[BibT_eX]

[DOI]

Zeev Dvir

Alexander Golovnev

Omri Weinstein

Electron. Colloquium Comput. Complex., 2018

2017

Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation.

[BibT_eX]

[DOI]

SIAM J. Comput., 2017

Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds.

[BibT_eX]

[DOI]

Kasper Green Larsen

Omri Weinstein

Huacheng Yu

Electron. Colloquium Comput. Complex., 2017

Coding with asymmetric prior knowledge.

[BibT_eX]

[DOI]

CoRR, 2017

2016

Amortized Dynamic Cell-Probe Lower Bounds from Four-Party Communication.

[BibT_eX]

[DOI]

Omri Weinstein

Huacheng Yu

Electron. Colloquium Comput. Complex., 2016

On the Communication Complexity of Approximate Fixed Points.

[BibT_eX]

[DOI]

Tim Roughgarden

Omri Weinstein

Electron. Colloquium Comput. Complex., 2016

The Minrank of Random Graphs.

[BibT_eX]

[DOI]

Alexander Golovnev

Oded Regev

Omri Weinstein

Electron. Colloquium Comput. Complex., 2016

A Discrepancy Lower Bound for Information Complexity.

[BibT_eX]

[DOI]

Mark Braverman

Omri Weinstein

Algorithmica, 2016

An improved upper bound for the most informative boolean function conjecture.

[BibT_eX]

[DOI]

Or Ordentlich

Ofer Shayevitz

Omri Weinstein

Proceedings of the IEEE International Symposium on Information Theory, 2016

2015

The Simultaneous Communication of Disjointness with Applications to Data Streams.

[BibT_eX]

[DOI]

Omri Weinstein

David P. Woodruff

Electron. Colloquium Comput. Complex., 2015

Information Complexity and the Quest for Interactive Compression.

[BibT_eX]

[DOI]

Omri Weinstein

Electron. Colloquium Comput. Complex., 2015

Dictatorship is the Most Informative Balanced Function at the Extremes.

[BibT_eX]

[DOI]

Or Ordentlich

Ofer Shayevitz

Omri Weinstein

Electron. Colloquium Comput. Complex., 2015

ETH Hardness for Densest-k-Subgraph with Perfect Completeness.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

Welfare Maximization with Limited Interaction.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

Information Complexity and the Quest for Interactive Compression (A Survey).

[BibT_eX]

[DOI]

Omri Weinstein

CoRR, 2015

ETH Hardness for Densest-$k$-Subgraph with Perfect Completeness.

[BibT_eX]

[DOI]

CoRR, 2015

Welfare and Revenue Guarantees for Competitive Bundling Equilibrium.

[BibT_eX]

[DOI]

Proceedings of the Web and Internet Economics - 11th International Conference, 2015

An Interactive Information Odometer and Applications.

[BibT_eX]

[DOI]

Mark Braverman

Omri Weinstein

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Approximating the best Nash Equilibrium in no(log n)-time breaks the Exponential Time Hypothesis.

[BibT_eX]

[DOI]

Mark Braverman

Young Kun-Ko

Omri Weinstein

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

2014

An Interactive Information Odometer with Applications.

[BibT_eX]

[DOI]

Mark Braverman

Omri Weinstein

Electron. Colloquium Comput. Complex., 2014

Approximating the best Nash Equilibrium in no(log n)-time breaks the Exponential Time Hypothesis.

[BibT_eX]

[DOI]

Mark Braverman

Young Kun-Ko

Omri Weinstein

Electron. Colloquium Comput. Complex., 2014

Display Advertising with Information Mediators.

[BibT_eX]

[DOI]

Moran Feldman

Moshe Tennenholtz

Omri Weinstein

CoRR, 2014

2013

Toward Better Formula Lower Bounds: An Information Complexity Approach to the KRW Composition Conjecture.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

Direct product via round-preserving compression.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

2012

Approximating the Influence of Monotone Boolean Functions in O(√n) Query Complexity.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2012

Direct Products in Communication Complexity.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

Information lower bounds via self-reducibility.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

From Information to Exact Communication.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

Unsupervised SVMs: On the Complexity of the Furthest Hyperplane Problem.

[BibT_eX]

[DOI]

Proceedings of the COLT 2012, 2012

2011

On the Furthest Hyperplane Problem and Maximal Margin Clustering

[BibT_eX]

[DOI]

Edo Liberty

Shachar Lovett

Omri Weinstein

CoRR, 2011

Approximating the Influence of a monotone Boolean function in O(\sqrt{n}) query complexity

[BibT_eX]

[DOI]

CoRR, 2011

Approximating the Influence of Monotone Boolean Functions in $O(\sqrt{n})$ Query Complexity.

[BibT_eX]

[DOI]

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

Omri Weinstein

Timeline

Legend:

Links

Online presence:

On csauthors.net:

Bibliography

Loading...