VC dimension of disambiguations of Gap Hamming Distance

Establish the existence of a function g(k) → ∞ such that for every total completion A of the Gap Hamming Distance partial function GHD_k^n (obtained by assigning arbitrary signs to all unspecified entries), the VC dimension satisfies VC(A) ≥ g(k).

Background

The authors prove essentially tight lower bounds on the Z2-coindex of the sign complex S(GHD_kn), and discuss implications of relating coindex to VC dimension for total concept classes. They highlight a well-known learning-theoretic challenge about whether disambiguations (total completions) of large-margin halfspaces must have growing VC dimension.

They state a conjecture (attributed to Alon et al.) in a stronger form within their framework, asking for a function g(k) that lower bounds the VC dimension of any total completion of GHD_kn, thereby connecting geometric/topological obstructions to learnability.

References

it immediately implies the following, which is a strong form of a major open problem on learnability of disambiguations of the concept class of half-spaces with margin conjectured by Alon et. al., . Conjecture There exists a function $g(k)\to\infty$ such that the following is true: for every completion of $\GHD_kn$ to a total sign matrix $A$ by changing all the $*$ outputs of $\GHD_kn$ arbitrarily to $-1$,$1$,

\VC(A)\ge g(k).

— A $\mathbb{Z}_2$-Topological Framework for Sign-rank Lower Bounds  (2604.01510 - Frick et al., 2 Apr 2026) in Section 7, Concluding remarks and open questions (Conjecture \ref{conj:disambig})