The moment-sum-of-squares (moment-SOS) hierarchy is one of the most celebrated and widely applied methods for approximating the minimum of an n-variate polynomial over a feasible region defined by polynomial (in)equalities. A key feature of the hierarchy is that, at a fixed level, it can be formulated as a semidefinite program of size polynomial in the number of variables n. Although this suggests that it may therefore be computed in polynomial time, this is not necessarily the case. Indeed, as O’Donnell [16] and later Raghavendra & Weitz [20] show, there exist examples where the sos-representations used in the hierarchy have exponential bit-complexity. We study the computational complexity of the moment-SOS hierarchy, complementing and expanding upon earlier work of Raghavendra & Weitz [20]. In particular, we establish algebraic and geometric conditions under which polynomial-time computation is guaranteed to be possible.

We introduce and study two new pricing problems in networks: Suppose we are given a directed graph G = (V, E) with non-negative edge costs (c_e)_{e in E}, k commodities (s_i, t_i, w_i)_{i in [k]} and a designated node u in V. Each commodity i in [k] is represented by a source-target pair (s_i, t_i) in V x V and a demand w_i>0, specifying that w_i units of flow are sent from s_i to t_i along shortest s_i, t_i-paths (with respect to (c_e)_{e in E}). The demand of each commodity is split evenly over all shortest paths. Assume we can change the edge costs of some of the outgoing edges of u, while the costs of all other edges remain fixed; we also say that we price (or tax) the edges of u. We study the problem of pricing the edges of u with respect to the following two natural objectives: (i) max-flow: maximize the total flow passing through u, and (ii) max-revenue: maximize the total revenue (flow times tax) through u. Both variants have various applications in practice. For example, the max flow objective is equivalent to maximizing the betweenness centrality of u, which is one of the most popular measures for the influence of a node in a (social) network. We prove that (except for some special cases) both problems are NP-hard and inapproximable in general and therefore resort to approximation algorithms. We derive approximation algorithms for both variants and show that the derived approximation guarantees are best possible.

For $$n,d,w \in \mathbb {N}$$ n , d , w ∈ N , let A(n, d, w) denote the maximum size of a binary code of word length n, minimum distance d and constant weight w. Schrijver recently showed using semidefinite programming that $$A(23,8,11)=1288$$ A ( 23 , 8 , 11 ) = 1288 , and the second author that $$A(22,8,11)=672$$ A ( 22 , 8 , 11 ) = 672 and $$A(22,8,10)=616$$ A ( 22 , 8 , 10 ) = 616 . Here we show uniqueness of the codes achieving these bounds. Let A(n, d) denote the maximum size of a binary code of word length n and minimum distance d. Gijswijt et al. showed that $$A(20,8)=256$$ A ( 20 , 8 ) = 256 . We show that there are several nonisomorphic codes achieving this bound, and classify all such codes with all distances divisible by 4.

For nonnegative integers n, d, and w, let A(n,d,w) be the maximum size of a code C⊆F2nwith a constant weight w and minimum distance at least d. We consider two semidefinite programs based on quadruples of code words that yield several new upper bounds on A(n,d,w). The new upper bounds imply that A(22,8,10)=616 and A(22,8,11)=672. Lower bounds on A(22,8,10) and A(22,8,11) are obtained from the (n,d)=(22,7) shortened Golay code of size 2048. It can be concluded that the shortened Golay code is a union of constant-weight w codes of sizes A(22,8,w).

For $$q,n,d \in \mathbb {N}$$ , let $$A_q(n,d)$$ be the maximum size of a code $$C \subseteq [q]^n$$ with minimum distance at least d. We give a divisibility argument resulting in the new upper bounds $$A_5(8,6) \le 65$$ , $$A_4(11,8)\le 60$$ and $$A_3(16,11) \le 29$$ . These in turn imply the new upper bounds $$A_5(9,6) \le 325$$ , $$A_5(10,6) \le 1625$$ , $$A_5(11,6) \le 8125$$ and $$A_4(12,8) \le 240$$ . Furthermore, we prove that for $$\mu ,q \in \mathbb {N}$$ , there is a 1–1-correspondence between symmetric $$(\mu ,q)$$ -nets (which are certain designs) and codes $$C \subseteq [q]^{\mu q}$$ of size $$\mu q^2$$ with minimum distance at least $$\mu q - \mu $$ . We derive the new upper bounds $$A_4(9,6) \le 120$$ and $$A_4(10,6) \le 480$$ from these ‘symmetric net’ codes.

For nonnegative integers q, n, d, let $$A_q(n,d)$$ denote the maximum cardinality of a code of length n over an alphabet [q] with q letters and with minimum distance at least d. We consider the following upper bound on $$A_q(n,d)$$ . For any k, let $$\mathcal{C}_k$$ be the collection of codes of cardinality at most k. Then $$A_q(n,d)$$ is at most the maximum value of $$\sum _{v\in [q]^n}x(\{v\})$$ , where x is a function $$\mathcal{C}_4\rightarrow {\mathbb {R}}_+$$ such that $$x(\emptyset )=1$$ and $$x(C)=\!0$$ if C has minimum distance less than d, and such that the $$\mathcal{C}_2\times \mathcal{C}_2$$ matrix $$(x(C\cup C'))_{C,C'\in \mathcal{C}_2}$$ is positive semidefinite. By the symmetry of the problem, we can apply representation theory to reduce the problem to a semidefinite programming problem with order bounded by a polynomial in n. It yields the new upper bounds $$A_4(6,3)\le 176$$ , $$A_4(7,3)\le 596$$ , $$A_4(7,4)\le 155$$ , $$A_5(7,4)\le 489$$ , and $$A_5(7,5)\le 87$$ .