{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreidozsheneaaotdw67knvh4ui2rbs3s4776kjjsd24v347h5db62iq",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3ml3dp6wubk22"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2605.01038v1",
  "publishedAt": "2026-05-05T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Riju Bindu",
    "Hamed Hatami",
    "Hasti Karimi",
    "Robert Robere"
  ],
  "textContent": "**Authors:** Riju Bindu, Hamed Hatami, Hasti Karimi, Robert Robere\n\nWe prove new upper and lower bounds on $ε$-approximate sign-rank, a relaxation of sign-rank introduced by Chornomaz, Moran, and Waknine (STOC 2025). We show that every $m \\times n$ sign matrix with approximate sign-rank $d$ contains a monochromatic rectangle of size $d^{-O(d)}m \\times d^{-O(d^2)}n$, paralleling classical results for exact sign-rank. As an application, we establish a lower bound of $Ω(\\sqrt{d/\\log d})$ on the $ε$-approximate sign-rank of large-margin $d$-dimensional half-spaces. Prior to our work, the only general lower bound technique known for approximate sign-rank yielded bounds of strength $ε^{-1} - 1$, which are constant for fixed $ε$. A key ingredient is a new geometric theorem on hyperplane avoidance: for any set of $n$ points in general position in $\\mathbb{R}^d$, there exist $d$ subsets, each of size $d^{-O(d)} n$, such that no hyperplane simultaneously splits all of them. The proof combines the Forster-Barthe isotropic position theorem with the Bourgain-Tzafriri restricted invertibility principle. We also study the relationship between approximate sign-rank and VC dimension. We prove a lower bound on approximate sign-rank in terms of VC dimension, and exhibit concept classes of VC dimension $2$ with large approximate sign-rank. Finally, we study the approximate sign-rank of the $2^m \\times 2^m$ Hadamard matrix $H_m$. The sign-rank of $H_m$ is known to be $Ω(\\sqrt{2^m})$ by Forster's classic theorem. Contrasting this, we adapt an argument of Alman and Williams to show that the approximate sign-rank of $H_m$ is at most $m^{O(\\sqrt{m} \\log(1/ε))}$, and hence the Hadamard matrix does not witness polynomial-strength lower bounds for approximate sign-rank. Using our VC dimension bound, we prove that the approximate sign-rank of $H_m$ is at least $Ω_ε(m)$.",
  "title": "Lower Bounds for Approximate Sign Rank"
}