20
$\begingroup$

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.

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

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

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

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.

$\endgroup$

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.