4 citations · 5 across the 4 of their papers we have counts for
4 papers
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…