# Explicit balanced matrix

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.

• It's an interesting question: I'm curious about the motivation though. – Suresh Venkat Dec 16 '10 at 8:52
• @Suresh It comes from quantitative non-extractability of mutual information. If you're interested, I can elaborate. – ilyaraz Dec 16 '10 at 9:38
• I actually am. you can email me (sureshv@gmail.com) if it's easier that way. – Suresh Venkat Dec 16 '10 at 11:22

## 2 Answers

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

• 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 Dec 16 '10 at 15:28
• @ilyaraz: When you (or anyone) finds out whether Bourgain’s construction gives a desired matrix or not, please share (unless you mind)! – Tsuyoshi Ito Dec 16 '10 at 15:49
• this has been a very interesting Q&A. I'll second Tsuyoshi's request. – Suresh Venkat Dec 16 '10 at 18:07
• 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 Aug 19 '11 at 22:24
• 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 Aug 21 '11 at 13:41

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.