Thank you for taking the time to review our work. We address your specific points below.

> I cannot find a topic for NIPS 2025 that meets the topic of this paper. Could the authors formally state that the topic of this paper is considered for NIPS 2025?

The relevant topic from the NeurIPS call for papers is "privacy" (under "Social and economic aspects of machine learning"). Differential privacy is a longstanding interest of the ML community and has consistently appeared at previous conferences. (For example, the same problem has been studied in Gopi et al. (2020), which was presented at ICML 2020.)

> Private Set Union has been a well-defined cryptography topic... I suggest changing the term used in this paper or having a separate description to clarify the differences between the two definitions

We agree and are open to changing the name. One option is to change the name to "Differentially private set union" to reflect the specific privacy constraint we are working with. This is also consistent with prior work such as Gopi et al. (2020), and Carvalho et al. (2022).

Thank you for taking the time to review our work. We address your specific points below.

> For the union set case where k=1, you refer to the sampling-based algorithm from the Cohen et al. paper. I believe there is another algorithm based on thresholding the histogram... I believe the thresholding approach achieves asymptotically similar error bounds... perhaps using the thresholding algorithms as the benchmark would be better?

We agree that the thresholding approach is very intuitive, and that it achieves asymptotically similar error bounds. But since the strictly optimal (not just asymptotic) reporting probabilities are known in the k=1 case, and since we can actually achieve it under some assumptions (see Theorem 1.3) then we believe that working with the optimal reporting probabilities is a stronger baseline.

Thanks for your response, will keep score.

Thank you for taking the time to review our work. We address your specific points below.

> While the authors characterize how the worst-case utility ratio deteriorates as per-user contribution bounds grow, they do not propose or evaluate any algorithmic techniques to mitigate this degradation.

Our results show that in the worst case, every mechanism is subject to low utility ratios for some privacy regimes and datasets, so mitigations do not exist. However, one interesting direction that we partially address is to explore non-worst-case conditions under which mechanisms can achieve high utility ratios. Our mechanism that makes use of predictions (Section 4) is one example: in cases where a reasonably accurate prediction of the histogram is available, it is possible to do much better than our impossibility results.

> There is little discussion of the runtime complexity or messaging costs of the proposed algorithms. In privacy-constrained settings, these overheads can dominate, especially when each user contributes multiple items, but the paper omits any comparative performance profiling against existing baselines

Let $N = \sum_i |B_i|$ denote the sum of bag sizes in an input dataset. The mechanisms discussed in Lemma 3.1, Lemma 3.4, and Theorem 4.1 all run in linear time in $N$ because they essentially build a histogram of the items that appear in the dataset and then do linear time operations on the histogram. The mechanism from Lemma 3.3 is also linear in $N$, since whenever it does not output an empty set, it just outputs the items of a randomly chosen user. Finally, the bi-criteria mechanism from Theorem 3.2 can also be implemented to run in linear time in $N$ with a bit of bookkeeping. Note that the linear dependence on N is unavoidable for any algorithm that goes over every data point. We will clarify this.

> The robust mechanism fundamentally assumes access to a reasonably accurate prior histogram of the data distribution. However, the paper does not comprehensively explore how sensitive the overall utility is to different types of prediction errors or misspecified priors

Theorem 4.1 shows that the expected output size of the mechanism that uses predictions degrades with the $\ell_\infty$ distance between the true and predicted dataset histograms. If the distance is $d$, then the mechanism performs as well as the Pi bound on a dataset where every item count is decreased by $d$. Studying robustness with respect to other discrepancy measures is an interesting future direction to explore. We will clarify this in the paper.

> The work fixes privacy parameters (epsilon, delta) and does not systematically study the privacy-utility frontier. As a result, readers lack guidance on how the utility ratio behaves under tighter privacy budgets or in regimes where sensitivity amplification techniques might apply

We did not emphasize the privacy-utility frontier, but our results do characterize some interesting regions of the privacy parameter space where utility ratios are bounded in different ways. For example, Lemmas 3.3 and 3.4 show that for fixed $\delta$, utility ratios of 1 are achievable in the limit as $\epsilon$ tends to zero or infinity. On the other hand, for a range of intermediate $\epsilon$ values, our results establish that utility ratios cannot be better than roughly $1/k$. Understanding implications for amplification, composition, etc. would be a nice direction for future research.

Thank you for taking the time to review our work. We address your specific points below.

> I'm not sure Definition 1.1 has the right citation

Agreed. This was indeed a mistake and we will update the citation.

> The definition of $\Pi(D, \epsilon, \delta)$ on lines 56-60 doesn't say what happens when epsilon=0

In the case when $\epsilon = 0$, we have $\pi(c, \epsilon, \delta) = \min(c \delta, 1)$. We will clarify this in the paper.

> Line 83 describes "the bounds roughly mirroring the behavior in Figure 2", but for large k, Figure 2 seems to contradict the bound in question, since the utility ratio starts to increase again and eventually reaches 1 as k increases. I guess it is not really a contradiction because Theorem 1.1's minimum value for k depends on epsilon, and so maybe it is not satisfied on the right side of Figure 2. Still, it makes that text on line 83 look untrue. (Or did I misunderstand something here?)

Your understanding is correct, our impossibility results establish combinations of the privacy parameters $\epsilon$ and $\delta$ under which high utility ratios are impossible. But, for fixed $\delta$, taking $\epsilon$ to zero or infinity allows for a utility ratio of 1 (see Lemmas 3.3 and 3.4), which matches the behavior in the plots. We intended for the text on line 83 to point out that the curves for each value of k have minimum values near 1/k, the worst-case ratio from the first part of Theorem 1.1. We agree that it is currently confusing and we will revise the text.

> The second bound in Theorem 1.1 (lines 80-81) has an unspecified dependence on n. This is indicated by the subscript n in the $\tilde O_n$ notation, but it may be unusual or unintuitive enough that it's worth commenting on in the prose: how exactly should one think of this bound? What does it mean? At least, I found it a bit tricky to wrap my head around, since usually n is the increasing variable in asymptotic bounds

The main focus of our paper is to study how the user contribution limit k impacts the utility ratio, so we emphasize the dependence on k in Theorem 1.1. The full bound is presented in Theorem 2.3, which includes the dependence on n. The bound holds when k is large compared to n and hence we include n as a subscript. We will clarify the notation used in Theorem 1.1 in the revision.

> Line 236: Not strictly necessary, but it would be nice to hear more about what $B_i$ is. Is there a precise mathematical definition of $B_i$ in terms of the query $q_i$ and dataset $D$? Or maybe an example would be appropriate, just to give some intuition?

The current text on line 236 uses clashing notation with the rest of the paper which we will address. In the work of Kaplan et al., the query $q_i$ counts the number of users u that match a predicate q and the set of users to remove (denoted by $B_i$ in the current version) contains all users u for which q(u) = 1.

> Line 38: "Two datasets D and D' as neighboring..." seems to be be missing something, e.g. "We consider two datasets D and D' as neighbouring..."

Right. We will fix this typo.

> Line 135: "after removing user i": unless I missed it, i isn't defined here. I guess you mean user 1?

Right. We will fix this typo.