13 citations · 39 across the 25 of their papers we have counts for
Showing 2018Show all
2 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.DC2018★ 1 cited
Population stability: regulating size in the presence of an adversary
Shafi Goldwasser, Rafail Ostrovsky, Alessandra Scafuro +1
We introduce a new coordination problem in distributed computing that we call the population stability problem. A system of agents each with limited memory and communication, as we…