{
  "id": "1910.09416",
  "version": "v1",
  "published": "2019-10-21T14:45:35.000Z",
  "updated": "2019-10-21T14:45:35.000Z",
  "title": "An Improved Linear Programming Bound on the Average Distance of a Binary Code",
  "authors": [
    "Lei Yu",
    "Vincent Y. F. Tan"
  ],
  "comment": "17 pages, 2 figures",
  "categories": [
    "math.CO",
    "cs.DM",
    "cs.IT",
    "math.IT",
    "math.MG"
  ],
  "abstract": "Ahlswede and Katona (1977) posed the following isodiametric problem in Hamming spaces: For every $n$ and $1\\le M\\le2^{n}$, determine the minimum average Hamming distance of binary codes with length $n$ and size $M$. Fu, Wei, and Yeung (2001) used linear programming duality to derive a lower bound on the minimum average distance. However, their linear programming approach was not completely exploited. In this paper, we improve Fu-Wei-Yeung's bound by finding a better feasible solution to their dual program. For fixed $0<a\\le1/2$ and for $M=\\left\\lceil a2^{n}\\right\\rceil $, our feasible solution attains the asymptotically optimal value of Fu-Wei-Yeung's dual program as $n\\to\\infty$. Hence for $0<a\\le1/2$, all possible asymptotic bounds that can be derived by Fu-Wei-Yeung's linear program have been characterized. Furthermore, noting that the average distance of a code is closely related to weights of Fourier coefficients of a Boolean function, we also apply the linear programming technique to prove bounds on Fourier weights of a Boolean function of various degrees.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-10-21T14:45:35.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "linear programming bound",
      "binary code",
      "boolean function",
      "minimum average distance",
      "minimum average hamming distance"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 17,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}