{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreihjlrnyunv6lcvnfo26zithdvcntukfipdulckm2wzyaseb5lwtiq",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mjct5jakgpv2"
  },
  "path": "/report/2026/056",
  "publishedAt": "2026-04-12T13:54:51.000Z",
  "site": "https://eccc.weizmann.ac.il",
  "textContent": "We develop a topological framework for proving lower bounds on sign-rank via $\\mathbb{Z}_2$–equivariant topology, and use it to resolve the sign-rank of the Gap Hamming Distance problem up to lower-order terms. For every (partial) sign matrix $A$, we associate a free $\\mathbb{Z}_2$–simplicial complex $S(A)$ and show that sign-rank of $A$ is characterized by the linear analog of $\\mathbb{Z}_2$-index of $S(A)$. As a consequence, the classical $\\mathbb{Z}_2$–index of $S(A)$ lower bounds the sign-rank of $A$, which reduces sign-rank lower bounds to topological obstructions. This reduction allows us to use various tools from $\\mathbb{Z}_2$–equivariant topology, particularly in regimes where classical lower-bound techniques break down. As the main application, we consider the Gap Hamming Distance function $\\mathrm{GHD}_k^n$ (defined for $k < n/2$), which distinguishes pairs of strings in $\\\\{0,1\\\\}^n$ with Hamming distance at most $k$ from pairs with distance at least $n-k$. We prove an essentially tight lower bound and show that for any $k$, \\\\[ \\text{sign-rank}(\\mathrm{GHD}_k^n) = (1-o_k(1))\\,2k. \\\\] where the $o_k(1)$ term is $O\\left(\\sqrt{\\frac{\\log k}{k}}\\right)$. This improves on the previous lower bound of Hatami, Hosseini, and Meng (STOC 2023) who proved that sign-rank of $\\mathrm{GHD}_k^n$ is at least $\\Omega(k/\\log(n/k))$. A key technical ingredient is a new analysis of the $\\mathbb{Z}_2$-coindex (which lower bounds $\\mathbb{Z}_2$-index) of the Vietoris--Rips complex of the hypercube in the sparse regime which yields an essentially tight lower bound. Previously, no results were known in the sparse regime.",
  "title": "TR26-056 |  A $\\mathbb{Z}_2$–Topological Framework for Sign-rank Lower Bounds | \n\n\tKaave Hosseini, \n\n\tFlorian Frick, \n\n\tAliaksei Vasileuski"
}