154 citations · 438 across the 55 of their papers we have counts for
12 papers · 1 filter
Max-Weight Online Stochastic Matching: Improved Approximations Against the Online Benchmark
Mark Braverman, Mahsa Derakhshan, Antonio Molina Lovett
In this paper, we study max-weight stochastic matchings on online bipartite graphs under both vertex and edge arrivals. We focus on designing polynomial time approximation algorith…
Convex Set Disjointness, Distributed Learning of Halfspaces, and LP Feasibility
Mark Braverman, Gillat Kol, Shay Moran +1
We study the Convex Set Disjointness (CSD) problem, where two players have input sets taken from an arbitrary fixed domain~ of size . T…
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…
Optimal Short-Circuit Resilient Formulas
Mark Braverman, Klim Efremenko, Ran Gelles +1
We consider fault-tolerant boolean formulas in which the output of a faulty gate is short-circuited to one of the gate's inputs. A recent result by Kalai et al. (FOCS 2012) convert…
Parallel Algorithms for Select and Partition with Noisy Comparisons
Mark Braverman, Jieming Mao, S. Matthew Weinberg
We consider the problem of finding the highest element in a totally ordered set of elements (select), and partitioning a totally ordered set into the top and botto…
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…