154 citations · 438 across the 55 of their papers we have counts for
7 papers · 1 filter
Interpolating Between Truthful and non-Truthful Mechanisms for Combinatorial Auctions
Mark Braverman, Jieming Mao, S. Matthew Weinberg
We study the communication complexity of combinatorial auctions via interpolation mechanisms that interpolate between non-truthful and truthful protocols. Specifically, an interpol…
Tight space-noise tradeoffs in computing the ergodic measure
Mark Braverman, Cristobal Rojas, Jon Schneider
In this note we obtain tight bounds on the space-complexity of computing the ergodic measure of a low-dimensional discrete-time dynamical system affected by Gaussian noise. If the…
Coding for interactive communication correcting insertions and deletions
Mark Braverman, Ran Gelles, Jieming Mao +1
We consider the question of interactive communication, in which two remote parties perform a computation while their communication channel is (adversarially) noisy. We extend here…
Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequality
Mark Braverman, Ankit Garg, Tengyu Ma +2
We study the tradeoff between the statistical error and communication cost of distributed statistical estimation problems in high dimensions. In the distributed sparse Gaussian mea…
Near-optimal bounds on bounded-round quantum communication complexity of disjointness
Mark Braverman, Ankit Garg, Young Kun Ko +2
We prove a near optimal round-communication tradeoff for the two-party quantum communication complexity of disjointness. For protocols with rounds, we prove a lower bound of $\…
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…