Seminars & Colloquia Calendar

We consider simultaneous protocols for the following communication problem: Alice and Bob each have some list of subsets of [m], A_1,...,A_a, and B_1,...,B_b, and wish to either:

(Allocation Problem): partition [m] into A sqcup B in order to maximize max_i {A cap A_i} + max_j {B cap B_j}.(Decision Problem): decide whether there exists an i, j, such that A_i cup B_ j geq C.

For interactive protocols, a (tight) 3/4-approximation is known in poly(m) communication for both problems. We show the following:

- A randomized, simultaneous protocol with O(m) communication that achieves a (tight) 3/4-approximation for the allocation problem.

- No randomized, simultaneous protocol with subexponential (in m) communication guarantees better than a 3/4-1/108 approximation for the decision problem.

I'll further discuss the implications of these results for truthful combinatorial auctions due to a recent result of Dobzinski [FOCS 16].

Joint work with Mark Braverman and Jieming Mao.