Skip to main content
add new reference to Barg and Nogin's work
Source Link

I don't know what they were thinking in the past, but there are moreseveral modern points of view these days.

  1. We can view the Delsarte LP as the symmetrization of a very large LP (or as the symmetrization of the Lovász theta function SDP on the hypercube graph with edges between strings of distance $\le d$). The Kravchuk polynomials arise naturally in this way since they are the symmetrization of the Boolean Fourier characters. Symmetrization makes the program exponentially smaller, but it does not change the value.
  2. The candidate solution to the Delsarte LP has the form $(a-x) F(x)^2$ after applying Christoffel-Darboux to the candidate $\beta(x)$ in the question. The term $(a-x)$ enforces the sign constraints of the LP, and $\widehat{F}(x)$ is chosen to be an approximate eigenfunction to the matrix $a\cdot\text{Id} - A$. Here $A$ is the adjacency matrix of the standard Boolean hypercube, then symmetry-reduced into a matrix on $\{0,1, \dots, n\}$. The approximate eigenfunction condition guarantees that the MacWilliams identities are satisfied. See "An Elementary Proof of the First LP Bound on the Rate of Binary Codes" by Nati Linial and Elyassaf Loyfer for more on this perspective (for disclosure, they are my collaborators).
  3. A precise perspective which constructs an exact eigenfunction (ultimately achieving the same asymptotic bound) is given in "Spectral Approach to Linear Programming Bounds on Codes" by Barg and Nogin.

See "An Elementary Proof of the First LP Bound on the Rate of Binary Codes" by Nati Linial and Elyassaf Loyfer for more on this perspective (for disclosure, they are my collaborators)

I don't know what they were thinking in the past, but there are more modern points of view these days.

  1. We can view the Delsarte LP as the symmetrization of a very large LP (or as the symmetrization of the Lovász theta function SDP on the hypercube graph with edges between strings of distance $\le d$). The Kravchuk polynomials arise naturally in this way since they are the symmetrization of the Boolean Fourier characters. Symmetrization makes the program exponentially smaller, but it does not change the value.
  2. The candidate solution to the Delsarte LP has the form $(a-x) F(x)^2$ after applying Christoffel-Darboux to the candidate $\beta(x)$ in the question. The term $(a-x)$ enforces the sign constraints of the LP, and $\widehat{F}(x)$ is chosen to be an approximate eigenfunction to the matrix $a\cdot\text{Id} - A$. Here $A$ is the adjacency matrix of the standard Boolean hypercube, then symmetry-reduced into a matrix on $\{0,1, \dots, n\}$. The approximate eigenfunction condition guarantees that the MacWilliams identities are satisfied.

See "An Elementary Proof of the First LP Bound on the Rate of Binary Codes" by Nati Linial and Elyassaf Loyfer for more on this perspective (for disclosure, they are my collaborators)

I don't know what they were thinking in the past, but there are several modern points of view these days.

  1. We can view the Delsarte LP as the symmetrization of a very large LP (or as the symmetrization of the Lovász theta function SDP on the hypercube graph with edges between strings of distance $\le d$). The Kravchuk polynomials arise naturally in this way since they are the symmetrization of the Boolean Fourier characters. Symmetrization makes the program exponentially smaller, but it does not change the value.
  2. The candidate solution to the Delsarte LP has the form $(a-x) F(x)^2$ after applying Christoffel-Darboux to the candidate $\beta(x)$ in the question. The term $(a-x)$ enforces the sign constraints of the LP, and $\widehat{F}(x)$ is chosen to be an approximate eigenfunction to the matrix $a\cdot\text{Id} - A$. Here $A$ is the adjacency matrix of the standard Boolean hypercube, then symmetry-reduced into a matrix on $\{0,1, \dots, n\}$. The approximate eigenfunction condition guarantees that the MacWilliams identities are satisfied. See "An Elementary Proof of the First LP Bound on the Rate of Binary Codes" by Nati Linial and Elyassaf Loyfer for more on this perspective (for disclosure, they are my collaborators).
  3. A precise perspective which constructs an exact eigenfunction (ultimately achieving the same asymptotic bound) is given in "Spectral Approach to Linear Programming Bounds on Codes" by Barg and Nogin.
added 10 characters in body
Source Link

I don't know what they were thinking in the past, but there are more modern points of view these days.

  1. We can view the Delsarte LP as the symmetrization of a very large LP (or as the symmetrization of the Lovász theta function SDP on the hypercube graph with edges between strings of distance $\le d$). The Kravchuk polynomials arise naturally in this way since they are the symmetrization of the Boolean Fourier characters. Symmetrization makes the program exponentially smaller, but it does not change the value.
  2. The candidate solution to the Delsarte LP has the form $(a-x) F(x)^2$ after applying Christoffel-Darboux to the candidate $\beta(x)$ in the question. The term $(a-x)$ enforces the sign constraints of the LP, and $F(x)$$\widehat{F}(x)$ is chosen to be an approximate eigenfunction to the matrix $a\cdot\text{Id} - A$. Here $A$ is the adjacency matrix of the standard Boolean hypercube, then symmetry-reduced into a matrix on $\{0,1, \dots, n\}$. The approximate eigenfunction condition guarantees that the MacWilliams identities are satisfied.

See "An Elementary Proof of the First LP Bound on the Rate of Binary Codes" by Nati Linial and Elyassaf Loyfer for more on this perspective (for disclosure, they are my collaborators)

I don't know what they were thinking in the past, but there are more modern points of view these days.

  1. We can view the Delsarte LP as the symmetrization of a very large LP (or as the symmetrization of the Lovász theta function SDP on the hypercube graph with edges between strings of distance $\le d$). The Kravchuk polynomials arise naturally in this way since they are the symmetrization of the Boolean Fourier characters. Symmetrization makes the program exponentially smaller, but it does not change the value.
  2. The candidate solution to the Delsarte LP has the form $(a-x) F(x)^2$ after applying Christoffel-Darboux to the candidate $\beta(x)$ in the question. The term $(a-x)$ enforces the sign constraints of the LP, and $F(x)$ is chosen to be an approximate eigenfunction to the matrix $a\cdot\text{Id} - A$. Here $A$ is the adjacency matrix of the standard Boolean hypercube, then symmetry-reduced into a matrix on $\{0,1, \dots, n\}$. The approximate eigenfunction condition guarantees that the MacWilliams identities are satisfied.

See "An Elementary Proof of the First LP Bound on the Rate of Binary Codes" by Nati Linial and Elyassaf Loyfer for more on this perspective (for disclosure, they are my collaborators)

I don't know what they were thinking in the past, but there are more modern points of view these days.

  1. We can view the Delsarte LP as the symmetrization of a very large LP (or as the symmetrization of the Lovász theta function SDP on the hypercube graph with edges between strings of distance $\le d$). The Kravchuk polynomials arise naturally in this way since they are the symmetrization of the Boolean Fourier characters. Symmetrization makes the program exponentially smaller, but it does not change the value.
  2. The candidate solution to the Delsarte LP has the form $(a-x) F(x)^2$ after applying Christoffel-Darboux to the candidate $\beta(x)$ in the question. The term $(a-x)$ enforces the sign constraints of the LP, and $\widehat{F}(x)$ is chosen to be an approximate eigenfunction to the matrix $a\cdot\text{Id} - A$. Here $A$ is the adjacency matrix of the standard Boolean hypercube, then symmetry-reduced into a matrix on $\{0,1, \dots, n\}$. The approximate eigenfunction condition guarantees that the MacWilliams identities are satisfied.

See "An Elementary Proof of the First LP Bound on the Rate of Binary Codes" by Nati Linial and Elyassaf Loyfer for more on this perspective (for disclosure, they are my collaborators)

Source Link

I don't know what they were thinking in the past, but there are more modern points of view these days.

  1. We can view the Delsarte LP as the symmetrization of a very large LP (or as the symmetrization of the Lovász theta function SDP on the hypercube graph with edges between strings of distance $\le d$). The Kravchuk polynomials arise naturally in this way since they are the symmetrization of the Boolean Fourier characters. Symmetrization makes the program exponentially smaller, but it does not change the value.
  2. The candidate solution to the Delsarte LP has the form $(a-x) F(x)^2$ after applying Christoffel-Darboux to the candidate $\beta(x)$ in the question. The term $(a-x)$ enforces the sign constraints of the LP, and $F(x)$ is chosen to be an approximate eigenfunction to the matrix $a\cdot\text{Id} - A$. Here $A$ is the adjacency matrix of the standard Boolean hypercube, then symmetry-reduced into a matrix on $\{0,1, \dots, n\}$. The approximate eigenfunction condition guarantees that the MacWilliams identities are satisfied.

See "An Elementary Proof of the First LP Bound on the Rate of Binary Codes" by Nati Linial and Elyassaf Loyfer for more on this perspective (for disclosure, they are my collaborators)