4 citations · 7 across the 6 of their papers we have counts for
7 papers
Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds
Kasper Green Larsen, Omri Weinstein, Huacheng Yu
This paper proves the first super-logarithmic lower bounds on the cell probe complexity of dynamic boolean (a.k.a. decision) data structure problems, a long-standing milestone in d…
Amortized Dynamic Cell-Probe Lower Bounds from Four-Party Communication
Omri Weinstein, Huacheng Yu
This paper develops a new technique for proving amortized, randomized cell-probe lower bounds on dynamic data structure problems. We introduce a new randomized nondeterministic fou…
An Improved Upper Bound for the Most Informative Boolean Function Conjecture
Or Ordentlich, Ofer Shayevitz, Omri Weinstein
Suppose is a uniformly distributed -dimensional binary vector and is obtained by passing through a binary symmetric channel with crossover probability . A recent…
ETH Hardness for Densest--Subgraph with Perfect Completeness
Mark Braverman, Young Kun Ko, Aviad Rubinstein +1
We show that, assuming the (deterministic) Exponential Time Hypothesis, distinguishing between a graph with an induced -clique and a graph in which all k-subgraphs have density…
Information Complexity and the Quest for Interactive Compression (A Survey)
Omri Weinstein
Information complexity is the interactive analogue of Shannon's classical information theory. In recent years this field has emerged as a powerful tool for proving strong communica…
Welfare Maximization with Limited Interaction
Noga Alon, Noam Nisan, Ran Raz +1
We continue the study of welfare maximization in unit-demand (matching) markets, in a distributed information model where agent's valuations are unknown to the central planner, and…