There are many links between discrepancy theory and computer science, and Bernard Chazelle has beautifully surveyed some of them in his book. A number of links have been found more recently as well, for example Kunal's blog post talks about the connection to differential privacy from [MN] and [NTZ]. Another example is Larsen's idea of using discrepancy to prove update/query time lower bounds for dynamic data structures. Many of these links can be instantiated with homogeneous arithmetic progressions (HAPs). This would give:
- upper bounds on the $\varepsilon$-samples for range spaces of HAPs
- lower bounds on time required to update/query a dynamic data structure for HAP range counting
- lower and upper bounds on the error required to privately answer HAP queries
However, there two things that you must realize with respect to these links. One is that it is not clear that range spaces of HAPs are very natural. When do you expect to have input that is a multiset of integers and want to answer how many elements of a HAP are in the input? I cannot think of a situation when this comes up, but maybe I am missing something.
Another thing that you must realize is that all these applications rely on the notion of hereditary discrepancy. This notion is more robust than discrepancy which makes it more tractable: there are stronger lower bounds available for it, it is approximable to within polylogarithmic factors, and it is approximately equal to the value of a convex optimization problem. The result Kunal talks about in the blog post (paper is here) and the construction by Alon and Kalai that Kalai wrote about in this blog post together essentially settle the hereditary discrepancy of HAPs. As Kunal explains, intuition for the lower bound on the hereditary discrepancy of HAPs came from the tight connection between hereditary discrepancy and differential privacy, together with prior results in differential privacy.
However EDP is about the discrepancy of HAPs. Discrepancy is much more brittle than hereditary discrepancy, and that makes it harder to lower bound. This also makes it less useful in applications than hereditary discrepapncy. And this is why EDP is still wide open while the hereditary discrepancy question is fairly well understood.
Let me finish with one approach to attack EDP that is inspired by computer science ideas. There is a way to relax discrepancy to a semidefinite program, see the survey by Bansal for details. The optimal value of the semidefinite program is lower bounded by the value of any feasible solution to its dual program. So one can attempt to prove EDP by exhibiting a family of dual solutions to this semidefinite relaxation of discrepancy, and showing that the value of the dual solutions goes to infinity. I see no reason why such an attack cannot work, in particular we do not know how to construct solutions to the semidefinite relaxation that have constant value for arbitrarily large instances. In fact a lot of the effort in polymath5 was centered around finding or ruling out dual solutions with particular structure.
The discrepancy of arbitrary arithmetic progressions is $\Theta(n^{1/4})$ in the worse case: the lower bound is known as Roth's 1/4 Theorem. Lovasz gives a proof of the theorem using semidefinite programming (although by arguing directly about the primal rather than by constructing dual solutions). For the proof, see Section 5.2. of his SDP survey.
