# Omri Weinstein

According to our database

Collaborative distances:

^{1}, Omri Weinstein authored at least 33 papers between 2011 and 2019.Collaborative distances:

## Timeline

#### Legend:

Book In proceedings Article PhD thesis Other## Links

#### Homepage:

#### On csauthors.net:

## Bibliography

2019

Lower Bounds for Oblivious Near-Neighbor Search.

IACR Cryptology ePrint Archive, 2019

Lower Bounds for Oblivious Near-Neighbor Search.

Electronic Colloquium on Computational Complexity (ECCC), 2019

Local decodability of the Burrows-Wheeler transform.

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Static data structure lower bounds imply rigidity.

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 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

Crossing the logarithmic barrier for dynamic Boolean data structure lower bounds.

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

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

Proceedings of the 2018 Information Theory and Applications Workshop, 2018

2017

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

SIAM J. Comput., 2017

ETH Hardness for Densest-

*k*-Subgraph with Perfect Completeness.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

The Minrank of Random Graphs.

Proceedings of the Approximation, 2017

2016

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

Proceedings of the IEEE International Symposium on Information Theory, 2016

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

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

On the Communication Complexity of Approximate Fixed Points.

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

Distributed Signaling Games.

Proceedings of the 24th Annual European Symposium on Algorithms, 2016

2015

Information Complexity and the Quest for Interactive Compression.

SIGACT News, 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

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

*n*^{o}^{(log n)}-time breaks the Exponential Time Hypothesis.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

The Simultaneous Communication of Disjointness with Applications to Data Streams.

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

Welfare Maximization with Limited Interaction.

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

2014

An Interactive Information Odometer with Applications.

Electronic Colloquium on Computational Complexity (ECCC), 2014

Approximating the best Nash Equilibrium in n

^{o(log n)}-time breaks the Exponential Time Hypothesis.
Electronic Colloquium on Computational Complexity (ECCC), 2014

Toward better formula lower bounds: an information complexity approach to the KRW composition conjecture.

Proceedings of the Symposium on Theory of Computing, 2014

2013

From information to exact communication.

Proceedings of the Symposium on Theory of Computing Conference, 2013

Direct Product via Round-Preserving Compression.

Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

Direct Products in Communication Complexity.

Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

Information Lower Bounds via Self-reducibility.

Proceedings of the Computer Science - Theory and Applications, 2013

2012

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

TOCT, 2012

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

Proceedings of the COLT 2012, 2012

A Discrepancy Lower Bound for Information Complexity.

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

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