Explicit balanced matrix

Question

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 08:52
@Suresh It comes from quantitative non-extractability of mutual information. If you're interested, I can elaborate. — ilyaraz, Dec 16 '10 at 09: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

score 11 · Accepted Answer · answered Dec 16 '10 at 15:11

11

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

answered Dec 16 '10 at 15:11

Dana Moshkovitz

10,979
1
50
77

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 Dec 16 '10 at 15:20
1

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
I will study it, of course. Thank you very much! – ilyaraz Dec 16 '10 at 15:31
7

@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
1

this has been a very interesting Q&A. I'll second Tsuyoshi's request. – Suresh Venkat Dec 16 '10 at 18:07
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 Aug 18 '11 at 20:00
2

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

1

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 Aug 22 '11 at 18:41

Mahdi Cheraghchi · Answer 2 · 2011-08-22T22:20:54.357

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.

Explicit balanced matrix

2 Answers2