Return to Question

I'd like to state explicitly a problem which was somehow hidden in my three-week-old post:

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 an example 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$?

I'd like to state explicitly a problem which was somehow hidden in my three-week-old post:

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 an example 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$?