A randomly signed sum of vectors is a random variable of the form $X = \sum_{i=1}^n a_i x_i$, where $\{a_i\}$ are vectors in $R^d$ with $\sum_{i=1}^n ||a_i||_2^2=1$, and $\{x_i\}$ are independent 'random signs', distributed as $Pr[x_i=1]=Pr[x_i=-1]=1/2$. Questions regarding tail probabilities of the form $Pr[|X|<=a]$ and $Pr[|X|>=a]$ appear naturally in problems in optimization theory (e.g., when dealing with robust solutions of uncertain quadratic problems), as well as in various other fields, including probability theory, geometric analysis, statistics, and theoretical computer science. A well-known specific example is Tomaszewski's conjecture from 1986, which asserts that in the one-dimensional case (i.e., where $\{a_i\}$ are real numbers), we have $Pr[|X|<=1]>=1/2$. The conjecture was recently proved by the authors (Advances in Mathematics, 2022). This talk will survey the tools used in the proof of the conjecture, several very recent developments (including the sharp 'counterpart' bound $Pr[|X|>=1]>=7/32$ obtained by Hollom and Portier), and various questions which remain open.

Numerous applications require verifying the nonnegativity of a polynomial over a set defined by polynomial equalities and inequalities. A classical approach is to search for multipliers that would constitute a Sum-of-Squares certificate of the nonnegativity. While this corresponds to a hierarchy of convex programs, the size of these programs grows rapidly with the total degree of the multipliers. If a Gröbner basis for the ideal generated by the equalities is known, it would allow to drastically reduce the size of the program to solve. Such basis is however NP-hard to compute. Using information from the null space of a Macaulay matrix, we show how to reduce the size of the programs for any degree. While the program size converges to the size that would be obtained by the Gröbner basis approach, our approach does not need Gröbner basis to be computed and is therefore not limited to small size problems. Furthermore, we show how to also compute reduced gram bases for the multipliers associated to the inequalities by exploiting both properties of a Macaulay null space and Newton polytopes. We show applications of these results to the analysis of descriptor systems.

The sequential optimality conditions, which improve algorithm convergence assumptions, have been studied over the past two decades. In particular, by considering the second-order information, the so-called approximate Karush-Kuhn-Tucker 2 (AKKT2) conditions for nonlinear programming problems were also proposed. While studies on a more general conic problem have been conducted, an explicit definition for AKKT2 has not been proposed in the literature. This work addresses this gap by providing a precise definition of AKKT2 conditions for second-order cone programming problems. We prove that the proposed AKKT2 conditions hold at local optimal points, without any constraint qualifications. Moreover, we show two algorithms based on augmented Lagrangian and sequential quadratic programming approaches that generate points satisfying these conditions.