{'fraction_non_alphanumeric': 0.038420037275610636, 'fraction_numerical': 0.011902037079423208, 'mean_word_length': 4.450721796471218, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Dual Query: Practical Private Query Release for High Dimensional Data

We present a practical, differentially private algorithm for answering a large number of queries on high dimensional datasets. Like all algorithms for this task, ours necessarily has worst-case complexity exponential in the dimension of the data. However, our algorithm packages the computationally hard step into a concisely defined integer program, which can be solved non-privately using standard solvers. We prove accuracy and privacy theorems for our algorithm, and then demonstrate experimentally that our algorithm performs well in practice. For example, our algorithm can efficiently and accurately answer millions of queries on the Netflix dataset, which has over 17,000 attributes; this is an improvement on the state of the art by multiple orders of magnitude.


Introduction
Privacy is becoming a paramount concern for machine learning and data analysis tasks, which often operate on personal data. The Netflix challenge exemplifies the tension between machine learning and data privacy. Netflix released an anonymized dataset of user movie ratings for teams competing to develop an improved recommendation mechanism. The competition was a great success (the winning team improved on the existing recommendation system by more than 10%), but the ad hoc anonymization was not as successful: Narayanan and Shmatikov [27] were later able to re-identify individuals in the dataset. This eventually led to a lawsuit and the cancellation of subsequent competitions.
Differentially private query release is an attempt to solve this problem. Differential privacy is a strong formal privacy guarantee (that, among other things, provably prevents re-identification attacks), and the problem of query release is to release accurate answers to a set of statistical queries. As observed early on by Blum et al. [6], performing private query release is sufficient to simulate any learning algorithm in the "statistical query model" of Kearns [22].
Since then, the query release problem has been extensively studied in the differential privacy literature. While simple perturbation can be used to privately answer a small number of queries [15], more sophisticated approaches can accurately answer nearly exponentially many queries in the size of the private database [5,13,14,29,18,17,19]. A natural approach, employed by many of these algorithms, is to answer queries by generating synthetic data: a fresh, safe version of the dataset approximates the real dataset on every statistical query of interest.
Unfortunately, even the most efficient approaches have a per-query running time linear in the size of the data universe, which is exponential in the dimension of the data [18]. Moreover, this running time is necessary in the worst case [32], especially if the algorithm produces synthetic data [33].
This exponential runtime has hampered practical evaluation of query release algorithms. One notable exception is due to Hardt et al. [19], who perform a thorough experimental evaluation of one such algorithm, which they called MWEM. They find that MWEM has quite good accuracy in practice and scales to higher dimensional data than suggested by a theoretical (worst-case) analysis. Nevertheless, running time remains a problem, and the approach does not seem to scale to high dimensional data (with more than 30 or so attributes for general queries, and more when the queries satisfy special structure 1 ). The critical bottleneck is the size of the state maintained by the algorithm: MWEM, like many query release algorithms, needs to manipulate an object that has size linear in the size of the data universe (i.e., exponential in the dimension). This quickly becomes impractical as the record space grows more complex.
We present DualQuery, an alternative algorithm which is dual to MWEM in a sense that we will make precise. Rather than manipulate an object of exponential size, DualQuery needs to solve a concisely represented (but NP-hard) optimization problem. Critically, the optimization step does not require a solution that is either private or exact: it can be solved by existing, off-the-shelf optimization packages quickly in practice. Except for this step, all parts of our algorithm are extremely efficient. As a result, DualQuery requires (worst-case) space and (in practice) time only linear in the number of queries of interest, which is often significantly smaller than the number of possible records. Like existing algorithms for query release, DualQuery has a provable accuracy guarantee and satisfies the strong differential privacy guarantee.
We evaluate DualQuery on a variety of datasets by releasing 3-way marginals (also known as conjunctions or contingency tables), demonstrating that it solves the query release problem accurately and efficiently even when the data includes hundreds of thousands of features. We know of no other algorithm to perform accurate, private query release for rich classes of queries on real data with more than even 100 features.

Related work
Differentially private learning has been studied since Blum et al. [6] showed how to convert learning algorithms in the SQ model of Kearns [22] into differentially private learning algorithms with similar accuracy guarantees. Since then, private machine learning has become a very active field with both foundational sample complexity results [21,7,4,12] and numerous efficient algorithms for particular learning problems [8,10,30,23,11,31].
In parallel, there has been a significant amount of work on privately releasing synthetic data based on a true dataset while preserving the answers to large numbers of statistical queries [5,13,29,14,18,17]. These results are extremely strong in an information theoretic sense: they ensure the consistency of the synthetic data with respect to an exponentially large family of statistics. But, all of these algorithms (including the notable multiplicative weights algorithm of Hardt and Rothblum [18], which achieves the theoretically optimal accuracy and runtime) have running time exponential in the dimension of the data. With standard cryptographic assumptions, this is necessary in the worst case for mechanisms that answer many arbitrary statistical queries [32].
Nevertheless, there have been some experimental evaluations of these approaches on real datasets. Most related to our work is the evaluation of the MWEM mechanism by Hardt et al. [19], which is based on the private multiplicative weights mechanism [18]. This algorithm is inefficient (it manipulates a probability distribution over a set exponentially large in the dimension of the data space) but with some heuristic optimizations, Hardt et al. [19] were able to implement the multiplicative weights algorithm on several real datasets with up to 77 attributes (and even more when the queries are restricted to take positive values only on a small number of disjoint groups of features). However, it seems difficult to scale this approach to higher dimensional data.
Another family of query release algorithms are based on the Matrix Mechanism [25,24]. The runtime guarantees of the matrix mechanism are similar to the approaches based on multiplicative weights-the algorithm manipulates a "matrix" of queries with dimension exponential in the number of features. Yaroslavtsev et al. [34] evaluate an approach based on this family of algorithms on low dimensional datasets, but scaling to high dimensional data also seems challenging.
Our algorithm is inspired by the view of the synthetic data generation problem as a zero-sum game, first proposed by Hsu et al. [20]. In this interpretation, Hardt et al. [19] solves the game by having a data player use a no-regret learning algorithm, while the query player repeatedly best responds by optimizing over queries. In contrast, our algorithm swaps the roles of the two players: the query player now uses the no-regret learning algorithm, whereas the data player now finds best responses by solving an optimization problem. This is reminiscent of "Boosting for queries," proposed by Dwork et al. [14]; the main difference is that our optimization problem is over single records rather than sets of records. As a result, our optimization can be handled non-privately.

Differential privacy background
Differential privacy has become a standard algorithmic notion for protecting the privacy of individual records in a statistical database. It formalizes the requirement that the addition or removal of a data record does not change the probability of any outcome of the mechanism by much.
We consider databases which are multisets of elements from an abstract domain X , representing the set of all possible data records. We often consider elements in X as bit-strings of length d. Two databases D, D ⊂ X are neighboring if they differ in a single data element: i.e., their symmetric difference D D is at most 1.
Definition 2.1 (Dwork et al. [15]). A mechanism M : X n → R satisfies (ε, δ)-differential privacy if for every S ⊆ R and for all neighboring databases D, D ∈ X n , the following holds: If δ = 0 we say M satisfies ε-differential privacy.
Definition 2.2. The (global) sensitivity of a query Q is its maximum difference when evaluated on two neighboring databases: In this paper, we consider the private release of information for the classes of linear queries, which have sensitivity 1/n.
The following composition theorem is a fundamental tool for private algorithm analysis: we can bound the privacy cost of an algorithm as a function of the privacy costs of its subcomponents. Lemma 2.4 (Dwork et al. [14]). Let M 1 , . . . , M k be such that each for any δ ∈ (0, 1).

The query release game
The analysis of our algorithm relies on the interpretation of query release as a two player, zero-sum game [20]. In the present section, we review this idea and related tools.

Game definition
Suppose we want to answer all queries in Q. For each query q ∈ Q, we can form the negated query q, which takes values q(D) = 1 − q(D) for every database D. Equivalently, for a linear query defined by a predicate ϕ, the negated query is defined by the negation ¬ϕ of the predicate. For the remainder, we will assume that Q is closed under negation; if not, we may add negated copies of each query to Q. Let there be two players, whom we call the data player and query player. The data player has action set equal to the data universe X , while the query player has action set equal to the query class Q. Given a play x ∈ X and q ∈ Q, we let the payoff be where D is the true database. As a zero sum game, the data player will try to minimize the payoff, while the query player will try to maximize the payoff.

Equilibrium of the game
Let ∆(X ) and ∆(Q) be the set of probability distributions over X and Q. We consider how well each player can do if they randomize over their actions, i.e., if they play from a probability distribution over their actions. By von Neumann's minimax theorem, for any two player zero-sum game, where is the expected payoff. The common value is called the value of the game, which we denote by v A . Intuitively, von Neumann's theorem states that there is no advantage in a player going first: the minimizing player can always force payoff at most v A , while the maximizing player can always force payoff at least v A . This suggests that each player can play an optimal strategy, assuming best play from the opponentthis is the notion of equilibrium strategies, which we now define. We will soon interpret these strategies as solutions to the query release problem.
Definition 3.1. Let α > 0. Let A be the payoffs for a two player, zero-sum game with action sets X , Q. Then, a pair of strategies u * ∈ ∆(X ) and w * ∈ ∆(Q) form an α-approximate mixed Nash equilibrium if If the true database D is normalized to be a distribution D in ∆(X ), then D always has zero payoff: Hence, the value of the game v A is at most 0. Also, for any data strategy u, the payoff of query q is the negated payoff of the negated query q: which is A(u, q). Thus, any query strategy that places equal weight on q and q has expected payoff zero, so v A is at least 0. Hence, v A = 0. Now, let (u * , w * ) be an α-approximate equilibrium. Suppose that the data player plays u * , while the query player always plays query q. By the equilibrium guarantee, we then have A(u * , q) ≤ α, but the expected payoff on the left is simply q(D) − q(u * ). Likewise, if the query player plays the negated query q, This is precisely what we need for query release: we just need to privately calculate an approximate equilibrium.

Solving the game
To construct the approximate equilibrium, we will use the multiplicative weights update algorithm (MW). 2 This algorithm maintains a distribution over actions (initially uniform) over a series of steps. At each step, the MW algorithm receives a (possibly adversarial) loss for each action. Then, MW reweights the distribution to favor actions with less loss. The algorithm is presented in Algorithm 1.

Algorithm 1 The Multiplicative Weights Algorithm
Let η > 0 be given, let A be the action space Initialize A 1 uniform distribution on A For t = 1, 2, . . . , T : Receive loss vector t For each a ∈ A: For our purposes, the most important application of MW is to solving zero-sum games. Freund and Schapire [16] showed that if one player maintains a distribution over actions using MW, while the other player selects a best-response action versus the current MW distribution (i.e., an action that maximizes his expected payoff), the average MW distribution and empirical best-response distributions will converge to an approximate equilibrium rapidly.
Interpreted this way, the private multiplicative weights algorithm of Hardt and Rothblum [18] (and the MWEM algorithm of Hardt et al. [19]) uses MW for the data player, while the query player plays best responses. For privacy, their algorithm selects the query best-responses privately via the exponential mechanism of McSherry and Talwar [26]. Our algorithm plays the same game, but with the roles reversed.

Dual query release
At a high level, our algorithm solves the query release game using an approach dual to the MWEM algorithm of Hardt et al. [19]. While MWEM uses a no-regret algorithm to maintain the data player's distribution, we will instead use a no-regret algorithm for the query player's distribution. Likewise, instead of finding a maximum payoff query at each round, our algorithm selects a minimum payoff record at each turn. The full algorithm can be found in Algorithm 2.
Our privacy argument differs slightly from the analysis for MWEM. There, the data distribution is public, and finding a query with high error requires access to the private data. Our algorithm instead maintains a distribution Q over queries which depends directly on the private data, so we cannot use Q directly. Instead, we argue that queries sampled from Q are privacy preserving. Then, we can use a non-private optimization method to find a minimal error record versus queries sampled from Q. We then trade off privacy (which degrades as we take more samples) with accuracy (which improves as we take more samples, since the distribution of sampled queries converges to Q).
Given known hardness results for the query release problem [32], our algorithm must have worst-case runtime polynomial in the universe size |X |, so is not theoretically more efficient than prior approaches. In fact, even compared to prior work on query release (e.g., Hardt and Rothblum [18]), our algorithm has a worse accuracy guarantee.
However, our approach has important practical benefits, the most important being that that hard step can be handled with standard, non-private solvers. The rest of our algorithm runs in time linear in the number of queries, independent of the dimension of the data.
The iterative structure of our algorithm, combined with our use of constraint solvers, allows for several heuristics improvements. For instance, we may run for fewer iterations than predicted by theory. Or, if the optimization problem turns out to be hard (even in practice), we can stop the solver early at a suboptimal (but often still good) solution. These heuristic tweaks can improve accuracy beyond what is guaranteed by our accuracy theorem, while always maintaining a strong provable privacy guarantee.

Privacy
The privacy proofs are largely routine, based on the composition theorems. Rather than fixing ε and solving for the other parameters, we present the privacy cost ε as function of parameters T, s, η. Later, we will tune these parameters for our experimental evaluation. We will use the privacy of the following mechanism (due to McSherry and Talwar [26]) as an ingredient in our privacy proof. The exponential mechanism is ε-differentially private.
We first prove pure ε-differential privacy.
Proof. We will argue that sampling from Q t is equivalent to running the exponential mechanism with some quality score. At round t, let {x i } for i ∈ [t − 1] be the best responses for the previous rounds. Let r(q, d) be defined by where q ∈ Q is a query and D is the true database. This function is evidently ((t − 1)/n)-sensitive in D: changing D changes each q(D) by at most 1/n. Now, note that sampling from Q t is simply sampling from the exponential mechanism, with quality score r(q, D). Thus, the privacy cost of each sample in round t is ε t = 2η(t − 1)/n (Definition 4.1). By the standard composition theorem (Lemma 2.4), the total privacy cost is We next show that DualQuery is (ε, δ)-differentially private, for a much smaller ε.
Again, note that sampling from Q t is simply sampling from the exponential mechanism, with a (T − 1)/nsensitive quality score. Thus, the privacy cost of each sample is ε = 2η(T − 1)/n (Definition 4.1). We plug in k = s(T − 1) samples, as in the first round our samplings are 0-differentially private.

Accuracy
The accuracy proof proceeds in two steps. First, we show that "average query" formed from the samples is close to the true weighted distribution Q t . We will need a standard Chernoff bound.  samples { q i } from p, and let q be the aggregate query Define the true weighted answer Q(x) to be Then with probability at least 1 − β, we have |q(x) − Q(x)| < α/4 for every x ∈ X .
Proof. For any fixed x, note that q(x) is the average of random variables q 1 (x), . . . , q s (x). Also, note that E[q(x)] = Q(x). Thus, by the Chernoff bound (Lemma 4.4) and our choice of s, By a union bound over x ∈ X , this equation holds for all x ∈ X with probability at least 1 − β.
Next, we show that we compute an approximate equilibrium of the query release game. In particular, the record best responses form a synthetic database that answer all queries in Q accurately. Note that our algorithm doesn't require an exact best response for the data player; an approximate best response will do. Theorem 4.6. With probability at least 1−β, DualQuery finds a synthetic database that answers all queries in Q within additive error α.
Proof. As discussed in Section 3, it suffices to show that the distribution of best responses x 1 , . . . , x T forms is an α-approximate equilibrium strategy in the query release game. First, we set the number of samples s according to in Lemma 4.5 with failure probability β/T . By a union bound over T rounds, sampling is successful for every round with probability at least 1 − β; condition on this event.
Since we are finding an α/4 approximate best response to the sampled aggregate query q, which differs from the true distribution by at most α/4 (by Lemma 4.5), each x i is an α/4 + α/4 = α/2 approximate best response to the true distribution Q t . Since q takes values in  Solving for α, we find for γ < β/T .

Case study: 3-way marginals
In our algorithm, the computationally difficult step is finding the data player's approximate best response against the query player's distribution. As mentioned above, the form of this problem depends on the particular query class Q. In this section, we first discuss the optimization problem in general, and then specifically for the well-studied class of marginal queries.

The best-response problem
Recall that the query release game has payoff A(x, q) defined by Equation (1); the data player tries to minimize the payoff, while the query player tries to maximize it. If the query player has distribution Q t over queries, the data player's best response minimizes the expected loss: For privacy reasons, the data player actually plays against the distribution of samples q 1 , . . . , q s . So, the best-response problem is since D is fixed and q i are linear queries. By Theorem 4.6 it even suffices to find an approximate maximizer, in order to guarantee accuracy.

3-way marginal queries
To look at the precise form of the best-response problem, we consider 3-way marginal queries. We think of records as having d binary attributes, so that the data universe |X | is all bitstrings of length d. We write x i for x ∈ X to mean the ith bit of record x. Though everything we do will apply to general k-way marginals, for concreteness we work with 3-way marginals. Recall that the query class Q includes each query and its negation. So, we also have negated conjunctions: Given sampled conjunctions { u i } and negated conjunctions { v i }, the best-response problem is In other words, this is a MAXCSP problem-we can associate a clause to each conjunction: and we want to find x ∈ {0, 1} d satisfying as many clauses as possible. 3 Since most solvers do not directly handle MAXCSP problems, we convert this optimization problem into a more standard, integer program form. We introduce a variable x i for each literal x i , a variable c i for each sampled conjunction u i , a variable d i for each sampled negated conjunction v i , and we form the following integer program.  We evaluate DualQuery on a large collection of 3-way marginal queries on several real datasets (Figure 1) and high dimensional synthetic data. Adult (census data) and KDD99 (network packet data) are from the UCI repository [2], and have a mixture of discrete (but non-binary) and continuous attributes, which we discretize into binary attributes. We also use the (in)famous Netflix [28] movie ratings dataset, with more than 17,000 binary attributes. More precisely, we can consider each attribute (corresponding to a movie) to be 1 if a user has watched that movie, and 0 otherwise.
Rather than set the parameters as in Algorithm 2, we experiment with a range of parameters. For instance, we frequently run for fewer rounds (lower T ) and take fewer samples (lower s). As such, the accuracy guarantee (Theorem 4.6) need not hold for our parameters. However, we find that our algorithm gives good error, often much better than predicted. In all cases, our parameters satisfy the privacy guarantee Theorem 4.3.

Accuracy
We evaluate the accuracy of the algorithm on 500,000 3-way marginals on Adult, KDD99 and Netflix. We report maximum error in Figure  For the Netflix dataset, we adopt the same heuristic except we set s to be 5000. The accuracy improves noticeably when ε increases from 0.25 to 1 across 3 datasets, and the improvement diminishes gradually with larger ε. With larger sizes, both KDD99 and Netflix datasets allow DualQuery to run with more steps and get significantly better error.

Scaling to More Queries
Next, we evaluate accuracy and runtime when varying the number of queries. We use a set of 40,000 to 2 million randomly generated marginals Q on the KDD99 dataset and run DualQuery with (1, 0.001)privacy. For all experiments, we use the same set of parameters: η = 1.2, T = 170 and s = 1750. By Theorem 4.3, each run of the experiment satisfies (1, 0.001)-differential privacy. These parameters give stable performance as the query class Q grows. As shown in Figure 3, both average and max error remain mostly stable, demonstrating improved error compared to simpler perturbation approaches. For example, the Laplace mechanism's error growth rate is O( |Q|) under (ε, δ)-differential privacy. The runtime grows almost linearly in the number of queries, since we maintain a distribution over all the queries.

Scaling to Higher Dimensional Data
Finally, we evaluate accuracy and runtime behavior for data dimension ranging from 50 to 512,000. We evaluate DualQuery under (1, 0.001)-privacy on 100,000 3-way marginals on synthetically genearted datasets. We report runtime, max, and average error over 3 runs in Figure 4; note the logarithmic scale for attributes axis. We do not include query evaluation in our time measurements-this overhead is common to all approaches that answer a set of queries.
When generating the synthetic data, one possibility is to set each attribute to be 0 or 1 uniformly at random. However, this generates very uniform synthetic data: a record satisfies any 3-way marginal with probability 1/8, so most marginals will have value near 1/8. To generate more challenging and realistic data, we pick a separate bias p i ∈ [0, 1] uniformly at random for each attribute i. For each data point, we then set attribute i to be 1 independently with probability equal to p i . As a result, different 3-way marginals have different answers on our synthetic data.
For parameters, we fix step size η to be 0.4, and increase the sample size s with the dimension of the data (from 200 to 50,000) at the expense of running fewer steps. For these parameters, our algorithm is (1, 0.001)-differentially private by Theorem 4.3. With this set of parameters, we are able to obtain 8% average error in an average of 10 minutes of runtime, excluding query evaluation.

Methodology
In this section, we discuss our experimental setup in more detail.
Implementation details. The implementation is written in OCaml, using the CPLEX constraint solver. We ran the experiments on a mid-range desktop machine with a 4-core Intel Xeon processor and 12 Gb of RAM. Heuristically, we set a timeout for each CPLEX call to 20 seconds, accepting the best current solution if we hit the timeout. For the experiments shown, the timeout was rarely reached.
Data discretization. We discretize KDD99 and Adult datasets into binary attributes by mapping each possible value of a discrete attribute to a new binary feature. We bucket continuous attributes, mapping each bucket to a new binary feature. We also ensure that our randomly generated 3-way marginal queries are sensible (i.e., they don't require an original attribute to take two different values).
Setting free attributes. Since the collection of sampled queries may not involve all of the attributes, CPLEX often finds solutions that leave some attributes unspecified. We set these free attributes heuristically: for real data, we set the attributes to 0 as these datasets are fairly sparse; 5 for synthetic data, we set attributes to 0 or 1 uniformly at random. 6 Parameter tuning. DualQuery has three parameters that can be set in a wide variety of configurations without altering the privacy guarantee (Theorem 4.3): number of iterations (T ), number of samples (s), and learning rate (η), which controls how aggressively to update the distribution. For a fixed level of ε and δ, there are many feasible private parameter settings.
While the accuracy guarantee (Theorem 4.6) may not hold for a particular set of parameters, the empirical accuracy is much better than predicted. Performance depends strongly on the choice of parameters: T has an obvious impact, increasing s increases the number of constraints in the integer program for CPLEX. We have investigated a range of parameters; for the experiments we have used some informal heuristics coming from our observations. For sparse datasets like the ones in Figure 1, with larger η (in the range of 1.5 to 2.0) and smaller s (in the same order as the number of attributes), we obtain good accuracy when we set the free attributes to be 0. But for denser data like our synthetic data, we get better accuracy when we have smaller η (around 0.4) and set the free attributes randomly. As for runtime, we observe that CPLEX could finish running quickly (in seconds) when the sample size is in about the same range as the number of attributes (factor of 2 or 3 different).
Parameter setting should be done under differential privacy for a truly realistic evaluation. Overall, we do not know of a principled approach to handling this issue; the problem of private parameter tuning is an area of active research (see e.g., Chaudhuri and Vinterbo [9]).

A Case study: Parity queries
In this section, we show how to apply DualQuery to another well-studied class of queries: parities. Each specified by a subset S of features, these queries measure the number of records with an even number of bits on in S compared to the number of records with an odd number of bits on in S. Like before, we can define a negated k-wise parity query: q S (x) = +1 : odd number of x i = +1 for i ∈ S −1 : otherwise.
Barak et al. [3] observed that answering k-way marginal queries can be reduced to answering k-wise parity queries to the same accuracy, in the following sense.
Theorem A.2 (Barak et al. [3]). Let q S be a k-way marginal query specified by the set of features S, and let D be a database of records. Then, where p T is the parity query for features T .
Note that the coefficients sum to 1: hence, answering parity queries with additive error α is enough to answer marginal queries with additive error α. We now consider how to handle these queries with our algorithm. For the remainder, we specialize to k = 3. Like marginal queries, it suffices to give the bestresponse optimization problem; unlike marginal queries, we need to handle k-wise parities for every k ≤ 3 in order to apply Theorem A.2.
Given sampled parity queries { u i } and negated parity queries { v i }, the best response problem is to find the record x ∈ X that takes value 1 on as many of these queries as possible. We can construct an integer program for this task: introduce d variables x i , and two variables c q , d q for each sampled query. The following integer program encodes the best-response problem.
Consider the (non-negated) parity queries first. The idea is that each variable c i can be set to 1 exactly when the corresponding parity query takes value 1, i.e., when x has an even number of bits in S set to +1. Since |S| ≤ 3, this even number will either be 0 or 2, hence is equal to 2d i for d i ∈ {0, 1}. A similar argument holds for the negated parity queries.