Geometric discrepancy

Geometric discrepancy theory is a sub-field of discrepancy theory, that deals with balancing points in geometric sets, such as intervals or rectangles. Two closely-related research questions in this field are:

Two-color discrepancy: Given a set of objects in a geometric space, and a set of points in the same space, can we color each point in one of two different colors (e.g. black and white), such that each object contains roughly the same number of points of each color? Formally, the discrepancy of an object is defined as the difference between the number of white points and the number of black points in that object; the goal is to color the points such that the maximum discrepancy of an object is as small as possible.
Expected-value discrepancy (also called Lebesgue-measure or continuous discrepancy): Given a set of objects in a geometric space, and an integer N, can we design a set of N points, such that each object contains a fraction of the points that is roughly proportional to its size? Formally, the discrepancy of an object is defined as the difference between the number of points in that object, and the expected number of points if the points were distributed uniformly at random; the goal is to find a set of points such that the maximum discrepancy of an object is as small as possible .

Two-color discrepancy

Intervals

In the simplest geometric discrepancy setting, the set of objects is the set of all sub-intervals of the real interval [0,1]. In this setting, it is possible to attain discrepancy 1: simply color the points alternately black - white - black - white - etc. Then, the discrepancy of every interval is either 0 or 1.

The problem becomes more challenging when the points are not available in advance, but arrive one by one, and each point should be colored immediately when it arrives. This setting is called the "Online Interval Discrepancy". Jiang, Kulkarni and Singla prove that:^: Sec.3.2

No online algorithm can guarantee a constant discrepancy.
Randomly coloring each point when it arrives gives $\tilde{O} (\sqrt{n})$ expected discrepancy.
If the point arrival is adversarial, the discrepancy of any online algorithm is $Ω (\sqrt{n})$ .
If the point arrival is stochastic, there is an efficient algorithm that guarantees $O (n^{c / \log \log n})$ discrepancy, for some universal constant c, with high probability (i.e. with probability 1-1/poly(n), where the exponent of the polynomial depends on c).

Their proof uses a reduction to the problem of Online Tree Balancing, which is a problem of discrepancy in which the set of objects is the set of sub-trees of a complete m-ary tree with height h. For this problem, they prove that, if $h \leq \log \log n / C$ for a sufficiently large constant C, and m ≥ 100, then there is an online algorithm that attains discrepancy $O (\log^{2} n)$ .^: Sec.2

Rectangles and boxes

Tusnady asked what is the discrepancy when the set of objects is the set of axes-parallel rectangles contained in the unit square.

Beck proved that the discrepancy is at least Ω(log n) and at most O(log⁴n).
Nikolov proved that the discrepancy is at most O(log^1.5 n).

When the set of objects is the set of all rectangles (possibly rotated), then:

Beck proved that the discrepancy is at least Ω(n^1/4-ε) and at most O(n^1/2+ε) for any ε>0.

Matousek studied the d-dimensional extension of Tusnady's problem. Improving previous results by Roth, Schmidt, Beck, Bohus, and Srinivasan, he proved an upper bound of $O_{d} ((\log n)^{d + 1 / 2} \sqrt{\log \log n})$ with a simple proof.

Stripes

When the set of objects is the set of stripes—rectangles of the form [a,b]x[0,1] and [0,1]x[a,b], the setting is equivalent to the problem of "two permutations": given two permutations on a set of n elements, we should color each element either black or white, such that the discrepancy in each interval of each permutation is minimized (the two permutations are the order of the x coordinates and the order of the y coordinates of the points).

Spencer proved that it is possible to attain a discrepancy of at most 2.

Jiang, Kulkarni and Singla study the online setting with stochastic point arrival, and prove that:

A random coloring yields an expected discrepancy of $\tilde{O} (\sqrt{n})$ .
There is an efficient algorithm that guarantees $O (n^{c / \log \log n})$ discrepancy, for some universal constant c, with high probability. They show an application of this result to online fair division.

Convex polytopes

Matousek and Nikolov studied a more general setting, where the set of objects is induced by dilations and translations of a fixed convex polytope. He proved upper and lower bounds on the discrepancy. The results are analogous to the results for rectangles and boxes.

Half-spaces

When the set of objects is the set of half-spaces in the Euclidean d-dimensional space:

Alexander proved a lower bound of $Ω (n^{1 / 2 - d / 2})$ for any dense point set, that is, the ratio of maximum and minimum interior distances is in O(n^1/d).
Matousek proved an upper bound of $C_{d} n^{1 / 2 - d / 2}$ . In fact, this upper bound holds not only for half-spaces but also for any set system for which the primal shatter function is in O(m^d).

Expected-value discrepancy

In expected-value (Lebesgue-measure) discrepancy, a set P of N points in the unit cube $[0, 1]^{d}$ is compared with the uniform distribution instead of being colored. For a point $x = (x_{1}, \dots, x_{d})$ of the cube, the discrepancy function of P is

D_{N} (x) = # (P \cap [0, x)) - N | [0, x) |,

where $[0, x) = [0, x_{1}) \times \dots \times [0, x_{d})$ is the box anchored at the origin and $| [0, x) |$ is its volume. A well-distributed point set is one for which $D_{N}$ is small in some function norm, and the central lower-bound question asks how small these norms can be, uniformly over all N-point sets.^{: Sec. 1} Most of the classical bounds were obtained by variants of a single approach, due to Roth, based on expanding $D_{N}$ in Haar or other orthogonal functions.

Roth's orthogonal function method

Roth proved that every N-point set in $[0, 1]^{d}$ satisfies

‖ D_{N} ‖_{2} \geq c_{d} (\log N)^{(d - 1) / 2},

where $c_{d} > 0$ is a constant that depends only on the dimension.^{: Thm. 1} Schmidt later showed that the same lower bound holds for the $L^{p}$ norm for every $1 < p < \infty$ .^{: Sec. 1}

Roth's argument, now called the orthogonal function method, works with the multiparameter Haar basis.^{: Sec. 2} A dyadic rectangle is a product $R = R_{1} \times \dots \times R_{d}$ of dyadic intervals, and its Haar function $h_{R}$ is the product of the one-dimensional Haar functions of its sides. One fixes an integer n with $2 N \leq 2^{n} < 4 N$ , so that $n \approx \log_{2} N$ , and considers only the dyadic rectangles of volume $2^{- n}$ . For each of the roughly $n^{d - 1}$ possible shapes of such rectangles, there are $2^{n} \geq 2 N$ rectangles of that shape, so at least half of them contain no point of P. On an empty rectangle, the counting part of $D_{N}$ is orthogonal to $h_{R}$ , so the Haar coefficient comes from the volume term alone and has a known sign and size. Summing, with matching signs, the Haar functions of the empty rectangles of one shape gives a function $f_{r}$ whose pairing with $D_{N}$ is bounded below by a constant; functions belonging to different shapes are orthogonal. Their sum F therefore satisfies $⟨ D_{N}, F ⟩ ≳ n^{d - 1}$ while $‖ F ‖_{2} ≲ n^{(d - 1) / 2}$ , and the Cauchy–Schwarz inequality gives Roth's bound.^{: Sec. 2}

Roth's bound is not sharp for the supremum norm. In two dimensions, Schmidt proved that $‖ D_{N} ‖_{\infty} \geq c \log N$ , which is larger than the $L^{2}$ bound by a factor of $\sqrt{\log N}$ and is attained, up to the constant, by the van der Corput point set.^{: Sec. 1}

Halász's Riesz product method

Halász refined Roth's method by replacing the linear test function F with a Riesz product built from the same functions $f_{r}$ . In two dimensions the shapes of rectangles of area $2^{- n}$ are $(j, n - j)$ for $j = 0, \dots, n$ , and the Haar functions obey a product rule: the product of the Haar functions of two such rectangles with different shapes is, up to sign, the Haar function of a smaller rectangle. As a result, the functions $f_{(j, n - j)}$ behave like independent random signs, a product such as $Ψ = \prod_{j} (1 + f_{(j, n - j)})$ is non-negative with integral 1, and its expansion consists of Roth's linear term plus higher-order terms whose pairings with $D_{N}$ are small.^{: Sec. 5} This yields a new proof of Schmidt's $L^{\infty}$ bound.^{: Sec. 5}

Using a bounded Riesz product of this kind as a dual test function, Halász also proved that in two dimensions

‖ D_{N} ‖_{1} \geq c \sqrt{\log N},

so Roth's bound already holds for the $L^{1}$ norm.^{: Sec. 1} His argument gives only $‖ D_{N} ‖_{1} ≳ \sqrt{\log N}$ in dimensions $d \geq 3$ , and whether Roth's bound $(\log N)^{(d - 1) / 2}$ holds for the $L^{1}$ norm in those dimensions is a well-known conjecture. The main obstacle in higher dimensions is that the product rule fails when two dyadic rectangles of the same volume share a side length.^{: Sec. 6}

Recent results

Between $L^{2}$ and $L^{\infty}$ in two dimensions. Bilyk, Lacey, Parissis and Vagharshakyan^{: Thm. 1.3} proved that every N-point set in the unit square satisfies $‖ D_{N} ‖_{\exp (L^{α})} ≳ (\log N)^{1 - 1 / α}$ for $2 \leq α < \infty$ , where $\exp (L^{α})$ denotes an exponential Orlicz norm. This interpolates between the theorems of Roth ( $α = 2$ ) and Schmidt ( $α = \infty$ ), and it is sharp, being attained by a digit-scrambled van der Corput set when N is a power of 2. Their proof is a variant of Halász's argument.^{: Sec. 1}
Near $L^{1}$ in higher dimensions. Lacey^{: Thm. 1.1} extended Halász's $L^{1}$ theorem to all dimensions $d \geq 2$ in a slightly weaker norm, proving $‖ D_{N} ‖_{L (\log L)^{(d - 2) / 2}} ≳ (\log N)^{(d - 1) / 2}$ ; in two dimensions this is exactly Halász's theorem.
The supremum norm in higher dimensions. In dimension 3, Beck obtained an improvement over Roth's bound by a factor logarithmic in $\log N$ . Bilyk and Lacey simplified and extended Beck's argument to obtain a power gain in dimension 3, and Bilyk, Lacey and Vagharshakyan extended it to all dimensions: for every $d \geq 3$ there is $η = η (d) > 0$ such that $‖ D_{N} ‖_{\infty} ≳ (\log N)^{(d - 1) / 2 + η}$ .^{: Sec. 1} These results were the first non-trivial improvements over Roth's bound in dimensions 4 and higher.
The small ball inequality. The results above are closely tied to the small ball inequality, a lower bound on the supremum norm of sums $\sum_{| R | = 2^{- n}} α_{R} h_{R}$ of Haar functions over rectangles of a fixed volume, which also arises in probability (small deviations of the Brownian sheet) and in approximation theory. Orthogonality alone gives the inequality with a factor $n^{(d - 1) / 2}$ , and it is conjectured that $n^{(d - 2) / 2}$ suffices. The two-dimensional case was proved by Talagrand, and Temlyakov later gave a proof closely related to Halász's Riesz product argument.^{: Sec. 5} In dimensions $d \geq 3$ , the inequality is known with $n^{(d - 1) / 2 - η}$ , where $η > c / d^{2}$ .^{: Thm. 7}
Consequences for Tusnády's problem. For the combinatorial discrepancy of boxes in dimension $d > 2$ , the best lower bound had long been of order roughly $\log^{(d - 1) / 2} n$ , the same order as Roth's bound. Matoušek and Nikolov improved this to $Ω (\log^{d - 1} n)$ using a different technique, the $γ_{2}$ factorization norm.

Relation between two-color and expected-value discrepancy

Let $𝒜$ be a family of measurable subsets of the unit cube $[0, 1]^{d}$ .

The expected-value (Lebesgue-measure) discrepancy of an N-point set P is: $D^{L} (P, 𝒜) := sup_{A \in 𝒜} | | P \cap A | - N v o l (A) |,$ and $D^{L} (N, 𝒜)$ is the smallest value of $D^{L} (P, 𝒜)$ over all N-point sets P.
The two-color (combinatorial) discrepancy $D^{C} (N, 𝒜)$ is the largest, over all N-point sets P, of the discrepancy of the best two-coloring of P with respect to the sets $A \cap P$ , $A \in 𝒜$ .

In the first problem one chooses the best placement of the points; in the second the points are given by an adversary and one chooses only the coloring.^{: Sec. 1}

Transference principle

The transference principle (or transference lemma) states that small combinatorial discrepancy implies small Lebesgue-measure discrepancy. Suppose that $𝒜$ contains the whole cube, that $D^{L} (N, 𝒜) = o (N)$ , and that $D^{C} (N, 𝒜) \leq f (N)$ for a function f satisfying $f (2 N) \leq (2 - δ) f (N)$ for some fixed $δ > 0$ . Then $D^{L} (N, 𝒜) = O (f (N))$ .^{: Thm. 3} The idea is attributed to Sós, and Beck used it in his lower bound for Tusnády's problem.^{: Sec. 1} A general form of the principle was given by Lovász, Spencer and Vesztergombi,^{: Sec. 2.3} who also proved the closely related inequality that the linear discrepancy of a set system (the worst case of rounding fractional weights to 0 and 1) is at most twice its hereditary discrepancy.

The proof is by repeated halving. One starts from a very large point set $P_{0}$ whose Lebesgue-measure discrepancy is small relative to its size, which exists by the assumption $D^{L} (N, 𝒜) = o (N)$ . If P has $2 m$ points and $χ$ is a coloring of P with discrepancy at most $f (2 m)$ , then, for one color class $P^{'}$ ,

| P^{'} \cap A | - m v o l (A) = \frac{1}{2} (| P \cap A | - 2 m v o l (A)) + \frac{1}{2} χ (P \cap A)

for every $A \in 𝒜$ , so $D^{L} (P^{'}, 𝒜) \leq \frac{1}{2} D^{L} (P, 𝒜) + \frac{1}{2} f (2 m)$ . Because the whole cube belongs to $𝒜$ , the two color classes have almost equal sizes. Repeating the step until N points remain, the errors form a geometric series, and the growth condition on f makes the sum $O (f (N))$ .^{: Sec. 2.3}

The same argument works when Lebesgue measure is replaced by an arbitrary Borel probability measure on the cube, with a constant that does not depend on the measure.^{: Sec. 2.3}

Consequences

Lower bounds. Read in the contrapositive direction, the principle shows that, for axis-parallel boxes, the combinatorial discrepancy cannot be asymptotically smaller than the smallest achievable Lebesgue-measure discrepancy. Hence the bounds of Roth (of order $\log^{(d - 1) / 2} n$ ) and of Schmidt (of order $\log n$ in the plane) also apply to Tusnády's problem. Until the work of Matoušek and Nikolov, all known lower bounds for Tusnády's problem relied on the transference principle.^{: Sec. 1} Similarly, the previous best lower bound for dilates and translates of a convex polytope followed from a result of Drmota on Lebesgue-measure discrepancy.^{: Sec. 1}
Upper bounds. Nikolov combined the transference lemma with his combinatorial bound for polytopes to show that the Lebesgue-measure discrepancy of dilates and translates of a fixed convex polytope in $ℝ^{d}$ is $O (\log^{d - 1 / 2} n)$ .^{: Sec. 2.1} Aistleitner, Bilyk and Nikolov used the version for general measures, together with an upper bound for Tusnády's problem, to show that for every Borel probability measure $μ$ on $[0, 1]^{d}$ there are N points whose star discrepancy with respect to $μ$ is at most $c_{d} (\log N)^{d - 1 / 2} / N$ .^{: Thm. 1}
A barrier. For axis-parallel boxes, the Lebesgue-measure discrepancy $O (\log^{d - 1} n)$ is already attained by explicit point sets, and Matoušek and Nikolov proved a combinatorial lower bound of the same order. Therefore combinatorial discrepancy cannot be used to improve the upper bound for the Lebesgue-measure problem for boxes.^{: Sec. 1}

Limits of the reduction

The relation cannot be reversed in general. For the family of all convex subsets of the unit cube, the Lebesgue-measure discrepancy is of order $N^{1 - 2 / (d + 1)}$ , while the combinatorial discrepancy is of order N.^{: Sec. 2.3} The combinatorial value is large because the adversary may place the points on a sphere, where every subset of the points is cut out by a convex set, namely its own convex hull. Likewise, lower bounds for Tusnády's problem do not imply lower bounds for the Lebesgue-measure problem, since the combinatorial problem requires the chosen points to come from a given point set.^{: Sec. 2.2}

References

↑ Matoušek, Jiří (1999). Geometric Discrepancy: An Illustrated Guide. Springer. ISBN 3-540-65528-X.
1 2 3 4 Jiang, Haotian; Kulkarni, Janardhan; Singla, Sahil (2019-10-02). "Online Geometric Discrepancy for Stochastic Arrivals with Applications to Envy Minimization". arXiv:1910.01073 [cs.DS].
1 2 Beck, József (1981-12-01). "Balanced two-colorings of finite sets in the square I". Combinatorica. 1 (4): 327–335. doi:10.1007/BF02579453. ISSN 1439-6912.
1 2 3 4 Nikolov, Aleksandar (January 2017). "Tighter Bounds for the Discrepancy of Boxes and Polytopes". Mathematika. 63 (3): 1091–1113. arXiv:1701.05532. doi:10.1112/S0025579317000250. ISSN 0025-5793.
1 2 3 Alexander, R. (1990-06-01). "Geometric methods in the study of irregularities of distribution". Combinatorica. 10 (2): 115–136. doi:10.1007/BF02123006. ISSN 1439-6912.
↑ Matoušek, J. (1995-06-01). "Tight upper bounds for the discrepancy of half-spaces". Discrete & Computational Geometry. 13 (3): 593–601. doi:10.1007/BF02574066. ISSN 1432-0444.
1 2 3 4 5 6 7 8 9 Bilyk, Dmitriy; Lacey, Michael (2013). "The supremum norm of the discrepancy function: recent results and connections". In Dick, Josef; Kuo, Frances; Peters, Gareth; Sloan, Ian (eds.). Monte Carlo and Quasi-Monte Carlo Methods 2012. Springer Proceedings in Mathematics & Statistics. Vol. 65. Springer. pp. 23–38.
↑ Bilyk, Dmitriy (2014). "Roth's orthogonal function method in discrepancy theory and some new connections". In Chen, William; Srivastav, Anand; Travaglini, Giancarlo (eds.). A Panorama of Discrepancy Theory. Lecture Notes in Mathematics. Vol. 2107. Springer. pp. 71–158.
1 2 Roth, Klaus Friedrich (1954). "On irregularities of distribution". Mathematika. 1 (2): 73–79.
1 2 3 4 Bilyk, Dmitriy; Lacey, Michael; Parissis, Ioannis; Vagharshakyan, Armen (2009). "Exponential squared integrability of the discrepancy function in two dimensions". Mathematika. 55 (1–2): 1–27.
1 2 3 Lacey, Michael (2008). "On the discrepancy function in arbitrary dimension, close to L¹". Analysis Mathematica. 34: 119–136.
1 2 Schmidt, Wolfgang (1972). "Irregularities of distribution, VII". Acta Arithmetica. 21: 45–50.
↑ Halász, Gábor (1981). "On Roth's method in the theory of irregularities of point distributions". In Halberstam, Heini; Hooley, Christopher (eds.). Recent Progress in Analytic Number Theory. Vol. 2. London: Academic Press. pp. 79–94.
1 2 Bilyk, Dmitriy; Lacey, Michael (2008). "On the small ball inequality in three dimensions". Duke Mathematical Journal. 143 (1): 81–115.
1 2 3 Bilyk, Dmitriy; Lacey, Michael; Vagharshakyan, Armen (2008). "On the small ball inequality in all dimensions". Journal of Functional Analysis. 254 (9): 2470–2502.
1 2 3 4 5 Matoušek, Jiří; Nikolov, Aleksandar (2015). "Combinatorial discrepancy for boxes via the γ₂ norm". In Arge, Lars; Pach, János (eds.). 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics. Vol. 34. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. pp. 1–15.
1 2 3 4 5 6 7 Aistleitner, Christoph; Bilyk, Dmitriy; Nikolov, Aleksandar (2018). "Tusnády's problem, the transference principle, and non-uniform QMC sampling". In Owen, Art; Glynn, Peter (eds.). Monte Carlo and Quasi-Monte Carlo Methods: MCQMC 2016, Stanford, CA, August 14–19. Springer Proceedings in Mathematics & Statistics. Vol. 241. Springer. pp. 169–180.
↑ Lovász, László; Spencer, Joel; Vesztergombi, Katalin (1986). "Discrepancy of set-systems and matrices". European Journal of Combinatorics. 7 (2): 151–160.

[1] Matoušek, Jiří (1999). Geometric Discrepancy: An Illustrated Guide. Springer. ISBN 3-540-65528-X.

[:2-2] 1 2 3 4 Jiang, Haotian; Kulkarni, Janardhan; Singla, Sahil (2019-10-02). "Online Geometric Discrepancy for Stochastic Arrivals with Applications to Envy Minimization". arXiv:1910.01073 [cs.DS].

[:0-3] 1 2 Beck, József (1981-12-01). "Balanced two-colorings of finite sets in the square I". Combinatorica. 1 (4): 327–335. doi:10.1007/BF02579453. ISSN 1439-6912.

[:1-4] 1 2 3 4 Nikolov, Aleksandar (January 2017). "Tighter Bounds for the Discrepancy of Boxes and Polytopes". Mathematika. 63 (3): 1091–1113. arXiv:1701.05532. doi:10.1112/S0025579317000250. ISSN 0025-5793.

[:3-5] 1 2 3 Alexander, R. (1990-06-01). "Geometric methods in the study of irregularities of distribution". Combinatorica. 10 (2): 115–136. doi:10.1007/BF02123006. ISSN 1439-6912.

[6] Matoušek, J. (1995-06-01). "Tight upper bounds for the discrepancy of half-spaces". Discrete & Computational Geometry. 13 (3): 593–601. doi:10.1007/BF02574066. ISSN 1432-0444.

[BL13-7] 1 2 3 4 5 6 7 8 9 Bilyk, Dmitriy; Lacey, Michael (2013). "The supremum norm of the discrepancy function: recent results and connections". In Dick, Josef; Kuo, Frances; Peters, Gareth; Sloan, Ian (eds.). Monte Carlo and Quasi-Monte Carlo Methods 2012. Springer Proceedings in Mathematics & Statistics. Vol. 65. Springer. pp. 23–38.

[Bilyk14-8] Bilyk, Dmitriy (2014). "Roth's orthogonal function method in discrepancy theory and some new connections". In Chen, William; Srivastav, Anand; Travaglini, Giancarlo (eds.). A Panorama of Discrepancy Theory. Lecture Notes in Mathematics. Vol. 2107. Springer. pp. 71–158.

[Roth1954-9] 1 2 Roth, Klaus Friedrich (1954). "On irregularities of distribution". Mathematika. 1 (2): 73–79.

[BLPV09-10] 1 2 3 4 Bilyk, Dmitriy; Lacey, Michael; Parissis, Ioannis; Vagharshakyan, Armen (2009). "Exponential squared integrability of the discrepancy function in two dimensions". Mathematika. 55 (1–2): 1–27.

[Lacey08-11] 1 2 3 Lacey, Michael (2008). "On the discrepancy function in arbitrary dimension, close to L¹". Analysis Mathematica. 34: 119–136.

[Schmidt1972-12] 1 2 Schmidt, Wolfgang (1972). "Irregularities of distribution, VII". Acta Arithmetica. 21: 45–50.

[Halasz1981-13] Halász, Gábor (1981). "On Roth's method in the theory of irregularities of point distributions". In Halberstam, Heini; Hooley, Christopher (eds.). Recent Progress in Analytic Number Theory. Vol. 2. London: Academic Press. pp. 79–94.

[BL08-14] 1 2 Bilyk, Dmitriy; Lacey, Michael (2008). "On the small ball inequality in three dimensions". Duke Mathematical Journal. 143 (1): 81–115.

[BLV08-15] 1 2 3 Bilyk, Dmitriy; Lacey, Michael; Vagharshakyan, Armen (2008). "On the small ball inequality in all dimensions". Journal of Functional Analysis. 254 (9): 2470–2502.

[MN15-16] 1 2 3 4 5 Matoušek, Jiří; Nikolov, Aleksandar (2015). "Combinatorial discrepancy for boxes via the γ₂ norm". In Arge, Lars; Pach, János (eds.). 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics. Vol. 34. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. pp. 1–15.

[ABN18-17] 1 2 3 4 5 6 7 Aistleitner, Christoph; Bilyk, Dmitriy; Nikolov, Aleksandar (2018). "Tusnády's problem, the transference principle, and non-uniform QMC sampling". In Owen, Art; Glynn, Peter (eds.). Monte Carlo and Quasi-Monte Carlo Methods: MCQMC 2016, Stanford, CA, August 14–19. Springer Proceedings in Mathematics & Statistics. Vol. 241. Springer. pp. 169–180.

[LSV86-18] Lovász, László; Spencer, Joel; Vesztergombi, Katalin (1986). "Discrepancy of set-systems and matrices". European Journal of Combinatorics. 7 (2): 151–160.