<p>There are many links between discrepancy theory and computer science, and Bernard Chazelle has beautifully surveyed some of them in <a href="http://www.cs.princeton.edu/~chazelle/book.html">his book</a>. 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 <a href="http://dl.acm.org/citation.cfm?doid=2213977.2214090">[MN]</a> and <a href="http://arxiv.org/abs/1212.0297">[NTZ]</a>. Another example is <a href="http://www.madalgo.au.dk/~larsen/papers/range_and_disc.pdf">Larsen's idea</a> 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:</p>

<ul>
<li>upper bounds on the $\varepsilon$-samples for range spaces of HAPs</li>
<li>lower bounds on time required to update/query a dynamic data structure for HAP range counting</li>
<li>lower and upper bounds on the error required to privately answer HAP queries</li>
</ul>

<p>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. </p>

<p>Another thing that you must realize is that all these applications rely on the notion of <strong>hereditary discrepancy</strong>. 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 <a href="http://arxiv.org/abs/1309.6034">here</a>) and the construction by Alon and Kalai that Kalai wrote about in <a href="http://gowers.wordpress.com/2012/08/22/edp22-first-guest-post-from-gil-kalai/">this blog post</a> 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.</p>

<p>However EDP is about the <strong>discrepancy</strong> 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. </p>

<p>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 <a href="http://www.win.tue.nl/~nikhil/pubs/disc-ismp%20-final.pdf">survey</a> 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. </p>

<p>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 <a href="http://www.cs.elte.hu/~lovasz/semidef.ps">SDP survey</a>.</p>

CC BY-SA 3.0
2014-02-22T19:55:28.617Z
SN ***thx*** for answer & rescuing question with answer/edit. found chazelles book yrs ago & felt while outstanding it was hard to sort out the (TCS) applications, it would be nice if it was clearer or separated into a separate chapter.
vzn
CC BY-SA 3.0
2014-02-23T09:32:32.440Z
the *entire* book is about applications of discrepancy methods to computer science. chapeters 1-3 are basic techniques and intro, and then chapters 4-11 are **all** about applications to TCS.
Sasho Nikolov
CC BY-SA 3.0
2015-09-27T02:14:51.453Z
@Arul While I have only gone through a part of the paper, by the look of it he *has* in fact proved the conjecture. I.e. he has shown that the discrepancy of homogeneous arithmetic progressions is unbounded. He even shows that for the vector version, i.e. the SDP relaxation.
Sasho Nikolov
CC BY-SA 3.0
2015-09-27T06:33:01.633Z
Yes, that was a strange statement. I think they meant that there are still open questions around it, e.g. what the exact growth rate of the discrepancy is. Background: some basic Fourier analysis and mostly analytic number theory.
Sasho Nikolov
CC BY-SA 3.0
2015-09-27T19:52:14.477Z
Chazelle's book is  a start https://www.cs.princeton.edu/~chazelle/pubs/book.pdf. Or Matousek's is easier to read, but not available online http://www.springer.com/us/book/9783540655282
Sasho Nikolov
CC BY-SA 3.0
2014-02-20T00:36:04.803Z
2014-02-20T20:35:04.227Z
2014-02-20T20:35:04.227Z
Sasho Nikolov
<p>Recently there have been some new results on computer-based experimental study of the <a href="http://en.wikipedia.org/wiki/Erd%C5%91s_discrepancy_problem">Erdos Discrepancy Problem (EDP)</a> (via SAT solvers, cited below). This problem has been cited and studied by several (T)CS researchers. However the (possibly deep?) links to (T)CS are not so obvious.</p>

<blockquote>
  <p>What are the link(s) of the EDP to (T)CS?</p>
</blockquote>

<p>Here are some references that show interest of the (T)CS community in EDP:</p>

<ul>
<li><p><a href="http://arxiv.org/pdf/1402.2184v1.pdf">SAT attack on EDP</a> by Konev and Lisitsa, and reaction by <a href="http://gowers.wordpress.com/2014/02/11/recent-news-concerning-the-erdos-discrepancy-problem/">Gowers</a>; also, other connections to <a href="http://vzn1.wordpress.com/2014/02/14/great-moments-in-empiricalexperimental-mathtcs-research-breakthough-sat-induction-idea/">empirical/experimental TCS</a> (e.g. SAT automated theorem proofs)</p></li>
<li><p><a href="http://rjlipton.wordpress.com/2013/03/25/win-five-hundred-or-a-million-dollars-by-recursion/">Intro to EDP and techniques</a> on Lipton's blog</p></li>
<li><p><a href="http://windowsontheory.org/2012/09/05/from-discrepancy-to-privacy-and-back/">EDP and Differential Privacy</a> on the Windows on Theory blog, by Talwar</p></li>
<li><p><a href="http://michaelnielsen.org/polymath1/index.php?title=The_Erd%C5%91s_discrepancy_problem">EDP polymath project</a>, with some contributions by computer scientists</p></li>
</ul>

CC BY-SA 3.0
2014-02-19T17:36:11.200Z
Why do you think there is one?  You cite some popular expositions: if they didn't discuss the links then they might not yet have been established.
András Salamon
CC BY-SA 3.0
2014-02-19T17:52:37.923Z
AS, could research this & have somewhat & even venture an answer but am looking/hoping for expert responses/synopses/surveys with TCS angle focus & think answer(s) would be worthwhile for others & future ref also, not an expert in this area (and maybe experts in this area are not very common because of its highly advanced/deep nature). much of EDP research is more focused on the strictly mathematical side. also looking for [tag:application-of-theory]
vzn
CC BY-SA 3.0
2014-02-19T21:32:14.267Z
update just found this link covering the Konev/Lisitsa breakthrough in [New Scientist](http://www.newscientist.com/article/dn25068-wikipediasize-maths-proof-too-big-for-humans-to-check.html)
vzn
CC BY-SA 3.0
2014-02-20T01:41:28.173Z
also covered in [UK independent](http://www.independent.co.uk/life-style/gadgets-and-tech/news/computer-cracks-erds-puzzle--but-no-human-brain-can-check-the-answer-9137097.html)
vzn
CC BY-SA 3.0
2014-02-21T13:05:45.347Z
Why the down votes?  This is a perfectly legitimate research-level question.
Jeffε
CC BY-SA 3.0
2014-02-21T19:29:35.507Z
I agree with @JɛﬀE, I do think it's legitimate research question (I am biased by having worked on it). One criticism might be that it smells of a wild goose chase, but I would say that it is reasonable to expect links between EDP and TCS given how many TCS folks have shown interest in the problem (and Kunal's blog shows explicit connections do exist).
Sasho Nikolov
CC BY-SA 3.0
2014-02-21T20:41:51.990Z
@JɛﬀE They are down voting it because he is supposedly a "crank" or a "troll" according to some people! These people also think that if you do or say one wrong thing (or wrong according to them) then you are always wrong. Anyways, Upvoted the question and Sasho's answer.
Tayfun Pay
CC BY-SA 3.0
2014-03-01T17:02:28.493Z
@Tayfun Pay: If your claim was true all of the posts by this user would have down votes which is not the case. Here are some more reasonable explanations for the down votes: the question is too broad, [it lacks good motivation explaining why the user personally cares about the topic](http://meta.cstheory.stackexchange.com/q/300/), [it was using broken English before Sasho Nikolov's edits](https://cstheory.stackexchange.com/posts/21155/revisions).
Anonymous
CC BY-SA 3.0
2014-03-01T17:34:12.313Z
@Anonymous I will reply to you when I know what is your second account. Since it seems extremely suspicious for your comment to get an upvote within 25 minutes of it being posted on here. This question is not even on the front page of cstheory anymore! I guess somebody keeps refreshing this questions!! Have a nice day.
Tayfun Pay
CC BY-SA 3.0
2014-03-01T18:51:26.123Z
@Tayfun Pay: My point is made, I wasn't expecting a reply.
Anonymous
<reference-request><co.combinatorics><soft-question><big-picture>
Connections between the Erdos Discrepancy Problem and (Theoretical) CS?
vzn
# Connections between the Erdos Discrepancy Problem and (Theoretical) CS?

(Asked by: username_0 on 2014-02-18)

Recently there have been some new results on computer-based experimental study of the [Erdos Discrepancy Problem (EDP)](http://en.wikipedia.org/wiki/Erd%C5%91s_discrepancy_problem) (via SAT solvers, cited below). This problem has been cited and studied by several (T)CS researchers. However the (possibly deep?) links to (T)CS are not so obvious.

> What are the link(s) of the EDP to (T)CS?

Here are some references that show interest of the (T)CS community in EDP:

* [SAT attack on EDP](http://arxiv.org/pdf/1402.2184v1.pdf) by Konev and Lisitsa, and reaction by [Gowers](http://gowers.wordpress.com/2014/02/11/recent-news-concerning-the-erdos-discrepancy-problem/); also, other connections to [empirical/experimental TCS](http://username_01.wordpress.com/2014/02/14/great-moments-in-empiricalexperimental-mathtcs-research-breakthough-sat-induction-idea/) (e.g. SAT automated theorem proofs)
* [Intro to EDP and techniques](http://rjlipton.wordpress.com/2013/03/25/win-five-hundred-or-a-million-dollars-by-recursion/) on Lipton's blog
* [EDP and Differential Privacy](http://windowsontheory.org/2012/09/05/from-discrepancy-to-privacy-and-back/) on the Windows on Theory blog, by Talwar
* [EDP polymath project](http://michaelnielsen.org/polymath1/index.php?title=The_Erd%C5%91s_discrepancy_problem), with some contributions by computer scientists

**Tags:** reference-request, co.combinatorics, soft-question, big-picture

> **Comments:**
> **username_1**: Why do you think there is one?  You cite some popular expositions: if they didn't discuss the links then they might not yet have been established.  
> **username_0**: AS, could research this & have somewhat & even venture an answer but am looking/hoping for expert responses/synopses/surveys with TCS angle focus & think answer(s) would be worthwhile for others & future ref also, not an expert in this area (and maybe experts in this area are not very common because of its highly advanced/deep nature). much of EDP research is more focused on the strictly mathematical side. also looking for [tag:application-of-theory]  
> **username_0**: update just found this link covering the Konev/Lisitsa breakthrough in [New Scientist](http://www.newscientist.com/article/dn25068-wikipediasize-maths-proof-too-big-for-humans-to-check.html)  
> **username_0**: also covered in [UK independent](http://www.independent.co.uk/life-style/gadgets-and-tech/news/computer-cracks-erds-puzzle--but-no-human-brain-can-check-the-answer-9137097.html)  
> **username_2**: Why the down votes?  This is a perfectly legitimate research-level question.  
> **username_3**: I agree with @JɛﬀE, I do think it's legitimate research question (I am biased by having worked on it). One criticism might be that it smells of a wild goose chase, but I would say that it is reasonable to expect links between EDP and TCS given how many TCS folks have shown interest in the problem (and Kunal's blog shows explicit connections do exist).  
> **username_4**: @JɛﬀE They are down voting it because he is supposedly a "crank" or a "troll" according to some people! These people also think that if you do or say one wrong thing (or wrong according to them) then you are always wrong. Anyways, Upvoted the question and Sasho's answer.  
> **username_5**: @username_4: If your claim was true all of the posts by this user would have down votes which is not the case. Here are some more reasonable explanations for the down votes: the question is too broad, [it lacks good motivation explaining why the user personally cares about the topic](http://meta.cstheory.stackexchange.com/q/300/), [it was using broken English before username_3's edits](https://cstheory.stackexchange.com/posts/21155/revisions).  
> **username_4**: @username_5 I will reply to you when I know what is your second account. Since it seems extremely suspicious for your comment to get an upvote within 25 minutes of it being posted on here. This question is not even on the front page of cstheory anymore! I guess somebody keeps refreshing this questions!! Have a nice day.  
> **username_5**: @username_4: My point is made, I wasn't expecting a reply.  

---

## 1 answers

### Answer by username_3 on 2014-02-20. Score: 15 | Accepted answer

There are many links between discrepancy theory and computer science, and Bernard Chazelle has beautifully surveyed some of them in [his book](http://www.cs.princeton.edu/~chazelle/book.html). 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]](http://dl.acm.org/citation.cfm?doid=2213977.2214090) and [[NTZ]](http://arxiv.org/abs/1212.0297). Another example is [Larsen's idea](http://www.madalgo.au.dk/~larsen/papers/range_and_disc.pdf) 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](http://arxiv.org/abs/1309.6034)) and the construction by Alon and Kalai that Kalai wrote about in [this blog post](http://gowers.wordpress.com/2012/08/22/edp22-first-guest-post-from-gil-kalai/) 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](http://www.win.tue.nl/~nikhil/pubs/disc-ismp%20-final.pdf) 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](http://www.cs.elte.hu/~lovasz/semidef.ps).

> **Comments:**
> **username_0**: SN ***thx*** for answer & rescuing question with answer/edit. found chazelles book yrs ago & felt while outstanding it was hard to sort out the (TCS) applications, it would be nice if it was clearer or separated into a separate chapter.  
> **username_3**: the *entire* book is about applications of discrepancy methods to computer science. chapeters 1-3 are basic techniques and intro, and then chapters 4-11 are **all** about applications to TCS.  
> **username_3**: @Arul While I have only gone through a part of the paper, by the look of it he *has* in fact proved the conjecture. I.e. he has shown that the discrepancy of homogeneous arithmetic progressions is unbounded. He even shows that for the vector version, i.e. the SDP relaxation.  
> **username_3**: Yes, that was a strange statement. I think they meant that there are still open questions around it, e.g. what the exact growth rate of the discrepancy is. Background: some basic Fourier analysis and mostly analytic number theory.  
> **username_3**: Chazelle's book is  a start https://www.cs.princeton.edu/~chazelle/pubs/book.pdf. Or Matousek's is easier to read, but not available online http://www.springer.com/us/book/9783540655282  

---

