Omri Weinstein

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

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

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2021
Training (Overparametrized) Neural Networks in Near-Linear Time.
Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

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

Polynomial Data Structure Lower Bounds in the Group Model.
Electron. Colloquium Comput. Complex., 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

An Adaptive Step Toward the Multiphase Conjecture.
Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Settling the Relationship Between Wilber's Bounds for Dynamic Optimality.
Proceedings of the 28th Annual European Symposium on Algorithms, 2020

2019
Lower Bounds for Oblivious Near-Neighbor Search.
Electron. Colloquium Comput. Complex., 2019

An Adaptive Step Toward the Multiphase Conjecture.
Electron. Colloquium Comput. Complex., 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.
Electron. Colloquium Comput. Complex., 2018

Static Data Structure Lower Bounds Imply Rigidity.
Electron. Colloquium Comput. Complex., 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.
Electron. Colloquium Comput. Complex., 2017

Coding with asymmetric prior knowledge.
CoRR, 2017

2016
Amortized Dynamic Cell-Probe Lower Bounds from Four-Party Communication.
Electron. Colloquium Comput. Complex., 2016

On the Communication Complexity of Approximate Fixed Points.
Electron. Colloquium Comput. Complex., 2016

The Minrank of Random Graphs.
Electron. Colloquium Comput. Complex., 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.
Electron. Colloquium Comput. Complex., 2015

Information Complexity and the Quest for Interactive Compression.
Electron. Colloquium Comput. Complex., 2015

Dictatorship is the Most Informative Balanced Function at the Extremes.
Electron. Colloquium Comput. Complex., 2015

ETH Hardness for Densest-<i>k</i>-Subgraph with Perfect Completeness.
Electron. Colloquium Comput. Complex., 2015

Welfare Maximization with Limited Interaction.
Electron. Colloquium Comput. Complex., 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 <i>n<sup>o</sup></i><sup>(log <i>n</i>)</sup>-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.
Electron. Colloquium Comput. Complex., 2014

Approximating the best Nash Equilibrium in n<sup>o(log n)</sup>-time breaks the Exponential Time Hypothesis.
Electron. Colloquium Comput. Complex., 2014

Display Advertising with Information Mediators.
CoRR, 2014

2013
Toward Better Formula Lower Bounds: An Information Complexity Approach to the KRW Composition Conjecture.
Electron. Colloquium Comput. Complex., 2013

Direct product via round-preserving compression.
Electron. Colloquium Comput. Complex., 2013

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

Direct Products in Communication Complexity.
Electron. Colloquium Comput. Complex., 2012

Information lower bounds via self-reducibility.
Electron. Colloquium Comput. Complex., 2012

From Information to Exact Communication.
Electron. Colloquium Comput. Complex., 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


  Loading...