13 citations · 17 across the 10 of their papers we have counts for
4 papers · 1 filter
Stochastic Vertex Cover with Few Queries
Soheil Behnezhad, Avrim Blum, Mahsa Derakhshan
We study the minimum vertex cover problem in the following stochastic setting. Let be an arbitrary given graph, a parameter of the problem, and let be a ra…
Opting Into Optimal Matchings
Avrim Blum, Ioannis Caragiannis, Nika Haghtalab +3
We revisit the problem of designing optimal, individually rational matching mechanisms (in a general sense, allowing for cycles in directed graphs), where each player --- who is as…
Ignorance is Almost Bliss: Near-Optimal Stochastic Matching With Few Queries
Avrim Blum, John P. Dickerson, Nika Haghtalab +3
The stochastic matching problem deals with finding a maximum matching in a graph whose edges are unknown but can be accessed via queries. This is a special case of stochastic -s…
The Johnson-Lindenstrauss Transform Itself Preserves Differential Privacy
Jeremiah Blocki, Avrim Blum, Anupam Datta +1
This paper proves that an "old dog", namely -- the classical Johnson-Lindenstrauss transform, "performs new tricks" -- it gives a novel way of preserving differential privacy. We s…