The resilience of a voting system has been a central topic in computational social choice. Many voting rules, like plurality, are shown to be vulnerable as the attacker can target specific voters to manipulate the result. What if a local differential privacy (LDP) mechanism is adopted such that the true preference of a voter is never revealed in pre-election polls? In this case, the attacker can only infer stochastic information about a voter's true preference, and this may cause the manipulation of the electoral result significantly harder. The goal of this paper is to provide a quantitative study on the effect of adopting LDP mechanisms on a voting system. We introduce the metric PoLDP (power of LDP) that quantitatively measures the difference between the attacker's manipulation cost under LDP mechanisms and that without LDP mechanisms. The larger PoLDP is, the more robustness LDP mechanisms can add to a voting system. We give a full characterization of PoLDP for the voting system with plurality rule and provide general guidance towards the application of LDP mechanisms.

We consider a classical scheduling problem on m identical machines. For an arbitrary constant q > 1, the aim is to assign jobs to machines such that is minimized, where Ci is the total processing time of jobs assigned to machine i. It is well known that this problem is strongly NP-hard. Under mild assumptions, the running time of an (1 + ∊)-approximation algorithm for a strongly NP-hard problem cannot be polynomial on 1/∊, unless P = NP. For most problems in the literature, this translates into algorithms with running time at least as large as 2Ω(1/∊) + nO(1). For the natural scheduling problem above, we establish the existence of an algorithm which violates this threshold. More precisely, we design a PTAS that runs in time. This result is in sharp contrast to the closely related minimum makespan variant, where an exponential lower bound is known under the exponential time hypothesis (ETH). We complement our result with an essentially matching lower bound on the running time, showing that our algorithm is best-possible under ETH. The lower bound proof exploits new number-theoretical constructions for variants of progression-free sets, which might be of independent interest. Furthermore, we provide a fine-grained characterization on the running time of a PTAS for this problem depending on the relation between ∊ and the number of machines m. More precisely, our lower bound only holds when . Better algorithms, that go beyond the lower bound, exist for other values of m. In particular, there even exists an algorithm with running time polynomial in 1/∊ if we restrict ourselves to instances with m = Ω(1/∊ log2 1/∊).