8
$\begingroup$

Recently there have been some new results on computer-based experimental study of the Erdos Discrepancy Problem (EDP) (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:

$\endgroup$

migrated from mathoverflow.net Feb 19 '14 at 12:28

This question came from our site for professional mathematicians.

  • 4
    $\begingroup$ 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. $\endgroup$ – András Salamon Feb 19 '14 at 17:36
  • 2
    $\begingroup$ 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 application-of-theory $\endgroup$ – vzn Feb 19 '14 at 17:52
  • 8
    $\begingroup$ Why the down votes? This is a perfectly legitimate research-level question. $\endgroup$ – Jeffε Feb 21 '14 at 13:05
  • 7
    $\begingroup$ I agree with @JɛffE, 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). $\endgroup$ – Sasho Nikolov Feb 21 '14 at 19:29
  • 3
    $\begingroup$ @JɛffE 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. $\endgroup$ – Tayfun Pay Feb 21 '14 at 20:41
15
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – vzn Feb 22 '14 at 19:55
  • 1
    $\begingroup$ 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. $\endgroup$ – Sasho Nikolov Feb 23 '14 at 9:32
  • $\begingroup$ @SashoNikolov So did Terry Tao prove Erdos conjecture or not? Reading lipton blog with frogs confused me even more. What is the verdict in summary? Could you please explain? $\endgroup$ – user34945 Sep 27 '15 at 2:00
  • $\begingroup$ @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. $\endgroup$ – Sasho Nikolov Sep 27 '15 at 2:14
  • $\begingroup$ @SashoNikolov Thank you for the feedback. What is with rjl's statement then "One thing for sure, the problem of Erdős discrepancy is still a problem. Yogi Berra who passed away yesterday said “it ain’t over ’til it’s over,” and it isn’t over."?? $\endgroup$ – user34945 Sep 27 '15 at 3:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.