# Omri Weinstein

According to our database1, Omri Weinstein authored at least 43 papers between 2011 and 2020.

Collaborative distances:
• Dijkstra number2 of four.
• Erdős number3 of two.

Book
In proceedings
Article
PhD thesis
Other

## Bibliography

2020
Distributed Signaling Games.
ACM Trans. Economics and Comput., 2020

Polynomial Data Structure Lower Bounds in the Group Model.
Electronic Colloquium on Computational Complexity (ECCC), 2020

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

Faster Dynamic Matrix Inverse for Faster LPs.
CoRR, 2020

How to Store a Random Walk.
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

2019
Lower Bounds for Oblivious Near-Neighbor Search.
Electronic Colloquium on Computational Complexity (ECCC), 2019

An Adaptive Step Toward the Multiphase Conjecture.
Electronic Colloquium on Computational Complexity (ECCC), 2019

Settling the relationship between Wilber's bounds for dynamic optimality.
CoRR, 2019

An Adaptive Step Toward the Multiphase Conjecture.
CoRR, 2019

Massively Parallel Algorithms for Finding Well-Connected Components in Sparse Graphs.
Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, 2019

2018
Local Decodability of the Burrows-Wheeler Transform.
Electronic Colloquium on Computational Complexity (ECCC), 2018

Static Data Structure Lower Bounds Imply Rigidity.
Electronic Colloquium on Computational Complexity (ECCC), 2018

2017
Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation.
SIAM J. Comput., 2017

Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds.
Electronic Colloquium on Computational Complexity (ECCC), 2017

Coding with asymmetric prior knowledge.
CoRR, 2017

2016
Amortized Dynamic Cell-Probe Lower Bounds from Four-Party Communication.
Electronic Colloquium on Computational Complexity (ECCC), 2016

On the Communication Complexity of Approximate Fixed Points.
Electronic Colloquium on Computational Complexity (ECCC), 2016

The Minrank of Random Graphs.
Electronic Colloquium on Computational Complexity (ECCC), 2016

A Discrepancy Lower Bound for Information Complexity.
Algorithmica, 2016

An improved upper bound for the most informative boolean function conjecture.
Proceedings of the IEEE International Symposium on Information Theory, 2016

2015
The Simultaneous Communication of Disjointness with Applications to Data Streams.
Electronic Colloquium on Computational Complexity (ECCC), 2015

Information Complexity and the Quest for Interactive Compression.
Electronic Colloquium on Computational Complexity (ECCC), 2015

Dictatorship is the Most Informative Balanced Function at the Extremes.
Electronic Colloquium on Computational Complexity (ECCC), 2015

ETH Hardness for Densest-k-Subgraph with Perfect Completeness.
Electronic Colloquium on Computational Complexity (ECCC), 2015

Welfare Maximization with Limited Interaction.
Electronic Colloquium on Computational Complexity (ECCC), 2015

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

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

Welfare and Revenue Guarantees for Competitive Bundling Equilibrium.
Proceedings of the Web and Internet Economics - 11th International Conference, 2015

An Interactive Information Odometer and Applications.
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.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

2014
An Interactive Information Odometer with Applications.
Electronic Colloquium on Computational Complexity (ECCC), 2014

Approximating the best Nash Equilibrium in no(log n)-time breaks the Exponential Time Hypothesis.
Electronic Colloquium on Computational Complexity (ECCC), 2014

CoRR, 2014

2013
Toward Better Formula Lower Bounds: An Information Complexity Approach to the KRW Composition Conjecture.
Electronic Colloquium on Computational Complexity (ECCC), 2013

Direct product via round-preserving compression.
Electronic Colloquium on Computational Complexity (ECCC), 2013

2012
Approximating the Influence of Monotone Boolean Functions in O(√n) Query Complexity.
ACM Trans. Comput. Theory, 2012

Direct Products in Communication Complexity.
Electronic Colloquium on Computational Complexity (ECCC), 2012

Information lower bounds via self-reducibility.
Electronic Colloquium on Computational Complexity (ECCC), 2012

From Information to Exact Communication.
Electronic Colloquium on Computational Complexity (ECCC), 2012

Unsupervised SVMs: On the Complexity of the Furthest Hyperplane Problem.
Proceedings of the COLT 2012, 2012

2011
On the Furthest Hyperplane Problem and Maximal Margin Clustering
CoRR, 2011

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

Approximating the Influence of Monotone Boolean Functions in $O(\sqrt{n})$ Query Complexity.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011