{"id":"4bb5e25e-01d2-4eeb-bdb2-1b93c3104582","arxiv_id":"2507.08758","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"Fair epsilon-nets and fair geometric hitting sets can be computed with provable size overhead, while some custom-ratio fair epsilon-samples are impossible.","lead":"Computers often summarize large datasets with a small sample that must hit every large query region, but those samples can underrepresent demographic groups. This paper adds fairness to that geometric tool, giving algorithms whose summaries preserve group proportions at a small extra cost in size.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The FMC top-up cannot realize exact ratios as stated: (1+v)τ_cλ is generally non-integral and may exceed |X_c|, so Theorem 6, and Theorem 22 via Theorem 7, do not follow from Algorithm 1.","rationale":"The central claim depends on outputting exact group ratios. The top-up step is the only mechanism enforcing fairness in the sampling-based results, and Theorem 22's FGHS reduction goes through the weighted version of that same step. The integrality/supply gap is not a matter of tighter constants: for generic φ the multiplier 1+v is irrational, so the algorithm's own arithmetic cannot be executed exactly. This is why I chose it over other issues, such as the FSM wording about monochromatic leaves, which may be reconcilable by reinterpreting 'fair' at each node as 'same proportion as the descendants'. The reader's weakest assumption identified exactly the same integrality/supply condition, so my read agrees with the reader's verdict. I keep the verdict UNCHANGED (CONDITIONAL) rather than moving to REJECT because the construction is likely salvageable by adding integrality/supply assumptions to the theorem statements, by rounding the ratios, or by explicitly relaxing Definition 4 to approximate fairness; however, as written, the stated theorems are not established.","tokens_in":27162,"tokens_out":12663,"duration_ms":156951,"concrete_test":"Compute the top-up counts for Algorithm 1 on the instance ε = 1, φ = 0.1, k = 2, d = 1, n = 256 (128 points per color), with λ = 23. The prescribed addition is (1+2 ln 40)·(1/2)·23 ≈ 96.34 points per color, a non-integer; therefore the algorithm cannot return integer color counts satisfying |S_c|/|S| = 1/2. If the authors instead round, the output ratio will deviate from τ, contradicting Definition 4. This check settles whether exact-ratio fairness is achievable by the published algorithm as written.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Definition 4 demands the exact identity |S_c|/|S| = τ_c. Algorithm 1 (§4.1) tops up each color with max((1+v)·|X_c|/|X|·λ − |N_c|, 0) and Lemma 4 concludes |S| = (1+v)λ and therefore |S_c|/|S| = |X_c|/|X|. This conclusion is valid only when every (1+v)τ_cλ is an integer and at most |X_c|. Section 3 imposes only τ_cλ ≥ 1 and power-of-two group sizes; the integrality and supply conditions are never stated. For φ = 0.1, k = 2, the parameter v = 2 ln(2k/φ) = 2 ln 40, so 1+v is irrational; with rational τ_c the target (1+v)τ_cλ is irrational for every integer λ. Example: ε = 1, φ = 0.1, d = 1, n = 256 with 128 points per color gives λ = 23 from Theorem 1, but the top-up target per color is (1+2 ln 40)·(1/2)·23 ≈ 96.34, a fractional count. Algorithm 1 as written cannot produce a set of size (1+v)λ ≈ 192.69, nor can it satisfy Definition 4. The weighted variant in §4.1.1 has a second defect: it samples with probability W_c but tops up with |X_c|/|X|, so it enforces unweighted proportions, not the weighted τ_c = W_c required by Theorem 7. Since Theorem 22 reduces FGHS to Theorem 7, the hitting-set approximation inherits both failures. Experimental 'zero unfairness' figures do not repair the theorems, and the promised code link is absent.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces fair versions of epsilon-nets, epsilon-samples, and geometric hitting set under demographic parity (DP) and custom-ratio (CR) constraints. It proposes a Monte-Carlo sampling algorithm (Section 4.1), a deterministic discrepancy-based algorithm (Section 4.2), and a sketch-and-merge variant (Section 4.2.2) for fair epsilon-nets; a reduction from CR fair epsilon-nets to fair geometric hitting set (Section 4.3); a negative result for fair epsilon-samples with CR constraints (Section 4.4, Appendix A); and an LP-based reduction of FGHS to weighted fair epsilon-nets (Section 5). The main theoretical claims are an O(log(k/phi)) size overhead over standard epsilon-nets for the Monte-Carlo algorithm (Theorem 6), a deterministic fair epsilon-net of size O(d/epsilon log(d/epsilon)) (Theorems 13 and 17), and an O(max{log 1/phi, d log OPT_FGHS} log(k/phi)) approximation for FGHS (Theorem 22). Experiments on real and synthetic data report near-zero unfairness with modest size increases.","tokens_in":27599,"tokens_out":14528,"duration_ms":156236,"significance":"The paper addresses a timely and natural question: how to make geometric approximation constructions group-fair. The high-level approach—combining Chernoff-based top-up sampling, discrepancy-based halving with fair matchings, and LP rounding—is sensible, and the reduction of fair geometric hitting set to weighted fair epsilon-nets is elegant. The paper uses classical external tools (Chernoff bounds, Haussler-Welzl theorem, discrepancy lemmas) with no fitted parameters, and the Appendix A infeasibility result is a useful limitation statement. However, the correctness of the central theorems rests on several conditions that are not stated in the manuscript: exact integrality and per-color supply for the Monte-Carlo top-up, a mismatch between the sampling distribution and the top-up ratios in the weighted variant, and missing per-color size conditions for the deterministic halving procedures. These are load-bearing gaps, not mere presentation issues. The experimental validation is helpful but cannot substitute for the missing hypotheses. If the stated conditions and fixes are supplied, the paper would be a solid contribution to fair geometric data summarization.","major_comments":[{"comment":"The proof of Lemma 4 requires that for every color c the target count (1+v)τ_c λ is an integer and does not exceed |X_c|, because Algorithm 1 adds exactly (1+v)τ_c λ − |N_c| points of color c; neither condition is stated or guaranteed. For DP, τ_c = |X_c|/|X|, and with v = 2 ln(2k/phi) generally irrational, (1+v)τ_c λ is typically non-integral; for example, with epsilon=1, phi=0.1, k=2, n=256, and 128 points per color, lambda=23 (from Theorem 1) gives a per-color target of (1+2 ln 40)·23/2 ≈ 96.34 points. Algorithm 1 cannot add a fractional number of points, so the exact-ratio condition |S_c|/|S| = τ_c in Definition 4 is not achieved and Theorem 6 does not follow as stated.","section":"§4.1, Algorithm 1, Lemma 4"},{"comment":"In the weighted fair Monte-Carlo algorithm, the initial sample N is drawn with probabilities proportional to the point weights w_i, so the expected count for color c is lambda W_c, where W_c = Σ_{p_i in X_c} w_i. The top-up step, however, adds (1+v)|X_c|/|X| lambda − |N_c| points, using the unweighted input proportions rather than the weighted DP ratios τ_c = W_c that the section defines. The Chernoff bound stated in that subsection likewise uses |X_c|/|X| as the mean, which is inconsistent with the sampling distribution. As a result, the output enforces unweighted ratios rather than the required weighted ratios, and Theorem 7 is not proven.","section":"§4.1.1"},{"comment":"The FGHS algorithm in Section 5 constructs weights w_i from the LP (3) and then runs the algorithm from Theorem 7 on (X,R) with those weights and with DP constraints T. Since Theorem 7 is not established (see the two preceding comments), the size guarantee O(max{log 1/phi, d log OPT_FGHS} · log(k/phi) · OPT_FGHS) in Theorem 22 does not follow. The same applies to the CR fair epsilon-net bound in Theorem 19, which depends on Theorem 22.","section":"§5, Theorem 22"},{"comment":"The discrepancy-based algorithms construct fair matchings that pair only points of the same color at every halving level. For the algorithm of Section 4.2, this requires each color count to be even at each of the U = log(n/(c0 d/epsilon log(d/epsilon))) iterations; the assumption |X_c| = 2^{xi_c} alone does not imply U ≤ xi_c, so a color may be left with one point before the process terminates, making the fair matching impossible. In the sketch-and-merge algorithm of Section 4.2.2, the initial partition requires every color to have size divisible by 2^p and p ≤ xi_c, which is not stated. The proofs of Lemmas 10, 14, and 16, and hence Theorems 13 and 17, need explicit sufficient conditions on the group sizes.","section":"§4.2 and §4.2.2"}],"minor_comments":[{"comment":"In Definition 1, the condition '|N ∩ R| ≥ 0' is trivially true; it should be '|N ∩ R| ≥ 1' (i.e., the net must intersect every heavy range), otherwise the definition does not characterize an epsilon-net.","section":"Definition 1"},{"comment":"The text says 'Draw a set N of lambda ... uniform random samples (with replacement)', but Algorithm 1 states 'N ← a random subset of size lambda'; with replacement sampling produces a multiset, which is inconsistent with the later set operations and with the definition of a subset. Please clarify.","section":"§4.1"},{"comment":"The derivation of the probability bound uses the inequality exp(−v²/(2+v)) ≤ exp(−ln(k/(phi/2))), which holds only when ln(2k/phi) ≥ 1; for small values of 2k/phi (e.g., k=1 and phi close to 1) the claimed bound is off by a constant. The proof should use a Chernoff variant that is valid for all parameter ranges or adjust the constant v.","section":"Lemma 3"},{"comment":"The statement 'The code and other artifacts are publicly available' is followed only by the footnote 'Github repository' with no URL; please provide the actual link for reproducibility.","section":"Section 7"}],"recommendation":"major_revision","confidential_remarks":"The paper addresses a relevant problem and contains interesting ideas, but the central theorems currently have unstated feasibility assumptions and a mismatch in the weighted variant. The authors should either relax the fairness definition to an approximate ratio or add explicit integrality and supply conditions, and correct the weighted top-up to use W_c. The deterministic algorithms also need clear sufficient conditions on per-color counts. With these fixes, the paper could be suitable for publication; as it stands, the main results are not fully supported."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First thing to know: this is the first paper to put fairness constraints on epsilon-nets, epsilon-samples, and geometric hitting sets, and the fair-matching trick in the discrepancy algorithm is a nice idea. The bad news is that the main Monte Carlo theorem (Theorem 6) and everything stacked on it (Theorems 7 and 22) are not supported by the algorithm as written.\n\nWhat's actually new and good: the problem formulation is natural and will likely be reused. The discrepancy-based construction that pairs points of the same color before halving is clean and, under the power-of-two assumptions the authors state, it does preserve exact demographic ratios while producing a standard-size epsilon-net. The reduction from fair geometric hitting set to weighted fair epsilon-nets via the LP is conceptually appealing, and the infeasibility example for fair epsilon-samples under custom ratios is a useful cautionary result.\n\nWhere it falls down: Algorithm 1 tops up each color to (1+v)·(|X_c|/|X|)·lambda and Lemma 4 concludes the output has exactly these ratios. That conclusion only holds if every (1+v)·tau_c·lambda is an integer and no larger than |X_c|. Neither condition is stated or generally true; for phi=0.1, k=2, v=2 ln 40, so (1+v) is irrational and the target count is fractional. You cannot top up to a fractional number of points, so the exact-ratio guarantee in Definition 4 is unattainable as written. The weighted version in §4.1.1 is worse: it samples with probability proportional to W_c but tops up with |X_c|/|X|, so it enforces unweighted demographic parity, not the weighted ratios that Theorem 7 and the FGHS reduction need. That makes Theorem 22 unsupported. There is also a likely typo in Algorithm 2's loop condition (the stop condition is missing the 1/eps^2 factor), and the code link promised in Section 7 is absent.\n\nProportionately: the discrepancy-based section looks sound under the stated power-of-two assumptions; the sketch-and-merge follows from the same ideas; and the experiments are at least suggestive that a repaired algorithm would work in practice. The problems are concentrated in the sampling-based and weighted sections, but those sections carry the main theorem and the hitting-set reduction.\n\nWho should read it: anyone working on fair data summarization or geometric approximation with group constraints. It deserves a serious referee — the editor should send it out — but the authors need to fix the integrality and supply conditions, correct the weighted topping-up formula, and provide the code before the theorems can be trusted.","headline":"First fair-epsilon-net paper with a genuinely new formulation and a nice fair-matching construction, but the main Monte Carlo theorem breaks on unstated integrality/supply conditions and the weighted variant enforces the wrong fairness ratios.","tokens_in":28079,"tokens_out":4608,"would_cite":false,"duration_ms":49992,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper shows that epsilon-nets and geometric hitting sets can be made fair by preserving exact demographic group ratios, with only a logarithmic increase in output size for nets, and it introduces a reduction that yields an $O(\\log…","keywords":["fair epsilon-net","geometric hitting set","demographic parity","custom-ratio fairness","discrepancy method","VC dimension","random sampling","linear programming rounding"],"falsifier":"Build a range space with two colors where one color has a single point, choose a target ratio $\\tau$ and $\\varepsilon$ such that $(1+v)\\tau\\lambda$ exceeds that group's size, and run the fair Monte-Carlo algorithm: the top-up step cannot add the demanded number of minority points, so the output either misses the exact ratio or has size larger than the theorem allows.","tokens_in":26991,"feed_emoji":"⚖️","tokens_out":8784,"duration_ms":107794,"temperature":0.7,"pith_summary":"This paper asks whether the standard geometric approximation tools used to summarize large datasets can be made fair, meaning the compact subset they return is forced to preserve the demographic proportions of the original data. The answer, for $\\varepsilon$-nets and geometric hitting sets, is yes: a randomized sampling algorithm produces a fair $\\varepsilon$-net in linear time whose size exceeds the unfair optimum by only a factor logarithmic in the number of groups, while a deterministic discrepancy-based algorithm removes the randomness with no added asymptotic size. A reduction through linear programming gives a fair geometric hitting set within an $O(\\log \\mathsf{OPT} \\cdot \\log k)$ factor of optimum, and the paper also shows a limit: once ranges can separate a demographic group, arbitrary custom target ratios become impossible for $\\varepsilon$-samples, so demographic parity is the safer notion for sampling-based summaries.","feed_headline":"Fair epsilon-nets add only a log k size penalty","feed_subtitle":"Exact demographic ratios in linear time, and a log OPT log k approximation for fair hitting sets.","key_machinery":"The two load-bearing mechanisms are the top-up sample and the fair matching. The top-up sample draws $\\lambda$ points uniformly at random, using the classical size that guarantees an unfair $\\varepsilon$-net, then for each color $c$ adds enough extra points of that color to reach the target count $(1+v)(|X_c|/|X|)\\lambda$ with $v = 2\\ln(k/\\varphi)$. A Chernoff bound guarantees that no color overshoots its quota with probability at least $1-\\varphi/2$, so the output is exactly proportional and has size $(1+v)\\lambda$. The fair matching is the discrepancy-method analogue: at each halving step, points are paired only within the same demographic group, so keeping one point from each pair halves every group's count and preserves ratios exactly; repeated halving yields an $\\varepsilon$-net by the standard discrepancy argument. The reduction from custom-ratio fairness to the weighted fair $\\varepsilon$-net runs through a linear program whose variables are point weights; the LP's optimal value supplies the $\\varepsilon$ and the group-total weights supply the demographic-parity constraint, turning the hitting set into a weighted fair $\\varepsilon$-net instance that the sampling algorithm rounds.","core_discovery":"The central claim is that fairness constraints can be layered onto classical geometric approximation problems without losing their guarantees. For a range space of VC dimension $d$ over $n$ points partitioned into $k$ demographic groups, a uniformly random sample of size $\\lambda = O\\!\\big((1/\\varepsilon)\\max\\{\\log(1/\\varphi), d\\log(1/\\varepsilon)\\}\\big)$, topped up with the right number of extra points from each under-represented group, is an $\\varepsilon$-net that exactly matches the input group ratios with probability at least $1-\\varphi$, running in $O(n)$ time and producing size $O(\\lambda \\log(k/\\varphi))$. The same top-up trick extends to weighted points. When randomness is undesirable, the discrepancy method can be adapted by pairing points of the same demographic group at every halving step, which preserves group ratios exactly and gives a deterministic fair $\\varepsilon$-net of size $O\\!\\big((d/\\varepsilon)\\log(d/\\varepsilon)\\big)$. The paper further shows that fair geometric hitting set with arbitrary target ratios reduces to a weighted fair $\\varepsilon$-net instance whose LP relaxation is rounded by the fair sampling algorithm, yielding an $O\\!\\big(\\max\\{\\log(1/\\varphi), d\\log \\mathsf{OPT}\\} \\cdot \\log(k/\\varphi)\\big)$-approximation. Finally, fair $\\varepsilon$-samples under arbitrary custom ratios are shown to be infeasible in general, because a range that isolates one group pins that group's sample share within an $\\varepsilon$ window of its input share.","pith_inferences":["This suggests the top-up formula could be made robust to non-integral target counts by allowing a one-point slack per color, at a negligible size cost, which would widen applicability beyond the exact-ratio setting.","The fair-matching halving hints at a general template: enforce fairness at every node of a divide-and-conquer hierarchy, which could be inserted into other hierarchical geometric constructions such as partition trees or coresets.","The LP-to-sampling rounding could generalize to other covering LPs with color constraints, potentially offering a unified scheme for fair covering problems where randomized rounding is already used.","The infeasibility result for $\\varepsilon$-samples implies that for sampling-based fairness the safer target is demographic parity, and any custom-ratio requirement must be validated against the dataset's geometry before a sampling-based summary is used."],"forward_implications":["A data curator can build a fair summary of a large table for approximate range-query answering in $O(n)$ time, with zero measured group-ratio distortion and only a $\\log k$ increase in summary size.","The deterministic discrepancy-based variant gives the same exact-ratio guarantee without randomization, at the cost of $O(n m \\log n)$ time when all ranges are materialized.","Fair geometric hitting sets (and, by geometric duality, fair set covers) admit approximation factors that depend on $\\log \\mathsf{OPT}$ and $\\log k$ rather than $\\log n$, which is sharper than generic fair set cover.","When a custom-ratio target is feasible, the reduction to weighted fair $\\varepsilon$-nets shows that the target can be met as long as the linear program and the per-color count conditions hold.","Fair $\\varepsilon$-samples with arbitrary target ratios are not always possible, so any sampling-based fairness requirement must be checked against the geometry before deployment."],"supporting_citations":[{"why":"supplies the classical random-sampling bound for $\\varepsilon$-nets (Theorem 1), which sets the base sample size that the fair Monte-Carlo algorithm tops up.","marker":"[30]"},{"why":"supplies the discrepancy halving procedure and the conditional-expectations derandomization used by the fair discrepancy-based algorithms.","marker":"[27]"},{"why":"establishes that repeated halving with arbitrary matchings yields an $\\varepsilon$-net and an $\\varepsilon$-sample, so fair matchings preserve the existing correctness arguments.","marker":"[16]"},{"why":"provides the general fair set cover algorithm used as a baseline and as the starting point for the custom-ratio fair $\\varepsilon$-net reduction in Section 4.3.","marker":"[20]"},{"why":"one of the references for reducing geometric hitting set to weighted $\\varepsilon$-net via LP relaxation, used in the fair hitting set reduction.","marker":"[14]"},{"why":"gives the $\\varepsilon$-sample size bound (Theorem 2) used for constructing fair $\\varepsilon$-samples and for the sketch-and-merge analysis.","marker":"[48]"}],"fun_headline_variants":["Fair epsilon-nets: exact ratios, log k size penalty","Fair hitting sets: log OPT log k approximation","Deterministic fair epsilon-nets from discrepancy","Linear-time fair epsilon-nets with exact ratios"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The algorithms assume that the target number of points of each group, after the top-up step or after each halving, is a whole number that can actually be taken from the data; for the deterministic halving, this also requires every group's size to be a power of two, and if a group has too few points or the counts do not come out integral, the exact-ratio guarantee and the stated size bound cannot both hold.","fun_headline_variants_meta":{"raw":{"variants":["Fair epsilon-nets: exact ratios, log k size penalty","Fair hitting sets: log OPT log k approximation","Deterministic fair epsilon-nets from discrepancy","Linear-time fair epsilon-nets with exact ratios"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000576,"raw_usage":{"total_tokens":2826,"prompt_tokens":1162,"completion_tokens":1664,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":778,"completion_tokens_details":{"reasoning_tokens":1602}},"tokens_in":778,"tokens_out":1664,"duration_ms":19148,"temperature":1.0,"reasoning_tokens":1602,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T18:11:55.257583+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Build a range space with two colors where one color has a single point, choose a target ratio $\\tau$ and $\\varepsilon$ such that $(1+v)\\tau\\lambda$ exceeds that group's size, and run the fair Monte-Carlo algorithm: the top-up step cannot add the demanded number of minority points, so the output either misses the exact ratio or has size larger than the theorem allows.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"supplies the classical random-sampling bound for $\\varepsilon$-nets (Theorem 1), which sets the base sample size that the fair Monte-Carlo algorithm tops up."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"supplies the discrepancy halving procedure and the conditional-expectations derandomization used by the fair discrepancy-based algorithms."},{"cited_title":"Chazelle","cited_arxiv_id":null,"evidence_quote":"establishes that repeated halving with arbitrary matchings yields an $\\varepsilon$-net and an $\\varepsilon$-sample, so fair matchings preserve the existing correctness arguments."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"provides the general fair set cover algorithm used as a baseline and as the starting point for the custom-ratio fair $\\varepsilon$-net reduction in Section 4.3."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"one of the references for reducing geometric hitting set to weighted $\\varepsilon$-net via LP relaxation, used in the fair hitting set reduction."}],"review_version":1}