154 citations · 438 across the 55 of their papers we have counts for
71 papers
Optimally Pacing Budget Spending and Learning
Mark Braverman, Jingyi Liu, Jieming Mao +2
We establish near-optimal regret bounds for budget-constrained online learning against arbitrary classes of budget-pacing experts in the adversarial setting. In particular, given a…
Stronger core results with multidimensional prices
Mark Braverman, Jingyi Liu, Eric Xue +1
We study one-sided matchings with endowments in the absence of money. It is well-known that a competitive equilibrium may not always exist and that the strong core may be empty in…
A New Benchmark for Online Learning with Budget-Balancing Constraints
Mark Braverman, Jingyi Liu, Jieming Mao +2
The adversarial Bandit with Knapsack problem is a multi-armed bandits problem with budget constraints and adversarial rewards and costs. In each round, a learner selects an action…
A New Information Complexity Measure for Multi-pass Streaming with Applications
Mark Braverman, Sumegha Garg, Qian Li +3
We introduce a new notion of information complexity for multi-pass streaming problems and use it to resolve several important questions in data streams. In the coin problem, one se…
Welfare Distribution in Two-sided Random Matching Markets
Itai Ashlagi, Mark Braverman, Geng Zhao
We study the welfare structure in two-sided large random matching markets. In the model, each agent has a latent personal score for every agent on the other side of the market and…
Parallel Repetition for the GHZ Game: Exponential Decay
Mark Braverman, Subhash Khot, Dor Minzer
We show that the value of the -fold repeated GHZ game is at most , improving upon the polynomial bound established by Holmgren and Raz. Our result is established via…