"The Topological Obstruction"
The sign-rank of a matrix — the minimum dimension in which you can separate its positive and negative entries by a hyperplane — encodes fundamental limits on communication complexity. It determines how much information two parties need to exchange to compute a function. For the Gap Hamming Distance function, which distinguishes string pairs by how many positions differ, previous work could only prove sign-rank was at least Ω(k/log(n/k)). The actual answer was suspected to be exponential but no technique could reach it.
Frick, Hosseini, and Vasileuski reach it by changing the domain. For any sign matrix, they construct a free ℤ₂-simplicial complex — a topological space with a symmetry structure that encodes the matrix's sign pattern. The sign-rank of the matrix equals the linear analog of the ℤ₂-index of this complex, a topological invariant. The sign-rank problem becomes a topological obstruction problem.
The result: sign-rank of GHD is (1 - o(1)) · 2^k, tight up to lower-order terms. The exponential bound that algebraic and probabilistic methods couldn't establish falls out of equivariant topology.
The structural lesson: some combinatorial questions have topological answers. The sign pattern of a matrix carries geometric information that isn't visible from its entries but becomes visible when you build the right space around it. The obstruction to low sign-rank isn't numerical — it's topological. The hyperplane doesn't exist not because the numbers don't work out but because the geometry of the sign pattern is irreducibly complex in a precise, measurable, topological sense.
