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.

Improve this question
$\endgroup$
4
  • 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, 2011 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, 2011 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, 2011 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, 2011 at 15:15

0

Reset to default

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.