Witsenhausen’s problem asks for the maximum fraction αn of the (n − 1)-dimensional unit sphere that can be covered by a measurable set containing no pairs of orthogonal points. The best upper bounds for αn are given by extensions of the Lovász theta number. In this paper, optimization hierarchies based on the Lovász theta number, like the Lasserre hierarchy, are extended to Witsenhausen’s problem and similar problems. These hierarchies are shown to converge and are used to compute the best upper bounds for αn in low dimensions.

The theta body of a graph, introduced by Grötschel, Lovász, and Schrijver (in 1986), is a tractable relaxation of the independent-set polytope derived from the Lovász theta number. In this paper, we recursively extend the theta body, and hence the theta number, to hypergraphs. We obtain fundamental properties of this extension and relate it to the high-dimensional Hoffman bound of Filmus, Golubev, and Lifshitz. We discuss two applications: triangle-free graphs and Mantel’s theorem, and bounds on the density of triangle-avoiding sets in the Hamming cube.

The average kissing number in ℝⁿ is the supremum of the average degrees of contact graphs of packings of finitely many balls (of any radii) in ℝⁿ. We provide an upper bound for the average kissing number based on semidefinite programming that improves previous bounds in dimensions 3,.., 9. A very simple upper bound for the average kissing number is twice the kissing number; in dimensions 6,.., 9 our new bound is the first to improve on this simple upper bound.

We propose a hierarchy of k-point bounds extending the Delsarte–Goethals–Seidel linear programming 2-point bound and the Bachoc–Vallentin semidefinite programming 3-point bound for spherical codes. An optimized implementation of this hierarchy allows us to compute 4, 5, and 6-point bounds for the maximum number of equiangular lines in Euclidean space with a fixed common angle.

We describe a factor-revealing convex optimization problem for the integrality gap of the maximum-cut semidefinite programming relaxation: for each n 2 we present a convex optimization problem whose optimal value is the largest possible ratio between the value of an optimal rank-n solution to the relaxation and the value of an optimal cut. This problem is then used to compute lower bounds for the integrality gap.

In this paper we prove a theorem that provides an upper bound for the density of packings of congruent copies of a given convex body in ℝⁿ; this theorem is a generalization of the linear programming bound for sphere packings. We illustrate its use by computing an upper bound for the maximum density of packings of regular pentagons in the plane. Our computational approach is numerical and uses a combination of semidefinite programming, sums of squares, and the harmonic analysis of the Euclidean motion group. We show how, with some extra work, the bounds so obtained can be made rigorous.