I'd like to state explicitly a problem which was somehow hidden in <a href="http://mathoverflow.net/questions/41660/is-the-operator-norm-always-attained-on-a-0-1-vector">my three-week-old post</a>:

>Does there exist an absolute constant $c>0$ with the property that for any matrix $M\in{\mathcal M}_{m\times n}(\{0,1\})$ (zero-one matrices with $m$ rows and $n$ columns), there is a non-zero vector $x\in\{0,1\}^n$ such that $\|Mx\|/\|x\|\ge c\|M\|$?

(Here $\|\cdot\|$ denotes both the Euclidean norms in ${\mathbb R}^m$ and ${\mathbb R}^n$ and the induced operator norm.)

---

I can prove the conclusion with $c\sim 1/\sqrt{\log n}$ even in the case $M\in{\mathcal M}_{m\times n}({\mathbb R})$, and <a href="http://mathoverflow.net/questions/41660/is-the-operator-norm-always-attained-on-a-0-1-vector/41669#41669">an example</a> due to Greg Kuperberg shows that this is, essentially, best possible. The question is, can one make an improvement under the assumption that all elements of $M$ are restricted to the values $0$ and $1$?