NP-hardness of maximum set cover with even/odd coverage requirement Given universal set $U=X \cup Y = \{x_1, \ldots, x_{n_1} \} \cup \{y_1, \ldots, y_{n_2}\}$ where $X \cap Y = \emptyset$
and sets $\mathcal{S}=\{s_1, \ldots, s_m\}$ such that $s_i \subseteq U$ for all $i=1,\ldots,m$ and integer $k \in \mathbb{Z}^{+}$.

Find $\mathcal{C} \subseteq \mathcal{S}$ (denote $Z = \cup_{s \in \mathcal{C}} s$) that maximizes

$|\{ z \in Z \mid (z \in X \text{ and is covered even times by } \mathcal{C}) \text{ or } (z \in Y \text{ and is covered odd times by } \mathcal{C} )\}|$

s.t 


$|\mathcal{C}| = k$ 


In other words, we consider an element to be covered if it satisfies the odd/even coverage requirement according to its membership ($X$ or $Y$). 

This problem differs from the standard maximum set cover in the definition of "covering an element". 

Is this problem NP-hard? Is so, how to prove it?
One can rephrase your question as follows:


  Given a matrix $A$ and a vector $b$ over $GF(2)$, find a vector $x$ of weight $k$ such that $|Ax-b|$ is as small as possible.


A very similar problem was shown to be NP-complete by Stadnicki on cstheory:


  Given a matrix $A$ and a vector $b$ over $GF(2)$, does there exist a vector $x$ of weight at most $k$ such that $Ax = b$?


This implies that your problem is intractable as well.