Biblio

We show that the basic semidefinite programming relaxation value of any constraint satisfaction problem can be computed in NC; that is, in parallel polylogarithmic time and polynomial work. As a complexity-theoretic consequence we get that $\backslash$MIPone[k,c,s] $\backslash$subseteq $\backslash$PSPACE provided s/c $\backslash$leq (.62-o(1))k/2textasciicircumk, resolving a question of Austrin, H$\backslash$aa stad, and Pass. Here $\backslash$MIPone[k,c,s] is the class of languages decidable with completeness c and soundness s by an interactive proof system with k provers, each constrained to communicate just 1 bit.

We prove that the integrality gap of the Goemans–Linial semidefinite programming relaxation for the Sparsest Cut Problem is Î\textcopyright(√logn) on inputs with n vertices, thus matching the previously best known upper bound (logn)1/2+o(1) up to lower-order factors. This statement is a consequence of the following new isoperimetric-type inequality. Consider the 8-regular graph whose vertex set is the 5-dimensional integer grid â„\textcurrency5 and where each vertex (a,b,c,d,e)∈ â„\textcurrency5 is connected to the 8 vertices (aÂ$\pm$ 1,b,c,d,e), (a,bÂ$\pm$ 1,c,d,e), (a,b,cÂ$\pm$ 1,d,eÂ$\pm$ a), (a,b,c,dÂ$\pm$ 1,eÂ$\pm$ b). This graph is known as the Cayley graph of the 5-dimensional discrete Heisenberg group. Given Î\textcopyright⊂ â„\textcurrency5, denote the size of its edge boundary in this graph (a.k.a. the horizontal perimeter of Î\textcopyright) by textbar∂hÎ\textcopyrighttextbar. For t∈ ℕ, denote by textbar∂vtÎ\textcopyrighttextbar the number of (a,b,c,d,e)∈ â„\textcurrency5 such that exactly one of the two vectors (a,b,c,d,e),(a,b,c,d,e+t) is in Î\textcopyright. The vertical perimeter of Î\textcopyright is defined to be textbar∂vÎ\textcopyrighttextbar= √∑t=1∞textbar∂vtÎ\textcopyrighttextbar2/t2. We show that every subset Î\textcopyright⊂ â„\textcurrency5 satisfies textbar∂vÎ\textcopyrighttextbar=O(textbar∂hÎ\textcopyrighttextbar). This vertical-versus-horizontal isoperimetric inequality yields the above-stated integrality gap for Sparsest Cut and answers several geometric and analytic questions of independent interest. The theorem stated above is the culmination of a program whose aim is to understand the performance of the Goemans–Linial semidefinite program through the embeddability properties of Heisenberg groups. These investigations have mathematical significance even beyond their established relevance to approximation algorithms and combinatorial optimization. In particular they contribute to a range of mathematical disciplines including functional analysis, geometric group theory, harmonic analysis, sub-Riemannian geometry, geometric measure theory, ergodic theory, group representations, and metric differentiation. This article builds on the above cited works, with the “twist” that while those works were equally valid for any finite dimensional Heisenberg group, our result holds for the Heisenberg group of dimension 5 (or higher) but fails for the 3-dimensional Heisenberg group. This insight leads to our core contribution, which is a deduction of an endpoint L1-boundedness of a certain singular integral on ℝ5 from the (local) L2-boundedness of the corresponding singular integral on ℝ3. To do this, we devise a corona-type decomposition of subsets of a Heisenberg group, in the spirit of the construction that David and Semmes performed in ℝn, but with two main conceptual differences (in addition to more technical differences that arise from the peculiarities of the geometry of Heisenberg group). Firstly, the“atoms” of our decomposition are perturbations of intrinsic Lipschitz graphs in the sense of Franchi, Serapioni, and Serra Cassano (plus the requisite “wild” regions that satisfy a Carleson packing condition). Secondly, we control the local overlap of our corona decomposition by using quantitative monotonicity rather than Jones-type Î$^2$-numbers.

We consider a class of robust optimization problems that we call “robust-to-dynamics optimization” (RDO). The input to an RDO problem is twofold: (i) a mathematical program (e.g., an LP, SDP, IP, etc.), and (ii) a dynamical system (e.g., a linear, nonlinear, discrete, or continuous dynamics). The objective is to maximize over the set of initial conditions that forever remain feasible under the dynamics. The focus of this paper is on the case where the optimization problem is a linear program and the dynamics are linear. We establish some structural properties of the feasible set and prove that if the linear system is asymptotically stable, then the RDO problem can be solved in polynomial time. We also outline a semidefinite programming based algorithm for providing upper bounds on robust-to-dynamics linear programs.