.png){kind=icon}
Return
The Generalized Trifference Problem
.png){kind=icon}
PRE
AI
DOI：10.1109/tit.2026.3665439.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We study the problem of finding the largest number T(n,m) of ternary vectors of length n such that for any three distinct vectors there are at least m coordinates where they pairwise differ. This problem is a special case of the perfect k-hashing problem in theoretical computer science, corresponding to the k=3 case. For m=1 , we get the classical trifference problem which is wide open. We prove upper and lower bounds on T(n,m) for various ranges of the parameter m and determine the phase transition threshold on m=m(n) where T(n,m) jumps from constant to exponential in n. By relating the linear version of this problem to a problem on blocking sets in finite geometry, we give explicit constructions and probabilistic lower bounds. We also compute the exact values of this function and its linear variation for small parameters. Moreover, we relate the trifference problem to the sunflower conjecture.
Keywords:
k-hashing
minimal codes
trifference problem
Journal
I
IF:
2.9
Papers:
317
Citations:
0
Organization
Cited Papers
.png){kind=icon}
ShareSaveShareSaveShareSave
View more