Should We Combine Our Data? Algorithms and Limits for Privately Assessing Data Sharing

arXiv:2611.03599v1 [cs.LG] 2 Nov 2026

Should We Combine Our Data? Algorithms and Limits for Privately Assessing Data Sharing Mahdi Haghifam

Kumar Kshitij Patel

Toyota Technological Institute at Chicago

Yale University

Avrim Blum*

Giulia Fanti*

Juba Ziani*

Toyota Technological Institute at Chicago

Carnegie Mellon University

Georgia Institute of Technology

Abstract In this paper, we study when two parties should pool their data to train a machine learning model. Two agents, Alice and Bob, each hold a sensitive labeled dataset and want to train a classifier from a given hypothesis class H . Even when each party’s dataset can be perfectly classified on its own, the two parties may follow conflicting labeling standards or have selection biases that affect their features and label sets, such that no single classifier in H fits their combined data. Before committing to data sharing, Alice and Bob therefore want to test whether a single classifier in H can jointly fit both datasets—without revealing their individual data points to one another. We formalize this problem from a learning-theoretic viewpoint via opt H , the minimum number of mistakes made by any hypothesis in H on their pooled data. Through interactive communication, the agents must distinguish opt H = 0 (compatible datasets) from opt H ≥ 𝑡 (conflicting datasets) under pure 𝜀-two-party differential privacy. A trusted curator could do this with 𝑡 = 𝑂 (1/𝜀), and we ask how small 𝑡 can be without one. For thresholds on the real line over a domain of size 𝑚, we show that the optimal 𝑡 is Θ̃(log log 𝑚/𝜀), exponentially smaller than the Θ(log 𝑚/𝜀) samples needed to privately learn thresholds, even with a curator. For halfspaces in R𝑑 , the dependence on 𝑚 jumps to log(𝑚): we give a protocol with 𝑡 = 𝑂˜ (𝑑 3 log 𝑚/𝜀) and show that some domains require 𝑡 = Ω(𝑑 log(𝑚/𝑑)/𝜀).

1

Introduction

Institutions often hold complementary datasets that capture different aspects of the same downstream learning task. For example, a breast screening clinic may hold primarily negative cases, while a specialized diagnostic center may hold a much higher proportion of confirmed cancer cases [LASLBKHOTRM17; SAMHBORLTKLB17]. Similarly, organizations trying to detect cybersecurity incidents frequently share data to provide a comprehensive view of the cybersecurity landscape, as attackers may target different organizations with different exploits at different times [CH23]. In such settings, pooling data may enable institutions to learn a useful classifier that no entity could learn on its own. Indeed, this potential was highlighted and analyzed in early theoretical works on distributed machine learning [BBFM12]. * The starred authors are listed in alphabetical order.

Part of this work was supported by and carried out while Mahdi Haghifam, Giulia Fanti, Kumar Kshitij Patel, and Juba Ziani were visiting the Simons Institute for the Theory of Computing. Juba Ziani was supported by NSF awards 2336236 (CAREER) and 2504990. Giulia Fanti was supported in part by NSF award CCF-2338772 (CAREER).

1

Realizing the potential benefit of collaboration, however, often requires institutions to commit resources upfront through legal agreements, financial compensation, governance approvals, and dedicated infrastructure. Before incurring these costs, institutions need to assess the utility of combining their datasets: will pooling improve model accuracy or other downstream metrics enough to justify the collaboration? Yet this assessment depends on joint properties of the datasets, generally hidden from each institution’s local view. Institutions face a circular dilemma: they must judge whether collaboration is worthwhile before committing, yet doing so may require the very data sharing whose value they seek to assess. Privacy requirements further complicate this dilemma. Hospitals, for example, must protect sensitive patient records even when sharing them would help evaluate a collaboration. Institutions may also hesitate to disclose valuable data to a prospective partner who could use them independently and decline to collaborate. When no trusted third party is available, each party must therefore assess whether collaboration is promising while limiting what it reveals about its data. This tension between the need to preserve data privacy while enabling agents to assess the utility of collaboration motivates the main conceptual question of this paper: How can agents estimate whether it is beneficial to combine their datasets while preserving the privacy of individual records? What algorithms can achieve this goal, and what are their fundamental limits?

1.1

How to Assess the Benefits of Data Sharing?

In this section, we propose a learning-theoretic notion that agents can use to assess the value of data sharing and provide two real-world scenarios in which it can inform the decision to collaborate. Our focus throughout the paper is on binary classification on a data space (or feature space) X ⊆ R𝑑 of size 𝑚 for some 𝑑 ≥ 1 and a fixed publicly known hypothesis class H ⊆ {±1} X . We consider a setting with two agents, Alice (𝐴) and Bob (𝐵) who respecitvely hold a labeled dataset 𝑆𝐴, 𝑆 𝐵 ∈ (X × {±1})𝑛 of size 𝑛 ∈ N. We focus on a basic question that arises before joint training: can a single classifier in a given hypothesis class explain both parties’ data? We formalize this question using their joint empirical loss defined as ∑︁ ∑︁ opt H (𝑆𝐴, 𝑆 𝐵 ) := min 1{ℎ(𝑥) ≠ 𝑦}. (1) ℎ∈ H 𝑈 ∈ {𝐴,𝐵 } (𝑥,𝑦) ∈𝑆

𝑈

We use opt H (𝑆𝐴, 𝑆 𝐵 ), the number of mistakes made on the pooled data by the best classifier in H , to assess the value of combining the data. It is zero when one hypothesis explains both datasets, and large when every hypothesis in H makes many mistakes on their union. A large joint loss may indicate conflicting labeling practices, selection biases causing missing features and labels, or that the hypothesis class is not complex enough to fit the combined data. We therefore focus on distinguishing between the following: opt H (𝑆𝐴, 𝑆 𝐵 ) = 0

opt H (𝑆𝐴, 𝑆 𝐵 ) ≥ 𝑡

(2)

for some 𝑡 > 0. When opt H (𝑆𝐴, 𝑆 𝐵 ) = 0, Alice and Bob agree to collaborate. When opt H (𝑆𝐴, 𝑆 𝐵 ) ≥ 𝑡, Alice and Bob must reassess1 . Finally, if 0 < opt H (𝑆𝐴, 𝑆 𝐵 ) < 𝑡, we make no claims, as is standard in distribution testing. We now present two examples that further motivate the property-testing problem in (2). Example 1 (Learning from disparate label sets). Suppose Alice is a screening clinician and Bob is a diagnostician. They want to develop a classifier to determine whether a patient in a target population should 1 This could take the form of Alice and Bob realizing they do not have the expertise or computing power to fit a good model, in

which case they refuse to collaborate; or, this could mean that Alice and Bob need to reconcile their labeling practices, jointly rectify their selection biases to account for missingness, potentially re-label data, or choose a more complex hypothesis class.

2

be referred for further diagnostic testing. Their datasets reflect different stages of care: Alice’s screening dataset 𝑆𝐴 mainly contains records of patients who were not referred, whereas Bob’s diagnostic dataset 𝑆 𝐵 contains only records of patients who were referred and received more thorough testing [GBRRDJM11]. Since the records contain sensitive patient information, neither agent is willing to disclose individual records to assess a possible collaboration, and no trusted third party is available. To isolate this selection bias, suppose Alice’s labels are all −1, and Bob’s are all +1. Then, neither can train a useful model alone; they must assess opt H (𝑆𝐴, 𝑆 𝐵 ) to determine whether they can train a low-error model on their joint data. Example 2 (Identifying conflicting labeling practices). Now suppose Alice has labeled spam and non-spam emails in her dataset. However, her data may be limited or imbalanced, so she wants to augment it with Bob’s curated, labeled email dataset. The challenge is that Bob may have a different view of what constitutes spam, so his labels could conflict with Alice’s data [KCG24]. For example, Alice may label unsolicited promotional emails as spam, while Bob uses that label for fraudulent or malicious messages. Before joint training, Alice wants to know whether a single classifier can achieve a sufficiently low test error under both labeling policies. To isolate conflicting labeling practices, suppose the agents encounter the same distribution of emails but may assign different labels to the same email. In this case, opt H (𝑆𝐴, 𝑆 𝐵 ) = 0 indicates that, under the hypothesis class 𝐻 , Alice’s and Bob’s labeling practices are compatible, implying a collaboration may be worthwhile. On the other end, opt H (𝑆𝐴, 𝑆 𝐵 ) ≥ 𝑡 points to differing labeling practices. Remark 1.1 (From in-sample to in-population error). Note that our insights extend beyond the in-sample case and hold when considering generalization error over the underlying population distributions. We provide more details using standard arguments in Appendix A. ⊳

1.2

Problem Formalization

In this section, we formalize our problem and state our main technical question. We first consider the disjoint-label setting as in Example 1, where Alice holds only negatively labeled examples, and Bob holds only positively labeled ones. Since the labels are fixed by the party holding each record, we suppress them and write 𝑆𝐴, 𝑆 𝐵 ∈ X𝑛 . This setting isolates the joint aspect of the problem: when H contains the constant predictors, each local dataset is perfectly realizable, but their union need not be. Thus, the local optimal errors alone do not determine whether a common classifier can explain both datasets. For our algorithms, we later show that they extend to datasets with arbitrary label mixtures (see Corollaries 4.8 and 3.13). The definition of opt H in Equation (1) in the disjoint-label setting can be rewritten as ( opt H (𝑆𝐴, 𝑆 𝐵 ) ≜ min

) ∑︁

1{ℎ(𝑥𝐴 ) ≠ −1} +

ℎ∈ H 𝑥𝐴 ∈𝑆𝐴

∑︁

1{ℎ(𝑥 𝐵 ) ≠ +1} .

(3)

𝑥 𝐵 ∈𝑆 𝐵

To assess a potential collaboration, the agents first agree on an error threshold 𝑡 ∈ [2𝑛]. They seek a private assessment algorithm that rejects with high probability when every classifier in H makes at least 𝑡 mistakes on the pooled data, i.e., opt H (𝑆𝐴, 𝑆 𝐵 ) ≥ 𝑡. We call this requirement soundness. However, a trivial algorithm that always rejects also satisfies soundness. We therefore also require the algorithm to accept with high probability when the pooled data are jointly realizable, i.e., opt H (𝑆𝐴, 𝑆 𝐵 ) = 0, a requirement we call completeness. Finally, to protect the privacy of individual records throughout the interaction, we use differential privacy [DMNS06] in its two-party form [BNO08; MMPRTV10], which requires each agent’s view to be differentially private with respect to the other agent’s dataset (see Definition 2.1). We combine these pieces and formally define the two-party algorithm for dataset valuation as follows:

3

Definition 1.2 (𝜀-DP tester with resolution 𝑡). Fix a data space X, a hypothesis class H ⊆ {±1} X , a dataset size 𝑛 ∈ N, a privacy parameter 𝜀 > 0, and 𝑡 ∈ [2𝑛]. Let Π be an almost-surely terminating interactive two-party protocol on all pairs of finite multisets over X, with common output in {Match, Far}. We interpret these outputs as acceptance or rejection of the proposed collaboration at this preliminary stage, respectively. We call Π an 𝜀-private tester with resolution 𝑡 for H at dataset size 𝑛 if it satisfies the following requirements: 1. Privacy. Π satisfies 𝜀-two-party differential privacy as in Definition 2.1 for every input 𝑆𝐴, 𝑆 𝐵 ∈ X𝑛 2. Soundness. For every 𝑆𝐴, 𝑆 𝐵 ∈ X𝑛 s.t. opt H (𝑆𝐴, 𝑆 𝐵 ) ≥ 𝑡, we have Pr[Π(𝑆𝐴, 𝑆 𝐵 ) = Far] ≥ 0.9. 3. Completeness. For every 𝑆𝐴, 𝑆 𝐵 ∈ X𝑛 , s.t. opt H (𝑆𝐴, 𝑆 𝐵 ) = 0, we have Pr[Π(𝑆𝐴, 𝑆 𝐵 ) = Match] ≥ 0.9. The probabilities are over the protocol’s private and public randomness. We seek the smallest achievable resolution 𝑡, since smaller values let agents enforce stricter error tolerances. Without privacy constraints, the agents can exchange their datasets and compute opt H (𝑆𝐴, 𝑆 𝐵 ) exactly, achieving 𝑡 = 1, the best possible resolution. A trusted curator could also ensure differential privacy by releasing opt H (𝑆𝐴, 𝑆 𝐵 ) + Lap(1/𝜀), since the joint loss has sensitivity one. This gives a tester with resolution 𝑡 central = 𝑂 (1/𝜀), independent of the dimension and hypothesis class. However, we require information-theoretic two-party differential privacy without a trusted curator. This motivates the main technical question that our paper seeks to answer: For fixed H and 𝜀, what is the smallest resolution 𝑡 that an 𝜀-DP private tester can guarantee?

1.3

Our Results

We answer the above technical question for two fundamental classes of hypotheses: thresholds on the real line and half-spaces in R𝑑 . For each class, we establish both upper and lower bounds on the optimal resolution 𝑡 of any 𝜀-private tester (summarized in Table 1). Notably, our main interactive protocols achieve a resolution 𝑡 that is completely independent of the dataset size 𝑛, and all of our upper bounds extend immediately from the disjoint-label setting to arbitrary mixed-label datasets (see Corollaries 4.8 and 3.13). 1.3.1

Thresholds on Real Line

We start with the simplest nontrivial class, thresholds on the real line, where each hypothesis labels a point positive exactly when it lies at or above a cutoff 𝜃 : Hthr = {ℎ𝜃 : R → {±1} | ∃ 𝜃 ∈ R s.t. ℎ𝜃 (𝑥) = 1 for 𝑥 ≥ 𝜃 and ℎ𝜃 (𝑥) = −1 for 𝑥 < 𝜃 }.

(4)

Our main result for this class is as follows: Theorem 1.3 (Informal Version of Theorems 3.1 and  3.12). Fix 𝑚, 𝑛 ∈ N and 𝜀 ∈ (0, 1]. For every domain log log 𝑚 log log 𝑚 X ⊂ R with |X| = 𝑚, provided 𝑛, 𝑡 ≳ log , there exists an interactive, randomized, and 𝜀 𝜀 polynomial-time algorithm that is an 𝜀-DP tester with resolution 𝑡 for Hthr . Moreover, for every domain X ⊂ R log log 𝑚 with |X| = 𝑚, every 𝜀-DP tester with resolution 𝑡 ∈ [𝑛] for Hthr requires 𝑡 ≳ . 𝜀 Next, we mention a few implications of this result: 4

• Minimal overhead compared to the centralized/non-private setting: Recall that a trusted curator achieves resolution 𝑂 (1/𝜀) for every hypothesis class. In comparison, two-party differential privacy introduces only an 𝑂˜ (log log 𝑚) dependence on the domain size 𝑚, negligible in most practical settings. • Exponential improvement using an interactive protocol: Interaction is provably required to achieve    log log 𝑚 log log 𝑚 the near optimal Θ resolution: without interaction, any 𝜀-private tester requires log 𝜀 𝜀 log 𝑚

𝑡 ≳ 𝜀 , yielding an exponential separation between interactive and non-interactive private testing (see Remark 3.4). • Exponential separation between private testing and private learning: A natural approach to the testing problem in Equation (3) is to privately learn a good classifier and then privately evaluate its error  on each dataset. However, any pure 𝜀-DP threshold learner, whether proper or improper, requires log 𝑚 Ω 𝜀 samples at constant accuracy and confidence, even when a trusted curator holds the pooled    log log 𝑚 log log 𝑚 data [BNS13; FX14]. In contrast, Theorem 1.3 gives a private tester using only 𝑂 log 𝜀 𝜀 samples, yielding an exponential separation in the dependence on 𝑚. Qualitatively similar separations arise in non-private settings, where testing or estimating optimal prediction error can require fewer samples or label queries than learning a predictor [KR00; BBBY12; BH18; KV18]. 1.3.2

Halfspaces in Higher Dimension

The next fundamental hypothesis class we consider is halfspaces in R𝑑 defined as follows: Hhs = {ℎ 𝑤 : R𝑑 → {±1} | ∃ 𝑤 ∈ R𝑑 s.t. ℎ 𝑤 (𝑥) = sign(⟨𝑤, 𝑥⟩)}.

(5)

Our main result for this class is as follows: Theorem 1.4 (Informal Version of Theorems 4.1, 4.7 and E.4). Fix 𝑑 ≥ 2, 𝑚, 𝑛 ∈ N, and 𝜀 ∈ (0, 1]. For 𝑑 2 log 𝑚 every domain X ⊂ R𝑑 with |X| = 𝑚, provided 𝑛, 𝑡 ≳ 𝜀 (𝑑 + log log(𝑚)), there exists an interactive 𝜀-DP private algorithm with resolution 𝑡 for Hhs . Moreover, for every sufficiently large 𝑑 and every 𝑚 ≳ 𝑑, there exists a public domain X𝑑,𝑚 ⊆ R𝑑 with |X𝑑,𝑚 | = 𝑚, chosen only from (𝑑, 𝑚), such that for every sufficiently small 𝜀√ > 0 and  every 𝑛∈ N with  𝑛𝜀 ≳ 1, min{𝑑, 𝑛𝜀 } 𝑚 𝑛𝜀 every 𝜀-private tester over X𝑑,𝑚 with resolution 𝑡 ∈ [𝑛] requires 𝑡 ≳ log 2 + min 𝑑 , 𝑑 2 . 𝜀 Next, we mention a few implications of this result: • Sharp jump in domain-size dependence: Comparing Theorem 1.3 and Theorem 1.4 reveals that, as we move from one-dimensional thresholds (𝑑 = 1) to halfspaces in any fixed dimension 𝑑 ≥ 𝑑 0 for some constant 𝑑 0 , the dependence of the testing resolution 𝑡 on the domain size 𝑚 jumps exponentially from log log 𝑚 to log 𝑚. Our lower bound confirms that this log 𝑚 dependence is tight up to secondary logarithmic factors in the stated parameter regime. • Dimension dependence despite a one-bit output: Our lower bound implies that, even though opt H (𝑆𝐴, 𝑆 𝐵 ) is a scalar, two-party pure DP testing
incurs a resolution error that scales with 𝑑, whereas a 1 centralized algorithm incurs only 𝑡 central = 𝑂 𝜀 . This gap reflects the privacy cost of decentralization, as the agents must replace a trusted curator with a protocol that protects each party’s records from the other throughout their interaction. 5

Class Thresholds in R Halfspaces in R𝑑

Upper bound

Lower bound

  log log 𝑚 log log 𝑚 log 𝜀 𝜀 (  2  1/3 ) 2 𝑑 log(2𝑚) 𝑛 𝑑 log(2𝑚) (𝑑 + log(log(2𝑚))), min ,𝑛 𝜀 𝜀

log log 𝑚 𝜀 √  n 𝑚 𝑛𝜀 o min{𝑑, 𝑛𝜀} log 2 + min , 2 † 𝜀 𝑑 𝑑

Table 1: Bounds on the error gap 𝑡 for pure 𝜀-two-party DP testing with success probability at least 0.9, up to universal constant factors. † The halfspace lower bound holds for some input domains, 𝑑 ≥ 𝑑 0 , 𝑚 ≳ 𝑑, and sufficiently small 𝜀.

• The privacy cost even with abundant data: Even with arbitrarily large datasets, two-party private testing can require resolution Ω(𝑑 log(𝑚/𝑑)/𝜀) on the same fixed public domain. Thus, increasing the number of records does not eliminate this worst-case cost in absolute resolution, although the corresponding fraction of errors decreases. Complementary bounds for smaller datasets. An interesting aspect of both of our main results is that the achievable resolution 𝑡 does not depend on 𝑛. For halfspaces, however, our main tester from 𝑑 2 log 𝑚 Theorem 1.4 provides a nontrivial guarantee only when 𝑛 ≳ 𝜀 (𝑑 + log log(𝑚)). For smaller datasets, we complement it with two simple testers whose resolution grows with 𝑛. The first one is an application of the net mechanism of [BLR13]: each party privately releases a
small synthetic dataset, which gives a non-interactive tester with resolution 𝑡 = 𝑂 (𝑛 2𝑑 log(2𝑚)/𝜀) 1/3 (see Theorem 4.11). The second one targets the coarsest nontrivial resolution, i.e., 𝑡 = 𝑛. It turns out that opt Hhs (𝑆𝐴, 𝑆 𝐵 ) = 𝑛 happens only when Alice and Bob have the same number of records on every ray through the origin, and this can be tested with shared randomness as long as 𝑛 ≳ 1/𝜀 2 (see Theorem 4.9). Putting the three testers together, for every 𝑛 ≳ 1/𝜀 2 we get (ignoring smaller logarithmic factors), (  1/3 )!  2 𝑑 2 log(2𝑚) 𝑛 𝑑 log(2𝑚) (𝑑 + log(log(2𝑚))), ,𝑛 . 𝑡 = 𝑂 min 𝜀 𝜀 The 𝑡 = 𝑛 tester is the best of the three when 𝑛 ≲ 𝑑 log(2𝑚)/𝜀, the synthetic-data tester when 𝑑 log(2𝑚)/𝜀 ≲ 𝑛 ≲ 𝑑 4 log(2𝑚)/𝜀, and the geometric protocol for larger 𝑛; see Figure 1.

1.4

Technical Overview

In this section, we outline the main ideas behind our lower bounds and private testing algorithms. We first explain in Section 1.4.1 the idea behind our lower bound, which is based on the connection between opt H and error-correcting codes. We then describe in Section 1.4.2, our threshold algorithm which uses private binary search over prefix lengths to compare two ordered blocks of data. Finally, in Section 1.4.3, we explain the ideas behind our algorithm for halfspaces, which is based on the cutting-plane method in the dual space, i.e., classifier space. 1.4.1

Lower Bounds: Coding Against Erasures

Our lower bounds use the connection between information complexity and DP [MMPRTV10]. We consider a communication problem in which Alice and Bob receive secrets 𝑣 𝐴, 𝑣 𝐵 ∈ V in a finite domain V, and 6

t Upper bound Lower bound

Geometric (Thm. 4.7)

d4 "

hm. R (T

t=

n

Trivial (t > n)

BL

4.10

)

t ≲ d"

4

¡ ¢1=3

t ≲ n 2=3 d"

2

4.9 )

d2 " n(

Th

m.

ound L o w er b

t≳ 1 "

1 "2

t ≳ d"

2

¡ ¢

t ≳ d" log n" d2

t=

d "

Thm. 4.1

.3) (Thm. E

pn "

d2 "

n d5 "

d 2 2d "

Figure 1: Upper and lower bounds on the resolution 𝑡 for private halfspace testing as a function of dataset size 𝑛, illustrated for 𝑚 = 2𝑑 (for 𝑑 > 1/𝜀, hiding constant and log 𝑑 factors). Since opt Hhs (𝑆𝐴, 𝑆 𝐵 ) ≤ 𝑛, the region 𝑡 > 𝑛 is trivial; the upper bound (blue) starts at 𝑛 ≍ 𝜀12 with 𝑡 = 𝑛 2 𝑑 log 𝑚 = 𝑑𝜀 (Theorem 4.11), and reaches the 𝜀 𝑑 4 log 𝑚 𝑛-independent geometric bound at 𝑛 ≍ 𝜀 (Theorem 4.7). The lower bound (orange) starts at 𝑛 ≍ 𝜀1 𝑚𝑑 log(𝑚/𝑑 ) 𝑑 log(𝑚/𝑑 ) (where 𝑡 ≍ 𝜀1 ) and grows across two regimes (Theorem E.4) before saturating at for 𝑛 ≳ 𝜀 𝜀

(Theorem 4.9), transitions to the synthetic-data bound at 𝑛 ≍

(Theorem 4.1). exchange messages to compute a binary function 𝐹 : V × V → {0, 1}. For a protocol computing 𝐹 on inputs (𝑉𝐴, 𝑉𝐵 ) ∼ 𝜇, let Π denote its public transcript, including public randomness, exchanged messages, and final output. The protocol’s internal information cost is defined as IC𝜇 (Π, 𝐹 ) := 𝐼 (𝑉𝐴 ; Π | 𝑉𝐵 ) + 𝐼 (𝑉𝐵 ; Π | 𝑉𝐴 ). Intuitively, it measures what the transcript reveals about each input, given the other. To force a private tester to incur a large information cost, we choose 𝐹 and 𝜇 such that every protocol Π computing 𝐹 with bounded error has large IC𝜇 (Π, 𝐹 ). To relate the communication problem to our problem, we construct local encoders 𝐸𝐴, 𝐸𝐵 : V → X𝑛 , producing datasets 𝑆𝐴 = 𝐸𝐴 (𝑣 𝐴 ) and 𝑆 𝐵 = 𝐸𝐵 (𝑣 𝐵 ) that satisfy 𝐹 (𝑣 𝐴, 𝑣 𝐵 ) = 0 =⇒ opt H (𝑆𝐴, 𝑆 𝐵 ) = 0,

and

𝐹 (𝑣 𝐴, 𝑣 𝐵 ) = 1 =⇒ opt H (𝑆𝐴, 𝑆 𝐵 ) ≥ 𝑡 .

Running a private tester with resolution 𝑡 on these datasets therefore yields a bounded-error protocol Π for 𝐹 . To capture the sensitivity of the encoders to the secrets, we define the encoding diameters Δ𝑈 (𝑛, 𝑡) := max𝑣,𝑣 ′ ∈ V dham (𝐸𝑈 (𝑣), 𝐸𝑈 (𝑣 ′ )) for 𝑈 ∈ {𝐴, 𝐵}, and write Δ = Δ(𝑛, 𝑡) := Δ𝐴 (𝑛, 𝑡) + Δ𝐵 (𝑛, 𝑡). The delicacy is that we need to design an encoding function that relates the encoding diameters to 𝑛, 𝑡. Then, we can invoke existing results [MMPRTV10] (also see Lemma 2.2) that show that IC𝜇 (Π, 𝐹 ) ≤ 𝑂 (𝜀Δ). Comparing this upper bound with the information required to compute 𝐹 forces Δ to be large. Our encoders upper-bound Δ in terms of the loss gap 𝑡, turning this requirement into a lower bound on 𝑡. To design encoders for Alice and Bob, we link joint empirical loss to robustness against record erasures. For any hypothesis class H , opt H (𝑆𝐴, 𝑆 𝐵 ) equals the minimum number of records that must be removed from the pooled data to make it realizable. Thus, ensuring opt H (𝑆𝐴, 𝑆 𝐵 ) ≥ 𝑡 requires the pooled data to remain non-realizable after removing any set of fewer than 𝑡 records. This suggests using error-correcting codes to make non-realizability robust to erasures while keeping the encoding diameter 7

small. Repetition suffices for thresholds, while our halfspace construction uses an expander code. For thresholds on a domain X ⊂ R of size 𝑚, Alice and Bob hold inputs 𝑣 𝐴, 𝑣 𝐵 ∈ V = X. We use the Greater-Than predicate 𝐹 (𝑣 𝐴, 𝑣 𝐵 ) = 1{𝑣 𝐴 ≥ 𝑣 𝐵 }. Alice creates 𝑡 copies of (𝑣 𝐴, −1), and Bob creates 𝑡 copies of (𝑣 𝐵 , +1). The pooled data are realizable when 𝑣 𝐴 < 𝑣 𝐵 , whereas every threshold misclassifies an entire block when 𝑣 𝐴 ≥ 𝑣 𝐵 . This gives a loss gap of 𝑡 with encoding diameter Δ = 𝑂 (𝑡). Since Greater-Than has information complexity Ω(log log 𝑚) under a suitable input distribution [BW11], we use prior results connecting DP to information complexity [MMPRTV10] (Lemma 2.2) to compare this lower bound with an 𝑂 (𝜀𝑡) privacy bound, yielding 𝑡 = Ω(log log(𝑚)/𝜀). For halfspaces, Alice and Bob hold vectors 𝑣 𝐴, 𝑣 𝐵 ∈ V = F𝑞𝑘 , where 𝑘 = Θ(𝑑) and 𝑞 is a power of two. Our encoders map these inputs to labeled data points in a public feature domain X ⊂ R𝑑 of Í size 𝑚. We use the trace inner-product predicate 𝐹 (𝑣 𝐴, 𝑣 𝐵 ) = TrF𝑞 /F2 ( 𝑘𝑖=1 𝑣 𝐴,𝑖 𝑣 𝐵,𝑖 ), whose information complexity is Ω(𝑘 log 𝑞) (Lemma B.6). To construct the datasets, we view halfspace consistency as a linear feasibility problem, with classifier parameters as variables and one constraint per labeled record. We use this correspondence in reverse, building an LP and converting its constraints into records. For each 𝑖 ∈ [𝑘], Alice supplies one input-dependent, or private, constraint fixing the LP representation of 𝑣 𝐴,𝑖 , and Bob does the same for 𝑣 𝐵,𝑖 . The input-independent public constraints force an output variable 𝑧 to equal 𝐹 (𝑣 𝐴, 𝑣 𝐵 ) once the private constraints fix the inputs. They also require 𝑧 = 0, making the LP feasible iff 𝐹 (𝑣 𝐴, 𝑣 𝐵 ) = 0. To obtain a loss gap of 𝑡, we could repeat every constraint 𝑡 times, as for thresholds. However, the resulting diameter Δ = 𝑂 (𝑘𝑡) cancels the dimension factor in the information comparison 𝑘 log 𝑞 ≲ 𝜀𝑘𝑡 (see Section 4.1.1). We instead encode 𝑣 𝐴 and 𝑣 𝐵 using an expander code with Θ(𝑘) symbols and constant-size checks [FWK05; FMSSW07]. Private constraints fix the codeword symbols, while public constraints enforce the code checks. Our key step shows that, with public constraints enforced, fewer than 𝐷 = Θ(𝑑) private deletions cannot change the codewords, even through fractional LP solutions. Indeed, unique-neighbor expansion gives any nonempty set of fewer than 𝐷 deviating symbols a check touching exactly one of them; the unchanged symbols force it back to its original value. Thus, repeating each private constraint ⌈𝑡/𝐷⌉ times and each public constraint 𝑡 times prevents fewer than 𝑡 record deletions from restoring realizability when 𝐹 (𝑣 𝐴, 𝑣 𝐵 ) = 1. Only private copies affect the diameter, giving Δ = 𝑂 (𝑑 ⌈𝑡/𝐷⌉) = 𝑂 (𝑡 + 𝑑). Finally, we represent field elements as polygon vertices in R2 ; restricting each symbol to this polygon lets one supporting inequality fix its value. Together with sparse checks, this keeps the dimension 𝑂 (𝑑) and the universe size 𝑂 (𝑑𝑞𝑂 (1) ). Choosing 𝑞 = (𝑚/𝑑) Θ(1) and applying the information bound yields 𝑡 = Ω(𝑑 log(𝑚/𝑑)/𝜀) under the parameter conditions of Theorem 4.1. 1.4.2

Algorithm for Thresholds: A Robust and Private Greater-Than Protocol

We describe the algorithm in the simpler setting where Alice holds only negative records, Bob holds only positive records, and their feature supports are disjoint (Lemma 3.5 handles overlapping supports, and Corollary 3.13 extends the algorithm to mixed labels.) Also, recall that thresholds label points below their respective cutoffs as negative and those at or above as positive (see Equation (4)). For thresholds with |X| = 𝑚 and 𝑡 ≥ 2, we reduce the promise problem to comparing two witness blocks of 𝑘 = ⌊𝑡/2⌋ records from the size-𝑛 datasets (Figure 2). We prove a simple structural result that implies that if opt Hthr (𝑆𝐴, 𝑆 𝐵 ) = 0, then all of Alice’s points are smaller than all of Bob’s points, and if opt Hthr (𝑆𝐴, 𝑆 𝐵 ) ≥ 𝑡, then every retained point of Alice exceeds every retained point of Bob. See Figure 2 for intuition. Therefore, 𝑘 points are sufficient to distinguish between Match and Far. Note that if 0 < opt Hthr < 𝑡, both answers can happen, as is standard in distribution testing. Given this reduction, a natural idea is for Alice and Bob to compare their blocks using a privately chosen

8

Alice (−)

(a) Match input

Bob (+)

(b) Far input

opt(SA , SB ) = 0

Full datasets

Full datasets

x

Retain extremal records Witness blocks ↑ SA,k

largest k

opt(SA , SB ) ≥ t x

Retain extremal records Witness blocks

x ↓ SB,k

↓ SB,k

smallest k

smallest k

↑ ↓ max SA,k < min SB,k

x ↑ SA,k

largest k

↓ ↑ max SB,k < min SA,k

Solid points are retained; faded points are discarded.

Figure 2: Reduction to witness blocks for thresholds with disjoint supports. Alice retains her largest 𝑘 = ⌊𝑡/2⌋ records, and Bob retains his smallest 𝑘 records. Solid points are retained and used by our algorithm; faded points are discarded and never be used by our algorithm. In Match, Alice’s retained block lies entirely below Bob’s; in Far, their order is reversed. The illustration uses 𝑛 = 8, 𝑡 = 6, and 𝑘 = 3. point. Alice applies the exponential mechanism over the full public domain X, favoring points near her block’s median, and sends her choice to Bob, who privately counts how many of his records fall below it. Selecting among 𝑂 (𝑚) candidates incurs score error 𝑂 (log(𝑚)/𝜀). Taking 𝑘 large enough to dominate this error and Bob’s counting noise ensures, with constant failure probability, that Alice’s choice lies within her block’s range and Bob’s comparison identifies the
correct order. This yields resolution 𝑂 (log(𝑚)/𝜀), but leaves a gap with respect to our Ω log log(𝑚)/𝜀 lower bound. To compare the blocks with a better dependence on 𝑚, we build on the standard Greater-Than protocol for comparing two numbers [RY20, Chapter 3]. We adapt its search over prefix lengths to handle blocks of records while preserving privacy. Specifically, we encode each point’s rank in the public domain as a binary string of length 𝑏 = 𝑂 (log 𝑚) and organize these strings into a binary trie; see Figure 3. Each node at depth ℓ contains the strings sharing a particular prefix of length ℓ. When each party holds a single distinct string, their first differing bit determines their order. Their prefixes agree before that bit and disagree from that bit onward, so binary search locates it using 𝑂 (log 𝑏) = 𝑂 (log log 𝑚) prefix-equality tests. At that position, the string with bit 0 precedes the string with bit 1. For blocks of records, however, the first separation may involve too few points to overcome privacy noise. We therefore search for a depth at which sufficiently many records have left the shared prefix. To measure this, let 𝐴𝑝ℓ and 𝐵𝑝ℓ contain the records in the respective blocks with prefix 𝑝 ∈ {0, 1}ℓ , and define 𝑀 (ℓ) := max𝑝 min{|𝐴𝑝ℓ |, |𝐵𝑝ℓ |} and 𝐹 (ℓ) := 𝑘 − 𝑀 (ℓ). Since the blocks are strictly ordered, at most one node at each depth contains records from both parties. When this common node exists, 𝐹 (ℓ) is the larger of the two counts of records outside it. As each child contains only records from its parent, 𝑀 (ℓ) cannot increase with depth; consequently, 𝐹 (ℓ) is nondecreasing from 𝐹 (0) = 0 to 𝐹 (𝑏) = 𝑘. We can therefore use noisy binary search to find adjacent depths 𝐿, 𝐻 = 𝐿 + 1 whose values of 𝐹 bracket a target level 𝛼 up to the estimation error, with 𝛼 chosen well above that error. To estimate 𝐹 (ℓ) without incurring the unwanted log 𝑚 cost, we estimate 𝑀 (ℓ) through a small hashed histogram. A direct noisy histogram over all 2ℓ prefixes would incur an error that grows with ℓ, but at most 2𝑘 prefixes are occupied. The parties therefore use the same public hash into 𝑂 (𝑘 2 /𝛽 0 ) buckets, which keeps distinct occupied prefixes in different buckets with probability at least 1 − 𝛽 0 /2. They then add Laplace noise to their bucket counts and take the maximum over buckets of the smaller noisy count. With privacy budget 𝜀 0 per party, this estimates 𝑀 (ℓ), and hence 𝐹 (ℓ), to error 𝑂 (log(𝑘/𝛽 0 )/𝜀 0 ) with failure probability

9

Alice: Aℓp ̸= ∅

Bob: Bpℓ ̸= ∅

common node

depth 0

0

1

1 0

1

0

1

2 0

1

0

1

0

1

0

1

3=b 000

001

010

011

b = 3,

X = {0, 1}3 ,

100

101

110

111

m = 2b = 8

Figure 3: A binary trie for the ordered witness blocks. A node 𝑝 at depth ℓ represents a prefix; 𝐴𝑝ℓ and 𝐵𝑝ℓ contain the records in Alice’s and Bob’s blocks with that prefix. Blue and red shading indicate Alice’s and Bob’s records, respectively, and dashed circles mark the common nodes shared by both. Because the blocks are strictly ordered, at most one node at each depth is common.

at most 𝛽 0 . The error thus depends logarithmically on 𝑘 and 1/𝛽 0 , rather than on the full prefix universe. These estimates locate a useful depth, but we must still determine which block comes first. If the estimated increase from 𝐹 (𝐿) to 𝐹 (𝐻 ) is large, the common node at depth 𝐿 splits enough records between its two children to reveal the order. Otherwise, 𝐹 (𝐻 ) is already of order 𝛼, while the common node at depth 𝐻 still contains most of each block. The records accumulated outside this node then reveal the order: in Match, Alice’s lie to its left and Bob’s to its right, with these directions reversed in Far. In both cases, each party computes a comparison statistic from weighted maxima of counts. These statistics have constant sensitivity even when their maximizing prefixes change, and their difference distinguishes the two orders with a margin of Ω(𝛼). We can therefore add noise without identifying the common prefix itself. The search uses only 𝑇 = ⌈log2 𝑏⌉ = 𝑂 (log log 𝑚) adaptive queries. We give each query a privacy budget 𝜀 0 = 𝜀/(2𝑇 ) and a failure budget 𝛽 0 = 𝛽/(2𝑇 ), leaving half of each party’s privacy budget and half of the
total failure budget for the final comparison. With these allocations, a margin 𝛼 = 𝑂 (𝑇 /𝜀) log(𝑘𝑇 /𝛽) suffices to dominate the noise in both stages. Taking 𝑘 ≥ 4𝛼 makes the final comparisons reliable; since 𝑘 = ⌊𝑡/2⌋, this condition holds when 𝑡 is a sufficiently large constant multiple of (𝑇 /𝜀) log(𝑇 /(𝜀𝛽)). Thus, at
constant failure probability, we obtain an 𝜀-private tester with resolution 𝑡 = 𝑂˜ log log(𝑚)/𝜀 , independent of the original dataset size 𝑛, provided 𝑛 ≥ 𝑡. 1.4.3

Algorithm for Halfspaces: Cutting Plane in the Dual Space

For the class of halfspaces in R𝑑 with |X| = 𝑚, our main idea is to move to the dual space, where each classifier ℎ 𝑤 is represented by a point 𝑤 ∈ R𝑑 . Since only the predictions on the public domain matter, the Sauer–Shelah lemma allows us to restrict attention to a finite public set of candidate classifiers Wdisc of size at most 𝑚𝑑 . Let 𝐺𝐴𝑘 and 𝐺 𝐵𝑘 denote the candidates that make at most 𝑘 = ⌊(𝑡 − 1)/(2(𝑑 + 1))⌋ mistakes on Alice’s and Bob’s data, respectively. Unlike the ordered witness blocks for thresholds, these sets of low-error classifiers can be very unstructured. Our key observation is that their convex hulls distinguish the two cases. In

10

feature space 

classifier space 

MATCH

conv(GBk ) be

st

cla

ss

ifi

w⋆ er

dual space

conv(GAk)

FAR

conv(GAk ) ∩ conv(GBk ) ≠ ∅

be

conv(GBk ) st

cla

ss

ifi

er

dual space

every classifier errs

conv(GAk) conv(GAk ) ∩ conv(GBk ) = ∅

Alice: negatives, GAk

Bob: positives, GBk

Figure 4: The halfspace promise problem viewed in the dual space. Our algorithm works in the dual space and tests which case holds.

Match, the sets share a consistent classifier 𝑤 ★. In Far, even their convex hulls are disjoint: conv(𝐺𝐴𝑘 ) ∩ conv(𝐺 𝐵𝑘 ) = ∅. To see why, suppose a point belongs to both convex hulls. By Carathéodory’s theorem, it is a convex combination of at most 𝑑 + 1 low-error classifiers from each party. A convex combination can misclassify a record only if at least one of its constituent classifiers misclassifies that record. Thus, this point would define a classifier with at most 2(𝑑 + 1)𝑘 < 𝑡 mistakes on the pooled data, contradicting Far. This geometric separation suggests an iterative elimination algorithm, inspired by [BKMS19]. The parties maintain a public set of active candidates. In Far, a hyperplane separates the convex hulls of their remaining low-error classifiers. At least one side of this hyperplane contains at most half of the active candidates. Thus, at least one party has a halfspace cut that retains all of its low-error classifiers while discarding at least half of the candidates. The next challenge is to choose such a cut privately. Searching directly over all possible halfspace cuts would be costly in terms of privacy. Instead, we use halfspace containers [BKMS19; DGM22] to obtain a small public menu of 2𝑂 (𝑑 ) subsets of the active candidates. Whenever a halfspace contains at most half of the active candidates, one of these containers covers its candidates while containing at most 3/4 of the active set. We can therefore search over this small menu while still eliminating a constant fraction of the candidates. Alice and Bob use the exponential mechanism with a low-sensitivity cost to select a container or abstain. With high probability, at least one party selects a shrinking container in each Far round, while every selected container preserves 𝑤 ★ in Match. Thus, within 𝑂 (𝑑 log 𝑚) rounds, the active set becomes empty in Far and remains nonempty in Match.
Considering all the factors, we can show this algorithm is an 𝜀-private tester with 𝑡 = 𝑂˜ 𝑑 3 log(𝑚)/𝜀 . 𝑑 log 𝑚 𝑑 log 𝑚 Intuitively, the resolution 𝑂˜ (𝑑 3 log(𝑚)/𝜀) factors as 𝜀 · 𝑑 · 𝑑, where 𝜀 arises from splitting the privacy budget across 𝑂 (𝑑 log 𝑚) elimination rounds, the second factor of 𝑑 is the entropy of the containers 11

that we need to pay due to exponential mechanism, and the third factor of 𝑑 comes from Carathéodory theorem when relating the global mistake gap 𝑡 to the local error threshold 𝑘 = Θ(𝑡/𝑑).

1.5

Related Work

Our work lies at the intersection of three lines of research: communication-efficient distributed learning, testing whether a good model exists without learning one, and data valuation. Distributed Communication-Efficient Learning. A line of work studies communication-efficient distributed learning [BBFM12; CBC16; KLMY19]. Broadly speaking, in the two-party setting, each agent holds a set of labeled examples, and the players communicate to learn a classifier with small error. In much of this work, the algorithms communicate with each other using samples, and the goal is to minimize the number of samples communicated. However, [BBFM12] also propose and analyze the more general setting in which communication can be arbitrary, and the goal is to minimize the total number of bits communicated, possibly subject to privacy constraints. Our setting can be viewed as a property-testing version of the distributed communication-efficient learning problem. More closely related to our halfspace algorithm is the work of [BKMS19], who study distributed halfspace learning and convex set disjointness over a known finite domain and measure communication in bits. Their goal is to minimize the number of bits exchanged. Our focus is on the smallest resolution 𝑡 for testing whether opt H = 0 or opt H ≥ 𝑡 under two-party DP. On the technical side, our halfspace algorithm builds on their container approach, using the improved container bounds of [DGM22]. We apply this approach to sets of low-error classifiers in the dual space and select containers privately to eliminate candidates while preserving a shared, consistent classifier when one exists. Testing and Estimating Learnability. A related line of work asks whether one can test if the optimal population error using classifiers in a hypothesis class is small or large without learning a classifier [BBBY12; KNOW14; BH18; KV18]. In the active testing setting, the learner has access to a large pool of unlabeled samples and chooses which points to label. The goal is to answer this question using as few label queries as possible. A related question with access to i.i.d. labeled samples is studied in [KV18]. Under distributional assumptions, they show that the optimal population loss can be estimated using fewer samples than are needed to learn an accurate predictor. For example, in isotropic√regression with suitable moment bounds, they show a quadratic gap in the dependence on dimension: 𝑂 ( 𝑑) samples suffice to estimate the optimal squared loss to constant accuracy, whereas learning can require Ω(𝑑) samples. They also discuss using such estimates for data valuation and comparing separate and pooled datasets to assess whether joint training is promising. These works share our goal of assessing prediction error without learning a classifier. They focus on using as few labels or samples as possible to assess population error. Our main constraint is privacy: two agents hold labeled datasets and want to determine whether a single classifier in their hypothesis class fits all the pooled records, or whether every classifier makes at least 𝑡 mistakes. The challenge is to achieve a small resolution 𝑡 while protecting individual records throughout the agents’ interaction. We provide upper and lower bounds on 𝑡 that quantify the cost of two-party DP. Similar to this line of work, our threshold result also distinguishes between private testing and private learning. For fixed fractional empirical testing gap, learning accuracy, and confidence, our tester needs e(log log 𝑚/𝜀) samples per party, whereas distribution-free pure-private threshold learning requires only 𝑂 Ω(log 𝑚/𝜀) samples even with a trusted curator. Data Valuation and Selection. Data valuation supports decisions throughout the machine learning 12

pipeline, from selecting and pricing training data to debugging trained models [WYZKJ24; TLLCJKLR22; KL17]. Popular approaches guide these decisions by assigning scores to individual records or entire datasets using Shapley values or leave-one-out contributions [GZ19; JDWHHGLZSS19; GHVLP24]. These methods must, however, account for non-monotonicity, since adding training data can worsen downstream test performance, including when pooling data from heterogeneous sources [NKBYBS20; CZPR23]. Our opt H (𝑆𝐴, 𝑆 𝐵 ) > 𝑡 scenario captures a related obstacle when individually realizable datasets admit no shared classifier that fits both perfectly. For data selection, such non-monotonicity can give adaptive methods a strict advantage over fixed score-based methods under equal value-query budgets [PKFZ26], paralleling the benefit of interaction between agents in private threshold testing noted in Remark 3.4. Private Data Appraisal and Valuation. Existing private appraisal methods differ in both what they protect and what their assessments establish. Secure-computation methods, for example, estimate learning gains or Shapley values while permitting leakage through the released appraisal [XHV22; TLLCJKLR22]. Differential privacy can address such leakage, but its scope varies across methods. Protocols combining homomorphic encryption with label differential privacy leave features public [ALZK23], while private KNN-based valuation assumes a trusted server and excludes validation-data privacy [WZWJM23]. Similar asymmetries arise in dataset valuation that protects sellers without providing corresponding guarantees for the buyer [JMMC24]. Protecting both sides therefore remains a challenge, as broader analyses of private valuation also emphasize [FWC26]. Beyond these privacy constraints, the assessment itself may not certify compatibility. Similarity-based methods estimate dataset divergence or correlation without establishing whether a shared classifier fits the combined data [FXC25; CPP23; JMMC24]. Likewise, protecting fixed valuation scores does not itself ensure that they identify useful data combinations [PKFZ26]. These limitations leave unresolved the worst-case accuracy limits of compatibility testing under two-party recordlevel differential privacy without a trusted curator or computational assumptions.

2

Preliminaries

2.1

Notations

For a positive integer 𝑟 , let [𝑟 ] := {1, . . . , 𝑟 }. The public data domain is denoted by X ⊆ R𝑑 ; when it is finite, we write 𝑚 := |X|. For 𝑆, 𝑆 ′ ∈ X𝑛 , we write 𝑆 ∼ 𝑆 ′ when they are neighboring, meaning that one record is replaced; the corresponding replacement distance is denoted by dham (𝑆, 𝑆 ′ ). For two vectors 𝑢, 𝑣 ∈ R𝑑 , we write ⟨𝑢, 𝑣⟩ for the Euclidean inner product, conv(𝐺) for the convex hull of 𝐺 ⊂ R𝑑 . Finally, Lap(𝑏) is the mean-zero Laplace distribution with scale 𝑏.

2.2

Two-Party DP and Connection to Information Complexity

In an interactive protocol, privacy must hold not only for the final Match or Far output, but for the entire interaction transcript observed by each party. For a protocol Π and inputs (𝑆𝐴, 𝑆 𝐵 ), let View𝐴Π (𝑆𝐴, 𝑆 𝐵 ) denote Alice’s complete view of the execution, consisting of her input 𝑆𝐴 , her private randomness, the public randomness, all exchanged messages, and the common output; define View𝐵Π (𝑆𝐴, 𝑆 𝐵 ) similarly. Definition 2.1 (Differential privacy for two-party protocols [MMPRTV10]). A two-party protocol Π is 𝜀-differentially private if each party’s view is 𝜀-differentially private with respect to the other party’s dataset. More precisely, for every fixed 𝑆𝐴 , every pair of neighboring datasets 𝑆 𝐵 , 𝑆 𝐵′ , and every measurable event 𝐸,     Pr View𝐴Π (𝑆𝐴, 𝑆 𝐵 ) ∈ 𝐸 ≤ 𝑒 𝜀 Pr View𝐴Π (𝑆𝐴, 𝑆 𝐵′ ) ∈ 𝐸 , 13

and, symmetrically, for every fixed 𝑆 𝐵 , every pair of neighboring datasets 𝑆𝐴, 𝑆𝐴′ , and every measurable event 𝐸,     Pr View𝐵Π (𝑆𝐴, 𝑆 𝐵 ) ∈ 𝐸 ≤ 𝑒 𝜀 Pr View𝐵Π (𝑆𝐴′ , 𝑆 𝐵 ) ∈ 𝐸 . We require differential privacy on the full input domain, including inputs that do not satisfy the promise of the testing problem. We also make a repeated use of this lemma which is a simple modification of the connection between DP and internal information complexity from [MMPRTV10]. Lemma 2.2. Let A and B be finite sets, and let 𝐸𝐴 : A → X𝑛 and 𝐸𝐵 : B → X𝑛 be deterministic maps that encode inputs in A and B as size-𝑛 datasets over X. Define the encoding diameter of 𝐸𝐴 and 𝐸𝐵 as follows:
Δ𝐴 := max dham 𝐸𝐴 (𝑎), 𝐸𝐴 (𝑎 ′ ) ,

Δ𝐵 := max dham 𝐸𝐵 (𝑏), 𝐸𝐵 (𝑏 ′ ) .

𝑎,𝑎 ′ ∈ A

𝑏,𝑏 ′ ∈ B

Suppose (𝐴, 𝐵) ∼ 𝜇 for a distribution 𝜇 over A ×
B, and Alice and Bob execute an 𝜀-differentially private protocol Π on the encoded datasets 𝐸𝐴 (𝐴), 𝐸𝐵 (𝐵) . Let 𝑇 denote the resulting public transcript (consisting of the public randomness, all exchanged messages, and the final output). Then the internal information cost of 𝑇 (in bits) satisfies 𝜀 (Δ𝐴 + Δ𝐵 ) 𝐼 (𝐴;𝑇 | 𝐵) + 𝐼 (𝐵;𝑇 | 𝐴) ≤ . ln 2

3

Threshold in One Dimension

In this section, we focus on the class of thresholds on real line. In particular, define Hthr = {ℎ𝜃 : R → {±1} | ∃𝜃 ∈ R s.t. ℎ𝜃 (𝑥) = 1 for 𝑥 ≥ 𝜃 and ℎ𝜃 (𝑥) = −1 for 𝑥 < 𝜃 }.

(6)

First notice that opt Hthr (𝑆𝐴, 𝑆 𝐵 ) ≤ 𝑛, therefore, the non-vacuous regime for the resolution will be 1 ≤ 𝑡 ≤ 𝑛. We first provide an information-theoretic lower bound on 𝑡 for this class, and then present an algorithm that (nearly) matches the lower bound.

3.1

Lower bound for thresholds

The next result presents a fundamental lower bound on 𝑡 for the class of thresholds. The main idea is to embed a binary function with a high information complexity and then use the connection between information complexity and two-view DP from [MMPRTV10] to provide a lower bound. Theorem 3.1 (Lower bound for thresholds). There exist universal constants 𝑐 > 0 and 𝑚 0 ∈ N such that the following holds. For every 𝑚 ≥ 𝑚 0 , every X ⊆ R with |X| = 𝑚, every 𝜀 > 0, and every 𝑛, 𝑡 ∈ N such that 𝑡 ≤ 𝑛, we have that every 𝜀-private tester for Hthr with resolution 𝑡 for dataset of size 𝑛 (from Definition 1.2) requires 𝑡 ≥𝑐

log log 𝑚 . 𝜀

Remark 3.2. Fix 𝜀 ∈ (0, 1] and 𝑛 ∈ N. Theorem 3.1 implies that no 𝜀-private tester for thresholds over R at dataset size 𝑛 can achieve a resolution 1 ≤ 𝑡 ≤ 𝑛. Indeed, restricting such a tester to a finite domain of size 𝑚 would give 𝑡 ≥ 𝑐 log log(𝑚)/𝜀 for arbitrarily large 𝑚, contradicting the fact that 𝑡 is fixed. 14

A trusted curator can achieve resolution 𝑡 = 𝑂 (1/𝜀), independently of the domain size, by adding Laplace noise to the sensitivity-one quantity opt. This resolution is nontrivial provided 𝑛 ≥ 𝐶/𝜀 for a sufficiently large universal constant 𝐶. Thus, on finite domains of size 𝑚, the two-party setting incurs an unavoidable multiplicative Ω(log log 𝑚) overhead relative to the centralized resolution. ⊳ Remark 3.3. Under cryptographic assumptions, secure function evaluation can emulate the trusted curator and achieve 𝑡 = 𝑂 (1/𝜀) with computational differential privacy [MMPRTV10]. However, Theorem 3.1 shows that information-theoretic view-based privacy requires 𝑡 = Ω(log log(𝑚)/𝜀). Thus, the two models exhibit a separation in the achievable promise gap. ⊳ Remark 3.4. The lower bound in Theorem 3.1 allows arbitrary interaction between Alice and Bob. For one-way protocols with bounded worst-case error, however, the standard information-theoretic argument underlying the Greater-Than lower bound [RY20, Chapter 6] shows that Alice’s message must reveal Ω(log 𝑚) bits about her input when it is uniformly random. Indeed, given any prefix of Alice’s input, Bob can choose a comparison that predicts her next bit with constant error; Fano’s inequality and the chain rule then give the information lower bound. Applying this argument to the encoding in Theorem 3.1, group privacy bounds the information revealed by Alice’s message by 𝑂 (𝜀𝑡), yielding 𝑡 = Ω(log(𝑚)/𝜀). The private-interior-point baseline in Section 3.2.3 achieves the matching 𝑂 (log(𝑚)/𝜀) resolution. Thus, e(log log(𝑚)/𝜀). interaction is necessary to achieve our improved resolution of 𝑂 ⊳ Proof of Theorem 3.1. Without loss of generality write X = {𝑥 1, · · · , 𝑥𝑚 } where 𝑥 1 ≤ · · · ≤ 𝑥𝑚 . Fix an arbitrary integer 𝑛 ≥ 𝑡 and let ℓ = ⌊log2 (𝑚 − 2)⌋. For 𝑖, 𝑗 ∈ {2, · · · , 2ℓ + 1}, define the size-𝑛 multisets 𝑆𝐴(𝑖 ) = (𝑥 1, . . . , 𝑥 1, 𝑥𝑖 , · · · , 𝑥𝑖 ), | {z } | {z } 𝑛 − 𝑡 times

𝑆 𝐵( 𝑗 ) = (𝑥 𝑗 , . . . , 𝑥 𝑗 , 𝑥𝑚 , · · · , 𝑥𝑚 ), | {z } | {z }

𝑡 times

𝑡 times

𝑛 − 𝑡 times

where Alice’s records are negatively labeled and Bob’s records are positively labeled. Then, ( 0, 𝑖 < 𝑗, opt Hthr (𝑆𝐴(𝑖 ) , 𝑆 𝐵( 𝑗 ) ) = 𝑡, 𝑖 ≥ 𝑗 .

(7)

There exists a distribution 𝜇ℓ over ∈ {2, · · · , 2ℓ +1}2 such that every protocol computing GTℓ (𝑖, 𝑗) = 1{𝑖 ≥ 𝑗 } with error at most 1/10 has internal information cost Ω(log ℓ) [BW11; Vio15]. More precisely, let Π be a private tester from Definition 1.2. Then, given (𝐼, 𝐽 ) ∼ 𝜇ℓ , run Π on (𝑆𝐴(𝐼 ) , 𝑆 𝐵( 𝐽 ) ). By Equation (7), the resulting protocol computes GTℓ with error at most 1/10. Therefore, if 𝑇 consists of the shared randomness, exchanged messages, and common output, then 𝐼 (𝐼 ;𝑇 | 𝐽 ) + 𝐼 (𝐽 ;𝑇 | 𝐼 ) = Ω(log ℓ) by [BW11; Vio15]. The padding is independent of 𝑖 and 𝑗, and hence both encoding diameters     are at most 2𝑡. By Lemma 2.2, log ℓ log log 𝑚 4𝜀𝑡 𝐼 (𝐼 ;𝑇 | 𝐽 ) + 𝐼 (𝐽 ;𝑇 | 𝐼 ) ≤ ln 2 . Then, it follows that 𝑡 = Ω 𝜀 = Ω , as claimed. □ 𝜀

3.2

Algorithm for Thresholds

In this part, we present our algorithm that achieves the lower bound up to log log log(𝑚) factor. 3.2.1

Structural Properties and Binary Trie

First, we introduce a notation: For a multiset 𝑆 of size 𝑛 over a totally ordered domain, write its elements, with multiplicity, as 𝑠 (1) ≤ · · · ≤ 𝑠 (𝑛) . For 𝑘 ∈ [𝑛], define the multisets of the 𝑘 smallest and 𝑘 largest 15

elements by 𝑆𝑘↓ := {𝑠 (1) , . . . , 𝑠 (𝑘 ) }, and 𝑆𝑘↑ := {𝑠 (𝑛−𝑘+1) , . . . , 𝑠 (𝑛) }. Now, we are ready to present a structural property. Lemma 3.5. Let X = {0, 1}𝑏 where 𝑚 = 2𝑏 . Define 𝜓𝐴 (𝑥) = 𝑥 ∥1 and 𝜓𝐵 (𝑥) = 𝑥 ∥0. In particular, 𝜓𝐴 and 𝜓𝐵 add a bit 1 and 0 after the least significant bit of the input, respectively. Let 𝑆𝐴, 𝑆 𝐵 be multisets of size 𝑛 over X, let 𝑘 ∈ [𝑛], and write 𝑆e𝐴 = 𝜓𝐴 (𝑆𝐴 ) and 𝑆e𝐵 = 𝜓𝐵 (𝑆 𝐵 ). Then opt Hthr (𝑆e𝐴, 𝑆e𝐵 ) = opt Hthr (𝑆𝐴, 𝑆 𝐵 ). Moreover: ↑ ↓ 1. if opt Hthr (𝑆𝐴, 𝑆 𝐵 ) = 0, then max 𝑆e𝐴,𝑘 < min 𝑆e𝐵,𝑘 ; ↑ ↓ 2. if opt Hthr (𝑆𝐴, 𝑆 𝐵 ) ≥ 2𝑘 − 1, then min 𝑆e𝐴,𝑘 > max 𝑆e𝐵,𝑘 .

Proof. Reading strings as integers, 𝜓𝐴 (𝑥) = 2𝑥 + 1 and 𝜓𝐵 (𝑥) = 2𝑥. Thus both maps are strictly increasing, and their images are disjoint by parity. At an even threshold 𝜃e = 2𝑠, the Alice and Bob errors are, respectively, {𝑥 ∈ 𝑆𝐴 : 𝑥 ≥ 𝑠},

{𝑥 ∈ 𝑆 𝐵 : 𝑥 < 𝑠},

which are exactly the errors at threshold 𝑠 in the original instance. At an odd threshold 𝜃e = 2𝑠 + 1, the error multisets are {𝑥 ∈ 𝑆𝐴 : 𝑥 ≥ 𝑠}, {𝑥 ∈ 𝑆 𝐵 : 𝑥 ≤ 𝑠}. Thus, compared with 2𝑠, the odd threshold 2𝑠 + 1 makes exactly the same errors except that it may additionally misclassify Bob’s records at s. It can therefore never be better than 2𝑠. It follows that the two optimal errors are equal. If the original instance is realizable, then max 𝑆𝐴 < min 𝑆 𝐵 . So every element of 𝑆e𝐴 lies below every element of 𝑆e𝐵 , proving part (i). For part (ii), suppose instead that ↑ ↓ 𝑎 := min 𝑆e𝐴,𝑘 ≤ 𝑏 := max 𝑆e𝐵,𝑘 .

Since 𝑎 is odd and 𝑏 is even, we have 𝑎 < 𝑏. At threshold 𝑏, every Alice error is strictly larger than 𝑎, so there are at most 𝑘 − 1 Alice errors. Likewise, every Bob error is strictly smaller than 𝑏, so there are at most 𝑘 − 1 Bob errors. Therefore, opt Hthr (𝑆e𝐴, 𝑆e𝐵 ) ≤ 2𝑘 − 2, contradicting the assumption. This proves part (ii).

□

The lemma reduces the promise problem to a comparison between two extremal blocks. Fix 𝑘 = ⌊𝑡/2⌋. In ↑ ↓ the Match case, every point in 𝑆e𝐴,𝑘 lies below every point in 𝑆e𝐵,𝑘 . In the Far case, their order is reversed: ↑ ↓ e e every point in 𝑆𝐴,𝑘 lies above every point in 𝑆 𝐵,𝑘 . In particular, being far from realizable creates not merely one misordered pair, but two blocks of 𝑘 records with opposite order. This introduces a stability that we later exploit: the promised cases can be distinguished using robust order statistics rather than the maximum of 𝑆𝐴 and the minimum of 𝑆 𝐵 , which may each depend on a single record. Remark 3.6. To avoid ties between records owned by different parties, we apply the lifting function 𝜓𝐴 and 𝜓𝐵 from Lemma 3.5 and suppress the tildes. Since this transformation is local, it entails no loss of generality. ↑ ↓ Henceforth, we assume that the supports of 𝑆𝐴,𝑘 and 𝑆 𝐵,𝑘 are disjoint, so the preceding order comparisons ↑ are strict. Without loss of generality to reduce notation clutter, we assume Alice and Bob only use 𝑆𝐴,𝑘 and ↓ 𝑆 𝐵,𝑘 during the execution of the algorithm. It is easy to see that these subsets also respect the neighboring condition we require for the definition of DP. ⊳

16

Definition 3.7 (Binary Trie and Common Node). Let X = {0, 1}𝑏 with 2𝑏 = 𝑚. Let T be the complete Ð binary trie whose nodes are the binary strings 𝑣 ∈ {0, 1} ≤𝑏 = 𝑏𝑟=0 {0, 1}𝑟 . The depth of a node is its length |𝑣 |: the root is the empty string at depth 0, and the leaves are the depth-𝑏 strings, which we identify with X. For each ℓ ∈ [𝑏] and 𝑝 ∈ {0, 1}ℓ define 𝐴𝑝ℓ = {𝑥𝑖 ∈ 𝑆𝐴 : prefixℓ (𝑥𝑖 ) = 𝑝} and similarly define 𝐵𝑝ℓ = {𝑥𝑖 ∈ 𝑆 𝐵 : prefixℓ (𝑥𝑖 ) = 𝑝}. Also, we have the convention that 𝐴𝑝0 = 𝑆𝐴 and 𝐵𝑝0 = 𝑆 𝐵 . At depth ℓ a node is called common if it contains both Alice and Bob points. Next lemma shows an important property of the binary trie node, that we use in the sequel to design an algorithm. Lemma 3.8. Fix X = {0, 1}𝑏 and 𝑛 ∈ N. Let 𝑆𝐴, 𝑆 𝐵 ⊆ X𝑛 be two sequence of length 𝑛 and assume the promise holds. Recall the definition of the trie node from Definition 3.7. Then, for every given depth ℓ ∈ [𝑏], there exists at most on node that contains both Alice and bob’s data, i.e., |{𝑝 ∈ {0, 1}𝑙 : 𝐵𝑝ℓ · 𝐴𝑝ℓ ≠ 0}| ≤ 1. Also, at depth 𝑏, we have |{𝑝 ∈ {0, 1}𝑏 : 𝐵𝑝ℓ · 𝐴𝑝ℓ ≠ 0}| = 0. Proof. Under the promise from Lemma 3.5 and Remark 3.6, either max 𝑆𝐴 < 𝑚𝑖𝑛𝑆 𝐵 or max 𝑆 𝐵,𝑘 < 𝑚𝑖𝑛𝑆𝐴 . First, we prove the last claim: by Lemma 3.5 (recall also Remark 3.6), we have that under the promise, the block of Alice and Bob’s data are disjoint. For the first claim, we prove by contradiction. Lets assume at depth ℓ, there exists two nodes that are both common and denoted by 𝑝 1 ∈ {0, 1}ℓ and 𝑝 2 ∈ {0, 1}ℓ such that 𝐴𝑝ℓ 1 .𝐵𝑝ℓ 1 ≠ 0 and 𝐴𝑝ℓ 2 .𝐵𝑝ℓ 2 ≠ 0. Assume without loss of generality that 𝑝 1 < 𝑝 2 in lexicographic order. Every leaf below 𝑝 1 is smaller than every leaf below 𝑝 2 . Choose 𝑎𝑝 1 ∈ 𝐴𝑝ℓ 1 𝑏 𝑝 1 ∈ 𝐵𝑝ℓ 1 𝑎𝑝 2 ∈ 𝐴𝑝ℓ 2 𝑏 𝑝 2 ∈ 𝐵𝑝ℓ 2 . It follows that 𝑎𝑝 1 < 𝑏 𝑝 2 and 𝑏 𝑝 1 < 𝑎𝑝 2 . If max 𝑆𝐴 < min 𝑆 𝐵 , then 𝑎𝑞 < 𝑏 𝑝 , contradicting 𝑏 𝑝 < 𝑎𝑞 . If min 𝑆𝐴 > max 𝑆 𝐵 , then 𝑎𝑝 > 𝑏𝑞 , contradicting 𝑎𝑝 < 𝑏𝑞 . □ Example 3.9. To gain some intuition, behind how the binary trie structure, consider Figure 3 where it shows X = {0, 1}3 . Here, opt(𝑆𝐴, 𝑆 𝐵 ) = 0. Note that at depth zero, the single node is always common and the last depth doesn’t have any common nodes. ⊳ Lemma 3.10 (escaped points). Fix X = {0, 1}𝑏 and 𝑛 ∈ N. Let 𝑆𝐴, 𝑆 𝐵 ⊆ X𝑛 be two sequence of length 𝑛 and assume the promise holds. Define the function 𝐹 : [𝑏] → N as 𝐹 (ℓ) = 𝑛 − max𝑝 ∈ {0,1} ℓ min{𝐴𝑝ℓ , 𝐵𝑝ℓ }. Then 𝐹 ℓ is a non-decreasing function with 𝐹 (0) = 0 and 𝐹 (𝑏) = 𝑛.  Proof. Set 𝑀 (ℓ) := max𝑝 ∈ {0,1} ℓ min |𝐴𝑝ℓ |, |𝐵𝑝ℓ | , so that 𝐹 (ℓ) = 𝑛 − 𝑀 (ℓ). If 𝑞 is a node at depth ℓ + 1 and 𝑝 is its parent, then 𝐴𝑞ℓ+1 ⊆ 𝐴𝑝ℓ and 𝐵𝑞ℓ+1 ⊆ 𝐵𝑝ℓ . Hence   min |𝐴𝑞ℓ+1 |, |𝐵𝑞ℓ+1 | ≤ min |𝐴𝑝ℓ |, |𝐵𝑝ℓ | ≤ 𝑀 (ℓ). Maximizing over 𝑞 gives 𝑀 (ℓ + 1) ≤ 𝑀 (ℓ), and therefore 𝐹 (ℓ + 1) ≥ 𝐹 (ℓ). At the root, |𝐴0∅ | = |𝐵 0∅ | = 𝑛, so 𝐹 (0) = 0. At depth 𝑏, no leaf is common by Lemma 3.8; hence 𝑀 (𝑏) = 0 and 𝐹 (𝑏) = 𝑛. □ 3.2.2

Distributed Private Common-Frequency Estimation

In this section, we describe an algorithm for a problem that we refer to as distributed common heavy hitter. This subroutine later used in our algorithm for the thresholds. The task is simple: Alice and Bob hold a categorical dataset of size 𝑛 over a finite universe of size 𝑚. Their goal is to estimate the maximum number of points in a shared bucket in the distributed two-party DP case. We propose an algorithm for this task in Algorithm 1.

17

Algorithm 1 Private Common-Frequency Estimation: APCF Input: Alice holds 𝑆𝐴 = (𝑋 1, . . . , 𝑋𝑛 ) ∈ [𝑚] 𝑛 , Bob holds 𝑆𝐴 = (𝑌1, . . . , 𝑌𝑛 ) ∈ [𝑚] 𝑛 ; parameters 𝜀, 𝛽. Output: estimate 𝑓ˆ of 𝑓 = max𝑘 ∈ [𝑚] min{𝐴𝑘 , 𝐵𝑘 }. 1: 𝑅 ← ⌈4𝑛 2 /𝛽⌉. 2: if 𝑚 ≤ 𝑅 then 3: 𝑔 ← id [𝑚] , 𝑅 ← 𝑚. ⊲ domain already small: no hashing (id [𝑚] is the identity map) 4: else 5: draw 𝑔 : [𝑚] → [𝑅] uniformly at random from public coins. ⊲ public hash ˜ 6: Alice releases 𝐴𝑧 ← {𝑖 : 𝑔(𝑋𝑖 ) = 𝑧} + Lap(2/𝜀) for all 𝑧 ∈ [𝑅]. 7: Bob releases 𝐵˜ 𝑧 ← {𝑖 : 𝑔(𝑌𝑖 ) = 𝑧} + Lap(2/𝜀) for all 𝑧 ∈ [𝑅]. 8: return 𝑓ˆ ← max𝑧 ∈ [𝑅 ] min{𝐴˜𝑧 , 𝐵˜ 𝑧 }. Theorem 3.11 (Private Common-Frequency Estimation). For every 𝑛, 𝑚 ∈ N, 𝜀 > 0, and 𝛽 ∈ (0, 1), Algorithm 1 is an 𝜀-two-party differentially private protocol. of inputs 𝑆𝐴, 𝑆 𝐵 ∈ [𝑚] 𝑛 ,   Moreover, fornevery l pair mo 2 with probability at least 1 − 𝛽, 𝑓b− 𝑓 (𝑆𝐴, 𝑆 𝐵 ) ≤ 𝜀2 ln 4𝑟𝛽 where 𝑟 := min 𝑚, 4𝑛𝛽 . In particular, 

2 /𝛽)  2 log(16𝑛 Pr 𝑓b− 𝑓 (𝑆𝐴, 𝑆 𝐵 ) ≤ ≥ 1 − 𝛽. 𝜀

Proof. For 𝑧 ∈ [𝑟 ], let 𝑔

𝑔

𝐴𝑧 := {𝑖 ∈ [𝑛] : 𝑔(𝑋𝑖 ) = 𝑧} ,

𝐵𝑧 := {𝑖 ∈ [𝑛] : 𝑔(𝑌𝑖 ) = 𝑧} .

We first prove privacy. For every fixed public hash function 𝑔, changing one record changes the e𝑧 )𝑧 ∈ [𝑟 ] corresponding hashed histogram in ℓ1 -distance by at most 2. Thus, by Lemma B.1, Alice’s release (𝐴 e𝑧 )𝑧 ∈ [𝑟 ] is 𝜀-DP in 𝑆 𝐵 . All subsequent computations are post-processing. is 𝜀-DP in 𝑆𝐴 , and Bob’s release (𝐵 Therefore, Bob’s view is 𝜀-DP in 𝑆𝐴 and Alice’s view is 𝜀-DP in 𝑆 𝐵 , as required. It remains to prove accuracy. Let U := supp(𝑆𝐴 ) ∪ supp(𝑆 𝐵 ), and we have |U| ≤ 2𝑛. If 𝑟 = 𝑚, then 𝑔 is the identity. Otherwise, by a union bound,   2𝑛 1 Pr[𝑔 is not injective on U] ≤ 2 𝑟 𝛽 ≤ . 2 On the complementary event, every occupied hash bucket contains records from a single of [𝑚].  element  𝑔 𝑔 4𝑟 2 Consequently, max𝑧 ∈ [𝑟 ] min{𝐴𝑧 , 𝐵𝑧 } = max 𝑗 ∈ [𝑚] min{𝐴 𝑗 , 𝐵 𝑗 } = 𝑓 (𝑆𝐴, 𝑆 𝐵 ). Set 𝜏 := 𝜀 ln 𝛽 . There are 2𝑟 independent Laplace variables, each with scale 2/𝜀. Hence, by Lemma B.1 " #  e𝑧 − 𝐴𝑔𝑧 |, |𝐵 e𝑧 − 𝐵𝑔𝑧 | > 𝜏 ≤ 2𝑟𝑒 −𝜀𝜏/2 = 𝛽 . Pr max max |𝐴 2 𝑧 ∈ [𝑟 ] 𝑔

𝑔

e𝑧 , 𝐵 e𝑧 } − min{𝐴𝑧 , 𝐵𝑧 } ≤ 𝜏 . Taking the maximum On the complementary event, for every 𝑧 ∈ [𝑟 ], min{𝐴 𝑔 𝑔 over 𝑧 therefore gives 𝑓b− max𝑧 ∈ [𝑟 ] min{𝐴𝑧 , 𝐵𝑧 } ≤ 𝜏 . Combining the hashing and noise events proves the stated guarantee. □

18

3.2.3

Main Algorithm

In this section building up on various lemma we proved in the previous two sections, we state the main algorithm and its guarantees. Before, doing it, we discuss a simple baseline that shows why simple idea fails Simple baseline: private interior point. A natural approach is for Alice to privately select a point lying within the range of her witness block and send it to Bob. Bob can then determine whether his witness block lies above or below this point. We show that this idea already solves the promise problem, but at a log(𝑚) cost that our main algorithm improves to log log(𝑚). For 𝜃 ∈ X, define depth𝑆𝐴 (𝜃 ) := min{|{𝑥 ∈ 𝑆𝐴 : 𝑥 ≤ 𝜃 }|, |{𝑥 ∈ 𝑆𝐴 : 𝑥 ≥ 𝜃 }|}. This score has sensitivity one. Moreover,   max𝜃 ∈ X depth𝑆𝐴 (𝜃 ) ≥ 𝑘2 , since every median of 𝑆𝐴 has depth at least ⌈𝑘/2⌉. Alice applies the exponential mechanism with privacy 𝜀 and score depth𝑆𝐴 , and sends the resulting point 𝜃ˆ to Bob. The exponentiallog(2𝑚/𝛽 )

mechanism guarantee implies that, if 𝑘 ≥ 𝐶 , with probability at least 1 − 𝛽/2, for a sufficiently 𝜀 ˆ large universal constant 𝐶, then depth𝑆𝐴 (𝜃 ) > 0 and hence 𝜃ˆ ∈ [min 𝑆𝐴, max 𝑆𝐴 ]. Then, Bob releases e 𝑐 𝐵 := |{𝑥 ∈ 𝑆 𝐵 : 𝑥 < 𝜃ˆ}| + Lap(1/𝜀) and outputs Match if e 𝑐 𝐵 < 𝑘/2 and Far otherwise. It follows that log(2𝑚/𝛽 ) the baseline solves the 𝑡-promise problem for 𝑡 ≥ 𝐶 . The dependence on 𝑚 comes entirely from 𝜀 privately selecting a point from an 𝑚-element domain. As we will see, our main algorithm improves exponentially over this baseline by avoiding this direct selection by searching over a different object. Overview of the Technical Ideas of Our Algorithm. In this section, we provide an overview of the ideas in Algorithm 2. We organize the ordered domain as a binary trie as defined in Definition 3.7. The first step is two perform private private binary search in order to find ℓ ★ = min{ℓ ∈ [𝑏] : 𝐹 (ℓ) ≥ 𝛼 }, where 𝐹 : [𝑏] → N defined as 𝐹 (ℓ) = 𝑛 − max𝑝 ∈ {0,1} ℓ min{𝐴𝑝ℓ , 𝐵𝑝ℓ }. Notice that for every depth ℓ, {𝐴𝑝ℓ }𝑝 ∈ {0,1} ℓ and {𝐵𝑝ℓ }𝑝 ∈ {0,1} ℓ can be seen as a histogram. The straightforward implementation of DP histogram estimation incurs an error of 𝑂 (ℓ/𝜀 0 ) which can be 𝑂 (log(𝑚)/𝜀 0 ). The main observation here is that we only need to estimate max𝑝 ∈ {0,1} ℓ min{𝐴𝑝ℓ , 𝐵𝑝ℓ } without estimating the whole histogram. To do so, we develop Algorithm 1 where the main idea is to use public random hashing to design a distributed algorithm with two-view DP guarantee such that the error due to DP to estimate max𝑝 ∈ {0,1} ℓ min{𝐴𝑝ℓ , 𝐵𝑝ℓ } is independent of the domain size. Once the binary search returns two consecutive depths 𝐿 and 𝐻 , we consider whether the increase from 𝐹 (𝐿) to 𝐹 (𝐻 ) is large or small. For intuition, suppose first that the common nodes at these depths are known. If the increase is large, then many points leave the common node between depths 𝐿 and 𝐻 . Since 𝐻 = 𝐿 + 1, this information is concentrated in a single split, and comparing the numbers of Alice and Bob points in its two children reveals their relative order. To gain intuition behind this case, see Figure 5a. Our algorithm is based on privately finding the orientation of split on Alice and Bob’s side and comparing them. If the increase is small, the information is not concentrated in the final split. Instead, because 𝐹 (𝐻 ) is already above the noise level, sufficiently many points have accumulated outside the common node by depth 𝐻 , while the common node itself remains heavy. Under the Match promise, Alice’s points outside this node lie to its left and Bob’s points lie to its right; under the Far promise, these directions are reversed. To gain intuition see Figure 5b. Thus, comparing the total mass on the two sides reveals the correct answer. The actual implementation is more challenging because the common node depends on the private datasets and cannot be released explicitly; our statistics are designed to recover these two comparisons without identifying it.

19

Algorithm 2 Data Valuation for Threshold: Aval−thr
𝑛
𝑛 Input: Alice holds 𝑆𝐴 = (𝑋 1, . . . , 𝑋𝑛 ) ∈ {0, 1}𝑏 , Bob holds 𝑆𝐴 = (𝑌1, . . . , 𝑌𝑛 ) ∈ {0, 1}𝑏 ; parameters 𝜀, 𝛽. Output: 1: 𝑇 ← ⌈log2 𝑏⌉, 𝜀 0 ← 𝜀/2𝑇 , 𝛽 0 ← 𝛽/2𝑇 ( ) !  4 4𝑛 2 /𝛽 0 28 4 2 ln , ln 2: 𝛼 ← 20 max . 𝜀0 𝛽0 𝜀 𝛽 3: Set 𝐿 ← 0, 𝐻 ← 𝑏, 𝐹b(0) ← 0, and 𝐹b(𝑏) ← 𝑛. ⊲ Initialization of binary search 4: while 𝐻 − 𝐿 > 1 do ⊲ Binary search step 5: ℓ ← ⌊(𝐿 + 𝐻 )/2⌋. 6: Form the prefix datasets

𝑆𝐴ℓ ← Prefixℓ (𝑋 1 ), . . . , Prefixℓ (𝑋𝑛 ) , 𝑆 𝐵ℓ ← Prefixℓ (𝑌1 ), . . . , Prefixℓ (𝑌𝑛 ) . 𝐹b(ℓ) ← 𝑛 − APCF (𝑆𝐴ℓ , 𝑆 𝐵ℓ ; 𝜀 0, 𝛽 0 ). ⊲ See Algorithm 1 8: if 𝐹b(ℓ) < 𝛼 then 9: 𝐿 ← ℓ. 10: else 11: 𝐻 ← ℓ. b b 12: Δ ← 𝐹 (𝐻 ) − 𝐹b(𝐿). 13: if b Δ ≥ 𝛼/2 then ⊲ large-jump case 14: Alice releases n o n o 𝐿 𝐻 𝑉b𝐴 ← max 6|𝐴𝑝𝐿 | + |𝐴𝐻 𝑝0 | − max 6|𝐴𝑝 | + |𝐴𝑝1 | + Lap(28/𝜀). 7:

𝑝 ∈ {0,1} 𝐿

15:

𝑝 ∈ {0,1} 𝐿

Bob releases n

𝑉b𝐵 ←

max

o n o 𝐻 𝐻 6|𝐵𝑝𝐿 | + |𝐵𝑝0 | − max 6|𝐵𝑝𝐿 | + |𝐵𝑝1 | + Lap(28/𝜀).

𝑝 ∈ {0,1} 𝐿

𝑝 ∈ {0,1} 𝐿

16: else 17:

⊲ cumulative-escape case

Alice releases  𝑉b𝐴 ←

max

6|𝐴𝐻 𝑝 |+

𝑝 ∈ {0,1} 𝐻

18:

∑︁

 |𝐴𝑞𝐻 |

 6|𝐴𝐻 𝑝 |+

− max 𝑝 ∈ {0,1} 𝐻

𝑞 ∈ {0,1} 𝐻 𝑞<𝑝

∑︁

 |𝐴𝑞𝐻 |

+ Lap(28/𝜀).

𝑞 ∈ {0,1} 𝐻 𝑞>𝑝

Bob releases  𝑉b𝐵 ←

max 𝑝 ∈ {0,1} 𝐻

6|𝐵𝑝𝐻 | +

∑︁ 𝑞 ∈ {0,1} 𝐻

 |𝐵𝑞𝐻 |

 − max 𝑝 ∈ {0,1} 𝐻

𝑞<𝑝

6|𝐵𝑝𝐻 | +

∑︁ 𝑞 ∈ {0,1} 𝐻 𝑞>𝑝

b𝐴 ≥ 𝑉b𝐵 ; otherwise return Far. 19: return Match if 𝑉

20

 |𝐵𝑞𝐻 |

+ Lap(28/𝜀).

Large-jump case

Alice

A sharp rise between adjacent depths

Small-jump case

Bob

One split carries the signal

The crossing occurs through a small rise

depth

F (ℓ)

Alice

F (ℓ)

Bob

Escaped points accumulate outside the common core ordered buckets at depth H

L α

large ∆

α

···

small ∆

Alice’s escaped points

H L

H

depth ℓ

L

Bob’s escaped points

depth ℓ

H

(a) Large jump case

···

(b) Small jump case

Figure 5: Intuition behind the two-cases of the second stage of Algorithm 2 Theorem 3.12 (Upper bound for thresholds). There exists a universal constant 𝐶 > 0 such that the following holds. Let X ⊆ R be a finite ordered domain with |X| = 𝑚 ≥ 4, let 𝑛 ∈ N, let 𝜀 ∈ (0, 1] and 𝛽 ∈ (0, 1/3], and let 𝑡 ∈ [𝑛] satisfy      log log 𝑚 log log 𝑚 1 log + log 𝑡 ≥𝐶 𝜀 𝛽 𝜀   log log 𝑚 log log 𝑚 Also, assume 𝑛 ≥ 𝐶 𝜀 . Then Aval-thr (in Algorithm 2) is an 𝜀-private tester for Hthr with log 𝛽𝜀 resolution 𝑡 with failure probability at most 𝛽. Proof. The proof has three parts: private binary search, and then, after that we have two cases, large-jump case and cumulative-escape case. Step 1: private binary search. The goal of this step is to approximate ℓ ★ = min{ℓ ∈ [𝑏] : 𝐹 (ℓ) ≥ 𝛼 }. Define the following bad event B𝑏𝑠 = {∃𝑡 ≤ 𝑇 : |𝐹 (ℓ𝑡 ) − 𝐹ˆ (ℓ𝑡 )| ≥ 𝛼/20},

(8)

where {ℓ𝑡 }𝑡 ∈ [𝑇 ] are itself random variable denoting the indices chosen by the private binary search step. Also, 𝑇 = 𝑂 (log(𝑏)) and determinstic. Then, we write Pr(B𝑏𝑠 ) ≤

𝑇 ∑︁

  Pr |𝐹 (ℓ𝑡 ) − 𝐹ˆ (ℓ𝑡 )| ≥ 𝛼/20

𝑡=

≤

𝑇 ∑︁

h  i Eℓ𝑡 Pr |𝐹 (ℓ𝑡 ) − 𝐹ˆ (ℓ𝑡 )| ≥ 𝛼/20 ℓ𝑡

𝑡=

≤ 𝑇 .𝛽 0 ≤ 𝛽. where the first step is due to the union bound, and the second step is by the law of the total probability, then, in the third step, we use the fact that each execution of the APCF uses a fresh randomness independent of the history of the algorithm to obtain the result.

21

Notice that the private binary search maintains 𝐿, 𝐻 such that 𝐻 − 𝐿 = 1 and 𝐹ˆ (𝐿) ≤ 𝛼 ≤ 𝐹ˆ (𝐻 ). Under the 𝑐 , we have event of Bbs 𝛼 21𝛼 𝐹 (𝐿) ≤ 𝐹ˆ (𝐿) + ≤ , 20 20 (9) 19𝛼 𝛼 ≥ . 𝐹 (𝐻 ) ≥ 𝐹ˆ (𝐻 ) − 20 20 𝑐 b Step 2-Case 1: Large Jump. Suppose that Δ ≥ 𝛼/2. Throughout the proof, we assume we are under B𝑏𝑠 𝛼 21𝛼 21𝑛 in Equation (8). First, we have Δ ≥ b Δ − 10 ≥ 2𝛼 5 . Since 𝑛 ≥ 4𝛼, we have 𝐹 (𝐿) ≤ 20 ≤ 80 < 𝑛. Therefore, 𝐿 𝐿 𝐿 𝑛 − 𝐹 (𝐿) > 0, so there is a node 𝑝 ∈ {0, 1} satisfying min |𝐴𝑝 |, |𝐵𝑝 | = 𝑛 − 𝐹 (𝐿). By Lemma 3.8, this is the unique common node at depth 𝐿.

We next show that the maximization used in this case are attained at the common node. We prove correctness when opt Hthr (𝑆𝐴, 𝑆 𝐵 ) = 0; the Far case is symmetric. To show that the argmax is achieved at the common node consider an arbitrary 𝑞 ≠ 𝑝 where 𝑞 ∈ {0, 1}𝐿 . Then, for every 𝑗 ∈ {0, 1}
6|𝐴𝑝 | + |𝐴𝑝 𝑗 | − (6|𝐴𝑞 | + |𝐴𝑞 𝑗 |) = 6 |𝐴𝑝 | − |𝐴𝑞 | + |𝐴𝑝 𝑗 | − |𝐴𝑞 𝑗 | ≥ 6(𝑛 − 𝐹 (𝐿) − 𝐹 (𝐿)) − 𝐹 (𝐿) ≥ 6𝑛 − 13𝐹 (𝐿) 21𝛼 ≥ 6𝑛 − 13 , 20 where the second step is by |𝐴𝑝 | = 𝑛 − 𝐹 (𝐿), |𝐴𝑞 | ≤ 𝐹 (𝐿), |𝐴𝑝 𝑗 | ≥ 0, and |𝐴𝑞 𝑗 | ≤ |𝐴𝑞 | ≤ 𝐹 (𝐿). The last step follows from Equation (9). It shows that assuming 𝑛 ≥ 4𝛼 the last term is positive and hence 𝑝 is argmax. Similarly it holds for Bob’s maximization part. Therefore, n o n o 𝐿 𝐻 𝐻 𝐻 max 6|𝐴𝑝𝐿 | + |𝐴𝐻 | − max 6|𝐴 | + |𝐴 | 𝑝 𝑝0 𝑝1 = |𝐴𝑝0 | − |𝐴𝑝1 |, 𝑝 ∈ {0,1} 𝐿

𝑝 ∈ {0,1} 𝐿

and similarly n max 𝑝 ∈ {0,1} 𝐿

o n o 𝐻 𝐻 𝐻 𝐻 6|𝐵𝑝𝐿 | + |𝐵𝑝0 | − max 6|𝐵𝑝𝐿 | + |𝐵𝑝1 | = |𝐵𝑝0 | − |𝐵𝑝1 |. 𝑝 ∈ {0,1} 𝐿

Under the Match promise, every Alice point is smaller than every Bob point. Therefore, Alice cannot have 𝐻 𝐻 a point in 𝑝1 while Bob has a point in 𝑝0. Equivalently, |𝐴𝐻 𝑝1 | · |𝐵𝑝0 | = 0. Suppose first that |𝐴𝑝1 | = 0; the 𝐻 𝐻 𝐻 case |𝐵𝑝0 | = 0 follows similarly. Since Δ > 0, we must have |𝐴𝑝0 | > |𝐵𝑝0 |. Indeed, otherwise the common frequency would remain |𝐴𝐻 passing from depth 𝐿 to depth 𝐻 , contradicting Δ > 0. Therefore, 𝑝0 | when n o 𝐻 𝐻 𝐻 𝑛 − 𝐹 (𝐿) = min |𝐴𝐻 𝑝0 |, |𝐵𝑝0 | + |𝐵𝑝1 | whereas 𝑛 − 𝐹 (𝐻 ) = |𝐵𝑝0 |. It follows that Δ = 𝐹 (𝐻 ) − 𝐹 (𝐿) n o 𝐻 𝐻 = min |𝐴𝐻 | − |𝐵 |, |𝐵 | 𝑝0 𝑝0 𝑝1 . Consequently, the difference between Alice’s and Bob’s unnoised statistics is     𝐻 𝐻 𝐻 |𝐴𝐻 𝑝0 | − |𝐴𝑝1 | − |𝐵𝑝0 | − |𝐵𝑝1 | 𝐻 𝐻 = |𝐴𝐻 𝑝0 | − |𝐵𝑝0 | + |𝐵𝑝1 | n o 𝐻 𝐻 ≥ 2 min |𝐴𝐻 | − |𝐵 |, |𝐵 | 𝑝0 𝑝0 𝑝1

= 2Δ ≥

4𝛼 . 5 22

𝐻 | = 0 follows symmetrically and gives the same lower bound. Thus, under the Match promise, The case |𝐵𝑝0 the unnoised statistic has positive margin at least 4𝛼/5. The final noise is smaller than this margin under the corresponding good event, and hence the algorithm outputs Match.

Under the Far promise, the order is reversed, and the same argument gives a negative margin of magnitude at least 4𝛼/5. Therefore, the algorithm outputs Far. For the privacy proof, each maximization has sensitivity at most 7, since changing one record changes the term multiplied by 6 by at most 6 and the remaining count by at most 1. Therefore, the difference of the two maximizations has sensitivity at most 14, and allocating privacy budget 𝜀/2 to its release requires noise Lap(14/(𝜀/2)) = Lap(28/𝜀). 𝑐 , we have Δ ≤ b Δ < 𝛼/2. Under Bbs Step 2-Case 2: Cumulative Escape. Suppose that b Δ + 𝛼/10 < 3𝛼/5. Therefore, by Equation (9), 21𝛼 3𝛼 33𝛼 + = . 𝐹 (𝐻 ) = 𝐹 (𝐿) + Δ < 20 5 20 Since 𝑛 ≥ 4𝛼, we have 𝐹 (𝐻 ) < 33𝑛/80 < 𝑛. Therefore, there is a node 𝑝 ∈ {0, 1}𝐻 satisfying 𝐻 min{|𝐴𝐻 𝑝 |, |𝐵𝑝 |} = 𝑛 − 𝐹 (𝐻 ). By Lemma 3.8, this is the unique common node at depth 𝐻 . We next show that the maximizations used in this case are attained at 𝑝. As before, we prove correctness under the Match promise; the Far case follows symmetrically. Consider an arbitrary 𝑞 ∈ {0, 1}𝐻 with 𝑞 ≠ 𝑝. Then   𝐻 𝐻 𝐻 6|𝐴𝐻 | + |𝐴 | − 6|𝐴 | + |𝐴 | 𝑝 <𝑝 𝑞 <𝑞

≥ 6(𝑛 − 𝐹 (𝐻 ) − 𝐹 (𝐻 )) − 𝑛 = 5𝑛 − 12𝐹 (𝐻 ) 33𝑛 𝑛 > 5𝑛 − 12 = > 0. 80 20 𝐻 𝐻 𝐻 𝐻 Here we used |𝐴𝐻 𝑝 | ≥ 𝑛 − 𝐹 (𝐻 ), |𝐴𝑞 | ≤ 𝐹 (𝐻 ), |𝐴 <𝑝 | ≥ 0, and |𝐴 <𝑞 | ≤ 𝑛. The same argument, with 𝐴 >𝑝 𝐻 𝐻 𝐻 and 𝐴 >𝑞 in place of 𝐴 <𝑝 and 𝐴 <𝑞 , shows that the second maximization is also attained at 𝑝. The same conclusion holds for Bob. Therefore,   max 6|𝐴𝑞𝐻 | + |𝐴𝐻<𝑞 | − max 6|𝐴𝑞𝐻 | + |𝐴𝐻>𝑞 | = |𝐴𝐻<𝑝 | − |𝐴𝐻>𝑝 |, 𝑞 ∈ {0,1} 𝐻

𝑞 ∈ {0,1} 𝐻

and similarly, max 𝑞 ∈ {0,1} 𝐻



6|𝐵𝑞𝐻 | + |𝐵 𝐻 <𝑞 | − max



𝐻 𝐻 6|𝐵𝑞𝐻 | + |𝐵 𝐻 >𝑞 | = |𝐵 <𝑝 | − |𝐵 >𝑝 |.

𝑞 ∈ {0,1} 𝐻

Under the Match promise, every Alice point is smaller than every Bob point. Since 𝑝 contains points from both parties, Alice cannot have a point to the right of 𝑝, and Bob cannot have a point to the left of 𝑝. Hence 𝐻 𝐻 |𝐴𝐻>𝑝 | = |𝐵𝐻 <𝑝 | = 0. Moreover, min{|𝐴𝑝 |, |𝐵𝑝 |} = 𝑛 − 𝐹 (𝐻 ) implies  𝐻 max 𝑛 − |𝐴𝐻 𝑝 |, 𝑛 − |𝐵𝑝 | = 𝐹 (𝐻 ). Consequently, the difference between Alice’s and Bob’s unnoised statistics is     𝐻 |𝐴𝐻<𝑝 | − |𝐴𝐻>𝑝 | − |𝐵 𝐻 <𝑝 | − |𝐵 >𝑝 | = |𝐴𝐻<𝑝 | + |𝐵 𝐻 >𝑝 | 19𝛼 ≥ 𝐹 (𝐻 ) ≥ . 20 23

Thus, under the Match promise, the unnoised statistic has positive margin at least 19𝛼/20. The final noise is smaller than this margin under the corresponding good event, and hence the algorithm outputs Match. Under the Far promise, the order is reversed, and the same argument gives a negative margin of magnitude at least 19𝛼/20. Therefore, the algorithm outputs Far. For the privacy proof, each maximization has sensitivity at most 7, since changing one record changes the term multiplied by 6 by at most 6 and the remaining count by at most 1. Therefore, the difference of the two maximizations has sensitivity at most 14, and allocating privacy budget 𝜀/2 to its release requires noise Lap(14/(𝜀/2)) = Lap(28/𝜀). □ Corollary 3.13 (Mixed labels for thresholds). There exists a universal constant 𝐶 > 0 such that the following holds. Let X ⊆ R be a finite ordered domain with |X| = 𝑚 ≥ 4, and suppose that each party 𝑃 ∈ 𝐴, 𝐵 holds Í Í a labeled dataset 𝑆𝑃 ∈ (X × ±1)𝑛 . Define optmix (𝑆 , 𝑆 ) = min𝜃 ∈R 𝑃 ∈ {𝐴,𝐵 } (𝑥,𝑦) ∈𝑆𝑃 1{ℎ𝜃 (𝑥) ≠ 𝑦}. Let Hthr 𝐴 𝐵 𝜀 ∈ (0, 1], 𝛽 ∈ (0, 1/3], and 𝑡 ∈ [𝑛]. If   log log(𝑚 + 2) log log(𝑚 + 2) 𝑡 ≥𝐶 log , 𝜀 𝛽𝜀 then there exists an 𝜀-private tester that distinguishes optmix (𝑆 , 𝑆 ) = 0 from optmix (𝑆 , 𝑆 ) ≥ 𝑡 with failure Hthr 𝐴 𝐵 Hthr 𝐴 𝐵 probability at most 𝛽. Proof. For 𝑃 ∈ 𝐴, 𝐵, let 𝑆𝑃− and 𝑆𝑃+ denote the multisets of negative and positive points held by 𝑃, respectively. For 𝑃, 𝑄 ∈ 𝐴, 𝐵, write 𝑞𝑃𝑄 := opt Hthr (𝑆𝑃− , 𝑆𝑄+ ). We first observe that max 𝑃,𝑄 ∈ {𝐴,𝐵 }

𝑞𝑃𝑄 ≤ optmix Hthr (𝑆𝐴 , 𝑆 𝐵 ) ≤

∑︁

𝑞𝑃𝑄 .

𝑃,𝑄 ∈ {𝐴,𝐵 }

The first inequality holds because each 𝑞𝑃𝑄 optimizes the threshold error over a subset of the pooled records. For the upper bound, for each pair (𝑃, 𝑄), let 𝜃 𝑃𝑄 achieve 𝑞𝑃𝑄 and let 𝐸𝑃𝑄 be the records it misclassifies, so Ð |𝐸𝑃𝑄 | = 𝑞𝑃𝑄 . Set 𝑅 = 𝑃,𝑄 𝐸𝑃𝑄 . Consider any negative point 𝑥 and positive point 𝑦 that do not belong to 𝑅. If 𝑥 ∈ 𝑆𝑃− and 𝑦 ∈ 𝑆𝑄+ , then both points are correctly classified by 𝜃 𝑃𝑄 , and hence 𝑥 < 𝜃 𝑃𝑄 ≤ 𝑦. Therefore, every surviving negative point is smaller than every surviving positive point, so the records outside 𝑅 are Í jointly realizable by a threshold. It follows that optmix (𝑆𝐴, 𝑆 𝐵 ) ≤ |𝑅| ≤ 𝑃,𝑄 𝑞𝑃𝑄 . H thr

Let 𝜏 = ⌈𝑡/4⌉. In the Match case, every 𝑞𝑃𝑄 is zero. In the Far case, the preceding upper bound gives Í 𝑃,𝑄 𝑞 𝑃𝑄 ≥ 𝑡, and hence some 𝑞 𝑃𝑄 is at least 𝜏. We therefore perform four tests and return Far if any of them returns Far. The cross-party quantities 𝑞𝐴𝐵 and 𝑞𝐵𝐴 are tested using Algorithm 2, with Bob playing the negative-holder role in the second execution. To obtain equal-length inputs, fix public points 𝑥 − < min X and 𝑥 + > max X. In a cross-party test, the negative holder replaces every positive record by 𝑥 − , while the positive holder replaces every negative record by 𝑥 + . The resulting datasets have size 𝑛, and their threshold optimum is exactly the corresponding 𝑞𝑃𝑄 . Indeed, an optimal threshold may be chosen in (𝑥 − , 𝑥 + ], in which case all dummy records are classified correctly. This preprocessing is recordwise and therefore maps neighboring labeled datasets to neighboring padded datasets. Notice that the enlarged domain has size 𝑚 + 2. For a same-party quantity 𝑞𝑃𝑃 , replacing one labeled record changes the error of every threshold by at most one, and hence 𝑞𝑃𝑃 has sensitivity one. Party 𝑃 releases 𝑞e𝑃𝑃 := 𝑞𝑃𝑃 + Lap(4/𝜀) and returns Far precisely when 𝑞e𝑃𝑃 ≥ 𝜏/2. This release is 𝜀/4-differentially private and distinguishes 𝑞𝑃𝑃 = 0 from 𝑞𝑃𝑃 ≥ 𝜏 with failure probability at most 𝛽/4, provided that 𝜏 ≥ (8/𝜀) log(4/𝛽). 24

We run the two cross-party testers with parameters (𝜀/4, 𝛽/4) and allocate the same privacy and failure budgets to the two same-party tests. By composition, the resulting protocol is 𝜀-two-party differentially private, and by a union bound its failure probability is at most 𝛽. After increasing the universal constant 𝐶, the assumptions of the corollary ensure that 𝜏 satisfies the conditions of Theorem 3.12 with domain size 𝑚 + 2 and parameters (𝜀/4, 𝛽/4). This proves the result. □

4

Halfspaces in High Dimensions

In this part we focus on the halfspace in high dimensions. More precisely, X ⊆ R𝑑 . Also, without loss of generality, we assume Alice and Bob add a dummy dimension to their datapoints and therefore we can represent the class of halfspaces with Hhs = {ℎ 𝑤 : R𝑑 → {±1} | ∃𝑤 ∈ R𝑑 s.t. ℎ 𝑤 (𝑥) = sign(⟨𝑤, 𝑥⟩)}.

4.1

(10)

Lower bound for half spaces

In this section, we prove an information-theoretic lower bound for Hhs . The argument for the lower bound is rather technical and it involves many steps. We first provide an overview of the proof and defer the formal proof to Appendix in Section D. In this informal overview, we only focus on the case of large 𝑛, i.e., 𝑚𝑑 log(𝑚/𝑑 ) 𝑛 ≥𝐶 to highlight main ideas. With slight modifications, we can extend the lower bound to all 𝜀 values of 𝑛 as shown in Section E and Theorem E.4. 4.1.1

Overview of the lower bound proof.

The proof follows the same template as that of Theorem 3.1. We take a binary predicate with high information complexity and embed it into the promise problem, so that the verdict of the promise problem determines the value of the predicate, and then derive the lower bound from the connection between DP and information complexity from [MMPRTV10]. For half spaces, however, constructing an embedding with a sufficiently large gap is substantially more delicate. Our starting viewpoint is that each of Alice’s and Bob’s data points may be read as a linear constraint on 𝑤 ∈ R𝑑 , namely ⟨𝑤, 𝑥⟩ ≥ 0 or ⟨𝑤, 𝑥⟩ < 0. Viewed in the dual space, the problem therefore becomes a linear program with finitely many constraints: in the Match case the system is feasible, whereas in the Far case it remains infeasible even after removing any 𝑡 − 1 of the constraints. Achieving this robustness in the Far case is the main technical difficulty of the proof, and it is what leads us to use error-correcting codes. Step 1: from inner product in a finite field to LP constraints. Let 𝑠 be an integer determined later and 𝑞 = 2𝑠 . Alice holds a secret 𝑢 ∈ F𝑞𝑘 and Bob holds a secret 𝑣 ∈ F𝑞𝑘 , and they wish to compute 𝐹 (𝑢, 𝑣) =

𝑘 Ê

TrF𝑞 /F2 (𝑢𝑖 𝑣𝑖 ) ∈ {0, 1}.

(11)

𝑖=1

𝐹 can be thought of as the trace of an inner product over F𝑞 . The internal information complexity of computing 𝐹 is Θ(𝑘 log 𝑞); for completeness we provide a proof in Lemma B.6. We now build a linear program whose feasibility decides Equation (11). The main challenge here is that the computation in Equation (11) consists of non-linear components over F𝑞 while we want to convert it to a feasibility problem 25

in R𝑑 . To do so, we embed the 𝑞 elements of F𝑞 as the vertices of a convex polygon 𝑃𝑞 ⊂ R2 lying on a parabola (so each symbol uses two real coordinates) and represent each finite-field relation by the convex hull of its satisfying assignments (for details see Figure 6). The resulting LP constraints come in two kinds: A public family, known to both parties and independent of 𝑢 and 𝑣, performs the computation itself: it holds the variables in the right ranges, forms the 𝑘 trace products, and accumulates their parity, with one last row requiring the parity to be zero. A private family encodes Alice’s and Bob’s secrets: each coordinate of 𝑢 and 𝑣 contributes exactly one constraint, which we call a pin (the naming is inspired by our way of converting elements of F𝑞 into a linear program in Figure 6). Once all 2𝑘 of these are present, the fixed rows propagate the computation and the program is feasible if and only if 𝐹 (𝑢, 𝑣) = 0. We give the details of constructing such a program in Section D. Reading this back through Definition 1.2, we obtain a Match instance whenever 𝐹 (𝑢, 𝑣) = 0 and a Far instance whenever 𝐹 (𝑢, 𝑣) = 1. This feasibility equivalence alone certifies only a Far gap of one. Repeating each linear constraint 𝐿 times guarantees opt Hhs ≥ 𝐿, but the encoding diameter of Lemma 2.2 rises to 2𝑘𝐿. Then, by the connection of the IC and encoding diameter from Lemma 2.2, we obtain only 𝑡 = Ω(log 𝑞/𝜀). The shortcoming of the simple repetition is that the Far gap grows only with the replication 𝐿, while the diameter grows with 𝑘𝐿. Can we instead design a program that is already robust to deleting 𝐷 ≥ 1 of its private pins (i.e., erasing 𝐷 symbols) before any replication? Step 2: turning code robustness into LP rigidity. What we need is that, as long as the public constraints remain enforced, removing fewer than 𝐷 pins still leaves the final answer intact. We therefore encode 𝑢 and 𝑣 using a public systematic linear code with generator 𝐺 = [I𝑘 | 𝐴] ∈ F𝑞𝑘 ×𝐾 where 𝐾 > 𝑘. Let 𝑐 = 𝑢𝐺 and 𝑐 ′ = 𝑣𝐺; since the code is systematic, the first 𝑘 coordinates of 𝑐 and 𝑐 ′ are 𝑢 and 𝑣 themselves, so the trace products of Equation (11) are still formed from these coordinates alone. Three properties are needed from the code and its parity-check representation: constant rate, so that 𝑘 = Θ(𝐾); linear LP-erasure rigidity, meaning the LP tolerates up to 𝐷 = Θ(𝐾) removed pins; and constant check degree, for a reason that will become clear below. The key subtlety is that local parity-check constraints only enforce a convex relaxation of the code, which can admit fractional solutions even when the code has large minimum distance. We therefore use a code whose parity-check graph is a constant-degree unique-neighbor expander [FWK05]: whenever fewer than 𝐷 = Θ(𝐾) pins are removed, any nonempty set of unpinned coordinates has an adjacent check touching it in a single coordinate, whose remaining pinned coordinates force that variable back to its true symbol (Lemma C.2). Thus the public constraints still uniquely force 𝑐 and 𝑐 ′ . Two counts govern the size of the construction, and separating them is what makes a large alphabet affordable. First, since each F𝑞 symbol is embedded in R2 , the program uses 𝑑 LP := 4𝐾 + 2𝑘 + 1 = Θ(𝐾) variables (2𝐾 per codeword, 𝑘 trace, and 𝑘 + 1 parity variables), independent of 𝑞, allowing us to choose 𝐾 = Θ(𝑑). Second, each distinct LP inequality corresponds to a point in the public data space X of size 𝑚. Because each check involves only 2 𝜌 = 𝑂 (1) symbols, its convex hull in R2𝜌 is described by 𝑞𝑂 (𝜌 ) = 𝑞𝑂 (1) inequalities; across all 𝑂 (𝐾) checks and computation gates, this yields at most 𝐶𝐾𝑞𝑎 distinct records for universal constants 𝐶, 𝑎 (replication increases multiplicities, not distinct records). The alphabet therefore costs records but never dimensions, which is what will let us take 𝑞 large. Step 3: producing the Far gap. Converting each LP inequality into a labeled data point, we repeat each private pin 𝐿 times and each public constraint 𝐽 times. When 𝐹 (𝑢, 𝑣) = 0, all constraints are simultaneously satisfiable. When 𝐹 (𝑢, 𝑣) = 1, removing fewer than min{𝐽, 𝐷𝐿} constraints leaves at least one copy of every public constraint intact and removes all 𝐿 copies of fewer than 𝐷 private pins; by Step 2, the remaining LP remains infeasible. Hence 𝐹 (𝑢, 𝑣) = 0 =⇒ opt Hhs (𝑆𝐴, 𝑆 𝐵 ) = 0,

𝐹 (𝑢, 𝑣) = 1 =⇒ opt Hhs (𝑆𝐴, 𝑆 𝐵 ) ≥ min{𝐽, 𝐷𝐿}. 26

For a hypothetical 𝑡-tester, take 𝐽 = ⌈𝑡⌉ and 𝐿 = ⌈𝑡/𝐷⌉, which guarantees a Far gap of at least 𝑡. Since only the 𝐾 private pins depend on each party’s secret, the encoding diameter is Δ𝐴, Δ𝐵 ≤ 𝐾𝐿 = 𝑂 (𝑡 + 𝐾) (as 𝐷 = Θ(𝐾)). The information lower bound and Lemma 2.2 then give
Ω(𝐾 log 𝑞) ≤ 𝑂 𝜀 (𝑡 + 𝐾) , which forces 𝑡 = Ω(𝐾 log 𝑞/𝜀) for sufficiently small 𝜀. Finally, we choose 𝐾 = Θ(𝑑) and the largest power of two 𝑞 satisfying 𝐵𝐾𝑞𝑎 log2 𝑞 ≤ 𝑚/8 for a universal constant 𝐵. This keeps the number of distinct records at 𝑑 log(𝑚/𝑑 )
most 𝑚 and gives log 𝑞 = Θ(log(𝑚/𝑑)), yielding 𝑡 = Ω . Moreover, when 𝑡 = 𝑂 (𝐾 log 𝑞/𝜀), the 𝜀 𝑎 total number of repeated records is 𝑂 (𝐾𝑞 𝐽 + 𝐾𝐿) = 𝑂 (𝑚𝑑/𝜀), which fits within datasets of size 𝑛 ≥ 𝐶𝑚𝑑/𝜀 after padding with input-independent records. Theorem 4.1 (Lower bound for halfspaces). There are universal constants 𝑐, 𝐶, 𝐶 0, 𝜀 0 > 0 and 𝑑 0 ∈ N such that, for every 𝑑, 𝑚 ∈ N with 𝑑 ≥ 𝑑 0 and 𝑚 ≥ 𝐶 0𝑑, there is a public domain X𝑑,𝑚 ⊆ R𝑑 with |X𝑑,𝑚 | = 𝑚 such 𝑚𝑑 log(𝑚/𝑑 ) that for every 0 < 𝜀 ≤ 𝜀 0 , every integer 𝑛 ≥ 𝐶 0 , and every resolution 𝑡 ∈ [𝑛], an 𝜀-private tester for 𝜀 Hhs at dataset size 𝑛 over X𝑑,𝑚 must satisfy 𝑡 ≥𝑐

𝑑 log(𝑚/𝑑) . 𝜀

The domain is chosen independently of 𝑛, 𝑡, 𝜀. Proof. Take the fixed domain from Lemma E.3, and let 𝑅 = Θ(𝑑) be its largest block length. Let 𝐵, 𝑎 be the constants in Lemma E.1. Among powers of two 𝑞 ≥ 2, choose the largest satisfying 𝐵𝑅𝑞𝑎 log2 𝑞 ≤ 𝑚/8.

(12)

For 𝐶 0 sufficiently large, 𝑞 = 2 is admissible. Every such alphabet is included in X𝑑,𝑚 , since 𝑞𝑎 ≤ 𝑚/(8𝐵𝑅). Put 𝑠 = log2 𝑞 ≥ 1. Maximality gives 𝑚 < (2𝑞)𝑎 (𝑠 + 1) ≤ 2𝑎+1𝑞𝑎 𝑠. 8𝐵𝑅 Taking logarithms and using log2 𝑠 ≤ 𝑠 shows that 𝑠 = Ω(log(𝑚/𝑅)) = Ω(log(𝑚/𝑑)). The reverse bound follows from (12) and 𝑅 = Θ(𝑑), so 𝑠 = Θ(log(𝑚/𝑑)). By Lemma E.1, the construction at scale (𝑅, 𝑞) forces 𝑡 ≥ 𝑏𝑅𝑠/𝜀 whenever 𝑛𝜀 ≥ 𝐴𝑅 2𝑞𝑎 𝑠, for universal 𝐴, 𝑏 > 0. The retuned alphabet satisfies 𝐴𝑅 2𝑞𝑎 𝑠 ≤

𝐴 𝑅𝑚 ≤ 𝐶𝑑𝑚 8𝐵

for a sufficiently large universal 𝐶. Thus the assumed sample size suffices, with each dataset padded to exactly 𝑛 as in Lemma E.1. Since 𝑅 = Θ(𝑑) and 𝑠 = Θ(log(𝑚/𝑑)), we obtain the claimed lower bound. □ Remark 4.2. The surprising behavior of this lower bound compared to the optimal gap for thresholds in Theorems 3.1 and 3.12 is that the dependence on 𝑚 is exponentially larger, i.e., log log(𝑚) for threshold and log(𝑚) for half spaces. Also, 𝑡 exhibits (at least) a linear dependence on 𝑑. ⊳

27

4.2

Algorithm for Half Spaces

4.2.1

Structural Results and Tools

As our lower bound in Theorem 4.1 shows we need to assume that X = {𝑥 1, . . . , 𝑥𝑚 } ⊂ R𝑑 is a finite set. Let |X| = 𝑚. Towards developing our algorithm, we mainly focus on the dual space: consider the dual space denoted by W = R𝑑 where we map each ℎ 𝑤 ∈ Hhs to 𝑤 ∈ R𝑑 . The cardinality of W is unbounded. However, we only need to consider the projection of X using Hhs , which means that two 𝑤 ∼ 𝑤 ′ are equivalent if and only if the predictions of ℎ 𝑤 and ℎ 𝑤 ′ over X be the same. The next lemma shows that considering this equivalent class, we can reduce W to a discrete set. The proof is an application of Sauer–Shelah lemma [Sau72; She72]. Lemma 4.3 (Finite dual discretization). Let X = {𝑥 1, . . . , 𝑥𝑚 } ⊆ R𝑑 . There exists a finite set Wdisc ⊆ R𝑑 such that, for every 𝑤 ∈ R𝑑 , some 𝑤 ′ ∈ Wdisc satisfies ℎ 𝑤 (𝑥𝑖 ) = ℎ 𝑤 ′ (𝑥𝑖 ) for every 𝑖 ∈ [𝑚]. Moreover, |Wdisc | ≤ (2𝑚)𝑑 . For each 𝑤 ∈ Wdisc , define the local error of ℎ on Alice and Bob datasets as ∑︁ ∑︁ 𝑓𝐴 (𝑤) = 1{ℎ 𝑤 (𝑥) ≠ −1} 𝑓𝐵 (𝑤) = 1{ℎ 𝑤 (𝑥) ≠ 1}, 𝑥 ∈𝑆𝐴

𝑥 ∈𝑆 𝐵

and using this notation, we have opt Hhs = min𝑤 ∈ Wdisc {𝑓𝐴 (𝑤) + 𝑓𝐵 (𝑤)}. For every 𝑘 ∈ [𝑛], we also define the set of local low-error classifiers on Alice and Bob’s side as 𝐺𝐴𝑘 = {𝑤 ∈ Wdisc : 𝑓𝐴 (𝑤) ≤ 𝑘 }

𝐺 𝐵𝑘 = {𝑤 ∈ Wdisc : 𝑓𝐵 (𝑤) ≤ 𝑘 }.

Note that 𝐺𝐴𝑘 and 𝐺 𝐵𝑘 as sets live in the dual space. Also, since Wdisc is a finite set, these sets are generally non-convex in R𝑑 . However, when we consider the convex hull of them, we have an important property. Lemma 4.4. Fix 𝑛, 𝑑 ∈ N, datasets 𝑆𝐴, 𝑆 𝐵 ∈ X𝑛 , and 𝑡 ∈ [𝑛]. Suppose that opt Hhs (𝑆𝐴, 𝑆 𝐵 ) ≥ 𝑡. Then, for every 𝑡 −1 , we have conv(𝐺𝐴𝑘 ) ∩ conv(𝐺 𝐵𝑘 ) = ∅. 𝑘 ∈ N0 satisfying 𝑘 ≤ 2(𝑑+1) Proof. Suppose toward a contradiction that there exists 𝑣 ∈ conv(𝐺𝐴𝑘 ) ∩ conv(𝐺 𝐵𝑘 ). By Carathéodory’s theorem Lemma B.3, there exist 𝑎 1, . . . , 𝑎𝑟 ∈ 𝐺𝐴𝑘 , where 𝑟 ≤ 𝑑 + 1, such that 𝑣 is a convex combination of 𝑎 1, . . . , 𝑎𝑟 . If 𝑣 misclassifies a point in 𝑆𝐴 , then at least one 𝑎𝑖 also misclassifies that point. Consequently, 𝑓𝐴 (𝑣) ≤

𝑟 ∑︁

𝑓𝐴 (𝑎𝑖 ) ≤ (𝑑 + 1)𝑘.

𝑖=1

Applying the same argument to a representation of 𝑣 as a convex combination of at most 𝑑 + 1 points from 𝐺 𝐵𝑘 gives 𝑓𝐵 (𝑣) ≤ (𝑑 + 1)𝑘. Therefore, 𝑓𝐴 (𝑣) + 𝑓𝐵 (𝑣) ≤ 2(𝑑 + 1)𝑘 ≤ 𝑡 − 1, contradicting opt Hhs (𝑆𝐴, 𝑆 𝐵 ) ≥ 𝑡.

□

Our algorithm employes a geometric tool that is called container. It is a special case of the cover where we also assume that the cover includes the set. We use the following result from [BKMS19; DGM22].

28

Lemma 4.5 (Halfspace containers [BKMS19; DGM22]). There exists a universal constant 𝑐 > 0 such that the following holds. For every finite set S ⊆ R𝑑 and every 𝜂 ∈ (0, 1), there exists a family C(S, 𝜂) ⊆ 2 S satisfying   𝑐𝑑 |C(S, 𝜂)| ≤ 𝜂2 . Moreover, for every affine halfspace 𝐻 ⊆ R𝑑 , there exists 𝐶 ∈ C(S, 𝜂) such that 𝐻 ∩S ⊆𝐶

and

|𝐶 \ 𝐻 | ≤ 𝜂|S|.

Remark 4.6. An special case of Lemma 4.5 that will be used in the sequel is as follows: consider a half space whose positive region is less than the whole space, i.e., |𝐻 ∩ S| ≤ |S|/2. Then, from |𝐶 \ 𝐻 |, we have |𝐶 \ 𝐻 | = |𝐶 | − |𝐻 ∩ S| ≥ |𝐶 | − | S2 | . Therefore, we have |𝐶 | ≤ ( 12 + 𝜂)|𝑆 |. ⊳ 4.2.2

Main Algorithm

In this section, we present the algorithm for half spaces. We begin with providing an overview of the technical ideas. Overview of the algorithm. Our algorithm is a private elimination procedure over the finite dual space Wdisc . At round 𝑟 , the parties maintain a public set W𝑟 of candidate halfspaces and attempt to replace it by a substantially smaller set. Ideally, a party would find a halfspace in the dual space that contains all of its low-error candidates but at most half of W𝑟 . Such a halfspace defines a safe cut, but the family of possible halfspaces is too large to search privately. The container lemma in Lemma 4.5 replaces these halfspace cuts by a small public family: whenever such a halfspace exists, the family contains a set covering it and containing at most 3|W𝑟 |/4 candidates. For 𝑃 ∈ {𝐴, 𝐵}, let 𝐺 𝑃𝑘 (W𝑟 ) denote the candidates in W𝑟 with local error at most 𝑘. We assign each container a low-sensitivity cost measuring the quality of the best halfspace candidate it excludes; its cost is zero exactly when it contains all of 𝐺 𝑃𝑘 (W𝑟 ). Alice and Bob can therefore use the exponential mechanism to privately search the public container family for a safe shrinking cut. The high level goal is as follows: The two promise cases interact with this mechanism in opposite ways, and the stopping rule reads off which occurred: a Match instance keeps W𝑟 nonempty forever, while a Far instance is driven to W𝑟 = ∅ within log(|Wdisc |) rounds, thanks to Lemma 4.3 that shows |Wdisc | is finite. Far case. By Lemma 4.4, conv(𝐺𝐴𝑘 (W𝑟 )) and conv(𝐺 𝐵𝑘 (W𝑟 )) are disjoint. A separating hyperplane therefore places one party’s low-error region in a halfspace containing at most half of W𝑟 . By Lemma 4.5, that party has a zero-cost real container of size at most 3|W𝑟 |/4 in the public menu. On a high-probability good event that we define later, each party selects a real container, not necessarily the particular zero-cost one. Since every real member of the menu has size at most 3|W𝑟 |/4, the active set shrinks by a constant factor. See Figure 4. Match case. Here the mechanism above can fail: the two low-error regions may overlap and be scattered across W𝑟 , so neither is guaranteed to lie in a halfspace holding at most half the candidates. We therefore add a dummy action ⊥ to the menu, which proposes no cut and lets a party abstain when no safe container exists; both parties abstaining is the protocol’s signal to output Match. The cost of ⊥ is fixed at 𝑘/2, wedged between the cost of a safe container (0) and that of any container excluding a consistent classifier (≥ 𝑘 + 1). This calibration makes abstention the preferred move exactly when no safe cut exists. Concretely, fix a classifier ℎ★ consistent with both datasets. On a high probability event, that we define in the proof, each party either selects ⊥ or selects a real container that still contains 𝑤 ★, since any container excluding 𝑤 ★ costs at least 𝑘 + 1 > 𝑘/2. If both select ⊥ the protocol outputs Match; otherwise 𝑤 ★ survives into W𝑟 +1 . If

29

the protocol reachs the log(|Wdisc | step, then the resulting active set is not empty since it contains 𝑤 ★. See Figure 4. Algorithm 3 Data Valuation for Half Spaces: Aval−hs Input: Alice holds 𝑆𝐴 ∈ X𝑛 , Bob holds 𝑆 𝐵 ∈ X𝑛 ; parameters 𝜀, 𝛽. Output: Far or Match. 1: W0 ← Wdisc   2: 𝑄 ← log4/3 |Wdisc | + 2   2𝑄 2𝑄 𝑐𝑑 3: 𝛼 ← ln(8 + 1) + ln 𝛽 𝜀  𝑡 −1 4: 𝑘 ← 2(𝑑 + 1) 5: 𝜀 0 ← 𝜀/𝑄. 6: for 𝑟 = 0, . . . , 𝑄 − 1 do
7: Construct container family C W𝑟 , 41 and define the public menu   3 1
|𝐶 | ≤ |W𝑟 | ∪ {⊥}. R𝑟 = 𝐶 ∈ C W𝑟 , 4 4

⊲ 𝑐 is a universal constant. ⊲ see Lemma 4.4.

⊲ See Lemma 4.5 8:

9:

10:

For 𝑃 ∈ {𝐴, 𝐵} and 𝐶 ∈ W𝑟 , define
   max 𝑘 + 1 − 𝑓𝑃 (ℎ) +, 𝐶 ≠ ⊥,  𝑞𝑃,W𝑟 (𝐶; 𝑆𝑃 ) ← ℎ∈ W𝑟 \𝐶 𝑘  𝐶 = ⊥,  2,   Alice samples 𝐶𝐴,𝑟 ∼ EM 𝑞𝐴,W𝑟 , R𝑟 , 𝑆𝐴, 𝜀 0 and releases it.   Bob samples 𝐶𝐵,𝑟 ∼ EM 𝑞𝐵,W𝑟 , R𝑟 , 𝑆 𝐵 , 𝜀 0 and releases it.

⊲ See Lemma B.4 ⊲ See Lemma B.4

if 𝐶𝐴,𝑟 = 𝐶𝐵,𝑟 = ⊥ then return Match 13: if 𝐶𝐴,𝑟 ≠ ⊥ then 14: W𝑟 +1 ← 𝐶𝐴,𝑟 15: else if 𝐶𝐴,𝑟 = ⊥ and 𝐶𝐵,𝑟 ≠ ⊥ then 16: W𝑟 +1 ← 𝐶𝐵,𝑟 17: return Far if W𝑄 = ∅; otherwise return Match. 11: 12:

Theorem 4.7. Let 𝑐 be a universal constant. Fix a finite data space X ⊆ R𝑑 with |X| = 𝑚, and let 𝜀 ∈ (0, 1], 𝛽 ∈ (0, 1), and 𝑡 ∈ [𝑛]. Let  2   𝑑 log(2𝑚) 𝑑 log(2𝑚) 𝑡 ≥𝑐 𝑑 + log . 𝜀 𝛽 then Aval−hs in Algorithm 3 is an 𝜀-private tester for the 𝑡-promise problem over Hhs with success probability at least 1 − 𝛽. Proof. The privacy proof is straightforward: in each round, Alice and Bob use exponential mechanism with 𝜀 0 . The maximum number of rounds is 𝑄, therefore, the composition theorem of pure-DP shows that the output satisfies 𝜀 two-view DP. Next we turn to the utility proof. 30

First, we define an event and then the rest of the analysis is based on assuming the event holds. For 𝑃 ∈ {𝐴, 𝐵} and 𝑟 ∈ {0, . . . , 𝑄 − 1}, lets define an event that shows the protocol reaches round 𝑟 and the exponential mechanism is accurate. More precisely, (

)

B𝑃,𝑟 := {𝑟 < 𝑇 } ∩ 𝑞𝑃,W𝑟 (𝐶𝑃,𝑟 ; 𝑆𝑃 ) − min 𝑞𝑃,W𝑟 (𝐶; 𝑆𝑃 ) > 𝛼 . 𝐶 ∈ R𝑟

Then define G :=

𝑄 −1  Ù

 𝑐 𝑐 B𝐴,𝑟 ∩ B𝐵,𝑟 .

(13)

𝑟 =0

Thus, on G, every exponential-mechanism call that is actually executed has additive cost error at most 𝛼.
It Í𝑄 −1 is easy to see that by the union bound and Lemma B.4, we have Pr(G𝑐 ) ≤ 𝑟 =0 Pr(B𝐴,𝑟 ) + Pr(B𝐵,𝑟 ) ≤ 𝛽 2𝑄 · 2𝑄 = 𝛽. For the rest of the proof, we assume G holds. Case 1: Far holds. We first assume that opt Hhs (𝑆𝐴, 𝑆 𝐵 ) ≥ 𝑡. Consider any round 𝑟 reached by the protocol with W𝑟 ≠ ∅. Since 𝑘 = ⌊(𝑡 − 1)/(2(𝑑 + 1))⌋, Lemma 4.4 gives conv(𝐺𝐴𝑘 (W𝑟 )) ∩ conv(𝐺 𝐵𝑘 (W𝑟 )) = ∅. If both low-error sets are nonempty, strict separation gives opposite affine halfspaces containing conv(𝐺𝐴𝑘 (W𝑟 )) and conv(𝐺 𝐵𝑘 (W𝑟 )), respectively. We may perturb the separating hyperplane so that its boundary avoids the finite set W𝑟 . The two halfspaces then partition W𝑟 , and one contains at most |W𝑟 |/2 points. Thus, for some 𝑃 ∈ {𝐴, 𝐵}, there is an affine halfspace 𝐻 such that 𝐺 𝑃𝑘 (W𝑟 ) ⊆ 𝐻 ∩ W𝑟 and |𝐻 ∩ W𝑟 | ≤ |W𝑟 |/2. By Lemma 4.5, there is a container 𝐶 ★ ∈ C(W𝑟 , 1/4) containing 𝐻 ∩ W𝑟 and satisfying |𝐶 ★ | ≤ 3|W𝑟 |/4. Hence 𝐶 ★ ∈ R𝑟 , 𝐺 𝑃𝑘 (W𝑟 ) ⊆ 𝐶 ★, and therefore 𝑞𝑃,W𝑟 (𝐶 ★; 𝑆𝑃 ) = 0. On the event G, the container released by party 𝑃 consequently satisfies 𝑞𝑃,W𝑟 (𝐶𝑃𝑟 ; 𝑆𝑃 ) ≤ 𝛼. Since 𝑞𝑃,W𝑟 (⊥; 𝑆𝑃 ) = 𝑘/2 > 𝛼, it follows that 𝐶𝑃,𝑟 ≠ ⊥. Thus, the protocol cannot return Match in this round. The protocol therefore either returns Far because the active set is empty or replaces W𝑟 by a real member of R𝑟 . In the latter case, |𝑊𝑟 +1 | ≤ 3|W𝑟 |/4. Consequently, if the protocol completes all 𝑄 rounds, then |𝑊𝑄 | ≤ (3/4)𝑄 |𝑊0 | < 1, where the last inequality follows from 𝑄 = ⌈log4/3 |𝑊0 |⌉ + 2. Since 𝑊𝑄 is finite, we must have 𝑊𝑄 = ∅, and the protocol returns Far. Case 2: Match holds. Assume that opt Hhs (𝑆𝐴, 𝑆 𝐵 ) = 0, and fix 𝑤 ★ ∈ 𝑊0 such that 𝑓𝐴 (𝑤 ★) = 𝑓𝐵 (𝑤 ★) = 0. We claim that if the protocol reaches round 𝑟 without having already returned Match, then 𝑤 ★ ∈ W𝑟 . The claim holds initially because 𝑊0 = Hhs . Suppose that 𝑤 ★ ∈ W𝑟 . For each 𝑃 ∈ {𝐴, 𝐵}, since ⊥ ∈ R𝑟 and 𝑞𝑃,W𝑟 (⊥; 𝑆𝑃 ) = 𝑘/2, the event G implies that 𝑞𝑃,W𝑟 (𝐶𝑃𝑟 ; 𝑆𝑃 ) ≤ 𝑘/2 + 𝛼 ≤ 𝑘 − 1, where the last inequality follows from 𝑘 ≥ 2𝛼 + 2. However, every real container 𝐶 ∈ R𝑟 excluding 𝑤 ★ has 𝑞𝑃,W𝑟 (𝐶; 𝑆𝑃 ) ≥ (𝑘 + 1 − 𝑓𝑃 (ℎ★))+ = 𝑘 + 1. Thus, every real container released by either party contains 𝑤 ★. If both parties release ⊥, the protocol correctly returns Match. Otherwise, 𝑊𝑟 +1 is one of the released real containers and therefore contains 𝑤 ★. This proves the claim by induction. Consequently, the active set never becomes empty. If the protocol does not terminate earlier, then 𝑤 ★ ∈ 𝑊𝑄 , and the protocol returns Match after the final round. Combining the two cases, the protocol is correct whenever G holds. Since Pr(G) ≥ 1 − 𝛽, its success probability is at least 1 − 𝛽. □

31

Corollary 4.8 (Mixed labels for halfspaces). Let 𝑐 be the universal constant in Theorem 4.7. Fix a finite data space X ⊆ R𝑑 with |X| = 𝑚, and suppose that each party 𝑃 ∈ 𝐴, 𝐵 holds a labeled dataset 𝑆𝑃 ∈ (X × ±1)𝑛 . Í Í Define optmix (𝑆 , 𝑆 ) := min𝑤 ∈R𝑑 𝑃 ∈ {𝐴,𝐵 } (𝑥,𝑦) ∈𝑆𝑃 1{ℎ 𝑤 (𝑥) ≠ 𝑦}. Let 𝜀 ∈ (0, 1], 𝛽 ∈ (0, 1), and 𝑡 ∈ [𝑛]. Hhs 𝐴 𝐵 If   𝑑 log(2𝑚) 𝑑 2 log(2𝑚) 𝑑 + log , 𝑡 ≥𝑐 𝜀 𝛽 Í then Algorithm 3, after redefining the local error as 𝑓𝑃 (𝑤) := (𝑥,𝑦) ∈𝑆𝑃 1{ℎ 𝑤 (𝑥) ≠ 𝑦}, is an 𝜀-private tester that distinguishes optmix (𝑆𝐴, 𝑆 𝐵 ) = 0 from optmix (𝑆𝐴, 𝑆 𝐵 ) ≥ 𝑡 with success probability at least 1 − 𝛽. H H hs

hs

Proof. The finite dual discretization is unchanged, since it depends only on the predictions over X. Redefine 𝐺 𝑃𝑘 (W) := 𝑤 ∈ W : 𝑓𝑃 (𝑤) ≤ 𝑘. To verify Lemma 4.4, suppose that 𝑣 ∈ conv(𝐺𝐴𝑘 (W)) ∩conv(𝐺 𝐵𝑘 (W)). By Í Carath’eodory’s theorem, write 𝑣 = 𝑟𝑖=1 𝜆𝑖 𝑎𝑖 for some 𝑟 ≤ 𝑑 + 1 and 𝑎 1, . . . , 𝑎𝑟 ∈ 𝐺𝐴𝑘 (W). If ℎ 𝑣 misclassifies Í a labeled record, then at least one ℎ𝑎𝑖 also misclassifies it. Therefore, 𝑓𝐴 (𝑣) ≤ 𝑟𝑖=1 𝑓𝐴 (𝑎𝑖 ) ≤ (𝑑 + 1)𝑘. The same argument gives 𝑓𝐵 (𝑣) ≤ (𝑑 + 1)𝑘, and hence, for 𝑘 = ⌊(𝑡 − 1)/(2(𝑑 + 1))⌋, optmix Hhs (𝑆𝐴 , 𝑆 𝐵 ) ≤ 𝑓𝐴 (𝑣) + 𝑓𝐵 (𝑣) ≤ 2(𝑑 + 1)𝑘 ≤ 𝑡 − 1, contradicting the Far assumption. Thus, the utility proof of Theorem 4.7 applies unchanged. Finally, replacing one labeled record changes 𝑓𝑃 (𝑤) by at most one for every 𝑤, so 𝑞𝑃,W (𝐶; 𝑆𝑃 ) retains sensitivity one. Therefore, the same exponential-mechanism and composition arguments give 𝜀-two-party differential privacy. □ 4.2.3

Complementary bounds for small data regime

An interesting aspect of the guarantee in Theorem 4.7 is that 𝑡 does not depend on the dataset size 𝑛. 𝑑 3 log(𝑚) However, the cost of such a result is that we need 𝑛 ≥ 𝑂˜ . In this section, we show that when 𝑛 is 𝜀 small, there are simple algorithms that extend the private tester to almost all non-trivial dataset sizes. A tester with 𝑡 = 𝑛. In this section, we give a simple algorithm to show that, as long as 𝑛 ≳ 1/𝜀 2 , we can design a tester that achieves 𝑡 = 𝑛. Note that this is the largest resolution one can ask for: classifier 𝑤 = 0 labels every point as positive and makes exactly 𝑛 mistakes, and therefore opt Hhs (𝑆𝐴, 𝑆 𝐵 ) ≤ 𝑛 for all datasets. The starting point is a simple characterization of when opt Hhs (𝑆𝐴, 𝑆 𝐵 ) = 𝑛. Note that we assume the homogeneous halfspaces in Equation (10) without a bias term. For 𝑥 ≠ 0, let 𝑅(𝑥) = {𝜆𝑥 : 𝜆 > 0} denote the ray through 𝑥, and let R = {𝑅(𝑥) : 𝑥 ∈ X} be the set of rays that contain at least one point of the domain. Since the domain is finite, this set is well-defined. Notice that R is public. For every 𝑅 ∈ R, let 𝑎𝑅 and 𝑏 𝑅 denote the number of Alice’s and Bob’s records that lie on 𝑅, respectively. The main observation is that a homogeneous halfspace assigns the same label to all the points on a ray. Using this observation, it is straightforward to see that opt Hhs (𝑆𝐴, 𝑆 𝐵 ) = 𝑛 ⇐⇒ 𝑎𝑅 = 𝑏 𝑅 for all 𝑅 ∈ R, opt Hhs (𝑆𝐴, 𝑆 𝐵 ) = 0 =⇒ 𝑎𝑅𝑏 𝑅 = 0 for all 𝑅 ∈ R.

32

(14)

In other words, in the Far case Alice and Bob have exactly the same histogram over the rays, while in the Match case their histograms have disjoint supports. Therefore, at 𝑡 = 𝑛 the testing problem reduces to checking whether two histograms over R are identical, and this can be done using shared randomness as we show in Algorithm 4. The next theorem summarize the privacy and utility guarantee of this tester. Algorithm 4 Testing at Resolution 𝑡 = 𝑛 for Half Spaces: Amax−hs Input: Alice holds 𝑆𝐴 = (𝑋 1, . . . , 𝑋𝑛 ) ∈ X𝑛 , Bob holds 𝑆 𝐵 = (𝑌1, . . . , 𝑌𝑛 ) ∈ X𝑛 ; parameter 𝜀. Output: Far or Match. √ 1: Let 𝑘 be a large enough constant, and set 𝜏 ← 𝑛/2. 2: Draw independent and uniform signs 𝜎 𝑗,𝑅 ∈ {±1} for 𝑗 ∈ [𝑘] and 𝑅 ∈ R. ⊲ public randomness 3: Alice computes 𝑎𝑅 ← |{𝑖 ∈ [𝑛] : 𝑋𝑖 ∈ 𝑅}| for every 𝑅 ∈ R, and releases ∑︁ 𝑍𝐴,𝑗 ← 𝜎 𝑗,𝑅 𝑎𝑅 + Lap(2𝑘/𝜀) for all 𝑗 ∈ [𝑘]. 𝑅∈R

4: Bob computes 𝑏 𝑅 ← |{𝑖 ∈ [𝑛] : 𝑌𝑖 ∈ 𝑅}| for every 𝑅 ∈ R, and releases

𝑍 𝐵,𝑗 ←

∑︁

𝜎 𝑗,𝑅 𝑏 𝑅 + Lap(2𝑘/𝜀)

for all 𝑗 ∈ [𝑘].

𝑅∈R

5: if max 𝑗 ∈ [𝑘 ] |𝑍𝐴,𝑗 − 𝑍 𝐵,𝑗 | > 𝜏 then 6:

return Match

7: else 8:

return Far

Theorem 4.9. There exists a universal constant 𝐶 > 0 such that the following holds. Fix a finite data space X ⊆ R𝑑 \ {0} and 𝜀 > 0, and let 𝑛 ≥ 𝐶/𝜀 2 . Then there exists a non-interactive algorithm (presented in Algorithm 4) that is 𝜀-private tester with resolution 𝑡 = 𝑛 for Hhs . Remark 4.10 (Mixed labels). Our tester at resolution 𝑡 = 𝑛 also applies when each agent holds both positive and negative examples. We retain the assumption that X ⊆ R𝑑 \ {0}, and write 𝑁 − for the total number of negatively labeled records across the two datasets. Unlike the disjoint-label setting, this number need not equal 𝑛. We first observe that the all-positive classifier makes exactly 𝑁 − mistakes. Thus, in the Far case, we must have 𝑁 − ≥ 𝑛. This suggests a simple first step: each agent releases a noisy count of its negative records, and the agents add these counts. If 𝑁 − < 𝑛/2, this already distinguishes the input from Far, using the threshold 3𝑛/4. It remains to handle the case in which there are at least 𝑛/2 negative records. For this case, we modify the random signs used by the tester. Independently for each line through the origin meeting X, we assign a random sign to one ray and the opposite sign to the other. Let 𝜎𝑅 denote the sign assigned to ray 𝑅. Each agent 𝑃 releases a noisy version of ∑︁ 𝑍𝑃 = 𝑦 𝜎𝑅 (𝑥 ) , (𝑥,𝑦) ∈𝑆𝑃

and the agents add their releases. Thus, the contribution of a record depends on both its ray and its label. The main observation is that these contributions cancel in the Far case. Indeed, when opt = 𝑛, every normal orthogonal to no domain point gives exactly 𝑛 errors. Moving the normal across the hyperplane perpendicular to one line shows that the positive-label count minus the negative-label count must agree on its two rays. Since these rays receive opposite signs, their contributions sum to zero.

33

In the Match case, consider a line containing a negative record. A classifier realizing the pooled data must place all negative records on this line on one ray and all positive records on the opposite ray. Consequently, multiplying by the labels makes all contributions from this line have the same sign. Since the signs on different lines are independent, the pooled sketch has variance at least 𝑁 − ≥ 𝑛/2. The same moment √ argument as before therefore gives a sketch of magnitude at least 𝑛/2 with constant probability. We repeat the sketch a constant number of times. Replacing one labeled record changes each sketch by at most two and the negative-label count by at most one, so Laplace noise of scale 𝑂 (1/𝜀) suffices for privacy. Combining the count test with the sketches gives an 𝜀-private tester whenever 𝑛 ≥ 𝐶/𝜀 2 , for 0 < 𝜀 ≤ 1 and a universal constant 𝐶, independently of 𝑑 and 𝑚. ⊳ A tester using private synthetic data generation. A simple application of the mechanism in [BLR13] gives a complementary bound with a better dependence on the dimension. The idea is to have each party privately release a small synthetic dataset that approximates its empirical error for every halfspace. Then, using it, we can approximate opt. Theorem 4.11 (Halfspace testing via the BLR net mechanism). There exists a universal constant 𝐶 > 0 such that the following holds. Fix 𝑑 ≥ 1, 𝑚, 𝑛 ∈ N, and 𝜀 ∈ (0, 1]. For every public data space X ⊆ R𝑑 with |X| = 𝑚 and every 𝑡 ∈ [𝑛] satisfying  2  1/3 𝑛 𝑑 log(2𝑚) 𝑡 ≥𝐶 , (15) 𝜀 there exists a non-interactive, randomized, 𝜀-two-party DP tester for Hhs with resolution 𝑡. 𝑑 log(2𝑚)
1/3 Remark 4.12. At first glance, the dependence on 𝑑, log 𝑚, and 1/𝜀 in Theorem 4.11 scales as , 𝜀 𝑑 log(𝑚/𝑑 )
which might appear to contradict our lower bound of 𝑡 = Ω from Theorem 4.1. However, there 𝜀 is no contradiction because the bound in Equation (15) also depends on 𝑛 and can be written as a weighted 𝑑 log(2𝑚) geometric mean of 𝑛 and : 𝜀

 2  1/3   1/3 𝑛 𝑑 log(2𝑚) 2/3 𝑑 log(2𝑚) =𝑛 . 𝜀 𝜀 Recall that any non-trivial tester requires 𝑡 ≤ 𝑛 (since opt Hhs (𝑆𝐴, 𝑆 𝐵 ) ≤ 𝑛 holds trivially for all datasets of size 𝑛). For the right-hand side of Equation (15) to be at most 𝑛, we must have 𝑛 ≳ 𝑑 log(2𝑚) the geometric mean always lies between and 𝑛, namely 𝜀

𝑑 log(2𝑚) . In this regime, 𝜀

 2  1/3 𝑑 log(2𝑚) 𝑛 𝑑 log(2𝑚) ≲ ≤ 𝑛. 𝜀 𝜀 𝑑 log(2𝑚)

Conversely, when 𝑛 ≪ , the right-hand side of Equation (15) exceeds 𝑛, so the range of admissible 𝜀 𝑡 ∈ [𝑛] in Theorem 4.11 is empty. Thus, whenever Theorem 4.11 is non-vacuous, its resolution 𝑡 is always consistent with Theorem 4.1. ⊳

Acknowledgment Mahdi Haghifam would like to thank Alireza Fallah and Adam Smith for discussions on this project.

34

AI Disclosure GPT-5 and GPT-6 were used to explore ideas for proving lower bound for halfspaces in Theorem 4.1. Authors also used AI tools for generating the figures in the paper as well as polishing, editing, and proof-reading.

References [ALZK23]

H. J. Asghar, Z. Lu, Z. Zhao, and D. Kaafar. “Practical, private assurance of the value of collaboration via fully homomorphic encryption”. arXiv preprint arXiv:2310.02563 (2023).

[BBBY12]

M.-F. Balcan, E. Blais, A. Blum, and L. Yang. “Active property testing”. In: 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science. IEEE. 2012, pp. 21–30.

[BBFM12]

M. F. Balcan, A. Blum, S. Fine, and Y. Mansour. “Distributed learning, communication complexity and privacy”. In: Conference on Learning Theory. JMLR Workshop and Conference Proceedings. 2012, pp. 26–1.

[BBL03]

O. Bousquet, S. Boucheron, and G. Lugosi. “Introduction to statistical learning theory”. In: Summer school on machine learning. Springer, 2003, pp. 169–207.

[BH18]

A. Blum and L. Hu. “Active tolerant testing”. In: Conference On Learning Theory. PMLR. 2018, pp. 474–497.

[BKMS19]

M. Braverman, G. Kol, S. Moran, and R. R. Saxena. “Convex set disjointness, distributed learning of halfspaces, and LP feasibility”. arXiv preprint arXiv:1909.03547 (2019).

[BLR13]

A. Blum, K. Ligett, and A. Roth. “A learning theory approach to noninteractive database privacy”. Journal of the ACM (JACM) 60.2 (2013), pp. 1–25.

[BNO08]

A. Beimel, K. Nissim, and E. Omri. “Distributed private data analysis: Simultaneously solving how and what”. In: Annual International Cryptology Conference. Springer. 2008, pp. 451–468.

[BNS13]

A. Beimel, K. Nissim, and U. Stemmer. “Private learning and sanitization: Pure vs. approximate differential privacy”. In: International Workshop on Approximation Algorithms for Combinatorial Optimization. Springer. 2013, pp. 363–378.

[BW11]

M. Braverman and O. Weinstein. “A Discrepancy Lower Bound for Information Complexity”. CoRR abs/1112.2000 (2011).

[Car07]

C. Carathéodory. “Über den Variabilitätsbereich der Koeffiziente von Kraftwerkreihen, die gegebene Werte nicht nehmen”. Mathematical Annals 64.1 (1907), pp. 95–115.

[CBC16]

S.-T. Chen, M.-F. Balcan, and D. H. Chau. “Communication efficient distributed agnostic boosting”. In: Artificial Intelligence and Statistics. PMLR. 2016, pp. 1299– 1307.

[CH23]

K. Chang and H. Huang. “Exploring the management of multi-sectoral cybersecurity information-sharing networks”. Government Information Quarterly 40.4 (2023), p. 101870.

35

[CPP23]

R. B. Christensen, S. R. Pandey, and P. Popovski. “Semi-Private Computation of Data Similarity with Applications to Data Valuation and Pricing”. IEEE Transactions on Information Forensics and Security 18 (2023), pp. 1978–1988.

[CZPR23]

R. Compton, L. Zhang, A. Puli, and R. Ranganath. “When More is Less: Incorporating Additional Datasets Can Hurt Performance By Introducing Spurious Correlations”. In: Proceedings of the 8th Machine Learning for Healthcare Conference. Vol. 219. Proceedings of Machine Learning Research. PMLR, 2023, pp. 110–127.

[DGM22]

K. Dutta, A. Ghosh, and S. Moran. “Uniform Brackets, Containers, and Combinatorial Macbeath Regions”. In: 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Ed. by M. Braverman. Vol. 215. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022, 59:1–59:10. isbn: 978-3-95977-217-4.

[DMNS06]

C. Dwork, F. McSherry, K. Nissim, and A. Smith. “Calibrating noise to sensitivity in private data analysis”. In: Theory of cryptography conference. Springer. 2006, pp. 265–284.

[FMSSW07]

J. Feldman, T. Malkin, R. A. Servedio, C. Stein, and M. J. Wainwright. “LP decoding corrects a constant fraction of errors”. IEEE Transactions on Information Theory 53.1 (2007), pp. 82–89.

[FSBG09]

M. F. Flanagan, V. Skachek, E. Byrne, and M. Greferath. “Linear-programming decoding of nonbinary linear codes”. IEEE Transactions on Information Theory 55.9 (2009), pp. 4134–4154.

[FWC26]

Y. Fu, T. Wang, and V. Chandrasekaran. “Challenges in Enabling Private Data Valuation”. arXiv preprint arXiv:2603.00342 (2026).

[FWK05]

J. Feldman, M. J. Wainwright, and D. R. Karger. “Using linear programming to decode binary linear codes”. IEEE Transactions on Information Theory 51.3 (2005), pp. 954–972.

[FX14]

V. Feldman and D. Xiao. “Sample complexity bounds on differentially private learning via communication complexity”. In: Conference on Learning Theory. PMLR. 2014, pp. 1000–1019.

[FXC25]

K. Fuentes, M. Xu, and I. Y. Chen. “Dataset-to-Dataset Evaluation Before (and Without) Sharing Data”. In: Proceedings of the AAAI/ACM Conference on AI, Ethics, and Society. Vol. 8. 1. 2025, pp. 963–977.

[GBRRDJM11]

J. A. de Groot, P. M. Bossuyt, J. B. Reitsma, A. W. Rutjes, N. Dendukuri, K. J. Janssen, and K. G. Moons. “Verification problems in diagnostic accuracy studies: consequences and solutions”. Bmj 343 (2011).

[GHVLP24]

F. Garrido-Lucero, B. Heymann, M. Vono, P. Loiseau, and V. Perchet. “DU-Shapley: A Shapley Value Proxy for Efficient Dataset Valuation”. In: Advances in Neural Information Processing Systems. Vol. 37. 2024.

[GZ19]

A. Ghorbani and J. Zou. “Data Shapley: Equitable Valuation of Data for Machine Learning”. In: Proceedings of the 36th International Conference on Machine Learning. Vol. 97. Proceedings of Machine Learning Research. PMLR, 2019, pp. 2242–2251.

36

[JDWHHGLZSS19]

R. Jia, D. Dao, B. Wang, F. A. Hubis, N. Hynes, N. M. Gürel, B. Li, C. Zhang, D. Song, and C. J. Spanos. “Towards Efficient Data Valuation Based on the Shapley Value”. In: Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics. Vol. 89. Proceedings of Machine Learning Research. PMLR, 2019, pp. 1167–1176.

[JMMC24]

T. Jahani-Nezhad, P. Moradi, M. A. Maddah-Ali, and G. Caire. “Private, Augmentation-Robust and Task-Agnostic Data Valuation Approach for Data Marketplace”. arXiv preprint arXiv:2411.00745 (2024).

[KCG24]

J.-C. Klie, R. E. d. Castilho, and I. Gurevych. “Analyzing dataset annotation quality management in the wild”. Computational Linguistics 50.3 (2024), pp. 817–866.

[KL17]

P. W. Koh and P. Liang. “Understanding Black-box Predictions via Influence Functions”. In: Proceedings of the 34th International Conference on Machine Learning. Vol. 70. Proceedings of Machine Learning Research. PMLR, 2017, pp. 1885–1894.

[KLMY19]

D. Kane, R. Livni, S. Moran, and A. Yehudayoff. “On communication complexity of classification problems”. In: Conference on Learning Theory. PMLR. 2019, pp. 1903– 1943.

[KNOW14]

P. Kothari, A. Nayyeri, R. O’Donnell, and C. Wu. “Testing surface area”. In: Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms. SIAM. 2014, pp. 1204–1214.

[KR00]

M. Kearns and D. Ron. “Testing Problems with Sublearning Sample Complexity”. Journal of Computer and System Sciences 61.3 (2000), pp. 428–456.

[KV18]

W. Kong and G. Valiant. “Estimating learnability in the sublinear data regime”. Advances in Neural Information Processing Systems 31 (2018).

[LASLBKHOTRM17]

C. D. Lehman, R. F. Arao, B. L. Sprague, J. M. Lee, D. S. M. Buist, K. Kerlikowske, L. M. Henderson, T. Onega, A. N. A. Tosteson, G. H. Rauscher, and D. L. Miglioretti. “National Performance Benchmarks for Modern Screening Digital Mammography: Update from the Breast Cancer Surveillance Consortium”. Radiology 283.1 (2017), pp. 49–58.

[McM70]

P. McMullen. “The maximum numbers of faces of a convex polytope”. Mathematika 17.2 (1970), pp. 179–184.

[MMPRTV10]

A. McGregor, I. Mironov, T. Pitassi, O. Reingold, K. Talwar, and S. Vadhan. “The Limits of Two-Party Differential Privacy”. In: Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science. 2010, pp. 81–90.

[MT07]

F. McSherry and K. Talwar. “Mechanism design via differential privacy”. In: 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07). IEEE. 2007, pp. 94–103.

[NKBYBS20]

P. Nakkiran, G. Kaplun, Y. Bansal, T. Yang, B. Barak, and I. Sutskever. “Deep Double Descent: Where Bigger Models and More Data Hurt”. In: International Conference on Learning Representations. 2020.

[PKFZ26]

K. K. Patel, S. P. Karimireddy, R. C. Fernandez, and M. Zampetakis. “Limits and Potential of Score-Based Data Valuation: Redundancy, Complementarity, and NonMonotonicity”. In: Advances in Neural Information Processing Systems. Accepted. 2026.

37

[RU08]

T. Richardson and R. Urbanke. Modern Coding Theory. Cambridge: Cambridge University Press, 2008.

[RY20]

A. Rao and A. Yehudayoff. Communication Complexity and Applications. Cambridge University Press, 2020.

[SAMHBORLTKLB17] B. L. Sprague, R. F. Arao, D. L. Miglioretti, L. M. Henderson, D. S. M. Buist, T. Onega, G. H. Rauscher, J. M. Lee, A. N. A. Tosteson, K. Kerlikowske, C. D. Lehman, and Breast Cancer Surveillance Consortium. “National Performance Benchmarks for Modern Diagnostic Digital Mammography: Update from the Breast Cancer Surveillance Consortium”. Radiology 283.1 (2017), pp. 59–69. [Sau72]

N. Sauer. “On the density of families of sets”. Journal of Combinatorial Theory, Series A 13.1 (1972), pp. 145–147.

[She72]

S. Shelah. “A combinatorial problem; stability and order for models and theories in infinitary languages”. Pacific Journal of Mathematics 41.1 (1972), pp. 247–261.

[TLLCJKLR22]

Z. Tian, J. Liu, J. Li, X. Cao, R. Jia, J. Kong, M. Liu, and K. Ren. “Private Data Valuation and Fair Payment in Data Marketplaces”. arXiv preprint arXiv:2210.08723 (2022).

[Vio15]

E. Viola. “The communication complexity of addition”. Combinatorica 35.6 (2015), pp. 703–747.

[WYZKJ24]

J. T. Wang, T. Yang, J. Zou, Y. Kwon, and R. Jia. “Rethinking Data Shapley for Data Selection Tasks: Misleads and Merits”. In: Proceedings of the 41st International Conference on Machine Learning. Vol. 235. Proceedings of Machine Learning Research. PMLR, 2024, pp. 52033–52063.

[WZWJM23]

J. T. Wang, Y. Zhu, Y.-X. Wang, R. Jia, and P. Mittal. “A Privacy-Friendly Approach to Data Valuation”. In: Advances in Neural Information Processing Systems. Vol. 36. 2023.

[XHV22]

X. Xu, A. Hannun, and L. Van Der Maaten. “Data appraisal without data sharing”. In: International Conference on Artificial Intelligence and Statistics. PMLR. 2022, pp. 11422–11437.

38

A

On the in-population error induced by OPT

The joint empirical loss opt H can be directly linked to an in-distribution loss. Suppose the agents want to minimize the loss with respect to a target distribution 𝑃 ∈ Δ(X × {±1}). We define the minimal population error on this distribution for a hypothesis class H as follows: 𝑅 ∗H (𝑃) := inf

Pr

ℎ∈ H (𝑋 ,𝑌 )∼𝑃

[ℎ(𝑋 ) ≠ 𝑌 ].

(16)

Clearly, if the agents require target population error at most 𝜏 ∈ (0, 1), then 𝑅 ∗H (𝑃) > 𝜏 implies that no shared classifier in H , including the Empirical Risk Minimizer (ERM) on their joint data, can satisfy them. In the following remark, we highlight how distinguishing between the conditions on opt H in (2) allows us to detect a large 𝑅 ∗H (𝑃), and vice-versa under distributional assumptions on 𝑆𝐴, 𝑆 𝐵 . Remark A.1 (Independently sampled training datasets). Suppose each agent’s dataset consists of 𝑛 i.i.d. samples from its population distribution 𝑃𝐴, 𝑃𝐵 ∈ Δ(X × {±1}), respectively, and the two datasets are ∗ 𝐵 independent. Define the minimal average population error by 𝑅 H := 𝑅 ∗H ( 𝑃𝐴 +𝑃 2 ). Let 𝑣 := VC(H ) and assume 1 ≤ 𝑣 ≤ 𝑛. Applying relative VC uniform convergence [BBL03, Thm. 7] separately to the two datasets gives, with probability at least 1 − 𝛿, √︄   opt H (𝑆𝐴, 𝑆 𝐵 ) opt H (𝑆𝐴, 𝑆 𝐵 ) ∗ ∗ − 𝑅 H ≤ 𝜂𝑛 min , 𝑅 H + 𝜂𝑛 , 2𝑛 2𝑛 where 𝜂𝑛 := 𝐶 (𝑣 log(𝑒𝑛/𝑣) + log(1/𝛿))/𝑛 for a sufficiently large universal constant 𝐶. Thus, the joint empirical loss bounds the minimal average population error from both above and below. In particular, for any ∗ √ 𝜏 ∈ (0, 1), on this event, opt H (𝑆𝐴, 𝑆 𝐵 ) > 2𝑛(𝜏 + 𝜏𝜂𝑛 +𝜂𝑛 ) implies 𝑅 H > 𝜏, ruling out any shared classifier in √ H with average population error at most 𝜏 across 𝑃𝐴 and 𝑃𝐵 . Conversely, opt H (𝑆𝐴, 𝑆 𝐵 ) ≤ 2𝑛(𝜏 − 𝜏𝜂𝑛 − 𝜂𝑛 ) ∗ ∗ implies 𝑅 H ≤ 𝜏. In particular, zero joint empirical loss implies 𝑅 H ≤ 𝜂𝑛 on the same event. Thus, under independent sampling, the joint empirical loss opt H (𝑆𝐴, 𝑆 𝐵 ) characterizes the minimal average population ∗ ∗ ∗ 𝐵 error 𝑅 H and importantly, when the target distribution satisfies 𝑃 = 𝑃𝐴 +𝑃 2 , we have 𝑅 H = 𝑅 H (𝑃), so this remark directly relates the joint empirical loss to the minimal target population error. ⊳ We go back to our running examples and apply Remark A.1 to demonstrate how, in real applications, a large joint empirical loss opt H (𝑆𝐴, 𝑆 𝐵 ) certifies that 𝑅 ∗H > 𝜏 with high probability. Example 3 (Learning from disparate label sets). Remember that Alice’s labels are all −1, and Bob’s are all +1, but their data otherwise follow the target distribution conditioned on the label. Formally, let 𝑃𝐴 := 𝑃 · |𝑦=−1 and 𝑃𝐵 := 𝑃 · |𝑦=1 , and suppose 𝑆𝐴 ∼ 𝑃𝐴𝑛 and 𝑆 𝐵 ∼ 𝑃𝐵𝑛 independently. If both labels have equal probability under 𝑃, then 12 (𝑃𝐴 + 𝑃𝐵 ) = 𝑃. By Remark A.1, with probability at least 1 − 𝛿, opt H (𝑆𝐴, 𝑆 𝐵 ) = 0 implies 𝑅 ∗H (𝑃) ≤ 𝜂𝑛 , whereas opt H (𝑆𝐴, 𝑆 𝐵 ) > 𝑡 implies 𝑅 ∗H (𝑃) > 𝑡/(2𝑛) − 𝜂𝑛 . Thus, the joint empirical loss allows the agents to conclude whether a shared classifier in H can achieve low target error. Example 4 (Identifying conflicting labeling practices). Remember that the agents encounter the same distribution of emails but may assign different labels to the same email. Let 𝐷 denote their common feature distribution and 𝑓𝐴, 𝑓𝐵 ∈ H their deterministic labeling functions, so each task is individually realizable. Let 𝑃𝐴 and 𝑃𝐵 be the distributions of (𝑋, 𝑓𝐴 (𝑋 )) and (𝑋, 𝑓𝐵 (𝑋 )), respectively, for 𝑋 ∼ 𝐷. We take the target distribution to be 𝑃 = 12 (𝑃𝐴 + 𝑃𝐵 ), a symmetric choice that gives the two agents’ test errors equal weight. Suppose 𝑆𝐴 ∼ 𝑃𝐴𝑛 and 𝑆 𝐵 ∼ 𝑃𝐵𝑛 independently. By Remark A.1, with probability at least 1 − 𝛿, opt H (𝑆𝐴, 𝑆 𝐵 ) = 0 implies that a shared classifier in H can achieve test error at most 𝜂𝑛 under 𝑃, whereas opt H (𝑆𝐴, 𝑆 𝐵 ) > 2𝑛(𝜏 + 𝜂𝑛 ) rules out any shared classifier in H with test error at most 𝜏 under 𝑃. 39

B

Helper Lemma

Lemma B.1 (Laplace mechanism [DMNS06]). Let 𝑓 : X𝑛 → R𝑑 be a vector-valued function with ℓ1 -sensitivity at most Δ, meaning ∥ 𝑓 (𝑋 ) − 𝑓 (𝑋 ′ ) ∥ 1 ≤ Δ for all neighboring 𝑋, 𝑋 ′ , i.e., two 𝑋, 𝑋 ′ ∈ X𝑛 that differ only in a single element. The mechanism 𝑓˜(𝑋 ) = 𝑓 (𝑋 ) + 𝑍 , where 𝑍 ∼ (Lap(Δ/𝜀)) ⊗𝑑 , is 𝑒𝑝𝑠𝑖𝑙𝑜𝑛-DP. Here Lap(𝑏) denotes the mean-zero Laplace distribution with density (2𝑏) −1𝑒 − |𝑧 |/𝑏 . Moreover, for every 𝑋 ∈ X𝑛 and  𝛽 ∈ (0, 1], we have Pr | 𝑓˜(𝑋 ) − 𝑓 (𝑋 )| ≥ Δ𝜀 log(1/𝛽) ≤ 𝛽. Lemma B.2 (A constant-degree expander [RU08]). There are universal constants 𝛿 > 0 and 𝐾0 ∈ N such that, for every even 𝐾 ≥ 𝐾0 , there is a simple bipartite graph with 𝐾 variable nodes of degree four and 𝐾/2 check nodes of degree eight satisfying |Γ(𝑇 )| > 2|𝑇 |

whenever ∅ ≠ 𝑇 ⊆ [𝐾] and |𝑇 | < 𝛿𝐾 .

Here Γ(𝑇 ) is the set of checks adjacent to 𝑇 . Consequently, every such 𝑇 has a check adjacent to exactly one of its variables. Lemma B.3 (Carathéodory’s theorem [Car07]). Let X ⊆ R𝑑 . Every point 𝑥 ∈ conv(X) can be written as a convex combination of at most 𝑑 + 1 points of X. That is for every 𝑥 ∈ conv(X), there exist 𝑛 ≤ 𝑑 + 1, points Í Í 𝑥 1, . . . , 𝑥𝑛 ∈ X, and coefficients 𝜆1, . . . , 𝜆𝑛 ≥ 0 with 𝑛𝑖=1 𝜆𝑖 = 1 such that 𝑥 = 𝑛𝑖=1 𝜆𝑖 𝑥𝑖 . Lemma B.4 (Exponential mechanism [MT07]). Let R be a finite output space, and let 𝑞 : X★ × R → R be a cost function with sensitivity at most Δ > 0; that is, for every pair of neighboring datasets 𝑆, 𝑆 ′ ′, 𝑟 )| ≤ Δ. The exponential mechanism outputs 𝑟 ∈ R with probability and every 𝑟 ∈ R, |𝑞(𝑆,𝑟 ) − 𝑞(𝑆  Pr[EM(𝑆) = 𝑟 ] = Í

exp −

𝜀𝑞 (𝑆,𝑟 ) 2Δ



𝑟 ′ ∈R exp −

 𝜀𝑞 (𝑆,𝑟 ′ ) 2Δ

. Then EM is 𝜀-DP. Moreover, for every 𝛽 ∈ (0, 1), with probability at least

1 − 𝛽,   1 2Δ ln |R| + ln . 𝑞 𝑆, Mexp (𝑆) ≤ min 𝑞(𝑆, 𝑟 ) + 𝜀 𝛽 𝑟 ∈R

Lemma B.5 (From LP constraints to halfspace datasets). Fix 𝑝, 𝑀 ∈ N. Let R = {𝑎𝑖⊤𝑥 ≤ 𝑏𝑖 }𝑖 ∈ [𝑀 ] be a finite set of linear constraints on 𝑥 ∈ R𝑝 . There exists a constant 𝜂 > 0, depending only on R, with the following property. For each 𝑖 ∈ [𝑀], define the points 𝑥𝑖− := (𝑎𝑖 , −𝑏𝑖 − 𝜂) ∈ R𝑝+1

and

𝑥𝑖+ := (−𝑎𝑖 , 𝑏𝑖 ) ∈ R𝑝+1,

together with 𝑥 0− := −𝑒𝑝+1 and 𝑥 0+ := 𝑒𝑝+1 in R𝑝+1 . Then for any subsets 𝐼𝐴, 𝐼𝐵 ⊆ [𝑀], if we form the datasets 𝑆𝐴 := {𝑥𝑖− : 𝑖 ∈ 𝐼𝐴 } ∪ {𝑥 0− }

and

𝑆 𝐵 := {𝑥𝑖+ : 𝑖 ∈ 𝐼𝐵 } ∪ {𝑥 0+ },

the linear system {𝑎𝑖⊤𝑥 ≤ 𝑏𝑖 : 𝑖 ∈ 𝐼𝐴 ∪ 𝐼𝐵 } is feasible in R𝑝 if and only if opt Hhs (𝑆𝐴, 𝑆 𝐵 ) = 0 (that is, there exists ℎ 𝑤 ∈ Hhs such that ℎ 𝑤 (𝑥) = −1 for all 𝑥 ∈ 𝑆𝐴 and ℎ 𝑤 (𝑥) = +1 for all 𝑥 ∈ 𝑆 𝐵 ). Proof. We first choose 𝜂 > 0 depending only on R. For each subset 𝑇 ⊆ [𝑀] such that {𝑎𝑖⊤𝑥 ≤ 𝑏𝑖 : 𝑖 ∈ 𝑇 } Í Í is infeasible, Farkas’ lemma gives a vector 𝑦𝑇 ∈ R𝑇≥0 with 𝑖 ∈𝑇 (𝑦𝑇 )𝑖 = 1, 𝑖 ∈𝑇 (𝑦𝑇 )𝑖 𝑎𝑖 = 0, and Í 𝛾𝑇 := − 𝑖 ∈𝑇 (𝑦𝑇 )𝑖 𝑏𝑖 > 0. Since [𝑀] has only finitely many subsets, we may choose 𝜂 > 0 smaller than min{𝛾𝑇 : 𝑇 ⊆ [𝑀] is infeasible} (or 𝜂 = 1 if every subset is feasible). Now fix any 𝐼𝐴, 𝐼𝐵 ⊆ [𝑀] and let 𝑆 := 𝐼𝐴 ∪ 𝐼𝐵 . Suppose first that there exists 𝑥 ∈ R𝑝 satisfying 𝑎𝑖⊤𝑥 ≤ 𝑏𝑖 for all 𝑖 ∈ 𝑆, and consider ℎ 𝑤 ∈ Hhs with 𝑤 = (𝑥, 1) ∈ R𝑝+1 . Then 𝑤, 𝑥 0− = −1 < 0, 𝑤, 𝑥 0+ = 1 ≥ 0, and for every 𝑖 ∈ 𝐼𝐴 and 𝑗 ∈ 𝐼𝐵 , 𝑤, 𝑥𝑖− = 𝑎𝑖⊤𝑥 − 𝑏𝑖 − 𝜂 ≤ −𝜂 < 0, 40

𝑤, 𝑥 +𝑗 = −𝑎 ⊤𝑗 𝑥 + 𝑏 𝑗 ≥ 0.

Hence ℎ 𝑤 (𝑥) = −1 for all 𝑥 ∈ 𝑆𝐴 and ℎ 𝑤 (𝑥) = +1 for all 𝑥 ∈ 𝑆 𝐵 , so opt Hhs (𝑆𝐴, 𝑆 𝐵 ) = 0. Conversely, suppose opt Hhs (𝑆𝐴, 𝑆 𝐵 ) = 0, and let 𝑤 = (𝑣, 𝜆) ∈ R𝑝 × R be such that ℎ 𝑤 (𝑥) = −1 for all 𝑥 ∈ 𝑆𝐴 and ℎ 𝑤 (𝑥) = +1 for all 𝑥 ∈ 𝑆 𝐵 . Since 𝑥 0− ∈ 𝑆𝐴 , we have 𝑤, 𝑥 0− = −𝜆 < 0, so 𝜆 > 0. Setting 𝑥˜ := 𝑣/𝜆 ∈ R𝑝 , the conditions D E 𝑤, 𝑥𝑖− < 0 for 𝑖 ∈ 𝐼𝐴 and 𝑤, 𝑥 +𝑗 ≥ 0 for 𝑗 ∈ 𝐼𝐵 divide by 𝜆 > 0 to yield 𝑎𝑖⊤𝑥˜ < 𝑏𝑖 + 𝜂

(∀𝑖 ∈ 𝐼𝐴 )

and

𝑎 ⊤𝑗 𝑥˜ ≤ 𝑏 𝑗

(∀𝑗 ∈ 𝐼𝐵 ).

In particular, 𝑎𝑖⊤𝑥˜ ≤ 𝑏𝑖 +𝜂 for all 𝑖 ∈ 𝑆. By our choice of 𝜂, the system {𝑎𝑖⊤𝑥 ≤ 𝑏𝑖 : 𝑖 ∈ 𝑆 } cannot be infeasible, since otherwise ∑︁ ∑︁ 0= (𝑦𝑆 )𝑖 𝑎𝑖⊤𝑥˜ ≤ (𝑦𝑆 )𝑖 (𝑏𝑖 + 𝜂) = −𝛾𝑆 + 𝜂 < 0, 𝑖 ∈𝑆

𝑖 ∈𝑆

a contradiction. Thus {𝑎𝑖⊤𝑥 ≤ 𝑏𝑖 : 𝑖 ∈ 𝐼𝐴 ∪ 𝐼𝐵 } is feasible in R𝑝 .

□

Lemma B.6 (Information complexity of the trace inner product). Let 𝑞 = 2𝑠 , and let 𝜇 be the uniform product É𝑘 distribution over F𝑞𝑘 × F𝑞𝑘 . For 𝐹 (𝑢, 𝑣) = 𝑖=1 TrF𝑞 /F2 (𝑢𝑖 𝑣𝑖 ),, we have IC𝜇,1/10 (𝐹 ) = Ω(𝑘 log 𝑞). Proof. The trace pairing (𝑎, 𝑏) ↦→ TrF𝑞 /F2 (𝑎𝑏) is nondegenerate. Therefore, there exist dual F2 -bases {𝛼 1, . . . , 𝛼𝑠 } and {𝛽 1, . . . , 𝛽𝑠 } of F𝑞 satisfying TrF𝑞 /F2 (𝛼𝑟 𝛽 ℓ ) = 1{𝑟 = ℓ }. Write 𝑢𝑖 =

Í𝑠

𝑟 =1 𝑥𝑖,𝑟 𝛼𝑟 , 𝑣 𝑖 =

Í𝑠

𝑟 =1 𝑦𝑖,𝑟 𝛽𝑟 where , 𝑥𝑖,𝑟 , 𝑦𝑖,𝑟 ∈ F2 . Then

TrF𝑞 /F2 (𝑢𝑖 𝑣𝑖 ) =

𝑠 Ê

𝑥𝑖,𝑟 𝑦𝑖,𝑟 ,

𝑟 =1

and consequently 𝐹 (𝑢, 𝑣) =

É𝑘 É𝑠 𝑖=1

𝑟 =1 𝑥𝑖,𝑟 𝑦𝑖,𝑟 = IP𝑘𝑠 (𝑥, 𝑦).

The changes of basis are bijections, so under 𝜇, the corresponding 𝑥, 𝑦 ∈ {0, 1}𝑘𝑠 are independent and uniform. Moreover, any protocol for 𝐹 induces a protocol for IP𝑘𝑠 with the same error and the same internal information cost. It is folklore that binary inner product on 𝑁 independent uniform bits has constant-error internal information complexity Ω(𝑁 ). Therefore, IC𝜇,1/10 (𝐹 ) = Ω(𝑘𝑠) = Ω(𝑘 log 𝑞). □

C

Embedding a codeword into an LP

In this section, we develop the machinery that turns a pair of codewords into an instance of the promise problem. Recall from Section 4.1.1 that each data point imposes one linear constraint on 𝑤, so that opt Hhs = 0 means the resulting system is feasible, while opt Hhs ≥ 𝑡 means it remains infeasible even after removing any 𝑡 − 1 constraints. Our goal is therefore a linear program whose feasibility encodes the value of a hard function, and in which each private symbol contributes exactly one inequality. Our representation is based on the fundamental-polytope approach from the literature on LP decoding of linear codes [FWK05; FSBG09]. In that approach, each row of a parity-check matrix is represented by the convex hull of its satisfying local assignments, and the resulting local polytopes are intersected to obtain an LP relaxation of the code. We adapt this machinery in two ways. First, we represent every symbol of F𝑞 as an exposed vertex of a two-dimensional polygon, rather than using the standard indicator representation. Second, we interpret the symbol-selecting inequalities as private data records and the parity-check inequalities as public records. 41

The function we want to compute. Fix the public parity-check matrix 𝐻 ∈ F𝑞𝑀 ×𝐾 with 𝑀 = 𝐾/2, retaining all its rows, and let C𝐻 = {𝑐 ∈ F𝑞𝐾 : 𝐻𝑐 ⊤ = 0} have dimension 𝑘. We assume that the code is systematic, i.e., the first 𝑘 coordinates carry the message and the remaining 𝐾 − 𝑘 are determined by the checks. Alice holds a codeword 𝑐 ∈ C𝐻 , Bob holds a codeword 𝑐 ′ ∈ C𝐻 , and they wish to compute Ê 𝐹 (𝑐, 𝑐 ′ ) = Tr(𝑐𝑖 𝑐𝑖′ ) ∈ {0, 1}, 𝑖 ∈ [𝑘 ]

where Tr denotes the trace from F𝑞 to F2 . The computation has three parts: each party’s input must be a genuine codeword, that is, satisfy every parity check of 𝐻 ; for every message coordinate 𝑖 ∈ [𝑘], the bit Tr(𝑐𝑖 𝑐𝑖′ ) must be computed from the pair (𝑐𝑖 , 𝑐𝑖′ ); and these 𝑘 bits must be combined by parity. We then plant a public condition on the output, namely that the resulting parity equals zero. Feasibility of the whole system is then equivalent to 𝐹 (𝑐, 𝑐 ′ ) = 0. Encoding a field element. Fix an enumeration F𝑞 = {𝛼 0, . . . , 𝛼𝑞−1 } and set 𝑒 (𝛼 𝑗 ) := ( 𝑗, 𝑗 2 ) ∈ R2 . To represent a field-valued variable we introduce a pair of real variables 𝑧𝑖 = (𝑧𝑖(1) , 𝑧𝑖(2) ) and impose the public constraint 𝑧𝑖 ∈ 𝑃𝑞 , where 𝑃𝑞 is the convex hull of the 𝑞 points 𝑒 (𝛼 0 ), . . . , 𝑒 (𝛼𝑞−1 ). Since these points lie on a parabola, they are in convex position, and 𝑃𝑞 is described by 0 ≤ 𝑧𝑖(1) ≤ 𝑞 − 1,

𝑧𝑖(2) ≤ (𝑞 − 1) 𝑧𝑖(1) ,

𝑧𝑖(2) ≥ (2𝑗 + 1) 𝑧𝑖(1) − 𝑗 ( 𝑗 + 1) for 𝑗 = 0, . . . , 𝑞 − 2.

See Figure 6. This constraint says only that 𝑧𝑖 is some mixture of field elements. The private input supplies one further inequality that selects a particular vertex. Lemma C.1 (Pinning a field element). Let ℓ 𝑗 (𝑢, 𝑣) := 2𝑗𝑢 − 𝑣. Then for every 𝑠 ∈ {0, . . . , 𝑞 − 1},
ℓ 𝑗 𝑒 (𝛼𝑠 ) = 2𝑗𝑠 − 𝑠 2 = 𝑗 2 − (𝑠 − 𝑗) 2 ≤ 𝑗 2, with equality if and only if 𝑠 = 𝑗. Consequently, the constraints 𝑧𝑖 ∈ 𝑃𝑞 and ℓ 𝑗 (𝑧𝑖 ) ≥ 𝑗 2 together force 𝑧𝑖 = 𝑒 (𝛼 𝑗 ). Proof. The displayed identity is immediate. Since 𝑧𝑖 ∈ 𝑃𝑞 , we may write 𝑧𝑖 = Í 𝑠 𝜆𝑠 = 1. As ℓ 𝑗 is linear, ∑︁ ∑︁
ℓ 𝑗 (𝑧𝑖 ) = 𝜆𝑠 ℓ 𝑗 𝑒 (𝛼𝑠 ) = 𝑗 2 − 𝜆𝑠 (𝑠 − 𝑗) 2 . 𝑠

Í

𝑠 𝜆𝑠 𝑒 (𝛼𝑠 ) with 𝜆𝑠 ≥ 0 and

𝑠

Í The constraint ℓ 𝑗 (𝑧𝑖 ) ≥ 𝑗 2 therefore forces 𝑠 𝜆𝑠 (𝑠 − 𝑗) 2 ≤ 0. Every term is nonnegative, so 𝜆𝑠 = 0 for all 𝑠 ≠ 𝑗, whence 𝜆 𝑗 = 1 and 𝑧𝑖 = 𝑒 (𝛼 𝑗 ).

□

We call ℓ 𝑗 (𝑧𝑖 ) ≥ 𝑗 2 the pin for 𝛼 𝑗 ; see Figure 6. The inequalities describing 𝑃𝑞 are public and identical for every input, and only the choice among the 𝑞 candidate pins depends on the data. Thus one private inequality specifies one of 𝑞 field elements, which is exactly the accounting we need. Imposing a public relation. The pins determine each symbol individually, but we also need to impose relations among several variables, such as a parity check or the trace of a product. Such relations are not linear, so we cannot write them directly. The following device converts any finite relation into linear inequalities. ′

Let R be a public finite set of tuples (𝑎 1, . . . , 𝑎𝑟 , 𝑏 1, . . . , 𝑏𝑟 ′ ) ∈ F𝑞𝑟 × {0, 1}𝑟 , listing the assignments we wish to allow. Replace each field symbol 𝑎𝑖 by the point 𝑒 (𝑎𝑖 ), we describe the construction above, and leave the 42

yi

y = x2

e(αj ) = (j, j 2 )

j2

Pq

public polytope

private pin

2jxi − yi ≥ j 2 0

j

q−1

xi

  2 ∩ zi : ℓj (z ≥ jfield’s = element e(αj ) . into R Figure 6:PqEncdoing ofi )the ′

bits unchanged. Then, let 𝑄 R be the convex hull of the resulting points in R2𝑟 +𝑟 . These points are rational, so 𝑄 R is a rational polytope and admits a finite description by linear inequalities, which we add to the linear program as public rows. If the polytope is lower-dimensional, this description includes equations for its affine hull, each written as two inequalities. This also covers 𝑞 = 2. In the linear program this reads (𝑧 1, . . . , 𝑧𝑟 , 𝛽 1, . . . , 𝛽𝑟 ′ ) ∈ 𝑄 R , where the 𝑧𝑖 are symbol variables and the 𝛽 𝑗 are real variables playing the role of bits. By itself this constraint is weak, as it says only that the tuple is some mixture of allowed assignments. The point is that pinning some of the variables collapses the mixture. Lemma C.2 (Forced relation). Fix nonnegative integers 𝑟, 𝑟 ′ with 𝑟 + 𝑟 ′ > 0, and use the convention [0] = ∅. ′ Let R ⊆ F𝑞𝑟 × {0, 1}𝑟 be a finite relation and let 𝑄 R be as above. Fix index sets 𝑆 ⊆ [𝑟 ] and 𝑆 ′ ⊆ [𝑟 ′ ], together with symbols 𝑎𝑖 ∈ F𝑞 for 𝑖 ∈ 𝑆 and bits 𝑏 𝑗 ∈ {0, 1} for 𝑗 ∈ 𝑆 ′ , and suppose that R contains exactly one tuple T ★ whose 𝑖-th symbol equals 𝑎𝑖 for every 𝑖 ∈ 𝑆 and whose 𝑗th bit equals 𝑏 𝑗 for every 𝑗 ∈ 𝑆 ′ . If a point (𝑧, 𝛽) ∈ 𝑄 R satisfies 𝑧𝑖 = 𝑒 (𝑎𝑖 ) for every 𝑖 ∈ 𝑆 and 𝛽 𝑗 = 𝑏 𝑗 for every 𝑗 ∈ 𝑆 ′ , then (𝑧, 𝛽) equals the point generated by T ★; in particular every remaining coordinate is forced to the value it takes in T ★. Proof. We want to show that in any convex decomposition of (𝑧, 𝛽) over the generating points, all the weight sits on the single generator coming from T ★. Í Í Write (𝑧, 𝛽) = T ∈ R 𝜆 T 𝑣 T with 𝜆 T ≥ 0 and T 𝜆 T = 1, where 𝑣 T denotes the point generated by the tuple T . Define ∑︁ ∑︁ 𝐿 := ℓ𝑎𝑖 + 𝜎𝑏 𝑗 , 𝜎0 (𝛽) := −𝛽, 𝜎1 (𝛽) := 𝛽, 𝑖 ∈𝑆

𝑗 ∈𝑆 ′

where ℓ𝛼 𝑗 denotes ℓ 𝑗 , ℓ𝑎𝑖 acts on the 𝑖th symbol block and 𝜎𝑏 𝑗 on the 𝑗th bit coordinate. By Lemma C.1, ℓ𝑎𝑖 is maximized over {𝑒 (𝛼) : 𝛼 ∈ F𝑞 } exactly at 𝑒 (𝑎𝑖 ), and clearly 𝜎𝑏 𝑗 is maximized over {0, 1} exactly at 𝑏 𝑗 . Writing 𝑀 for the resulting maximum, we therefore have 𝐿(𝑣 T ) ≤ 𝑀 for every T ∈ R, with equality if and only if T agrees with the fixed assignment on 𝑆 ∪ 𝑆 ′ . On the other hand 𝐿(𝑧, 𝛽) = 𝑀 by hypothesis, so linearity gives ∑︁
𝜆 T 𝑀 − 𝐿(𝑣 T ) = 0. T

43

Every summand is nonnegative, so 𝜆 T = 0 whenever 𝐿(𝑣 T ) < 𝑀; that is, only tuples agreeing with the fixed assignment receive positive weight. By hypothesis T ★ is the only such tuple, so 𝜆 T★ = 1 and (𝑧, 𝛽) = 𝑣 T★ . □ The four families of constraints. We can now assemble the linear program. Every part of the computation becomes an instance of the device above, and the private inputs enter through the pins alone. Symbols. For every 𝑖 ∈ [𝐾] we introduce 𝑧𝑖 ∈ R2 with 𝑧𝑖 ∈ 𝑃𝑞 , and Alice’s private input contributes the pin forcing 𝑧𝑖 = 𝑒 (𝑐𝑖 ). Bob contributes an identical family for a second collection 𝑧 1′ , . . . , 𝑧𝐾′ . Parity checks. For every row 𝑎 of 𝐻 , we take R to be the set of assignments to the coordinates in the support of 𝑎 that satisfy the check, and impose membership in the corresponding polytope. Applying this to both collections guarantees that pinned inputs are codewords. Trace products. For every 𝑖 ∈ [𝑘] we introduce a real variable 𝑟𝑖 and take R = {(𝑎, 𝑏, Tr(𝑎𝑏)) : 𝑎, 𝑏 ∈ F𝑞 }. Once 𝑧𝑖 and 𝑧𝑖′ are pinned, Lemma C.2 forces 𝑟𝑖 = Tr(𝑐𝑖 𝑐𝑖′ ) ∈ {0, 1}. Parity of the bits. We introduce 𝑝 0, . . . , 𝑝𝑘 , impose the public row 𝑝 0 = 0, and for every 𝑗 ∈ [𝑘] take R to be the four even-parity binary triples, so that the constraint reads (𝑝 𝑗 −1, 𝑟 𝑗 , 𝑝 𝑗 ) ∈ 𝑄 ⊕ . Once 𝑝 𝑗 −1 and 𝑟 𝑗 are bits, Lemma C.2 forces 𝑝 𝑗 = 𝑝 𝑗 −1 ⊕ 𝑟 𝑗 . Finally we plant the public row 𝑝𝑘 = 0. Notice that these families are not independent: the pins force the symbols, the symbols force the trace bits, and the trace bits together with the running parities force the next parity. Each gadget produces integral values only because the previous one already has, so the constraints must be read as a chain rather than as a set. Size of the embedding. Lemma C.3 (Dimension and number of rows). The linear program above uses 4𝐾 + 2𝑘 + 1 real variables. If 𝐻 has 𝑀 rows of maximum support size 𝜌, the public rows together with all candidate private pins admit a rational description using at most 2

𝑂 (𝐾𝑞) + 𝑀𝑞𝑂 (𝜌 ) + 𝑂 (𝑘𝑞 4 + 𝑘) inequalities. For the chosen (4, 8)-biregular graph, 𝑀 = 𝐾/2 and 𝜌 = 8, so both the public-row count and the full catalogue size are at most 𝐵𝐾𝑞𝑎 for universal 𝐵, 𝑎. Proof. The symbol blocks contribute 4𝐾 variables, the trace bits contribute 𝑘, and the running parities contribute 𝑘 + 1. For the rows, use a rational facet description in each polytope’s affine hull, together with equations defining that affine hull. The Upper Bound Theorem [McM70] bounds the number of facets of a polytope with 𝑁 vertices and intrinsic dimension ℎ ≥ 1 by 𝑂ℎ (𝑁 ⌊ℎ/2⌋ ). In ambient dimension 𝐷, at most 𝐷 affine-hull equations add at most 2𝐷 inequalities; a zero-dimensional polytope needs only these equations. All local ambient dimensions here are bounded by max{2𝜌, 5}. Symbol constraints and pins. Each of the 2𝐾 symbol blocks uses 𝑂 (𝑞) public inequalities for 𝑃𝑞 , including the affine-hull equation when 𝑞 = 2. Each block has 𝑞 possible pins, although only one pin per block is selected for a dataset. Thus the public symbol rows and all 2𝐾𝑞 candidate pins use 𝑂 (𝐾𝑞) catalogue rows. Parity checks. Fix a check with 𝑟 𝑎 nonzero entries. Its valid local assignments are the solutions of one linear equation in 𝑟 𝑎 unknowns over F𝑞 : any 𝑟 𝑎 − 1 of the symbols may be chosen freely, and the remaining one

44

is then determined, since its coefficient is nonzero. There are therefore 𝑞𝑟𝑎 −1 valid assignments, so the associated polytope has at most 𝑞𝑟𝑎 −1 vertices. Each symbol is represented by a point of R2 , so this polytope 𝑟𝑎 −1 and 𝐷 = 2𝑟 bounds the lies in dimension at most 2𝑟 𝑎
𝑎 . Applying the Upper Bound Theorem with 𝑁 = 𝑞 𝑟 (𝑟 −1) facet count by 𝑂 𝑞 𝑎 𝑎 ; at most 4𝑟 𝑎 inequalities describe the affine hull. Sum over all 𝑀 checks for both 2 words, including redundant checks, to obtain 𝑀𝑞𝑂 (𝜌 ) rows.
Trace products. The trace polytope is the convex hull of the 𝑞 2 points 𝑒 (𝑎), 𝑒 (𝑏), Tr(𝑎𝑏) for 𝑎, 𝑏 ∈ F𝑞 , which lie in R5 . The Upper Bound Theorem with 𝑁 = 𝑞 2 and 𝐷 = 5 gives 𝑂 (𝑞 4 ) = 𝑞𝑂 (1) facets, and there is one such polytope for each of the 𝑘 message coordinates. Including at most ten inequalities for each affine hull, these contribute 𝑂 (𝑘𝑞 4 ) public rows. Parity accumulation. The polytope 𝑄 ⊕ is the convex hull of four points in R3 and therefore has a constantsize description; there is one for each of the 𝑘 steps of the chain, and the endpoint equations 𝑝 0 = 0 and 𝑝𝑘 = 0 contribute four inequalities. Together these give 𝑂 (𝑘) inequalities, which is absorbed into the last term. With 𝜌 = 8, one may take 𝑎 = 56, increasing a universal multiplicative constant to cover every family. All descriptions are rational and fixed before the inputs are specified. The conversion in Lemma B.5 adds one homogenizing coordinate and two anchor types; these are counted in Lemma D.3. Repetitions affect the dataset lengths, but not this count of domain points. □ Remark C.4 (Why the parabola). The embedding 𝑒 (𝛼 𝑗 ) = ( 𝑗, 𝑗 2 ) is chosen for three reasons, all visible in Figure 6. First, a parabola is strictly convex, so no field element lies in the convex hull of the others; had some 𝑒 (𝛼 𝑗 ) fallen inside, no single inequality could isolate it, and one record could not specify a symbol. Second, the tangent line at 𝑒 (𝛼 𝑗 ) touches the parabola only there and has integer coefficients, so the pin 2𝑗 𝑧𝑖(1) − 𝑧𝑖(2) ≥ 𝑗 2 is rational and uniform in 𝑗; this matters because every inequality eventually becomes a point of the public data space. Third, two dimensions is the fewest in which 𝑞 ≥ 3 points can be in convex position, so the embedding is optimal in the resource that is scarce for us. The alphabet size therefore costs inequalities, never coordinates. ⊳

D

Proof of the lower bound for half spaces

Step 1: construction. Fix an even 𝐾 ≥ 𝐾0 , where 𝐾0 is the universal minimum in Lemma B.2, increased so that 𝛿𝐾0 ≥ 2. Let 𝑞 = 2𝑠 with 𝑠 ≥ 1. For each such 𝐾, fix once and for all a graph supplied by that lemma. This is a (4, 8)-biregular graph on 𝐾 variable nodes and 𝑀 = 𝐾/2 check nodes satisfying, for a universal constant 𝛿 > 0, |Γ(𝑇 )| > 2|𝑇 | for every 𝑇 ⊆ [𝐾] with 0 < |𝑇 | < 𝛿𝐾, (17) where Γ(𝑎) ⊆ [𝐾] denotes the support of check 𝑎 and Γ(𝑇 ) the set of checks meeting 𝑇 . The same chosen graph is used for every alphabet and every dataset size at this block length. Let 𝐻 ∈ {0, 1}𝑀 ×𝐾 be its incidence matrix, viewed over F𝑞 , and define C𝐻 := {𝑐 ∈ F𝑞𝐾 : 𝐻𝑐 ⊤ = 0},

𝑘 := dimF𝑞 (C𝐻 ).

Since rank(𝐻 ) ≤ 𝑀 = 𝐾/2, we have 𝑘 ≥ 𝐾/2. After relabeling the coordinates, fix a systematic generator 𝐺 = [I𝑘 | 𝐴] ∈ F𝑞𝑘 ×𝐾 .

45

Alice holds 𝑢 ∈ F𝑞𝑘 and Bob holds 𝑣 ∈ F𝑞𝑘 . Set 𝑐 = 𝑢𝐺 and 𝑐 ′ = 𝑣𝐺, and define 𝐹 (𝑢, 𝑣) =

𝑘 Ê

TrF𝑞 /F2 (𝑢𝑖 𝑣𝑖 ).

(18)

𝑖=1

É𝑘 Since 𝐺 is systematic, 𝐹 (𝑢, 𝑣) = 𝑖=1 TrF𝑞 /F2 (𝑐𝑖 𝑐𝑖′ ), so the trace products may be formed from the first 𝑘 coordinates of the codewords. We also write 𝐹 (𝑐, 𝑐 ′ ) for this value. By Section C, the pair (𝑐, 𝑐 ′ ) determines a rational linear program Λ(𝑐, 𝑐 ′ ) with 4𝐾 + 2𝑘 +𝑂 (1) variables and at most 𝐶𝐾𝑞𝑎 possible distinct rows, for universal constants 𝐶, 𝑎. Its only input-dependent rows are the 𝐾 pins determined by 𝑐 and the 𝐾 pins determined by 𝑐 ′ . We retain all 𝑀 parity checks, including redundant ones, since the rigidity proof uses the graph structure rather than a basis. Write 𝑃𝐻 for the set of 𝑧 ∈ (R2 ) 𝐾 satisfying every public symbol and parity-check row, so that 𝑃𝐻 ⊆ 𝑃𝑞𝐾 and 𝑒 (𝑐) ∈ 𝑃𝐻 for every 𝑐 ∈ C𝐻 ; note that 𝑃𝐻 is only a relaxation of C𝐻 and may contain further points. Step 2: Correctness and the gap. Let Λ(𝑐, 𝑐 ′ ) denote the linear program consisting of all public rows together with the 2𝐾 private pins determined by 𝑐 and 𝑐 ′ . Lemma D.1 (Feasibility decides 𝐹 ). For every 𝑐, 𝑐 ′ ∈ C𝐻 , the system Λ(𝑐, 𝑐 ′ ) is feasible if and only if 𝐹 (𝑐, 𝑐 ′ ) = 0. Proof. É Suppose 𝐹 (𝑐, 𝑐 ′ ) = 0. Set 𝑧𝑖 = 𝑒 (𝑐𝑖 ) and 𝑧𝑖′ = 𝑒 (𝑐𝑖′ ) for 𝑖 ∈ [𝐾], 𝑟𝑖 = Tr(𝑐𝑖 𝑐𝑖′ ) for 𝑖 ∈ [𝑘], and 𝑝𝑗 = 𝑖 ≤ 𝑗 𝑟 𝑖 . Each pin is satisfied by Lemma C.1; each parity-check polytope is satisfied because 𝐻𝑐 ⊤ = 𝐻 (𝑐 ′ ) ⊤ = 0, so the corresponding local assignment is valid and its embedding is one of the generators; the trace and parity polytopes are satisfied for the same reason; and 𝑝𝑘 = 𝐹 (𝑐, 𝑐 ′ ) = 0 satisfies the planted row. Conversely, let (𝑧, 𝑧 ′, 𝑟, 𝑝) be a solution of Λ(𝑐, 𝑐 ′ ). By Lemma C.1 the pins force 𝑧𝑖 = 𝑒 (𝑐𝑖 ) and 𝑧𝑖′ = 𝑒 (𝑐𝑖′ ) for every 𝑖. For each 𝑖 ∈ [𝑘] the trace relation assigns a unique bit to the pair (𝑐𝑖 , 𝑐𝑖′ ), so Lemma C.2 forcesÉ 𝑟𝑖 = Tr(𝑐𝑖 𝑐𝑖′ ). Since 𝑝 0 = 0 and each 𝑟𝑖 is a bit, induction on 𝑗 with Lemma C.2 applied to 𝑄 ⊕ forces 𝑝 𝑗 = 𝑖 ≤ 𝑗 𝑟𝑖 . In particular 𝑝𝑘 = 𝐹 (𝑐, 𝑐 ′ ), and the planted row gives 𝐹 (𝑐, 𝑐 ′ ) = 0. □ The feasibility equivalence by itself gives no quantitative guarantee after pins are removed. The next lemma supplies that guarantee: the codeword remains forced after a linear number of erasures, even inside the fractional relaxation 𝑃𝐻 . Lemma D.2 (LP-erasure rigidity). Let 𝑐 ∈ C𝐻 , let 𝑆 ⊆ [𝐾] with |𝑆 | < 𝛿𝐾, and let 𝑧 ∈ 𝑃𝐻 satisfy 𝑧𝑖 = 𝑒 (𝑐𝑖 ) for every 𝑖 ∉ 𝑆. Then 𝑧 = 𝑒 (𝑐). Proof. Let 𝑇 := {𝑖 ∈ [𝐾] : 𝑧𝑖 ≠ 𝑒 (𝑐𝑖 )} and suppose 𝑇 ≠ ∅. Since 𝑇 ⊆ 𝑆 we have 0 < |𝑇 | < 𝛿𝐾, so Equation (17) gives |Γ(𝑇 )| > 2|𝑇 |. Every coordinate lies in exactly four checks, so 𝑇 is incident to 4|𝑇 | edges; if every check in Γ(𝑇 ) met 𝑇 at least twice, then 4|𝑇 | ≥ 2|Γ(𝑇 )|, contradicting expansion. Hence some check 𝑎 has Γ(𝑎) ∩ 𝑇 = {𝑖 ★ } for a single 𝑖 ★. Every 𝑗 ∈ Γ(𝑎) \ {𝑖 ★ } lies outside 𝑇 , so 𝑧 𝑗 = 𝑒 (𝑐 𝑗 ). As 𝐻𝑎,𝑖 ★ ≠ 0, the relation of check 𝑎 assigns a unique symbol to coordinate 𝑖 ★ given the other seven, so Lemma C.2 forces 𝑧𝑖★ = 𝑒 (𝑐𝑖★ ), contradicting 𝑖 ★ ∈ 𝑇 . Hence 𝑇 = ∅. □ Step 3: from the LP to fixed-size datasets. We now convert the linear program Λ(𝑐, 𝑐 ′ ) into size-𝑛 datasets for Alice and Bob via Lemma B.5. Let R𝐾,𝑞 be the finite set of all linear constraints 𝑎𝑖⊤𝑥 ≤ 𝑏𝑖 46

appearing in the public polytopes (with each equality written as two inequalities), together with all 𝑞 candidate pins at each of Alice’s and Bob’s 𝐾 symbol positions. Applying Lemma B.5 to R𝐾,𝑞 yields a constant 𝜂𝐾,𝑞 > 0 and the corresponding points 𝑥𝑖− , 𝑥𝑖+ ∈ R𝑝+1 , along with the anchors 𝑥 0− = −𝑒𝑝+1 and 𝑥 0+ = 𝑒𝑝+1 . Let X𝐾,𝑞 ⊂ R𝑝+1 denote the resulting finite set of points; note that X𝐾,𝑞 depends only on (𝐾, 𝑞) and is independent of the inputs (𝑢, 𝑣) and the testing parameters. Let 𝑅pub be the number of public LP rows. For positive integers 𝐽, 𝐿, Alice’s encoder 𝐸𝐴𝐽 ,𝐿 (𝑢) consists of 𝐿 copies of each of her 𝐾 selected pin records and 𝐽 copies of 𝑥 0− . Bob’s encoder 𝐸𝐵𝐽 ,𝐿 (𝑣) consists of 𝐿 copies of each of his 𝐾 selected pin records, 𝐽 copies of each public row record, and 𝐽 copies of 𝑥 0+ . In particular, their lengths are 𝑁𝐴 = 𝐾𝐿 + 𝐽, 𝑁𝐵 = 𝐾𝐿 + (𝑅pub + 1) 𝐽 . (19) For these intermediate samples, opt denotes the same pooled-error sum, allowing unequal lengths; only the padded size-𝑛 inputs below are passed to the tester. Put 𝐷 = ⌊𝛿𝐾⌋ ≥ 𝛿𝐾/2. Lemma D.3 (Gap, diameter, and encoding resources). There are universal constants 𝐵, 𝑎 ≥ 1 such that, for every even 𝐾 ≥ 𝐾0 and every 𝑞 = 2𝑠 ≥ 2, the preceding construction has a fixed domain X𝐾,𝑞 in dimension at most 6𝐾 + 2 with |X𝐾,𝑞 | ≤ 𝐵𝐾𝑞𝑎 and 𝑅pub + 1 ≤ 𝐵𝐾𝑞𝑎 . For every 𝐽, 𝐿 ∈ N and every pair of secrets, 𝐹 (𝑢, 𝑣) = 0 =⇒ opt Hhs = 0,

𝐹 (𝑢, 𝑣) = 1 =⇒ opt Hhs ≥ min{𝐽, 𝐷𝐿}.

Each party’s encoder has length at most 𝐵𝐾𝑞𝑎 𝐽 + 𝐾𝐿 and replacement diameter at most 𝐾𝐿. Whenever both lengths are at most 𝑛, the encoders can be padded to exactly 𝑛 records per party with the same promise and diameter guarantees. The domain depends only on (𝐾, 𝑞). Proof. The LP has 𝑝 = 4𝐾 + 2𝑘 + 1 ≤ 6𝐾 + 1 real variables. Lemma C.3 bounds its public rows and all candidate pins by 𝑂 (𝐾𝑞𝑎 ) for a fixed universal 𝑎. Lemma B.5 adds one coordinate and two anchor types. Taking 𝐵 large enough proves the domain and row counts, and (19) gives the dataset lengths. If 𝐹 (𝑢, 𝑣) = 0, Lemma D.1 gives an exact feasible LP witness. Its homogenization classifies every record, including the anchors, correctly by Lemma B.5. Suppose 𝐹 (𝑢, 𝑣) = 1 and a halfspace makes fewer than min{𝐽, 𝐷𝐿} errors. No public row or anchor can be misclassified, because each appears 𝐽 times. Let 𝑆𝐴, 𝑆 𝐵 ⊆ [𝐾] be the positions of misclassified pin records. Each such record appears 𝐿 times, so |𝑆𝐴 |, |𝑆 𝐵 | < 𝐷. Keep every public row and precisely the pins outside 𝑆𝐴, 𝑆 𝐵 . The halfspace is consistent with all these records and the normalization anchor. By Lemma B.5, the corresponding original closed LP subsystem has an exact witness (𝑧★, 𝑧 ′★, 𝑟 ★, 𝑝 ★). The retained original pins give 𝑧𝑖★ = 𝑒 (𝑐𝑖 ) for 𝑖 ∉ 𝑆𝐴 and 𝑧𝑖′★ = 𝑒 (𝑐𝑖′ ) for 𝑖 ∉ 𝑆 𝐵 . Both symbol vectors satisfy all original public rows, so Lemma D.2 forces 𝑧★ = 𝑒 (𝑐) and 𝑧 ′★ = 𝑒 (𝑐 ′ ). The trace and parity relations now force 𝑝𝑘★ = 𝐹 (𝑢, 𝑣) = 1, contradicting the retained public condition 𝑝𝑘★ = 0. For the diameter, fix an ordering with one block of 𝐿 positions for each pin and fixed positions for the public rows and anchors. Changing a party’s secret replaces at most 𝐾𝐿 records; all other positions are identical. This bounds the replacement distance also when the datasets are regarded as multisets. Finally, append 𝑛 − 𝑁𝐴 copies of 𝑥 0− to Alice and 𝑛 − 𝑁𝐵 copies of 𝑥 0+ to Bob. These multiplicities depend only on the public parameters. Every Match witness already satisfies the anchors, while adding records cannot decrease the Far optimum. The fixed padding changes neither replacement diameter. Group privacy applies on the full size-𝑛 input space, so the padded encoders can be used directly in Lemma 2.2. □ With 𝐽 = ⌈𝑡⌉ and 𝐿 = ⌈𝐽 /𝐷⌉, the Far gap is at least 𝑡, the diameter is 𝑂 (𝑡 + 𝐾), and the sample cost is 𝑂 (𝐾𝑞𝑎 (𝑡 + 1) + 𝑡 + 𝐾) per party. 47

E

Sample-size-dependent lower bounds

The proof of Theorem 4.1 gives a lower bound of Ω(𝑑 log(𝑚/𝑑)/𝜀) whenever 𝑛 ≳ 𝑚𝑑/𝜀. To obtain bounds for smaller datasets, we return to the encoders in Section D. Recall that Bob repeats each of its 𝑂 (𝐾𝑞𝑎 ) public records 𝑡 times, where 𝑎 is a universal constant. These repetitions contribute 𝑂 (𝐾𝑞𝑎 𝑡) records, so the choice of block length and alphabet must also account for the dataset size. For smaller datasets, we shorten the block length or reduce the alphabet. This makes the encoders shorter, at the price of a weaker lower bound of order 𝐾 log 𝑞/𝜀. We call a pair (𝑟, 𝑞) a scale, where 𝑟 is an even block length and 𝑞 is a power of two. At scale (𝑟, 𝑞), we prove that 𝑟 log 𝑞 𝑡≳ provided that 𝑛𝜀 ≳ 𝑟 2𝑞𝑎 log 𝑞. 𝜀 Indeed, when 𝑡 is below the claimed lower bound, the encoders use 𝑂 (𝑟 2𝑞𝑎 log 𝑞/𝜀) records, which fit into datasets of size 𝑛 under this condition. For 𝑛𝜀 ≤ √︁ 𝑑 2 , with 𝑛𝜀 above a universal constant, we use the binary √ alphabet and choose 𝑟 = Θ( 𝑛𝜀). This gives 𝑡 ≳ 𝑛/𝜀. For 𝑛𝜀 > 𝑑 2 , we use 𝑟 = Θ(𝑑) and choose the largest alphabet allowed by the sample and domain sizes. This gives  n 𝑚 𝑛𝜀 o 𝑑 𝑡 ≳ log 2 + min , 2 . 𝜀 𝑑 𝑑 In particular, the bound reaches Ω(𝑑 log(𝑚/𝑑)/𝜀) once 𝑛𝜀 ≳ 𝑚𝑑. We also want the bounds for different sample sizes to hold on the same public domain. We therefore choose a domain X𝑑,𝑚 containing all the scales needed for the two regimes, before 𝑛, 𝑡, 𝜀 are specified. Each scale (𝑟, 𝑞) uses 𝑂 (𝑟𝑞𝑎 ) points. By taking geometrically spaced block lengths and alphabets, we can include these scales while keeping the total number of points at most 𝑚. All logarithms in this section are to base two. Lemma E.1 (Lower bound at a single scale). There are universal constants 𝐴, 𝐵, 𝑎 ≥ 1, 𝑏 > 0, 𝜀 0 ∈ (0, 1], and an even integer 𝑟 0 ≥ 2 such that the following holds. For every even 𝑟 ≥ 𝑟 0 and every 𝑞 = 2𝑠 with 𝑠 ∈ N, there is a public domain X𝑟,𝑞 ⊆ R6𝑟 +2 that depends only on (𝑟, 𝑞) and has |X𝑟,𝑞 | ≤ 𝐵𝑟𝑞𝑎 , such that for every 0 < 𝜀 ≤ 𝜀 0 and every 𝑛 ∈ N satisfying 𝑛𝜀 ≥ 𝐴𝑟 2𝑞𝑎 log 𝑞, (20) every 𝜀-private tester for Hhs over X𝑟,𝑞 with resolution 𝑡 at dataset size 𝑛 satisfies 𝑡 ≥𝑏

𝑟 log 𝑞 . 𝜀

(21)

Proof. Let 𝐾0 be the minimum block length used in Section D. Choose an even 𝑟 0 ≥ 𝐾0 large enough that 𝛿𝑟 0 ≥ 2, where 𝛿 is the expansion constant of Lemma B.2. For every even 𝑟 ≥ 𝑟 0 , we use the domain X𝐾,𝑞 of Lemma D.3 with 𝐾 = 𝑟 , padding its coordinates with zeros if necessary. The bounds on its dimension and size follow from that lemma, and the domain depends only on (𝑟, 𝑞). Recall also that 𝐷 = ⌊𝛿𝑟 ⌋ ≥ 𝛿𝑟 /2. Let 0 < 𝜀 ≤ 𝜀 0 and let 𝑛 satisfy (20), where 𝜀 0 ≤ 1 will be fixed at the end of the proof. Suppose toward a contradiction that there is an 𝜀-private tester with resolution 𝑡 < 𝑏 𝑟 log 𝑞/𝜀, where 𝑏 ≤ 1 will also be fixed at the end. Since 𝑡 is an integer, we apply Lemma D.3 with 𝐽 = 𝑡 and 𝐿 = ⌈𝑡/𝐷⌉. These choices give 𝐷𝐿 ≥ 𝑡. Thus the encodings of two secrets 𝑢, 𝑣 satisfy opt Hhs = 0 when 𝐹 (𝑢, 𝑣) = 0, and opt Hhs ≥ 𝑡 when 𝐹 (𝑢, 𝑣) = 1. First, we check that the encoders fit into 𝑛 records. Each encoder has length at most 𝐵𝑟𝑞𝑎 𝑡 + 𝑟𝐿, including the public records and anchors. Since 𝑟𝐿 ≤ 𝑟𝑡/𝐷 + 𝑟 ≤ 2𝑡/𝛿 + 𝑟 , we obtain   2 𝑎 𝑟 𝑞 log 𝑞 2 𝑎 𝐵𝑟𝑞 𝑡 + 𝑟𝐿 ≤ 𝐵 + + 1 ≤ 𝑛. 𝛿 𝜀 48

The first inequality uses 𝑡 < 𝑟 log 𝑞/𝜀, 𝑟, 𝑞𝑎 , log 𝑞 ≥ 1, and 𝜀 ≤ 1. The second follows from (20), provided that 𝐴 ≥ 𝐵 + 2/𝛿 + 1. By Lemma D.3, we can therefore pad both encoders to exactly 𝑛 records without changing their promise or encoding diameters. Next, let 𝑘 ≥ 𝑟 /2 be the dimension of the code, and let (𝑢, 𝑣) be uniform on F𝑞𝑘 × F𝑞𝑘 . Running the tester on the padded encodings, and reading Match as 0 and Far as 1, gives a protocol computing 𝐹 (𝑢, 𝑣) with error at most 1/10. By Lemma B.6, its internal information cost is at least 𝑐 𝐼 𝑟 log 𝑞 for a universal 𝑐 𝐼 > 0. On the other hand, changing one party’s secret replaces at most 𝑟𝐿 of its records. Hence Δ𝐴 + Δ𝐵 ≤ 2𝑟𝐿 ≤

4𝑡 + 2𝑟 ≤ 𝐶 Δ (𝑡 + 𝑟 ) 𝛿

(22)

for a universal 𝐶 Δ . Applying Lemma 2.2 to the same protocol gives 𝑐 𝐼 𝑟 log 𝑞 ≤ 𝐶𝐼 𝜀 (𝑡 + 𝑟 ),

𝐶𝐼 :=

𝐶Δ . ln 2

We now fix   𝑐𝐼 , 𝜀 0 := min 1, 2𝐶𝐼

  𝑐𝐼 𝑏 := min 1, . 4𝐶𝐼

Since 𝜀 ≤ 𝜀 0 and log 𝑞 ≥ 1, the term 𝐶𝐼 𝜀𝑟 is at most 𝑐 𝐼 𝑟 log 𝑞/2. Rearranging therefore gives 𝑡≥

𝑟 log 𝑞 𝑐 𝐼 𝑟 log 𝑞 >𝑏 , 2𝐶𝐼 𝜀 𝜀

contradicting the assumption on 𝑡.

□

Remark E.2 (Larger domains). Lemma E.1 also applies to testers over any domain X ⊆ R𝑑 , with 𝑑 ≥ 6𝑟 + 2, containing a copy of X𝑟,𝑞 padded with zeros. Indeed, restricting a tester to datasets supported on this copy preserves privacy and its completeness and soundness guarantees. Padding with zeros also preserves opt Hhs : a normal 𝑤 ∈ R𝑑 makes the same predictions on the copy as its first 6𝑟 + 2 coordinates, and every normal in R6𝑟 +2 extends to R𝑑 by adding zero coordinates. ⊳ We next construct a single domain containing the scales needed for both regimes. Lemma E.3 (A single domain for all scales). Let 𝐴, 𝐵, 𝑎, 𝑟 0 be the constants of Lemma E.1. There are universal constants 𝜅 > 0, 𝐶 0 ≥ 1, and 𝑑 0 ∈ N such that the following holds for every 𝑑 ≥ 𝑑 0 and 𝑚 ≥ 𝐶 0𝑑. There are an integer ℎ ≥ 0 and a public domain X𝑑,𝑚 ⊆ R𝑑 with |X𝑑,𝑚 | = 𝑚, depending only on (𝑑, 𝑚), such that 𝑅 := 𝑟 0 2ℎ satisfies 𝑑2 𝜅𝑑 < 𝑅 ≤ 𝜅𝑑, 6𝑅 + 2 ≤ 𝑑, 𝐴2𝑎 𝑅 2 ≤ , 2 16 and X𝑑,𝑚 contains a copy of X𝑟,𝑞 padded with zeros for every scale (𝑟, 𝑞) in   (𝑟 0 2 𝑗 , 2) : 0 ≤ 𝑗 ≤ ℎ ∪ (𝑅, 2𝑠 ) : 𝑠 ≥ 1, 2𝑎𝑠 ≤ 𝑚/(8𝐵𝑅) . (23) Proof. Fix 

 1 1 𝜅 := min , √ , 12 4 𝐴2𝑎

𝐶 0 := 8𝐵2𝑎 .

Let 𝑅 be the largest element of {𝑟 0 2 𝑗 : 𝑗 ≥ 0} that is at most 𝜅𝑑. Choose an integer 𝑑 0 ≥ max{4, 𝑟 0 /𝜅}, so that 𝑟 0 ≤ 𝜅𝑑 and this maximum exists. Maximality gives 2𝑅 > 𝜅𝑑. The remaining bounds on 𝑅 follow from the choice of 𝜅: 6𝑅 + 2 ≤ 𝑑/2 + 2 ≤ 𝑑, 𝐴2𝑎 𝑅 2 ≤ 𝐴2𝑎𝜅 2𝑑 2 ≤ 𝑑 2 /16. 49

For each scale in (23), fix one construction of X𝑟,𝑞 , including its graph, inequality descriptions, and the constant 𝜂 of Lemma B.5. Pad each domain with zeros to embed it in R𝑑 . All these embeddings fit because 6𝑟 + 2 ≤ 6𝑅 + 2 ≤ 𝑑. We count the points contributed by the two families separately. The binary scales (𝑟 0 2 𝑗 , 2) use at most ℎ ∑︁

𝐵2𝑎 𝑟 0 2 𝑗 < 2𝐵2𝑎 𝑅

𝑗=0

points. Since 𝑚 ≥ 𝐶 0𝑑 ≥ 8𝐵2𝑎 𝑅, this is less than 𝑚/4. For the alphabet scales (𝑅, 2𝑠 ), let 𝑄 be the largest power of two satisfying 𝑄 𝑎 ≤ 𝑚/(8𝐵𝑅). The inequality 𝑚 ≥ 8𝐵2𝑎 𝑅 ensures that 𝑄 ≥ 2 exists. These scales use at most

𝐵𝑅

log ∑︁𝑄

2𝑎𝑠 ≤

𝑠=1

𝑚 𝐵𝑅𝑄 𝑎 ≤ 2𝐵𝑅𝑄 𝑎 ≤ −𝑎 1−2 4

points, where we used 𝑎 ≥ 1. The union therefore has fewer than 𝑚/2 points. We add distinct unused points until the domain has exactly 𝑚 points. None of the encoded datasets uses these additional points. All choices have been made using only (𝑑, 𝑚), before the testing parameters are specified. □ We now choose a scale for each sample size. Theorem E.4 (Lower bounds as a function of the sample size). There are universal constants 𝑐 > 0, 𝑁 0 ≥ 1, 𝐶 0 ≥ 1, 𝑑 0 ∈ N, and 𝜀 0 > 0 such that the following holds. Let 𝑑 ≥ 𝑑 0 and 𝑚 ≥ 𝐶 0𝑑, and let X𝑑,𝑚 be the domain of Lemma E.3. For every 0 < 𝜀 ≤ 𝜀 0 and every 𝑛 ∈ N with 𝑛𝜀 ≥ 𝑁 0 , every 𝜀-private tester for Hhs over X𝑑,𝑚 with resolution 𝑡 at dataset size 𝑛 satisfies √︁   𝑁 0 ≤ 𝑛𝜀 ≤ 𝑑 2,   𝑛/𝜀,   n 𝑚 𝑛𝜀 o (24) 𝑡 ≥𝑐 𝑑    log 2 + min , 2 , 𝑛𝜀 > 𝑑 2 . 𝑑 𝑑 𝜀 Proof. Use the constants and scales of Lemmas E.1 and E.3, and set 𝑁 := 𝑛𝜀 and 𝑁 0 := 𝐴2𝑎 𝑟 02 . Enlarge 𝑑 0 if necessary so that 𝑑 2 ≥ 𝑁 0 . Every scale used below belongs to (23). Thus Lemma E.1 applies to testers over X𝑑,𝑚 by Remark E.2. Case 1: 𝑁 0 ≤ 𝑁 ≤ 𝑑 2 . We use the binary alphabet and choose 𝑟 to be the largest element of {𝑟 0 2 𝑗 : 0 ≤ 𝑗 ≤ ℎ} satisfying 𝐴2𝑎 𝑟 2 ≤ 𝑁 . Such an 𝑟 exists because 𝐴2𝑎 𝑟 02 = 𝑁 0 ≤ 𝑁 . √ To obtain the claimed bound, we need 𝑟 = Ω( 𝑁 ). If 𝑟 < 𝑅, the next scale 2𝑟 violates the constraint, so √ 𝑁 𝑎 2 𝐴2 (2𝑟 ) > 𝑁 =⇒ 𝑟 > √ . 2 𝐴2𝑎 √ √ √ If 𝑟 = 𝑅, then 𝑟 > 𝜅𝑑/2 ≥ 𝜅 𝑁 /2, since 𝑁 ≤ 𝑑 2 . Thus 𝑟 ≥ 𝑐𝑟 𝑁 for 𝑐𝑟 := min{1/(2 𝐴2𝑎 ), 𝜅/2}. For 𝑞 = 2, the inequality 𝑁 ≥ 𝐴2𝑎 𝑟 2 is precisely the sample-size condition in Lemma E.1. Applying that lemma gives √︂ √ 𝑛𝜀 𝑟 𝑛 𝑡 ≥ 𝑏 ≥ 𝑏𝑐𝑟 = 𝑏𝑐𝑟 . 𝜀 𝜀 𝜀 50

Case 2: 𝑁 > 𝑑 2 . We use the largest block length 𝑅 and choose the alphabet to satisfy both the domain-size and sample-size constraints. Define     𝑚 𝑁 𝑚 𝑁 , 𝑋 := min , 2 , , 𝑍 := min 8𝐵𝑅 𝐴𝑅 2 𝑑 𝑑 and let 𝑞 = 2𝑠 be the largest power of two satisfying 𝑞𝑎 log 𝑞 ≤ 𝑍 .

(25)

The choice 𝑞 = 2 is admissible. Indeed, 𝑚/(8𝐵𝑅) ≥ 2𝑎 because 𝑚 ≥ 𝐶 0𝑑 ≥ 8𝐵2𝑎 𝑅, while 𝑁 > 16 · 2𝑎 𝐴𝑅 2 follows from 𝐴2𝑎 𝑅 2 ≤ 𝑑 2 /16 < 𝑁 /16. Since log 𝑞 ≥ 1, our choice gives 𝑞𝑎 ≤ 𝑞𝑎 log 𝑞 ≤ 𝑍 ≤

𝑚 . 8𝐵𝑅

Thus (𝑅, 𝑞) is one of the scales included in X𝑑,𝑚 . We also have 𝑁 ≥ 𝐴𝑅 2𝑞𝑎 log 𝑞, so Lemma E.1 gives 𝑡 ≥𝑏

𝑅 log 𝑞 . 𝜀

It remains to show that log 𝑞 is large enough. By maximality, 2𝑞 violates (25), and therefore 𝑍 < (2𝑞)𝑎 log(2𝑞) = 2𝑎 (𝑠+1) (𝑠 + 1). Using 𝑍 ≥ 2 and log(𝑠 + 1) ≤ 𝑠, we obtain log(2 + 𝑍 ) ≤ 1 + log 𝑍 < 1 + 𝑎 + (𝑎 + 1)𝑠 ≤ 2(𝑎 + 1)𝑠. Also, 𝑅 ≤ 𝜅𝑑 implies 𝑍 ≥ 𝑐 𝑍 𝑋 for a universal 𝑐 𝑍 > 0, and hence log(2 + 𝑍 ) ≥ 𝑐 ′ log(2 + 𝑋 ) for a universal 𝑐 ′ > 0. Combining these inequalities gives log 𝑞 ≥ 𝑐𝑞 log(2 + 𝑋 ), where 𝑐𝑞 := 𝑐 ′ /(2(𝑎 + 1)). Finally, 𝑅 > 𝜅𝑑/2, so 𝑡 ≥𝑏

𝑅 log 𝑞 𝑏𝜅𝑐𝑞 𝑑 ≥ log(2 + 𝑋 ). 𝜀 2 𝜀

This gives the claimed bound for 𝑁 > 𝑑 2 . Taking 𝑐 := min{𝑏𝑐𝑟 , 𝑏𝜅𝑐𝑞 /2} completes the proof.

□

The two expressions agree up to universal constants when 𝑛𝜀 ≍ 𝑑 2 , where both give Ω(𝑑/𝜀). The theorem includes the resolution 𝑡 = 𝑛. As with the large-sample result, the sample-size conditions are sufficient and are not asserted to be sharp.

F

Additional Algorithms for Small-dataset Regime

Proof of Theorem 4.9. We write opt = opt Hhs (𝑆𝐴, 𝑆 𝐵 ). We first prove privacy and then turn to the utility proof. We first prove the privacy guarantee. Fix the public signs. Replacing one record of Alice moves one unit of Í count from one ray to another, so it changes each 𝑅 𝜎 𝑗,𝑅 𝑎𝑅 by at most two. Therefore, the vector of the 𝑘 sums has ℓ1 -sensitivity at most 2𝑘, and by Lemma B.1 and composition property of DP [DMNS06], Alice’s release is 𝜀-DP. The same argument works for Bob. Since the public signs are independent of the datasets and the output is a post-processing of the two releases, the protocol satisfies 𝜀-two-party DP. 51

Í To show this algorithm achieves the claimed resolution, for 𝑗 ∈ [𝑘], let 𝐷 𝑗 = 𝑅 𝜎 𝑗,𝑅 (𝑎𝑅 − 𝑏 𝑅 ) be the difference of the two sums before adding the noise. Since 𝑘 is a constant, the tail bound of the Laplace distribution and a union bound over the 2𝑘 noise terms show that, with probability at least 0.95, all of them are 𝑂 (1/𝜀) in absolute value. In the rest of the proof we assume that this event holds. Then, by choosing 𝐶 √ √ large enough, every noise term is at most 𝑛/8, and hence |𝑍𝐴,𝑗 − 𝑍 𝐵,𝑗 − 𝐷 𝑗 | ≤ 𝑛/4 for every 𝑗. √ Under the Far promise, Equation (14) gives 𝑎𝑅 = 𝑏 𝑅 for every 𝑅. Thus 𝐷 𝑗 = 0 and |𝑍𝐴,𝑗 − 𝑍 𝐵,𝑗 | ≤ 𝑛/4 < 𝜏 for every 𝑗, and the algorithm outputs Far. Í Under the Match promise, Equation (14) gives 𝑎𝑅𝑏 𝑅 = 0 for every 𝑅. Let 𝑉 = 𝑅 (𝑎𝑅 − 𝑏 𝑅 ) 2 . Since the counts are integers with disjoint supports, ∑︁ ∑︁ 𝑉 = (𝑎𝑅2 + 𝑏 𝑅2 ) ≥ (𝑎𝑅 + 𝑏 𝑅 ) = 2𝑛. 𝑅

𝑅

The signs are independent, so E[𝐷 2𝑗 ] = 𝑉 and E[𝐷 4𝑗 ] ≤ 3𝑉 2 . By the Paley–Zygmund inequality, 

Pr 𝐷 2𝑗 ≥ 𝑉 /2



≥

(E[𝐷 2𝑗 ]) 2 4 E[𝐷 4𝑗 ]

≥

1 , 12

√ and in particular |𝐷 𝑗 | ≥ 𝑛 with probability at least 1/12. The 𝑘 repetitions are independent, so if 𝑘 √ is large enough, with probability at least 0.95 there exists 𝑗 ∈ [𝑘] with |𝐷 𝑗 | ≥ 𝑛. For this 𝑗, we have √ √ |𝑍𝐴,𝑗 − 𝑍 𝐵,𝑗 | ≥ 𝑛 − 𝑛/4 > 𝜏, and the algorithm outputs Match. In both cases, the failure probability is at most 0.1, which completes the proof.

□

Proof of Theorem 4.11. First of all, by Sauer–Shelah lemma (see Lemma 4.3), we can restrict Hhs to a finite discretization H0 ⊆ Hhs since X is public and each party can find the projection of the hypothesis class on X. For any finite multiset 𝐷 over X, define the local error at Alice and Bob as ∑︁ ∑︁ 𝑓𝐴 (ℎ; 𝐷) := 1{ℎ(𝑥) ≠ −1}, 𝑓𝐵 (ℎ; 𝐷) := 1{ℎ(𝑥) ≠ +1}. 𝑥 ∈𝐷

𝑥 ∈𝐷

Using this notation, we can rewrite the optimal error as
opt Hhs (𝑆𝐴, 𝑆 𝐵 ) = min 𝑓𝐴 (ℎ; 𝑆𝐴 ) + 𝑓𝐵 (ℎ; 𝑆 𝐵 ) . ℎ∈ H0

Then, we show how we can use the mechanism of [BLR13] to perform the test. Fix a sufficiently large universal constant 𝑐 0 > 0, and set  2  𝑐 0𝑛 𝑑 𝑠 := and D𝑠 := X𝑠 . 𝑡2 The family D𝑠 is public and has cardinality 𝑚𝑠 . We claim that, for every party 𝑃 ∈ {𝐴, 𝐵} and every 𝑆𝑃 ∈ X𝑛 , some 𝐷 𝑃★ ∈ D𝑠 satisfies 𝑛 𝑡 max 𝑓𝑃 (ℎ; 𝑆𝑃 ) − 𝑓𝑃 (ℎ; 𝐷 𝑃★) ≤ . 𝑠 16 ℎ∈ H0 Indeed, view 𝑆𝑃 as defining an empirical distribution Unif (𝑆𝑃 ) over X. Sample 𝑠 records independently and uniformly from 𝑆𝑃 , with replacement, and let 𝐷 ∈ D𝑠 be the resulting multiset. Notice that 𝑛1 𝑓𝑃 (ℎ; 𝑆𝑃 ) is 52

the population error of ℎ under Unif (𝑆𝑃 ) and 𝑠1 𝑓𝑃 (ℎ; 𝐷) is its empirical average over the 𝑠 draws. Since the class of halfspaces Hhs in R𝑑 has VC dimension 𝑑, standard VC uniform convergence guarantees that for a sufficiently large universal constant 𝑐 0 > 0, a sample of size 𝑠 = ⌈𝑐 0𝑑/𝛼 2 ⌉ with 𝛼 = 𝑡/(16𝑛) satisfies "

# 1 1 𝑡 1 Pr max 𝑓𝑃 (ℎ; 𝑆𝑃 ) − 𝑓𝑃 (ℎ; 𝐷) > ≤ . 𝑠 16𝑛 2 ℎ∈ H0 𝑛 Multiplying both sides inside the probability by 𝑛 shows that such a 𝐷 𝑃★ ∈ D𝑠 exists. Then, we explain the protocol. Each party 𝑃 independently applies the exponential mechanism with privacy parameter 𝜀 to the public family D𝑠 , using the cost 𝑞𝑃 (𝑆𝑃 , 𝐷) := max 𝑓𝑃 (ℎ; 𝑆𝑃 ) − ℎ∈ H0

𝑛 𝑓𝑃 (ℎ; 𝐷) . 𝑠

Let 𝐷 𝑃 be its released synthetic dataset. After exchanging their releases, the parties compute c := opt

𝑛 min 𝑓𝐴 (ℎ; 𝐷𝐴 ) + 𝑓𝐵 (ℎ; 𝐷 𝐵 ) . 𝑠 ℎ∈ H0

c ≤ 𝑡/2, and Far otherwise. They output Match if opt The privacy proof is straightforward: For every fixed candidate 𝐷, changing one input record changes 𝑓𝑃 (ℎ; 𝑆𝑃 ) by at most one for every ℎ. Therefore, 𝑞𝑃 (𝑆𝑃 , 𝐷) has sensitivity at most one, and each release is 𝜀-DP by Lemma B.4. The public parameters 𝑛 and 𝑠 remain fixed, so the same sensitivity bound holds on the full domain of finite input multisets. Then, we prove the utility guarantee. By Lemma B.4, for each party 𝑃, with probability at least 19/20, 2 𝑞𝑃 (𝑆𝑃 , 𝐷 𝑃 ) ≤ min 𝑞𝑃 (𝑆𝑃 , 𝐷) + (log |D𝑠 | + log 20) 𝜀 𝐷 ∈ D𝑠 𝑡 2 ≤ + (𝑠 log 𝑚 + log 20) 16 𝜀 𝑡 ≤ . 8 The last inequality follows from Equation (15), for a sufficiently large universal constant 𝐶, using 𝑠 = 𝑂 (𝑛 2𝑑/𝑡 2 ) and 𝑡 ≤ 𝑛. By a union bound, both releases satisfy this guarantee with probability at least 0.9. On this event, the total error of every halfspace is approximated within 𝑡/4. Taking the minimum over ℎ therefore gives 𝑡 c − opt H (𝑆𝐴, 𝑆 𝐵 ) ≤ . opt hs 4 c ≤ 𝑡/4, so the protocol outputs Match. If opt H (𝑆𝐴, 𝑆 𝐵 ) ≥ 𝑡, then If the pooled data are realizable, then opt hs c ≥ 3𝑡/4, so it outputs Far. This proves completeness and soundness. opt □

53

Related documents

• Blinder: End-to-end Privacy Protection in Sensing Systems via Personalized Federated Learning#1469087
• Turning Privacy-preserving Mechanisms against Federated Learning#177333
• Coordination on a Budget: Federated Active Learning with Few Labels#984227
• Legal implications of data mining for journalistic purposes#1178564
• GuardianAgent: Policy-Conditioned Risk-Adaptive Anonymization with Verified Adversarial Escalation#790041