13
$\begingroup$

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.

| cite | improve this question | |
$\endgroup$
  • 1
    $\begingroup$ There is an upper bound independent of $n$ by compactness: set $m=2^{100/\epsilon^2}$, then the $m$-by-$m$ matrices with entries in $\{0,epsilon/2,\cdots,1\}$ give an $\epsilon$-net, I think. See cs.elte.hu/~lovasz/analyst.pdf . Prop 7.1 of that paper gives a lower bound of $2^{1/\epsilon}$ on the size of a weak Szemeredi partition but I don't see a way to translate that into a lower bound on the cardinality of an $\epsilon$-net. $\endgroup$ – Colin McQuillan Jan 28 '11 at 10:01
  • $\begingroup$ Can you elaborate on your first point? How are you thinking about the distance between an $m\times m$ matrix and an $n\times n$ matrix for $n \neq m$? $\endgroup$ – Aaron Jan 28 '11 at 13:13
  • $\begingroup$ Ah yes, sorry, that's using a slightly different notion of cut norm based on "fractional overlays". You can consider a square matrix as a function defined on the unit interval (or any probability space) and then compare different-sized matrices. See Theorem 2.3 of "Convergent Sequences of Dense Graphs I" research.microsoft.com/en-us/um/people/jchayes/Papers/… for a relationship $\endgroup$ – Colin McQuillan Jan 29 '11 at 11:07
  • $\begingroup$ Thanks for the reference. They seem to normalize their cut norm by $1/n^2$, so translating into an un-normalized world, this seems to require setting $m = 2^{2n^4/\epsilon^2}$. $\endgroup$ – Aaron Jan 29 '11 at 15:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.