Sign-Rank of k-Hamming Distance is Constant

2025/05/01 by Mika Göös, Nathaniel Harms, Göös, Mika +5
Computer Science · #68Q15 #Algorithms and Data Compression #Computational Complexity (cs.CC) #F.1.3 #FOS: Computer and information sciences #Neural Networks and Applications

paper · pdf · doi:10.48550/arxiv.2506.12022

openalex publication_date 2025/05/01 · openalex created_date 2025/10/13 · openalex updated_date 2026/07/28

Abstract

We prove that the sign-rank of the k-Hamming Distance matrix on n bits is 2^O(k), independent of the number of bits n. This strongly refutes the conjecture of Hatami, Hatami, Pires, Tao, and Zhao (RANDOM 2022), and Hatami, Hosseini, and Meng (STOC 2023), repeated in several other papers, that the sign-rank should depend on n. This conjecture would have qualitatively separated margin from sign-rank (or, equivalently, bounded-error from unbounded-error randomized communication). In fact, our technique gives constant sign-rank upper bounds for all matrices which reduce to k-Hamming Distance, as well as large-margin matrices recently shown to be irreducible to k-Hamming Distance.

Citations

• Borsuk-Ulam and Replicable Learning of Large-Margin Halfspaces
• Factorization norms and Zarankiewicz problems
• Boolean combinations of graphs
• The Communication Complexity of Approximating Matrix Rank
• Better Boosting of Communication Oracles, or Not
• No Complete Problem for Constant-Cost Randomized Communication
• Structure in Communication Complexity and Constant-Cost Complexity Classes
• The discrepancy of greater-than
• Adjacency Sketches in Adversarial Environments
• Randomized Communication and Implicit Representations for Matrices and Graphs of Small Sign-Rank
• Sketching Distances in Monotone Graph Classes
• A counter-example to the probabilistic universal graph conjecture via randomized communication complexity
• Randomized Communication and Implicit Graph Representations
• Universal Communication, Universal Graphs, and Graph Labeling
• Sign-Rank Can Increase Under Intersection
• The Unbounded-Error Communication Complexity of symmetric XOR functions
• Sample Complexity Bounds on Differentially Private Learning via Communication Complexity
• Two notions of unit distance graphs
• A discrepancy lower bound for information complexity

Related

• Sign rank versus VC dimension
• On the Hamming Distance between base-n representations of whole numbers
• Hamming and simplex codes for the sum-rank metric
• Probabilistic Rank and Matrix Rigidity
• Constant-Cost Communication is not Reducible to k-Hamming Distance