Source author record

Badih Ghazi

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Cryptography and Security Machine Learning Information Theory math.IT Computational Complexity math.CO

Catalog footprint

Research overview

17works

7topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Algorithms with More Granular Differential Privacy Guarantees

Differential privacy is often applied with a privacy parameter that is larger than the theory suggests is ideal; various informal justifications for tolerating large privacy parameters have been proposed. In this work, we consider partial differential privacy (DP), which allows quantifying the privacy guarantee on a per-attribute basis. In this framework, we study several basic data analysis and learning tasks, and design algorithms whose per-attribute privacy parameter is smaller that the best possible privacy parameter for the entire record of a person (i.e., all the attributes).

preprint2022arXiv

Connect the Dots: Tighter Discrete Approximations of Privacy Loss Distributions

The privacy loss distribution (PLD) provides a tight characterization of the privacy loss of a mechanism in the context of differential privacy (DP). Recent work has shown that PLD-based accounting allows for tighter $(\varepsilon, δ)$ -DP guarantees for many popular mechanisms compared to other known methods. A key question in PLD-based accounting is how to approximate any (potentially continuous) PLD with a PLD over any specified discrete support. We present a novel approach to this problem. Our approach supports both pessimistic estimation, which overestimates the hockey-stick divergence (i.e., $δ$ ) for any value of $\varepsilon$ , and optimistic estimation, which underestimates the hockey-stick divergence. Moreover, we show that our pessimistic estimate is the best possible among all pessimistic estimates. Experimental evaluation shows that our approach can work with much larger discretization intervals while keeping a similar error bound compared to previous approaches and yet give a better approximation than existing methods.

preprint2022arXiv

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

We study the problem of releasing the weights of all-pair 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 $\ell_1$ -distance. We give an $ε$ -DP algorithm with additive error $\tilde{O}(n^{2/3} / ε)$ and an $(ε, δ)$ -DP algorithm with additive error $\tilde{O}(\sqrt{n} / ε)$ where $n$ denotes the number of vertices. This positively answers a question of Sealfon (PODS'16), who asked whether a $o(n)$ -error algorithm exists. We also show that an additive error of $Ω(n^{1/6})$ is necessary for any sufficiently small $ε, δ> 0$ . Finally, we consider a relaxed setting where a multiplicative approximation is allowed. We show that, with a multiplicative approximation factor $k$ , % $2k - 1$ , the additive error can be reduced to $\tilde{O}\left(n^{1/2 + O(1/k)} / ε\right)$ in the $ε$ -DP case and $\tilde{O}(n^{1/3 + O(1/k)} / ε)$ in the $(ε, δ)$ -DP case, respectively.

preprint2022arXiv

Faster Privacy Accounting via Evolving Discretization

We introduce a new algorithm for numerical composition of privacy random variables, useful for computing the accurate differential privacy parameters for composition of mechanisms. Our algorithm achieves a running time and memory usage of $\mathrm{polylog}(k)$ for the task of self-composing a mechanism, from a broad class of mechanisms, $k$ times; this class, e.g., includes the sub-sampled Gaussian mechanism, that appears in the analysis of differentially private stochastic gradient descent. By comparison, recent work by Gopi et al. (NeurIPS 2021) has obtained a running time of $\widetilde{O}(\sqrt{k})$ for the same task. Our approach extends to the case of composing $k$ different mechanisms in the same class, improving upon their running time and memory usage from $\widetilde{O}(k^{1.5})$ to $\widetilde{O}(k)$ .

preprint2021arXiv

Advances and Open Problems in Federated Learning

Federated learning (FL) is a machine learning setting where many clients (e.g. mobile devices or whole organizations) collaboratively train a model under the orchestration of a central server (e.g. service provider), while keeping the training data decentralized. FL embodies the principles of focused data collection and minimization, and can mitigate many of the systemic privacy risks and costs resulting from traditional, centralized machine learning and data science approaches. Motivated by the explosive growth in FL research, this paper discusses recent advances and presents an extensive collection of open problems and challenges.

preprint2020arXiv

Differentially Private Clustering: Tight Approximation Ratios

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.

preprint2020arXiv

Near-tight closure bounds for Littlestone and threshold dimensions

We study closure properties for the Littlestone and threshold dimensions of binary hypothesis classes. Given classes $\mathcal{H}_1, \ldots, \mathcal{H}_k$ 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 $\mathcal{H}_1, \ldots, \mathcal{H}_k$ . 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.

preprint2020arXiv

On Distributed Differential Privacy and Counting Distinct Elements

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 $(ε, δ)$ -differentially privacy: - In the non-interactive local setting, we prove that the additive error of any protocol is $Ω(n)$ for any constant $ε$ and for any $δ$ inverse polynomial in $n$ . - In the single-message shuffle setting, we prove a lower bound of $Ω(n)$ on the error for any constant $ε$ and for some $δ$ inverse quasi-polynomial in $n$ . We do so by building on the moment-matching method from the literature on distribution estimation. - In the multi-message shuffle setting, we give a protocol with at most one message per user in expectation and with an error of $\tilde{O}(\sqrt(n))$ for any constant $ε$ and for any $δ$ inverse polynomial in $n$ . Our protocol is also robustly shuffle private, and our error of $\sqrt(n)$ matches a known lower bound for such protocols. Our proof technique relies on a new notion, that we call dominated protocols, and which can also be used to obtain the first non-trivial lower bounds against multi-message shuffle protocols for the well-studied problems of selection and learning parity. Our first lower bound for estimating the number of distinct elements provides the first $ω(\sqrt(n))$ separation between global sensitivity and error in local differential privacy, thus answering an open question of Vadhan (2017). We also provide a simple construction that gives $\tildeΩ(n)$ separation between global sensitivity and error in two-party differential privacy, thereby answering an open question of McGregor et al. (2011).

preprint2020arXiv

On the Power of Multiple Anonymous Messages

An exciting new development in differential privacy is the shuffled model, in which an anonymous channel enables non-interactive, differentially private protocols with error much smaller than what is possible in the local model, while relying on weaker trust assumptions than in the central model. In this paper, we study basic counting problems in the shuffled model and establish separations between the error that can be achieved in the single-message shuffled model and in the shuffled model with multiple messages per user. For the problem of frequency estimation for $n$ users and a domain of size $B$ , we obtain: - A nearly tight lower bound of $\tildeΩ( \min(\sqrt[4]{n}, \sqrt{B}))$ on the error in the single-message shuffled model. This implies that the protocols obtained from the amplification via shuffling work of Erlingsson et al. (SODA 2019) and Balle et al. (Crypto 2019) are essentially optimal for single-message protocols. A key ingredient in the proof is a lower bound on the error of locally-private frequency estimation in the low-privacy (aka high $ε$ ) regime. - Protocols in the multi-message shuffled model with $poly(\log{B}, \log{n})$ bits of communication per user and $poly\log{B}$ error, which provide an exponential improvement on the error compared to what is possible with single-message algorithms. For the related selection problem on a domain of size $B$ , we prove: - A nearly tight lower bound of $Ω(B)$ on the number of users in the single-message shuffled model. This significantly improves on the $Ω(B^{1/17})$ lower bound obtained by Cheu et al. (Eurocrypt 2019), and when combined with their $\tilde{O}(\sqrt{B})$ -error multi-message protocol, implies the first separation between single-message and multi-message protocols for this problem.

preprint2020arXiv

Pure Differentially Private Summation from Anonymous Messages

The shuffled (aka anonymous) model has recently generated significant interest as a candidate distributed privacy framework with trust assumptions better than the central model but with achievable errors smaller than the local model. We study pure differentially private (DP) protocols in the shuffled model for summation, a basic and widely used primitive: - For binary summation where each of n users holds a bit as an input, we give a pure $ε$ -DP protocol for estimating the number of ones held by the users up to an error of $O_ε(1)$ , and each user sends $O_ε(\log n)$ messages each of 1 bit. This is the first pure protocol in the shuffled model with error $o(\sqrt{n})$ for constant $ε$ . Using this protocol, we give a pure $ε$ -DP protocol that performs summation of real numbers in $[0, 1]$ up to an error of $O_ε(1)$ , and where each user sends $O_ε(\log^3 n)$ messages each of $O(\log\log n)$ bits. - In contrast, we show that for any pure $ε$ -DP protocol for binary summation in the shuffled model having absolute error $n^{0.5-Ω(1)}$ , the per user communication has to be at least $Ω_ε(\sqrt{\log n})$ bits. This implies the first separation between the (bounded-communication) multi-message shuffled model and the central model, and the first separation between pure and approximate DP protocols in the shuffled model. To prove our lower bound, we consider (a generalization of) the following question: given $γ$ in $(0, 1)$ , what is the smallest m for which there are two random variables $X^0, X^1$ supported on $\{0, \dots ,m\}$ such that (i) the total variation distance between $X^0$ and $X^1$ is at least $1-γ$ , and (ii) the moment generating functions of $X^0$ and $X^1$ are within a constant factor of each other everywhere? We show that the answer is $m = Θ(\sqrt{\log(1/γ)})$ .

preprint2016arXiv

Decidability of Non-Interactive Simulation of Joint Distributions

We present decidability results for a sub-class of "non-interactive" simulation problems, a well-studied class of problems in information theory. A non-interactive simulation problem is specified by two distributions $P(x,y)$ and $Q(u,v)$ : The goal is to determine if two players, Alice and Bob, that observe sequences $X^n$ and $Y^n$ respectively where $\{(X_i, Y_i)\}_{i=1}^n$ are drawn i.i.d. from $P(x,y)$ can generate pairs $U$ and $V$ respectively (without communicating with each other) with a joint distribution that is arbitrarily close in total variation to $Q(u,v)$ . Even when $P$ and $Q$ are extremely simple: e.g., $P$ is uniform on the triples $\{(0,0), (0,1), (1,0)\}$ and $Q$ is a "doubly symmetric binary source", i.e., $U$ and $V$ are uniform $\pm 1$ variables with correlation say $0.49$ , it is open if $P$ can simulate $Q$ . In this work, we show that whenever $P$ is a distribution on a finite domain and $Q$ is a $2 \times 2$ distribution, then the non-interactive simulation problem is decidable: specifically, given $δ> 0$ the algorithm runs in time bounded by some function of $P$ and $δ$ and either gives a non-interactive simulation protocol that is $δ$ -close to $Q$ or asserts that no protocol gets $O(δ)$ -close to $Q$ . The main challenge to such a result is determining explicit (computable) convergence bounds on the number $n$ of samples that need to be drawn from $P(x,y)$ to get $δ$ -close to $Q$ . We invoke contemporary results from the analysis of Boolean functions such as the invariance principle and a regularity lemma to obtain such explicit bounds.

preprint2016arXiv

NP-Hardness of Reed-Solomon Decoding, and the Prouhet-Tarry-Escott Problem

Establishing the complexity of {\em Bounded Distance Decoding} for Reed-Solomon codes is a fundamental open problem in coding theory, explicitly asked by Guruswami and Vardy (IEEE Trans. Inf. Theory, 2005). The problem is motivated by the large current gap between the regime when it is NP-hard, and the regime when it is efficiently solvable (i.e., the Johnson radius). We show the first NP-hardness results for asymptotically smaller decoding radii than the maximum likelihood decoding radius of Guruswami and Vardy. Specifically, for Reed-Solomon codes of length $N$ and dimension $K=O(N)$ , we show that it is NP-hard to decode more than $N-K- c\frac{\log N}{\log\log N}$ errors (with $c>0$ an absolute constant). Moreover, we show that the problem is NP-hard under quasipolynomial-time reductions for an error amount $> N-K- c\log{N}$ (with $c>0$ an absolute constant). These results follow from the NP-hardness of a generalization of the classical Subset Sum problem to higher moments, called {\em Moments Subset Sum}, which has been a known open problem, and which may be of independent interest. We further reveal a strong connection with the well-studied Prouhet-Tarry-Escott problem in Number Theory, which turns out to capture a main barrier in extending our techniques. We believe the Prouhet-Tarry-Escott problem deserves further study in the theoretical computer science community.

preprint2015arXiv

Communication Complexity of Permutation-Invariant Functions

Motivated by the quest for a broader understanding of communication complexity of simple functions, we introduce the class of "permutation-invariant" functions. A partial function $f:\{0,1\}^n \times \{0,1\}^n\to \{0,1,?\}$ is permutation-invariant if for every bijection $π:\{1,\ldots,n\} \to \{1,\ldots,n\}$ and every $\mathbf{x}, \mathbf{y} \in \{0,1\}^n$ , it is the case that $f(\mathbf{x}, \mathbf{y}) = f(\mathbf{x}^π, \mathbf{y}^π)$ . Most of the commonly studied functions in communication complexity are permutation-invariant. For such functions, we present a simple complexity measure (computable in time polynomial in $n$ given an implicit description of $f$ ) that describes their communication complexity up to polynomial factors and up to an additive error that is logarithmic in the input size. This gives a coarse taxonomy of the communication complexity of simple functions. Our work highlights the role of the well-known lower bounds of functions such as 'Set-Disjointness' and 'Indexing', while complementing them with the relatively lesser-known upper bounds for 'Gap-Inner-Product' (from the sketching literature) and 'Sparse-Gap-Inner-Product' (from the recent work of Canonne et al. [ITCS 2015]). We also present consequences to the study of communication complexity with imperfectly shared randomness where we show that for total permutation-invariant functions, imperfectly shared randomness results in only a polynomial blow-up in communication complexity after an additive $O(\log \log n)$ overhead.

preprint2015arXiv

Communication with Contextual Uncertainty

We introduce a simple model illustrating the role of context in communication and the challenge posed by uncertainty of knowledge of context. We consider a variant of distributional communication complexity where Alice gets some information $x$ and Bob gets $y$ , where $(x,y)$ is drawn from a known distribution, and Bob wishes to compute some function $g(x,y)$ (with high probability over $(x,y)$ ). In our variant, Alice does not know $g$ , but only knows some function $f$ which is an approximation of $g$ . Thus, the function being computed forms the context for the communication, and knowing it imperfectly models (mild) uncertainty in this context. A naive solution would be for Alice and Bob to first agree on some common function $h$ that is close to both $f$ and $g$ and then use a protocol for $h$ to compute $h(x,y)$ . We show that any such agreement leads to a large overhead in communication ruling out such a universal solution. In contrast, we show that if $g$ has a one-way communication protocol with complexity $k$ in the standard setting, then it has a communication protocol with complexity $O(k \cdot (1+I))$ in the uncertain setting, where $I$ denotes the mutual information between $x$ and $y$ . In the particular case where the input distribution is a product distribution, the protocol in the uncertain setting only incurs a constant factor blow-up in communication and error. Furthermore, we show that the dependence on the mutual information $I$ is required. Namely, we construct a class of functions along with a non-product distribution over $(x,y)$ for which the communication complexity is a single bit in the standard setting but at least $Ω(\sqrt{n})$ bits in the uncertain setting.

preprint2014arXiv

LP/SDP Hierarchy Lower Bounds for Decoding Random LDPC Codes

Random (dv,dc)-regular LDPC codes are well-known to achieve the Shannon capacity of the binary symmetric channel (for sufficiently large dv and dc) under exponential time decoding. However, polynomial time algorithms are only known to correct a much smaller fraction of errors. One of the most powerful polynomial-time algorithms with a formal analysis is the LP decoding algorithm of Feldman et al. which is known to correct an Omega(1/dc) fraction of errors. In this work, we show that fairly powerful extensions of LP decoding, based on the Sherali-Adams and Lasserre hierarchies, fail to correct much more errors than the basic LP-decoder. In particular, we show that: 1) For any values of dv and dc, a linear number of rounds of the Sherali-Adams LP hierarchy cannot correct more than an O(1/dc) fraction of errors on a random (dv,dc)-regular LDPC code. 2) For any value of dv and infinitely many values of dc, a linear number of rounds of the Lasserre SDP hierarchy cannot correct more than an O(1/dc) fraction of errors on a random (dv,dc)-regular LDPC code. Our proofs use a new stretching and collapsing technique that allows us to leverage recent progress in the study of the limitations of LP/SDP hierarchies for Maximum Constraint Satisfaction Problems (Max-CSPs). The problem then reduces to the construction of special balanced pairwise independent distributions for Sherali-Adams and special cosets of balanced pairwise independent subgroups for Lasserre. Some of our techniques are more generally applicable to a large class of Boolean CSPs called Min-Ones. In particular, for k-Hypergraph Vertex Cover, we obtain an improved integrality gap of $k-1-ε$ that holds after a \emph{linear} number of rounds of the Lasserre hierarchy, for any k = q+1 with q an arbitrary prime power. The best previous gap for a linear number of rounds was equal to $2-ε$ and due to Schoenebeck.

preprint2013arXiv

Linear Programming Decoding of Spatially Coupled Codes

For a given family of spatially coupled codes, we prove that the LP threshold on the BSC of the graph cover ensemble is the same as the LP threshold on the BSC of the derived spatially coupled ensemble. This result is in contrast with the fact that the BP threshold of the derived spatially coupled ensemble is believed to be larger than the BP threshold of the graph cover ensemble as noted by the work of Kudekar et al. (2011, 2012). To prove this, we establish some properties related to the dual witness for LP decoding which was introduced by Feldman et al. (2007) and simplified by Daskalakis et al. (2008). More precisely, we prove that the existence of a dual witness which was previously known to be sufficient for LP decoding success is also necessary and is equivalent to the existence of certain acyclic hyperflows. We also derive a sublinear (in the block length) upper bound on the weight of any edge in such hyperflows, both for regular LPDC codes and for spatially coupled codes and we prove that the bound is asymptotically tight for regular LDPC codes. Moreover, we show how to trade crossover probability for "LP excess" on all the variable nodes, for any binary linear code.

preprint2013arXiv

Sample-Optimal Average-Case Sparse Fourier Transform in Two Dimensions

We present the first sample-optimal sublinear time algorithms for the sparse Discrete Fourier Transform over a two-dimensional sqrt{n} x sqrt{n} grid. Our algorithms are analyzed for /average case/ signals. For signals whose spectrum is exactly sparse, our algorithms use O(k) samples and run in O(k log k) time, where k is the expected sparsity of the signal. For signals whose spectrum is approximately sparse, our algorithm uses O(k log n) samples and runs in O(k log^2 n) time; the latter algorithm works for k=Theta(sqrt{n}). The number of samples used by our algorithms matches the known lower bounds for the respective signal models. By a known reduction, our algorithms give similar results for the one-dimensional sparse Discrete Fourier Transform when n is a power of a small composite number (e.g., n = 6^t).

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Badih Ghazi

Research overview

Is this your work?

17 publications

Algorithms with More Granular Differential Privacy Guarantees

Connect the Dots: Tighter Discrete Approximations of Privacy Loss Distributions

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

Faster Privacy Accounting via Evolving Discretization

Advances and Open Problems in Federated Learning

Differentially Private Clustering: Tight Approximation Ratios

Near-tight closure bounds for Littlestone and threshold dimensions

On Distributed Differential Privacy and Counting Distinct Elements

On the Power of Multiple Anonymous Messages

Pure Differentially Private Summation from Anonymous Messages

Decidability of Non-Interactive Simulation of Joint Distributions

NP-Hardness of Reed-Solomon Decoding, and the Prouhet-Tarry-Escott Problem

Communication Complexity of Permutation-Invariant Functions

Communication with Contextual Uncertainty

LP/SDP Hierarchy Lower Bounds for Decoding Random LDPC Codes

Linear Programming Decoding of Spatially Coupled Codes

Sample-Optimal Average-Case Sparse Fourier Transform in Two Dimensions

See the researcher in context

Building this map preview