Let $C$ be the set of all vectors of dimension $n$ such that each of its entries are one of $-1$, $0$ and $1$ and also that the every $v \in C$ has at least $\frac{n}{100}$ $1$'s and at least $\frac{n}{100}$ $-1$'s. For a matrix $A$ (its dimensions are $\Lambda n \times n$ for some sufficiently large constant $\Lambda$), define $||A||\_{C,\infty}$ to be


$||A||\_{C,\infty} = min \_{x \in C} \ \ \ ||A x|| \_{\infty}$


Is it possible to construct an $A$ such that all its entries come from the interval $[-1,1]$
and $||A||\_{C,\infty} = n^{1/2 + \epsilon}$ for some $\epsilon>0$. Constructing the matrix $A$ randomly by choosing each of its entries to be independent and uniformly random elements 
in $[-1,1]$ gets $||A|| \_{C,\infty} =n^{1/2}$. The construction does not need to be explicit.



Norms over some subspaces
The answer is negative. You can achieve at most $O(\sqrt{n\log n})$.


Since more than half of the $\pm 1$ vectors are in $C$, 


$$\|A\|\_{C,\infty} \leq 2 Aver(\|Av\|\_\infty),$$


where the Average is taken over all $\pm 1$ vectors.


To give an upper bound on $Aver(\|Av\|\_\infty)$, note that each of the coordinates of $Av$ has distribution whose tail is subgaussian with parameter $\sqrt n$. By that I mean $Prob(|\sum\_ja\_{ij}v\_j|>C\sqrt n t)\le e^{-t^2}$, for some absolute constant $C$.


It follows that the expectation of the maximum of $\Lambda n$ such variables is at most $O(\sqrt{n\log n})$. (Note that independence of these variables is not needed).


