<p>This answer is based on the idea of Dana in her answer above.</p>

<p>I think you can construct such a matrix using two-source lossy condensers. Fix $\delta = 0.001$ and say $N=2^n$. Suppose you have an explicit function $f(x,y)$ that takes any two independent random sources $(X, Y)$, each of length $n$ and having min-entropy at least $k = n(1/2 - \delta)$ and outputs a sequence of $n&#39; = n/2$ bits that is $\epsilon$-close to a distribution with min-entropy at least $k&#39;=n(1/2-3\delta)$. I think you can use standard probabilistic arguments to show that a random function satisfies these properties (with overwhelming probability) if $2k &gt; k&#39;+\log(1/\epsilon)+O(1)$. To probabilistic argument should be similar to what used in the following paper for lossless condensers and more general conductors:</p>

<p>M. Capalbo, O. Reingold, S. Vadhan, A. Wigderson. Randomness Conductors and Constant-Degree Expansion Beyond the Degree/2 Barrier</p>

<p>In our case, we set $\epsilon = 2^{-k&#39;}$, so we are sure about the existence of the function that we need. Now, an averaging argument shows that there is an $n&#39;$-bit string $z$ such that the number of $(x,y)$ with $f(x,y)=z$ is at least $2^{1.5 n}$. Suppose you know such a $z$ and fix it (you can pick any arbitrary $z$ if you additionally know that your function maps the fully uniform distribution to a distribution that is $O(2^{-n/2})$-close to uniform). Now identify the entries of your $N \times N$ matrix by the possibilities of $(x,y)$ and put a $1$ at position $(x,y)$ iff $f(x,y)=z$. By our choice of $z$, this matrix has at least $2^{1.5n}$ ones.</p>

<p>Now take any $2^k \times 2^k$ submatrix and let $X, Y$ be uniform distributions on the picked rows and columns, respectively. By the choice of $f$, we know that $f(X,Y)$ is $\epsilon$-close to having min-entropy $k&#39;$. Therefore, if we pick a uniformly random entry of the submatrix, the probability of having a $1$ is at most $2^{-k&#39;}+\epsilon\leq 2^{-k&#39;+1}$. This means that you have at most $2^{2k-k&#39;+1} = O(2^{n/2 + \delta})$ ones in the submatrix, as desired.</p>

<p>Of course coming up with an <em>explicit</em> $f$ with the desired parameters (in particular, nearly optimal output length) is a very challenging task and no such function in known so far.</p>

CC BY-SA 3.0
2011-08-22T18:39:02.410Z
2011-08-22T22:20:54.357Z
2011-08-22T22:20:54.357Z
Mahdi Cheraghchi
<p>What you are looking for is a one-bit extractor for two independent sources: a function $E:[N]\times [N]\to \{0,1\}$, such that, provided X,Y are random variables with min-entropy 0.499*log(N), E(X,Y) is almost balanced. </p>

<p>It's a notorious hard problem. For the parameters you want, I believe it was solved by Bourgain. See here:
<a href="http://www.cs.washington.edu/homes/anuprao/pubs/bourgain.pdf" rel="nofollow">http://www.cs.washington.edu/homes/anuprao/pubs/bourgain.pdf</a></p>

CC BY-SA 3.0
2011-08-18T20:00:45.903Z
I don't think an extractor helps here. Any two source extractor matrix with entropy $k=0.499 \log N$ would have roughly $N^2 /2$ ones and moreover every $2^k \times 2^k$ submatrix would have roughly $2^{2k} \approx N$ ones. This is far from what the questioner needs.
Mahdi Cheraghchi
CC BY-SA 3.0
2011-08-19T22:24:02.907Z
Re-reading the question and answer (it has been a while ago..), I think that I didn't notice the questioner wanted only N^{1.5} ones, which corresponds to extracting a bit that is 1 with probability N^{-0.5} rather than a balanced bit. Still, I think that the reference to two-source extractors is helpful. I can imagine that similar techniques would be useful for the question's setting.
Dana Moshkovitz
CC BY-SA 3.0
2011-08-21T13:41:57.247Z
1) If an extractor outputs k nearly uniform bits, then, in particular, you can get one bit that is 1 with probability ~1/2^k. 2) This is pretty wasteful, and it sounds to me like a nice research question to find more efficient way to generate such bits.
Dana Moshkovitz
CC BY-SA 3.0
2011-08-22T18:41:24.700Z
Yes it is true that a two-source extractor may be wasteful, mainly because of the $2 \log(1/epsilon)$ entropy loss. However I think one can instead use a _lossy condenser_ and construct the desired matrix. I have posted the details in a separate answer below.
Mahdi Cheraghchi
CC BY-SA 2.5
2010-12-16T15:20:24.217Z
Right. By I need biased bit with $p = N^{-1/2}$. Is it possible to use this extractor as a black box to achieve this goal?
ilyaraz
CC BY-SA 2.5
2010-12-16T15:28:58.473Z
Bourgain gives bias $p=N^{-\alpha}$ for some $\alpha>0$. I'm not sure the analysis can give $\alpha = 1/2$. If I were you, I would study it and check. You can also ask Anup Rao, Zeev Dvir, Avi Wigderson, or any of the other people who worked on this problem.
Dana Moshkovitz
CC BY-SA 2.5
2010-12-16T15:31:49.600Z
I _will_ study it, of course. Thank you very much!
ilyaraz
CC BY-SA 2.5
2010-12-16T15:49:30.830Z
@ilyaraz: When you (or anyone) finds out whether Bourgain’s construction gives a desired matrix or not, please share (unless you mind)!
Tsuyoshi Ito
CC BY-SA 2.5
2010-12-16T18:07:49.720Z
this has been a very interesting Q&A. I'll second Tsuyoshi's request.
Suresh Venkat
CC BY-SA 2.5
2010-12-16T15:11:15.150Z
2010-12-16T15:11:15.150Z
Dana Moshkovitz
<p>Is it possible to build an explicit $N \times N$ $0/1$-matrix with $N^{1.5}$ ones such that every $N^{0.499} \times N^{0.499}$ submatrix contains less than $N^{0.501}$ ones?</p>

<p>Or probably it is possible to build an explicit hitting set for such property.</p>

<p>It is easy to see that random matrix has this property with probability exponentially close to $1$. Also, expander mixing lemma is not sufficient to derive this property.</p>

<p>I guess pseudorandom generators that fool combinatorial rectangles could help here, but they are designed for uniform distributions and I basically need $B(N^2, N^{-0.5})$ here.</p>

CC BY-SA 2.5
2010-12-16T08:52:53.680Z
It's an interesting question: I'm curious about the motivation though.
Suresh Venkat
CC BY-SA 2.5
2010-12-16T09:38:59.320Z
@Suresh It comes from quantitative non-extractability of mutual information. If you're interested, I can elaborate.
ilyaraz
CC BY-SA 2.5
2010-12-16T11:22:52.317Z
I actually am. you can email me (sureshv@gmail.com) if it's easier that way.
Suresh Venkat
<co.combinatorics><matrices><pseudorandomness><pseudorandom-generators>
Explicit balanced matrix
ilyaraz
# Explicit balanced matrix

(Asked by: username_0 on 2010-12-16)

Is it possible to build an explicit $N \times N$ $0/1$-matrix with $N^{1.5}$ ones such that every $N^{0.499} \times N^{0.499}$ submatrix contains less than $N^{0.501}$ ones?

Or probably it is possible to build an explicit hitting set for such property.

It is easy to see that random matrix has this property with probability exponentially close to $1$. Also, expander mixing lemma is not sufficient to derive this property.

I guess pseudorandom generators that fool combinatorial rectangles could help here, but they are designed for uniform distributions and I basically need $B(N^2, N^{-0.5})$ here.

**Tags:** co.combinatorics, matrices, pseudorandomness, pseudorandom-generators
> **Comments:**
> **username_1**: It's an interesting question: I'm curious about the motivation though.  
> **username_0**: @Suresh It comes from quantitative non-extractability of mutual information. If you're interested, I can elaborate.  
> **username_1**: I actually am. you can email me (sureshv@gmail.com) if it's easier that way.  

---

## 2 answers

### Answer by username_3 on 2010-12-16. Score: 11 | Accepted answer

What you are looking for is a one-bit extractor for two independent sources: a function $E:[N]\times [N]\to \{0,1\}$, such that, provided X,Y are random variables with min-entropy 0.499\*log(N), E(X,Y) is almost balanced.

It's a notorious hard problem. For the parameters you want, I believe it was solved by Bourgain. See here:
<http://www.cs.washington.edu/homes/anuprao/pubs/bourgain.pdf>

> **Comments:**
> **username_0**: Right. By I need biased bit with $p = N^{-1/2}$. Is it possible to use this extractor as a black box to achieve this goal?  
> **username_3**: Bourgain gives bias $p=N^{-\alpha}$ for some $\alpha>0$. I'm not sure the analysis can give $\alpha = 1/2$. If I were you, I would study it and check. You can also ask Anup Rao, Zeev Dvir, Avi Wigderson, or any of the other people who worked on this problem.  
> **username_0**: I _will_ study it, of course. Thank you very much!  
> **username_4**: @ilyaraz: When you (or anyone) finds out whether Bourgain’s construction gives a desired matrix or not, please share (unless you mind)!  
> **username_1**: this has been a very interesting Q&A. I'll second Tsuyoshi's request.  
> **username_2**: I don't think an extractor helps here. Any two source extractor matrix with entropy $k=0.499 \log N$ would have roughly $N^2 /2$ ones and moreover every $2^k \times 2^k$ submatrix would have roughly $2^{2k} \approx N$ ones. This is far from what the questioner needs.  
> **username_3**: Re-reading the question and answer (it has been a while ago..), I think that I didn't notice the questioner wanted only N^{1.5} ones, which corresponds to extracting a bit that is 1 with probability N^{-0.5} rather than a balanced bit. Still, I think that the reference to two-source extractors is helpful. I can imagine that similar techniques would be useful for the question's setting.  
> **username_3**: 1) If an extractor outputs k nearly uniform bits, then, in particular, you can get one bit that is 1 with probability ~1/2^k. 2) This is pretty wasteful, and it sounds to me like a nice research question to find more efficient way to generate such bits.  
> **username_2**: Yes it is true that a two-source extractor may be wasteful, mainly because of the $2 \log(1/epsilon)$ entropy loss. However I think one can instead use a _lossy condenser_ and construct the desired matrix. I have posted the details in a separate answer below.  

---

### Answer by username_2 on 2011-08-22. Score: 2

This answer is based on the idea of Dana in her answer above.

I think you can construct such a matrix using two-source lossy condensers. Fix $\delta = 0.001$ and say $N=2^n$. Suppose you have an explicit function $f(x,y)$ that takes any two independent random sources $(X, Y)$, each of length $n$ and having min-entropy at least $k = n(1/2 - \delta)$ and outputs a sequence of $n' = n/2$ bits that is $\epsilon$-close to a distribution with min-entropy at least $k'=n(1/2-3\delta)$. I think you can use standard probabilistic arguments to show that a random function satisfies these properties (with overwhelming probability) if $2k > k'+\log(1/\epsilon)+O(1)$. To probabilistic argument should be similar to what used in the following paper for lossless condensers and more general conductors:

M. Capalbo, O. Reingold, S. Vadhan, A. Wigderson. Randomness Conductors and Constant-Degree Expansion Beyond the Degree/2 Barrier

In our case, we set $\epsilon = 2^{-k'}$, so we are sure about the existence of the function that we need. Now, an averaging argument shows that there is an $n'$-bit string $z$ such that the number of $(x,y)$ with $f(x,y)=z$ is at least $2^{1.5 n}$. Suppose you know such a $z$ and fix it (you can pick any arbitrary $z$ if you additionally know that your function maps the fully uniform distribution to a distribution that is $O(2^{-n/2})$-close to uniform). Now identify the entries of your $N \times N$ matrix by the possibilities of $(x,y)$ and put a $1$ at position $(x,y)$ iff $f(x,y)=z$. By our choice of $z$, this matrix has at least $2^{1.5n}$ ones.

Now take any $2^k \times 2^k$ submatrix and let $X, Y$ be uniform distributions on the picked rows and columns, respectively. By the choice of $f$, we know that $f(X,Y)$ is $\epsilon$-close to having min-entropy $k'$. Therefore, if we pick a uniformly random entry of the submatrix, the probability of having a $1$ is at most $2^{-k'}+\epsilon\leq 2^{-k'+1}$. This means that you have at most $2^{2k-k'+1} = O(2^{n/2 + \delta})$ ones in the submatrix, as desired.

Of course coming up with an *explicit* $f$ with the desired parameters (in particular, nearly optimal output length) is a very challenging task and no such function in known so far.


---

