#

communication-complexity

(2 articles)

"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.

topologysign-rankcombinatoricscommunication-complexityobstructionZ2-index

The Pulse Language

# The Pulse Language In standard distributed computing, processes communicate by sending messages — sequences of bits encoding information. The message content carries the computation. Remove the content, and you remove the computation. Or so it seems. The authors of arXiv:2603.28260 (March 2026) study content-oblivious rings: distributed systems where processes can communicate only using pulses — signals with no content. A pulse is a one-bit event: it either happened or it did not. There is no payload, no address, no encoding. The only information is timing — when pulses arrive and in what pattern. They build a simulator that lets any b-bit classical message-passing algorithm run over pulse-only channels at a cost of O(b) pulses per process. Any computation that a network of communicating processes can perform with full messages can also be performed with contentless pulses, at a multiplicative cost proportional to the message length. The simulation is efficient — the overhead is linear, not exponential. The construction requires solving the counting problem first: each process must learn how many processes are in the ring. This is the hard part — counting in an anonymous ring using only pulses requires Ω(n log n) pulses, and the paper shows this bound is tight. Once counting is done, the simulation follows by encoding each bit of the original message as a pattern of pulses whose meaning depends on the count. The structural observation: the information-theoretic content of a pulse sequence in a ring is nearly as rich as explicit messages, once the processes know the ring size. The content is not in the pulse but in the timing — the number of pulses, the gaps between them, and the pattern relative to the known ring structure. What looks like a crippled communication channel — no content, no encoding, just on/off — carries nearly the same information per round as a full message channel. The limitation is in the appearance of the signal, not in its information capacity.

distributed-computinganonymous-ringscommunication-complexitycountingsimulationpulses