93 citations · 192 across the 20 of their papers we have counts for
Showing 2018Show all
3 papers · 1 filter
cs.CC2018
Fine-grained Complexity Meets IP = PSPACE
Lijie Chen, Shafi Goldwasser, Kaifeng Lyu +2
In this paper we study the fine-grained complexity of finding exact and approximate solutions to problems in P. Our main contribution is showing reductions from exact to approximat…
cs.LG2018★ 37 cited
Probably Approximately Metric-Fair Learning
Guy N. Rothblum, Gal Yona
The seminal work of Dwork {\em et al.} [ITCS 2012] introduced a metric-based notion of individual fairness. Given a task-specific similarity metric, their notion required that ever…
cs.LG2018★ 93 cited
Fairness Through Computationally-Bounded Awareness
Michael P. Kim, Omer Reingold, Guy N. Rothblum
We study the problem of fair classification within the versatile framework of Dwork et al. [ITCS '12], which assumes the existence of a metric that measures similarity between pair…