<p>Actually for applications to approximation algorithms, hereditary discrepancy is often the right quantity. The central result here is due to <a href="http://www.sciencedirect.com/science/article/pii/S0195669886800415">Lovasz, Spencer and Vesztergombi</a>:</p>

<blockquote>
  <p><strong>LSV Thm.</strong> For any $m\times n$ matrix $A$ and any vector $x \in [0,1]^n$, there exists a vector $y \in \{0,1\}^n$ such that $\|Ax - Ay\|_\infty \leq \mathrm{herdisc}(A)$.</p>
</blockquote>

<p>(If you don't have access to the paper, you can check Lemma 1.14 in <a href="http://www.cs.princeton.edu/~chazelle/pubs/book.pdf">Chazelle's book</a> for a proof.)
This theorem can then be used to round a solution to a linear programming relaxation of a combinatorial problem. A very nice example is the recent work on the bin packing problem: for the basic idea check the paper by <a href="http://www.math.washington.edu/~rothvoss/publications/BinPackingViaDiscrepancyOfPermutations-talg.pdf">Eisenbrand, Palvoelgyi, and Rothvoss</a>, and for the best result to date, check this recent <a href="http://arxiv.org/abs/1503.08796">arxiv paper</a> by Hoberg and Rothvoss.</p>

<p>The exact guarantee you mention -- efficiently finding a coloring with discrepancy bounded by the hereditary discrepancy -- fits very nicely into this, because it's exactly the guarantee to make the LSV theorem constructive. I.e. if you have an algorithm that for any matrix $A$ finds in polynomial time a coloring $x \in \{-1, 1\}^n$ such that $\|Ax\|_\infty \leq \alpha \cdot \mathrm{herdisc}(A)$, then we have an <em>efficient LSV theorem</em> in which for any $A$ and $x$ there exists a <em>polynomial time computable</em> $y$ such that $\|Ax - Ay\|_\infty \leq \alpha \cdot \mathrm{herdisc}(A)$.</p>

<p>By the way, hereditary discrepancy turns out to be the right quantity in other applications too: constructing $\epsilon$-samples and differential privacy, for example. Also it can be <a href="http://arxiv.org/abs/1311.6204">efficiently approximated</a> up to a factor of $\log^{3/2}m$. The <a href="http://eccc.hpi-web.de/report/2013/159/">largest hardness of approximation known</a> for hereditary discrepancy is factor 2, so hereditary discrepancy may even be approximable within a fixed constant (although I'd be surprised). </p>

<p><strong>EDIT</strong>: Let me say a few more words about the approximation, since you say you want to find upper bounds on $\mathrm{herdisc}$. Although my paper with Kunal is not written this way, what we show in fact is that 
$$
\gamma_2(A)/O(\log \min(m,n)) \leq \mathrm{herdisc}(A) \leq O(\sqrt{\log m})\gamma_2(A),
$$
where $\gamma_2(A)$ is a classical factorization norm, equal to the smallest number $t$ such that there exist vectors $u_1, \ldots, u_m$, $v_1, \ldots, v_n$ satisfying</p>

<ol>
<li>for all $i,j$, $\|u_i\|^2 \leq t$ and $\|v_j\|^2 \leq t$;</li>
<li>for all $i, j$, $a_{i,j} = u_i^T v_j$.</li>
</ol>

<p>It's not hard to turn this definition into a semidefinite program that computes $\gamma_2(A)$. Besides the approximation, this is very useful because $\gamma_2$ has many nice properties which make it easy to give upper and lower bounds which then translate into upper and lower bounds for hereditary discrepancy. My <a href="http://arxiv.org/abs/1408.1376">paper with Matousek</a> has some applications.</p>

CC BY-SA 3.0
2015-04-07T19:07:18.310Z
Thanks a lot for the answer. I happened to read an excellent survey article by Nikhil Bansal which cleared a lot of these doubts. So, is it correct that $herdisc$ is approximable to $\log^{3/2} m$, in the regime where $m = O(n)$ ?. I understand the algorithmic perspective that I can round to intergral solutions such that $||Ax - Ay|| _{\infty} \leq herdisc(A)$. I want to upper-bound $herdisc$ efficiently, so that I can provide error bounds in terms of $m,n$.
rajatsen91
CC BY-SA 3.0
2015-04-07T19:33:42.670Z
Yes, Nikhil's survey is highly recommended. You can approximate $\mathrm{herdisc}(A)$ up to $\log^{3/2} m$ no matter what $m$ and $n$ are: see the edit to my answer.
Sasho Nikolov
CC BY-SA 3.0
2015-04-07T19:36:38.687Z
Thanks a lot. I think I have a fair idea of what is doable. I will go through the papers you recommended.
rajatsen91
CC BY-SA 3.0
2015-04-08T19:09:59.227Z
Is this the review by Nikhil that is being referred to, http://www.win.tue.nl/~nikhil/pubs/disc-ismp%20-final.pdf ?
Student
CC BY-SA 3.0
2015-04-08T19:58:36.393Z
@Anirbit The article I was referring to is this one : http://link.springer.com/chapter/10.1007/978-3-319-04696-9_6
rajatsen91
CC BY-SA 3.0
2015-04-09T03:54:41.230Z
"It's not hard to turn this definition into a semidefinite program that computes γ2(A)" Could you explain how to do this?
Turbo
CC BY-SA 3.0
2015-04-09T05:30:09.287Z
It really is a nice exercise, you should try it. If you fail, see  page 9 of http://www.research.rutgers.edu/~troyjlee/dpt.pdf.
Sasho Nikolov
CC BY-SA 3.0
2015-04-07T18:41:20.840Z
2015-04-07T19:36:53.677Z
2015-04-07T19:36:53.677Z
Sasho Nikolov
<p>It is known that it is NP-hard to distinguish whether a set system has discrepancy $0$ or $O(\sqrt{n})$, given that the set system has $n$ elements and $m=O(n)$ sets.</p>

<p>In general if it is so hopeless to estimate or upper-bound discrepancy , then why do we care about algorithms that give colorings of $O(\mathrm{herdisc}(C)(\log m\log n)^{1/2})$ discrepancy ? I am interested in applications of discrepancy in approximation algorithms. </p>

<co.combinatorics>
Hereditary Discrepancy
rajatsen91
# Hereditary Discrepancy

(Asked by: username_0 on 2015-04-07)

It is known that it is NP-hard to distinguish whether a set system has discrepancy $0$ or $O(\sqrt{n})$, given that the set system has $n$ elements and $m=O(n)$ sets.

In general if it is so hopeless to estimate or upper-bound discrepancy , then why do we care about algorithms that give colorings of $O(\mathrm{herdisc}(C)(\log m\log n)^{1/2})$ discrepancy ? I am interested in applications of discrepancy in approximation algorithms.

**Tags:** co.combinatorics


---

## 1 answers

### Answer by username_1 on 2015-04-07. Score: 7 | Accepted answer

Actually for applications to approximation algorithms, hereditary discrepancy is often the right quantity. The central result here is due to [Lovasz, Spencer and Vesztergombi](http://www.sciencedirect.com/science/article/pii/S0195669886800415):

> **LSV Thm.** For any $m\times n$ matrix $A$ and any vector $x \in [0,1]^n$, there exists a vector $y \in \{0,1\}^n$ such that $\|Ax - Ay\|\_\infty \leq \mathrm{herdisc}(A)$.

(If you don't have access to the paper, you can check Lemma 1.14 in [Chazelle's book](http://www.cs.princeton.edu/~chazelle/pubs/book.pdf) for a proof.)
This theorem can then be used to round a solution to a linear programming relaxation of a combinatorial problem. A very nice example is the recent work on the bin packing problem: for the basic idea check the paper by [Eisenbrand, Palvoelgyi, and Rothvoss](http://www.math.washington.edu/~rothvoss/publications/BinPackingViaDiscrepancyOfPermutations-talg.pdf), and for the best result to date, check this recent [arxiv paper](http://arxiv.org/abs/1503.08796) by Hoberg and Rothvoss.

The exact guarantee you mention -- efficiently finding a coloring with discrepancy bounded by the hereditary discrepancy -- fits very nicely into this, because it's exactly the guarantee to make the LSV theorem constructive. I.e. if you have an algorithm that for any matrix $A$ finds in polynomial time a coloring $x \in \{-1, 1\}^n$ such that $\|Ax\|\_\infty \leq \alpha \cdot \mathrm{herdisc}(A)$, then we have an *efficient LSV theorem* in which for any $A$ and $x$ there exists a *polynomial time computable* $y$ such that $\|Ax - Ay\|\_\infty \leq \alpha \cdot \mathrm{herdisc}(A)$.

By the way, hereditary discrepancy turns out to be the right quantity in other applications too: constructing $\epsilon$-samples and differential privacy, for example. Also it can be [efficiently approximated](http://arxiv.org/abs/1311.6204) up to a factor of $\log^{3/2}m$. The [largest hardness of approximation known](http://eccc.hpi-web.de/report/2013/159/) for hereditary discrepancy is factor 2, so hereditary discrepancy may even be approximable within a fixed constant (although I'd be surprised).

**EDIT**: Let me say a few more words about the approximation, since you say you want to find upper bounds on $\mathrm{herdisc}$. Although my paper with Kunal is not written this way, what we show in fact is that
$$
\gamma\_2(A)/O(\log \min(m,n)) \leq \mathrm{herdisc}(A) \leq O(\sqrt{\log m})\gamma\_2(A),
$$
where $\gamma\_2(A)$ is a classical factorization norm, equal to the smallest number $t$ such that there exist vectors $u\_1, \ldots, u\_m$, $v\_1, \ldots, v\_n$ satisfying

1. for all $i,j$, $\|u\_i\|^2 \leq t$ and $\|v\_j\|^2 \leq t$;
2. for all $i, j$, $a\_{i,j} = u\_i^T v\_j$.

It's not hard to turn this definition into a semidefinite program that computes $\gamma\_2(A)$. Besides the approximation, this is very useful because $\gamma\_2$ has many nice properties which make it easy to give upper and lower bounds which then translate into upper and lower bounds for hereditary discrepancy. My [paper with Matousek](http://arxiv.org/abs/1408.1376) has some applications.

> **Comments:**
> **username_0**: Thanks a lot for the answer. I happened to read an excellent survey article by Nikhil Bansal which cleared a lot of these doubts. So, is it correct that $herdisc$ is approximable to $\log^{3/2} m$, in the regime where $m = O(n)$ ?. I understand the algorithmic perspective that I can round to intergral solutions such that $||Ax - Ay|| _{\infty} \leq herdisc(A)$. I want to upper-bound $herdisc$ efficiently, so that I can provide error bounds in terms of $m,n$.  
> **username_1**: Yes, Nikhil's survey is highly recommended. You can approximate $\mathrm{herdisc}(A)$ up to $\log^{3/2} m$ no matter what $m$ and $n$ are: see the edit to my answer.  
> **username_0**: Thanks a lot. I think I have a fair idea of what is doable. I will go through the papers you recommended.  
> **username_2**: Is this the review by Nikhil that is being referred to, http://www.win.tue.nl/~nikhil/pubs/disc-ismp%20-final.pdf ?  
> **username_0**: @Anirbit The article I was referring to is this one : http://link.springer.com/chapter/10.1007/978-3-319-04696-9_6  
> **username_3**: "It's not hard to turn this definition into a semidefinite program that computes γ2(A)" Could you explain how to do this?  
> **username_1**: It really is a nice exercise, you should try it. If you fail, see  page 9 of http://www.research.rutgers.edu/~troyjlee/dpt.pdf.  

---

