4 papers
Sorted Top-k in Rounds
Mark Braverman, Jieming Mao, Yuval Peres
We consider the sorted top- problem whose goal is to recover the top- items with the correct order out of items using pairwise comparisons. In many applications, multiple…
Diversity and Exploration in Social Learning
Nicole Immorlica, Jieming Mao, Christos Tzamos
In consumer search, there is a set of items. An agent has a prior over her value for each item and can pay a cost to learn the instantiation of her value. After exploring a subset…
Tighter Relations Between Sensitivity and Other Complexity Measures
Andris Ambainis, Mohammad Bavarian, Yihan Gao +3
Sensitivity conjecture is a longstanding and fundamental open problem in the area of complexity measures of Boolean functions and decision tree complexity. The conjecture postulate…
Simulating Noisy Channel Interaction
Mark Braverman, Jieming Mao
We show that rounds of interaction over the binary symmetric channel with feedback can be simulated with rounds of interaction over a noiseless channel…