# Pasin Manurangsi

Authored Publications

Google Publications

Other Publications

Sort By

Leveraging Bias-Variance Trade-offs for Regression with Label Differential Privacy

Avinash Varadarajan

Chiyuan Zhang

Ethan Leeman

Pritish Kamath

NeurIPS 2023 (2023)

Preview abstract
We propose a new family of label randomization mechanisms for the task of training regression models under the constraint of label differential privacy (DP). In particular, we leverage the trade-offs between bias and variance to construct better noising mechanisms depending on a privately estimated prior distribution over the labels. We demonstrate that these mechanisms achieve state-of-the-art privacy-accuracy trade-offs on several datasets, highlighting the importance of bias-reducing constraints when training neural networks with label DP. We also provide theoretical results shedding light on the structural properties of the optimal bias-reduced mechanisms.
View details

Differentially Private All-Pairs Shortest Path Distances: Improved Algorithms and Lower Bounds

Jelani Osei Nelson

Justin Y. Chen

Shyam Narayanan

Yinzhan Xu

SODA 2023 (to appear)

Preview abstract
We study the problem of releasing the weights of all-pairs shortest paths in a weighted undirected graph with differential privacy (DP). In this setting, the underlying graph is fixed and two graphs are neighbors if their edge weights differ by at most 1 in the ℓ1-distance. We give an algorithm with additive error ̃O(n^2/3/ε) in the ε-DP case and an algorithm with additive error ̃O(√n/ε) in the (ε, δ)-DP case, where n denotes the number of vertices. This positively answers a question of Sealfon [Sea16, Sea20], who asked whether a o(n) error algorithm exists. We also show that an additive error of Ω(n1/6) is necessary for any sufficiently small ε, δ > 0.
Furthermore, we show that if the graph is promised to have reasonably bounded weights, one can improve the error further to roughly n^{(√17−3)/2+o(1)}/ε in the ε-DP case and roughly n^{√2−1+o(1)}/ε in the (ε, δ)-DP case. Previously, it was only known how to obtain ̃O(n2/3/ε1/3) additive error in the ε-DP case and ̃O(√n/ε) additive error in the (ε, δ)-DP case for bounded-weight graphs [Sea16].
Finally, we consider a relaxation where a multiplicative approximation is allowed. We show that, with a multiplicative approximation factor k, the additive error can be reduced to ̃O(n^{1/2+O(1/k)}/ε) in the ε-DP case and ̃O(n^{1/3+O(1/k)}/ε) in the (ε, δ)-DP case.
View details

Improved Inapproximability of VC Dimension and Littlestone’s Dimension via (Unbalanced) Biclique

ITCS 2023 (to appear)

Preview abstract
We study the complexity of computing (and approximating) VC Dimension and Littlestone's Dimension when we are given the concept class explicitly. We give a simple reduction from Maximum (Unbalanced) Biclique problem to approximating VC Dimension and Littlestone's Dimension. With this connection, we derive a range of hardness of approximation results and running time lower bounds. For example, under the (randomized) Gap-Exponential Time Hypothesis or the Strongish Planted Clique Hypothesis, we show a tight inapproximability result: both dimensions are hard to approximate to within a factor of o(log n) in polynomial-time. These improve upon constant-factor inapproximability results from [Manurangsi and Rubinstein, COLT 2017].
View details

Distributed, Private, Sparse Histograms in the Two-Server Model

Adria Gascon

James Bell

Phillipp Schoppmann

CCS 2022

Preview abstract
We consider the computation of sparse, (ε, ϑ)-differentially private~(DP) histograms in the two-server model of secure multi-party computation~(MPC), which has recently gained traction in the context of privacy-preserving measurements of aggregate user data. We introduce protocols that enable two semi-honest non-colluding servers to compute histograms over the data held by multiple users, while only learning a private view of the data. Our solution achieves the same asymptotic l∞-error of O(log(1/ϑ)/ε) as in the central model of DP, but without relying on a trusted curator. The server communication and computation costs of our protocol are independent of the number of histogram buckets, and are linear in the number of users, while the client cost is independent of the number of users, ε, and ϑ. Its linear dependence on the number of users lets our protocol scale well, which we confirm using microbenchmarks: for a billion users, ε = 0.5, and ϑ = 10-11, the per-user cost of our protocol is only 1.08 ms of server computation and 339 bytes of communication. In contrast, a baseline protocol using garbled circuits only allows up to 106 users, where it requires 600 KB communication per user.
View details

The Price of Justified Representation

Ayumi Igarashi

Edith Elkind

Piotr Faliszewski

Ulrike Schmidt-Kraepelin

Warut Suksompong

AAAI 2022

Preview abstract
In multiwinner approval voting, the goal is to select k-member committees based on voters' approval ballots. A well-studied concept of proportionality in this context is the justified representation (JR) axiom, which demands that no large cohesive group of voters remains unrepresented. However, the JR axiom may conflict with other desiderata, such as coverage (maximizing the number of voters who approve at least one committee member) or social welfare (maximizing the number of approvals obtained by committee members). In this work, we investigate the impact of the JR axiom (as well as the more demanding EJR axiom) on social welfare and coverage. Our approach is threefold: we derive worst-case bounds on the loss of welfare/coverage that is caused by imposing JR, study the algorithmic complexity of finding 'good' committees that provide JR (obtaining a hardness result, an approximation algorithm, and a positive result for the one-dimensional setting), and study this problem empirically on several synthetic datasets.
View details

Justifying Committees in Multiwinner Approval Voting

Ayumi Igarashi

Edith Elkind

Piotr Faliszewski

Ulrike Schmidt-Kraepelin

Warut Suksompong

SAGT 2022

Preview abstract
Justified representation (JR) is a well-known notion of representation in multiwinner approval voting. Not only does a JR committee always exist, but previous work has also shown through experiments that the JR condition can typically be fulfilled by groups that are smaller than the target size k. In this paper, we study such groups—known as n/k-justifying groups—both theoretically and empirically. First, we show that under the impartial culture model, n/k-justifying groups of size less than k/2 are likely to exist, which implies that the number of JR committees is usually large. We then present approximation algorithms that compute a small n/k-justifying group for any given instance, and an exact algorithm when the instance admits a tree representation. In addition, we demonstrate that small n/k-justifying groups can often be useful for obtaining a gender-balanced JR committee even though the problem is NP-hard.
View details

Improved Approximation Algorithms and Lower Bounds for Search-Diversification Problems

Amir Abboud

Euiwoong Lee

49th International Colloquium on Automata, Languages and Programming (ICALP) (2022)

Sample-efficient proper PAC learning with approximate differential privacy

Noah Golowich

Symposium on Theory of Computing (STOC) (2021), pp. 183-196

Preview abstract
In this paper we prove that the sample complexity of properly learning a class of Littlestone dimension d with approximate differential privacy is Õ(d^6), ignoring privacy and accuracy parameters. This result answers a question of Bun et al. (FOCS 2020) by improving upon their upper bound of 2^O(d) on the sample complexity. Prior to our work, finiteness of the sample complexity for privately learning a class of finite Littlestone dimension was only known for improper private learners, and the fact that our learner is proper answers another question of Bun et al., which was also asked by Bousquet et al. (NeurIPS 2020). Using machinery developed by Bousquet et al., we then show that the sample complexity of sanitizing a binary hypothesis class is at most polynomial in its Littlestone dimension and dual Littlestone dimension. This implies that a class is sanitizable if and only if it has finite Littlestone dimension. An important ingredient of our proofs is a new property of binary hypothesis classes that we call irreducibility, which may be of independent interest.
View details

The Strongish Planted Clique Hypothesis and Its Applications

Aviad Rubinstein

Tselil Schramm

Innovations in Theoretical Computer Science (ITCS) (2021), 10:1-10:21

Preview abstract
We formulate a new hardness assumption, the Strongish Planted Clique Hypothesis (SPCH), which postulates that any algorithm for planted clique must run in time n^Ω(log n) (so that the state-of-the-art runtime of n^O(log n) is optimal up to a constant in the exponent).
We provide two sets of applications of the new hypothesis. First, we show that SPCH implies (nearly) tight inapproximability results for the following well-studied problems in terms of the parameter k: Densest k-Subgraph, Smallest k-Edge Subgraph, Densest k-Subhypergraph, Steiner k-Forest, Directed Steiner Network with k terminal pairs. For example, we show, under SPCH, that no polynomial time algorithm achieves o(k)-approximation for Densest k-Subgraph. This improves upon the previous best inapproximability ratio k^o(1) from (Chalermsook et al., FOCS 2017). Furthermore, our lower bounds hold even against fixed-parameter tractable (FPT) algorithms with parameter k.
Our second application focuses on the complexity of graph pattern detection. For both induced and non-induced graph pattern detection, we prove hardness results under SPCH, which improve the running time lower bounds obtained by (Dalirrooyfard et al., STOC 2019) under ETH.
View details

On Avoiding the Union Bound When Answering Multiple Differentially Private Queries

Annual Conference on Learning Theory (COLT) (2021), pp. 2133-2146

Preview abstract
In this work, we study the problem of answering k queries with (ε, δ)-differential privacy, where each query has sensitivity one. We give a mechanism for this task that achieves an error bound of O(sqrt(k ln(1/δ))/ε), which is known to be tight (Steinke and Ullman, 2016).
A parallel work by Dagan and Kur (2020) provides a similar result, albeit via a completely different approach. One difference between our work and theirs is that our guarantee holds even when δ < 2^−Ω(k/(log k)^8) whereas theirs does not apply in this case. On the other hand, the algorithm of Dagan and Kur has a remarkable advantage that the ℓ∞ error bound of O(sqrt(k ln(1/δ))/ε) holds not only in expectation but always (i.e., with probability one) while we can only get a high probability (or expected) guarantee on the error.
View details

Near-tight closure bounds for Littlestone and threshold dimensions

Noah Golowich

International Conference on Algorithmic Learning Theory (ALT) (2021), pp. 686-696

Preview abstract
We study closure properties for the Littlestone and threshold dimensions of binary hypothesis classes. Given classes H1,…,Hk of Boolean functions with bounded Littlestone (respectively, threshold) dimension, we establish an upper bound on the Littlestone (respectively, threshold) dimension of the class defined by applying an arbitrary binary aggregation rule to H1,…,Hk. We also show that our upper bounds are nearly tight. Our upper bounds give an exponential (in k) improvement upon analogous bounds shown by Alon et al. (COLT 2020), thus answering a question posed by their work.
View details

Robust and Private Learning of Halfspaces

Thao Nguyen

International Conference on Artificial Intelligence and Statistics (AISTATS) (2021), pp. 1603-1611

Preview abstract
In this work, we study the trade-off between differential privacy and adversarial robustness under L2-perturbations in the context of learning halfspaces. We prove nearly tight bounds on the sample complexity of robust private learning of halfspaces for a large regime of parameters. A highlight of our results is that robust and private learning is harder than robust or private learning alone. We complement our theoretical analysis with experimental results on the MNIST and USPS datasets, for a learning algorithm that is both differentially private and adversarially robust.
View details

Algorithmic Persuasion with Evidence

Martin Hoefer

Alex Psomas

Innovations in Theoretical Computer Science (ITCS) (2021), 3:1-3:20

Preview abstract
We consider optimization problems faced by a sender and a receiver in a game of persuasion with evidence. The sender wishes to persuade the receiver to take one of two actions by presenting evidence. The sender’s utility depends solely on the action taken, while the receiver’s utility depends on both the action as well as the sender’s private information. We study two natural variations. The first is verification, where the sender commits to a signaling scheme and then the receiver takes an action after seeing the evidence. The second is delegation, where the receiver first commits to taking a certain action if being presented certain evidence, and then the sender presents evidence to maximize the probability that her favorite action is taken. We study these problems through the computational lens, and give hardness results, optimal approximation algorithms, as well as efficient algorithms for special cases. In particular, we provide an approximation algorithm that rounds a semidefinite program that might be of independent interest, since, to the best of our knowledge, it is the first such approximation algorithm for a natural problem in algorithmic economics.
View details

Contextual Recommendations and Low-Regret Cutting-Plane Algorithms

Guru Prashanth Guruganesh

NeurIPS (2021)

Preview abstract
We consider the following variant of contextual linear bandits motivated by routing applications in navigational engines and recommendation systems. We wish to learn a hidden $d$-dimensional value $w^*$. Every round, we are presented with a subset $\mathcal{X}_t \subseteq \mathbb{R}^d$ of possible actions. If we choose (i.e. recommend to the user) action $x_t$, we obtain utility $\langle x_t, w^* \rangle$ but only learn the identity of the best action $\arg\max_{x \in \X_t} \langle x, w^* \rangle$.
We design algorithms for this problem which achieve regret $O(d\log T)$ and $\exp(O(d \log d))$. To accomplish this, we design novel cutting-plane algorithms with low “regret” -- the total distance between the true point $w^*$ and the hyperplanes the separation oracle returns.
We also consider the variant where we are allowed to provide a list of several recommendations. In this variant, we give an algorithm with $O(d^2 \log d)$ regret and list size $\poly(d)$. Finally, we construct nearly tight algorithms for a weaker variant of this problem where the learner only learns the identity of an action that is better than the recommendation. Our results rely on new algorithmic techniques in convex geometry (including a variant of Steiner’s formula for the centroid of a convex set) which may be of independent interest.
View details

On the Complexity of Fair House Allocation

Naoyuki Kamiyama

Warut Suksompong

Operations Research Letters, vol. 49 (4) (2021), pp. 572-577

Preview abstract
We study fairness in house allocation, where m houses are to be allocated among n agents so that
every agent receives one house. We show that maximizing the number of envy-free agents is hard to
approximate to within a factor of n^{1−γ} for any constant γ > 0, and that the exact version is NP-hard
even for binary utilities. Moreover, we prove that deciding whether a proportional allocation exists is
computationally hard, whereas the corresponding problem for equitability can be solved efficiently.
View details

Tight Hardness Results for Training Depth-2 ReLU Networks

Surbhi Goel

Adam Klivans

Daniel Reichman

Innovations in Theoretical Computer Science (ITCS) (2021), 22:1-22:14

Preview abstract
We prove several hardness results for training neural networks with a single hidden layer and the ReLU activation function. Our goal is to output a one-layer neural network that minimizes the square loss with respect to a given training set. We prove that this problem is NP-hard already for a network with a single ReLU. We also prove NP-hardness for outputting a weighted sum of k ReLUs minimizing the squared error (for k > 1) even in the realizable setting (i.e., when the labels are consistent with an unknown one layer ReLU network). We are also able to obtain lower bounds on the running time in terms of 1/epsilon where epsilon is the desired additive error. To obtain our lower bounds, we use the Gap-ETH hypothesis as well as a new hypothesis regarding the hardness of approximating the well known Densest k-Subgraph problem in subexponential time (these hypotheses are used separately in proving different lower bounds). For example, we prove that under reasonable hardness assumptions, any proper learning algorithm for finding the best fitting ReLU must run in time exponential in 1/epsilon^2. This implies the first separation between proper and improper algorithms for learning a ReLU due to prior work by Geol et al. We also study the problem of properly learning a depth-2 network with ReLUs with bounded weights giving new (worst-case) upper bounds on the running time needed to learn such networks, that essentially matches our lower bounds in terms of the dependency on epsilon.
View details

On Distributed Differential Privacy and Counting Distinct Elements

Lijie Chen

Innovations in Theoretical Computer Science (ITCS) (2021), 56:1-56:18

Preview abstract
We study the setup where each of n users holds an element from a discrete set, and the goal is to count the number of distinct elements across all users, under the constraint of (epsilon, delta)-differentially privacy:
- In the local setting, we prove that the additive error of any protocol is Omega(n) for any constant epsilon and any delta inverse polynomial in n. This provides the first separation between global sensitivity and error that is omega(sqrt{n}) in local differential privacy, thus answering a question of Vadhan (2017).
- In the single-message shuffle setting, we prove a lower bound of tilde{Omega}(n) on the error for any constant epsilon and for some delta inverse quasi-polynomial in n. We do so using the moment-matching method from the literature on distribution estimation.
- In the multi-message shuffle setting, we give a protocol with <= 1 message per user in expectation and with an error of tilde{O}(sqrt{n}) for any constant epsilon and delta inverse polynomial in n.
Our proof technique relies on a new notion, that we call dominated protocols, and which can be used to obtain the first non-trivial lower bounds against multi-message shuffle protocols for the well-studied problems of Selection and Parity Learning.
View details

Linear Discrepancy is Π2-Hard to Approximate

Information Processing Letters (2021) (to appear)

Preview abstract
In this note, we prove that the problem of computing the linear discrepancy of a given matrix is Π2- hard, even to approximate within 9/8 − ε factor for any ε > 0. This strengthens the NP-hardness result of Li and Nikolov (ESA 2020) for the exact version of the problem, and answers a question posed by them. Furthermore, since Li and Nikolov showed that the problem is contained in Π2, our result makes linear discrepancy another natural problem that is Π2-complete (to approximate).
View details

Locally Private k-Means in One Round

Alisa Chang

International Conference on Machine Learning (ICML) (2021), pp. 1441-1451

Preview abstract
We study k-means clustering in the non-interactive (aka one-round) local model of differential privacy. We give an approximation algorithm that requires a single round of communication and achieves an approximation ratio arbitrarily close to the best non private approximation algorithm. To show the flexibility of our framework, we also demonstrate that it yields a similar near-optimal approximation algorithm in the (one-round) shuffle model.
View details

Generalized Kings and Single-Elimination Winners in Random Tournaments

Warut Suksompong

International Joint Conference on Artificial Intelligence (IJCAI) (2021) (to appear)

Preview abstract
Tournaments can be used to model a variety of practical scenarios including sports competitions and elections. A natural notion of strength of alternatives in a tournament is a generalized king: an alternative is said to be a k-king if it can reach every other alternative in the tournament via a directed path of length at most k. In this paper, we provide an almost complete characterization of the probability threshold such that all alternatives are k-kings with high probability in two random models. We show that, perhaps surprisingly, all changes in the threshold occur in the regime of constant k, with the
biggest change being between k = 2 and k = 3. In addition, we establish an asymptotically tight bound on the probability under which all alternatives can win a single-elimination tournament under some bracket.
View details

Almost Envy-Freeness for Groups: Improved Bounds via Discrepancy Theory

Warut Suksompong

International Joint Conference on Artificial Intelligence (IJCAI) (2021) (to appear)

Preview abstract
We study the allocation of indivisible goods among groups of agents using well-known fairness notions such as envy-freeness and proportionality. While these notions cannot always be satisfied, we provide several bounds on the optimal relaxations that can be guaranteed. For instance, our bounds imply that when the number of groups is constant and the n agents are divided into groups arbitrarily, there exists an allocation that is envy-free up to Θ(√n) goods, and this bound is tight. Moreover, we show that while such an allocation can be found efficiently, it is NP-hard to compute an allocation that is envy-free up to o(√n) goods even when a fully envy-free allocation exists. Our proofs make extensive use of tools from discrepancy theory.
View details

Tight Inapproximability of Minimum Maximal Matching on Bipartite Graphs and Related Problems

Jan Marcinkowski

Szymon Dudycz

Workshop on Approximation and Online Algorithms (WAOA) (2021) (to appear)

Preview abstract
We study theMinimum Maximal Matching problem, where we are asked to find in a graph the smallest matching that cannot be extended. We show that this problem is hard to approximate with any constant smaller than 2 even in bipartite graphs, assuming either of two stronger variants of Unique Games Conjecture. The bound also holds for computationally equivalent Minimum Edge Dominating Set. Our lower bound matches the approximation provided by a trivial algorithm.
Our results imply conditional hardness of approximating Maximum Stable Matching with Ties and Incomplete Lists with a constant better than 3/2, which also matches the best known approximation algorithm
View details

Google COVID-19 Vaccination Search Insights: Anonymization Process Description

Adam Boulanger

Akim Kumok

Arti Patankar

Benjamin Miller

Chaitanya Kamath

Charlotte Stanton

Chris Scott

Damien Desfontaines

Evgeniy Gabrilovich

Gregory A. Wellenius

John S. Davis

Karen Lee Smith

Krishna Kumar Gadepalli

Mark Young

Shailesh Bavadekar

Tague Griffith

Yael Mayer

Arxiv.org (2021)

Preview abstract
This report describes the aggregation and anonymization process applied to the COVID-19 Vaccination Search Insights~\cite{vaccination}, a publicly available dataset showing aggregated and anonymized trends in Google searches related to COVID-19 vaccination. The applied anonymization techniques protect every user’s daily search activity related to COVID-19 vaccinations with $(\varepsilon, \delta)$-differential privacy for $\varepsilon = 2.19$ and $\delta = 10^{-5}$.
View details

The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise

Ilias Diakonikolas

Daniel Kane

Advances in Neural Information Processing Systems (NeurIPS) (2020)

Preview abstract
We study the computational complexity of adversarially robust proper learning of halfspaces in the distribution-independent agnostic PAC model, with a focus on L_p perturbations. We give a computationally efficient learning algorithm and a nearly matching computational hardness result for this problem. An interesting implication of our findings is that the L_∞ perturbations case is provably computationally harder than the case 2 ≤ p < ∞
View details

A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms

Andreas Emil Feldmann

Karthik C. S.

Euiwoong Lee

Algorithms, vol. 13(6) (2020), pp. 146

Preview abstract
Parameterization and approximation are two popular ways of coping with NP-hard problems. More recently, the two have also been combined to derive many interesting results. We survey developments in the area both from the algorithmic and hardness perspectives, with emphasis on new techniques and potential future research directions.
View details

Pure Differentially Private Summation from Anonymous Messages

Noah Golowich

Rasmus Pagh

Information Theoretic Cryptography (ITC) (2020), 15:1-15:23

Preview abstract
The shuffled (aka anonymous) model has recently generated significant interest as a candidate dis- tributed privacy framework with trust assumptions better than the central model but with achievable error rates smaller than the local model. In this paper, we study pure differentially private protocols in the shuffled model for summation, a very basic and widely used primitive. Specifically:
• For the binary summation problem where each of n users holds a bit as an input, we give a pure ε-
differentially private protocol for estimating the number of ones held by the users up to an absolute
error of Oε(1), and where each user sends Oε(logn) messages each consisting of a single bit. This √
is the first pure differentially private protocol in the shuffled model with error o( n) for constant values of ε.
Using our binary summation protocol as a building block, we give a pure ε-differentially private protocol that performs summation of real numbers (in [0,1]) up to an absolute error of Oε(1), and where each user sends Oε(log3 n) messages each consisting of O(loglogn) bits.
• In contrast, we show that for any pure ε-differentially private protocol for binary summation in the shuffled model having absolute error n0.5−Ω(1), the per user communication has to be at least
Ωε( log n) bits. This implies (i) the first separation between the (bounded-communication) multi- message shuffled model and the central model, and (ii) the first separation between pure and approximate differentially private protocols in the shuffled model.
Interestingly, over the course of proving our lower bound, we have to consider (a generalization of) the following question which might be of independent interest: given γ ∈ (0, 1), what is the smallest positive integer m for which there exist two random variables X0 and X1 supported on {0, . . . , m} such that (i) the total variation distance between X0 and X1 is at least 1 − γ, and (ii) the moment generating functions of X0 and X1 are within a constant factor of each other everywhere? We show that the answer to this question is m = Θ(
View details

Private Counting from Anonymous Messages: Near-Optimal Accuracy with Vanishing Communication Overhead

Rasmus Pagh

International Conference on Machine Learning (ICML) (2020), pp. 3505-3514

Preview abstract
Differential privacy (DP) is a formal notion for quantifying the privacy loss of algorithms. Algorithms in the central model of DP achieve high accuracy but make the strongest trust assumptions whereas those in the local DP model make the weakest trust assumptions but incur substantial accuracy loss. The shuffled DP model (Bittau et al., 2017; Erlingsson et al., 2019; Cheu et al.,2019) has recently emerged as a feasible middle ground between the central and local models, providing stronger trust assumptions than the former while promising higher accuracies than the latter. In this paper, we obtain practical communication-efficient algorithms in the shuffled DP model for two basic aggregation primitives used in machine learning: 1) binary summation, and 2) histograms over a moderate number of buckets. Our algorithms achieve accuracy that is arbitrarily close to that of central DP algorithms with an expected communication per user essentially matching what is needed without any privacy constraints! We demonstrate the practicality of our algorithms by experimentally comparing their performance to several widely-used protocols such as Randomized Response (Warner, 1965) and RAPPOR (Erlingsson et al., 2014).
View details

Differentially Private Clustering: Tight Approximation Ratios

Advances in Neural Information Processing Systems (NeurIPS) (2020)

Preview abstract
We study the task of differentially private clustering. For several basic clustering problems, including Euclidean DensestBall, 1-Cluster, k-means, and k-median, we give efficient differentially private algorithms that achieve essentially the same approximation ratios as those that can be obtained by any non-private algorithm, while incurring only small additive errors. This improves upon existing efficient algorithms that only achieve some large constant approximation factors.
Our results also imply an improved algorithm for the Sample and Aggregate privacy framework. Furthermore, we show that one of the tools used in our 1-Cluster algorithm can be employed to get a faster quantum algorithm for ClosestPair in a moderate number of dimensions.
View details

Nearly Optimal Robust Secret Sharing against Rushing Adversaries

Akshayaram Srinivasan

Prashant Nalini Vasudevan

Annual International Cryptology Conference (CRYPTO) (2020), pp. 156-185

Preview abstract
Robust secret sharing is a strengthening of secret sharing which allows the secret to be recovered even if some of the shares being used in the reconstruction have been adversarially modified. In this work, we study the setting where out of all the n shares, the adversary is allowed to adaptively corrupt and modify t shares, where n = 2t+1.
It is known that in this setting, to recover a secret of length m bits with error less than 2^-lambda, shares of size at least m + lambda bits are needed. Recently, Bishop, Pastro, Rajaraman, and Wichs (EUROCRYPT 2016) gave a construction with shares of size m + O(lambda * polylog(n, m, lambda)) bits that is secure against non-rushing adversaries. Later, Fehr and Yuan (EUROCRYPT 2019) constructed a scheme that is secure against rushing adversaries, and has shares of size m + O(lambda * n^epsilon * polylog(n, m, lambda)) bits for an arbitrary constant epsilon > 0. They also showed a variant of their construction with share size m + O(lambda * polylog(n, m, lambda)) bits, but with super-polynomial reconstruction time.
We present a robust secret sharing scheme that is secure against rushing adversaries, has shares of size m + O(lambda * log n * (log n + log m)) bits, and polynomial-time sharing and reconstruction. Central to our construction is an algorithm for a problem on semi-random graphs that arises naturally in the paradigm of local authentication of shares used by us and in the aforementioned work.
View details

Consensus Halving for Sets of Items

Paul W. Goldberg

Alexandros Hollender

Ayumi Igarashi

Warut Suksompong

Conference on Web and Internet Economics (WINE) (2020), pp. 384-397

Preview abstract
Consensus halving refers to the problem of dividing a resource into two parts so that every agent values both parts equally. Prior work has shown that when the resource is represented by an interval, a consensus halving with at most n cuts always exists, but is hard to compute even for agents with simple valuation functions. In this paper, we study consensus halving in a natural setting where the resource consists of a set of items without a linear ordering. When agents have additive utilities, we present a polynomial-time algorithm that computes a consensus halving with at most n cuts, and show that n cuts are almost surely necessary when the agents’ utilities are drawn from probabilistic distributions. On the other hand, we show that for a simple class of monotonic utilities, the problem already becomes PPAD-hard. Furthermore, we compare and contrast consensus halving with the more general problem of consensus k-splitting, where we wish to divide the resource into k parts in possibly unequal ratios, and provide some consequences of our results on the problem of computing small agreeable sets.
View details

To Close Is Easier Than To Open: Dual Parameterization To k-Median

Jaroslaw Byrka

Szymon Dudycz

Jan Marcinkowski

Michal Wlodarczyk

Workshop on Approximation and Online Algorithms (WAOA) (2020), pp. 113-126

Preview abstract
The k-Median problem is one of the well-known optimization problems that formalizes the task of data clustering. Here, we are given sets of facilities F and clients C, and the goal is to open k facilities from the set F, which provides the best division into clusters, that is, the sum of distances from each client to the closest open facility is minimized. In the Capacitated k-Median, the facilities are also assigned capacities specifying how many clients can be served by each facility.
Both problems have been extensively studied from the perspective of approximation algorithms. Recently, several surprising results have come from the area of parameterized complexity, which provided better approximation factors via algorithms with running times of the form f(k) · poly(n). In this work, we extend this line of research by studying a different choice of parameterization. We consider the parameter l = |F| − k, that is, the number of facilities that remain closed. It turns out that such a parameterization reveals yet another behaviour of k-Median. We observe that the problem is W[1]-hard but it admits a parameterized approximation scheme. Namely, we present an algorithm with running time 2^O(l · log(l/ε)) · poly(n) that achieves(1 + ε)-approximation. On the other hand, we show that under the assumption of Gap Exponential Time Hypothesis, one cannot extend this result to the capacitated version of the problem.
View details

Private Aggregation from Fewer Anonymous Messages

Rasmus Pagh

Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT) (2020), pp. 798-827

Preview abstract
Consider the setup where n parties are each given a number x_i in F_q and the goal is to compute the sum of x_i in a secure fashion and with as little communication as possible. We study this problem in
the anonymized model of Ishai et al. (FOCS 2006) where each party may broadcast anonymous messages on an insecure channel.
We present a new analysis of the one-round "split and mix" protocol of Ishai et al. In order to achieve the same security parameter, our analysis reduces the required number of messages by a Θ(log n) multiplicative factor. We complement our positive result with lower bounds showing that the dependence of the number of messages on the domain size, the number of parties, and the security parameter is essentially tight.
Using a reduction of Balle et al. (2019), our improved analysis of the protocol of Ishai et al. yields, in the same model, an (ε, δ)-differentially private protocol for aggregation that, for any constant ε > 0 and any δ = 1 / poly(n), incurs only a constant error and requires only a constant number of messages per party. Previously, such a protocol was known only for Θ(log n) messages per party.
View details

No Results Found