The cut norm $||A||\_C$ of a real matrix $A = (a_{i,j}) \in \mathcal{R}^{n\times n}$ is the maximum over all $I \subseteq [n], J \subseteq [n]$ of the quantity $\left|\sum_{i \in I, j \in J}a_{i,j}\right|$.
Define the distance between two matrices $A$ and $B$ to be $d_C(A,B) = ||A-B||\_C$
What is the cardinality of the smallest $\epsilon$-net of the metric space $([0,1]^{n\times n}, d_C)$?
i.e. the size of the smallest subset $S \subset \mathcal{R}_+^{n\times n}$ such that for all $A \in [0,1]^{n\times n}$, there exists an $A' \in S$ such that $d_C(A, A') \leq \epsilon$. (Note that I am allowing the entries in the net-matrices to lie outside the bounded range $[0,1]$)
I am interested in both upper bounds and lower bounds.
Edit: I have now cross-posted this question on the cstheory stack exchange.
