
We describe and analyze an algorithm for computing the homology (Betti
numbers and torsion coefficients) of basic semialgebraic sets which works in
weak exponential time. That is, out of a set of exponentially small measure in
the space of data the cost of the algorithm is exponential in the size of the
data. All algorithms previously proposed for this problem have a complexity
which is doubly exponential (and this is so for almost all data).

The permanent versus determinant conjecture is a major problem in complexity
theory that is equivalent to the separation of the complexity classes VP_{ws}
and VNP. Mulmuley and Sohoni (SIAM J. Comput., 2001) suggested to study a
strengthened version of this conjecture over the complex numbers that amounts
to separating the orbit closures of the determinant and padded permanent
polynomials. In that paper it was also proposed to separate these orbit
closures by exhibiting occurrence obstructions, which are irreducible
representations of GL_{n^2}(C), which occur in one coordinate ring of the orbit
closure, but not in the other. We prove that this approach is impossible.
However, we do not rule out the general approach to the permanent versus
determinant problem via multiplicity obstructions as proposed by Mulmuley and
Sohoni.

We present a polynomial time algorithm to approximately scale tensors of any
format to arbitrary prescribed marginals (whenever possible). This unifies and
generalizes a sequence of past works on matrix, operator and tensor scaling.
Our algorithm provides an efficient weak membership oracle for the associated
moment polytopes, an important family of implicitlydefined convex polytopes
with exponentially many facets and a wide range of applications. These include
the entanglement polytopes from quantum information theory (in particular, we
obtain an efficient solution to the notorious onebody quantum marginal
problem) and the Kronecker polytopes from representation theory (which capture
the asymptotic support of Kronecker coefficients). Our algorithm can be applied
to succinct descriptions of the input tensor whenever the marginals can be
efficiently computed, as in the important case of matrix product states or
tensortrain decompositions, widely used in computational physics and numerical
mathematics.
We strengthen and generalize the alternating minimization approach of
previous papers by introducing the theory of highest weight vectors from
representation theory into the numerical optimization framework. We show that
highest weight vectors are natural potential functions for scaling algorithms
and prove new bounds on their evaluations to obtain polynomialtime
convergence. Our techniques are general and we believe that they will be
instrumental to obtain efficient algorithms for moment polytopes beyond the
ones consider here, and more broadly, for other optimization problems
possessing natural symmetries.

We initiate the study of average intersection theory in real Grassmannians.
We define the expected degree $\textrm{edeg} G(k,n)$ of the real Grassmannian
$G(k,n)$ as the average number of real $k$planes meeting nontrivially $k(nk)$
random subspaces of $\mathbb{R}^n$, all of dimension $nk$, where these
subspaces are sampled uniformly and independently from $G(nk,n)$. We express
$\textrm{edeg} G(k,n)$ in terms of the volume of an invariant convex body in
the tangent space to the Grassmanian, and prove that for fixed $k\ge 2$ and
$n\to\infty$, $$ \textrm{edeg} G(k,n) = \textrm{deg}
G_\mathbb{C}(k,n)^{\frac{1}{2} \epsilon_k + o(1)}, $$ where $\textrm{deg}
G_\mathbb{C}(k,n)$ denotes the degree of the corresponding complex Grassmannian
and $\epsilon_k$ is monotonically decreasing with $\lim_{k\to\infty} \epsilon_k
= 1$. In the case of the Grassmannian of lines, we prove the finer asymptotic
\begin{equation*} \textrm{edeg} G(2,n+1) = \frac{8}{3\pi^{5/2}\sqrt{n}}\,
\left(\frac{\pi^2}{4} \right)^n \left(1+\mathcal{O}(n^{1})\right).
\end{equation*} The expected degree turns out to be the key quantity governing
questions of the random enumerative geometry of flats. We associate with a
semialgebraic set $X\subseteq\mathbb{R}\textrm{P}^{n1}$ of dimension $nk1$
its Chow hypersurface $Z(X)\subseteq G(k,n)$, consisting of the $k$planes $A$
in $\mathbb{R}^n$ whose projectivization intersects $X$. Denoting $N:=k(nk)$,
we show that $$ \mathbb{E}\#\left(g_1Z(X_1)\cap\cdots\cap g_N Z(X_N)\right)
= \textrm{edeg} G(k,n) \cdot \prod_{i=1}^{N}
\frac{X_i}{\mathbb{R}\textrm{P}^{m}}, $$ where each $X_i$ is of dimension
$m=nk1$, the expectation is taken with respect to independent uniformly
distributed $g_1,\ldots,g_m\in O(n)$ and $X_i$ denotes the $m$dimensional
volume of $X_i$.

We show that the problem of deciding membership in the moment polytope
associated with a finitedimensional unitary representation of a compact,
connected Lie group is in NP and coNP. This is the first nontrivial result on
the computational complexity of this problem, which naively amounts to a
quadraticallyconstrained program. Our result applies in particular to the
Kronecker polytopes, and therefore to the problem of deciding positivity of the
stretched Kronecker coefficients. In contrast, it has recently been shown that
deciding positivity of a single Kronecker coefficient is NPhard in general
[Ikenmeyer, Mulmuley and Walter, arXiv:1507.02955]. We discuss the consequences
of our work in the context of complexity theory and the quantum marginal
problem.

The numerical condition of the problem of intersecting a fixed
$m$dimensional irreducible complex projective variety $Z\subseteq\mathbb{P}^n$
with a varying linear subspace $L\subseteq\mathbb{P}^n$ of complementary
dimension $s=nm$ is studied. We define the intersection condition number
$\kappa_Z(L,z)$ at a smooth intersection point $z\in Z\cap L$ as the norm of
the derivative of the locally defined solution map
$\mathbb{G}(s,\mathbb{P}^n)\to\mathbb{P}^n,\, L\mapsto z$. We show that
$\kappa_Z(L,z) = 1/\sin\alpha$, where $\alpha$ is the minimum angle between the
tangent spaces $T_zZ$ and $T_zL$. From this, we derive a condition number
theorem that expresses $1/\kappa_Z(L,z)$ as the distance of $L$ to the local
Schubert variety, which consists of the linear subspaces having an illposed
intersection with $Z$ at $z$. A probabilistic analysis of the maximum condition
number $\kappa_Z(L) := \max \kappa_Z(L,z_i)$, taken over all intersection
points $z_i\in Z\cap L$, leads to the study of the volume of tubes around the
Hurwitz hypersurface $\Sigma(Z)$. As a first step towards this, we express the
volume of $\Sigma(Z)$ in terms of its degree.

We give an introduction to some of the recent ideas that go under the name
"geometric complexity theory". We first sketch the proof of the known upper and
lower bounds for the determinantal complexity of the permanent. We then
introduce the concept of a representation theoretic obstruction, which has
close links to algebraic combinatorics, and we explain some of the insights
gained so far. In particular, we address very recent insights on the complexity
of testing the positivity of Kronecker coefficients. We also briefly discuss
the related asymptotic version of this question.

Let $f=(f_1,\ldots,f_n)$ be a system of $n$ complex homogeneous polynomials
in $n$ variables of degree $d$. We call $\lambda\in\mathbb{C}$ an eigenvalue of
$f$ if there exists $v\in\mathbb{C}^n\backslash\{0\}$ with $f(v)=\lambda v$,
generalizing the case of eigenvalues of matrices ($d=1$). We derive the
distribution of $\lambda$ when the $f_i$ are independently chosen at random
according to the unitary invariant Weyl distribution and determine the limit
distribution for $n\to\infty$.

For several objects of interest in geometric complexity theory, namely for
the determinant, the permanent, the product of variables, the power sum, the
unit tensor, and the matrix multiplication tensor, we introduce and study a
fundamental SLinvariant function that relates the coordinate ring of the orbit
with the coordinate ring of its closure. For the power sums we can write down
this fundamental invariant explicitly in most cases. Our constructions
generalize the two Aronhold invariants on ternary cubics. For the other objects
we identify the invariant function conditional on intriguing combinatorial
problems much like the wellknown AlonTarsi conjecture on Latin squares. We
provide computer calculations in small dimensions for these cases. As a main
tool for our analysis, we determine the stabilizers, and we establish the
polystability of all the mentioned forms and tensors (including the generic
ones).

Quadrics in the Grassmannian of lines in 3space form a 19dimensional
projective space. We study the subvariety of coisotropic hypersurfaces.
Following Gel'fand, Kapranov and Zelevinsky, it decomposes into Chow forms of
plane conics, Chow forms of pairs of lines, and Hurwitz forms of quadric
surfaces. We compute the ideals of these loci.

Smale's 17th problem asks for an algorithm which finds an approximate zero of
polynomial systems in average polynomial time (see Smale 2000). The main
progress on Smale's problem is Beltr\'anPardo (2011) and B\"urgisserCucker
(2010). In this paper we will improve on both approaches and we prove an
important intermediate result. Our main results are Theorem 1 on the complexity
of a randomized algorithm which improves the result of Beltr\'anPardo (2011),
Theorem 2 on the average of the condition number of polynomial systems which
improves the estimate found in B\"urgisserCucker (2010), and Theorem 3 on the
complexity of finding a single zero of polynomial systems. This last Theorem is
the main result of B\"urgisserCucker (2010). We give a proof of it relying
only on homotopy methods, thus removing the need for the elimination theory
methods used in B\"urgisserCucker (2010). We build on methods developed in
Armentano et al. (2015).

Let Det_n denote the closure of the GL_{n^2}(C)orbit of the determinant
polynomial det_n with respect to linear substitution. The highest weights
(partitions) of irreducible GL_{n^2}(C)representations occurring in the
coordinate ring of Det_n form a finitely generated monoid S(Det_n). We prove
that the saturation of S(Det_n) contains all partitions lambda with length at
most n and size divisible by n. This implies that representation theoretic
obstructions for the permanent versus determinant problem must be holes of the
monoid S(Det_n).

We describe algorithms for computing eigenpairs (eigenvalueeigenvector
pairs) of a complex $n\times n$ matrix $A$. These algorithms are numerically
stable, strongly accurate, and theoretically efficient (i.e., polynomialtime).
We do not believe they outperform in practice the algorithms currently used for
this computational problem. The merit of our paper is to give a positive answer
to a longstanding open problem in numerical linear algebra.

We describe algorithms for computing eigenpairs (eigenvalueeigenvector) of
a complex $n\times n$ matrix $A$. These algorithms are numerically stable,
strongly accurate, and theoretically efficient (i.e., polynomialtime). We do
not believe they outperform in practice the algorithms currently used for this
computational problem. The merit of our paper is to give a positive answer to a
longstanding open problem in numerical linear algebra.

We analyze the probability that a random mdimensional linear subspace of R^n
both intersects a regular closed convex cone C\subseteq R^n and lies within
distance \alpha of an mdimensional subspace not intersecting C (except at the
origin). The result is expressed in terms of the spherical intrinsic volumes of
the cone C. This allows us to perform an average analysis of the Grassmann
condition number \C(A) for the homogeneous convex feasibility problem \exists
x\in C\setminus 0 : Ax=0. The Grassmann condition number is a geometric version
of Renegar's condition number, that we have introduced recently in [SIOPT
22(3):10291041, 2012]. We thus give the first average analysis of convex
programming that is not restricted to linear programming. In particular, we
prove that if the entries of A\in R^{m\times n} are chosen i.i.d. standard
normal, then for any regular cone C, we have E[ln\C(A)]<1.5 ln(n)+1.5. The
proofs rely on various techniques from Riemannian geometry applied to Grassmann
manifolds.

Starting with Knutson and Tao's hive model (in J. Amer. Math. Soc., 1999) we
characterize the LittlewoodRichardson coefficient $c_{\lambda,\mu}^\nu$ of
given partitions $\lambda,\mu,\nu\in N^n$ as the number of capacity achieving
hive flows on the honeycomb graph. Based on this, we design a polynomial time
algorithm for deciding $c_{\lambda,\mu}^\nu >0$. This algorithm is easy to
state and takes $O(n^3 \log \nu_1)$ arithmetic operations and comparisons. We
further show that the capacity achieving hive flows can be seen as the vertices
of a connected graph, which leads to new structural insights into
LittlewoodRichardson coefficients.

We prove the lower bound R(M_m) \geq 3/2 m^2  2 on the border rank of m x m
matrix multiplication by exhibiting explicit representation theoretic
(occurence) obstructions in the sense of the geometric complexity theory (GCT)
program. While this bound is weaker than the one recently obtained by Landsberg
and Ottaviani, these are the first significant lower bounds obtained within the
GCT program. Behind the proof is the new combinatorial concept of obstruction
designs, which encode highest weight vectors in Sym^d\otimes^3(C^n)^* and
provide new insights into Kronecker coefficients.

We prove that for any partition $(\lambda_1,...,\lambda_{d^2})$ of size $\ell
d$ there exists $k\ge 1$ such that the tensor square of the irreducible
representation of the symmetric group $S_{k\ell d}$ with respect to the
rectangular partition $(k\ell,...,k\ell)$ contains the irreducible
representation corresponding to the stretched partition
$(k\lambda_1,...,k\lambda_{d^2})$. We also prove a related approximate version
of this statement in which the stretching factor $k$ is effectively bounded in
terms of $d$. This investigation is motivated by questions of geometric
complexity theory.

We introduce and analyze a natural geometric version of Renegar's condition
number R for the homogeneous convex feasibility problem associated with a
regular cone C subseteq R^n. Let Gr_{n,m} denote the Grassmann manifold of
mdimensional linear subspaces of R^n and consider the projection distance
d_p(W_1,W_2) := Pi_{W_1}  Pi_{W_2} (spectral norm) between W_1 and W_2 in
Gr_{n,m}, where Pi_{W_i} denotes the orthogonal projection onto W_i. We call
C_G(W) := max {d_p(W,W')^{1}  W' \in Sigma_m} the Grassmann condition number
of W in Gr_{n,m}, where the set of illposed instances Sigma_m subset Gr_{n,m}
is defined as the set of linear subspaces touching C. We show that if W =
im(A^T) for a matrix A in R^{m\times n}, then C_G(W) \le R(A) \le C_G(W)
kappa(A), where kappa(A) =A A^\dagger denotes the matrix condition
number. This extends work by Belloni and Freund in Math. Program. 119:95107
(2009). Furthermore, we show that C_G(W) can as well be characterized in terms
of the Riemannian distance metric on Gr_{n,m}. This differential geometric
characterization of C_G(W) is the starting point of the sequel
[arXiv:1112.2603] to this paper, where the first probabilistic analysis of
Renegar's condition number for an arbitrary regular cone C is achieved.

We compute the intrinsic volumes of the cone of positive semidefinite
matrices over the real numbers, over the complex numbers, and over the
quaternions, in terms of integrals related to Mehta's integral. Several
applications for the probabilistic analysis of semidefinite programming are
given.

We prove that for all natural numbers k,n,d with k <= d and every partition
lambda of size kn with at most k parts there exists an irreducible GL(d,
C)representation of highest weight 2*lambda in the plethysm Sym^k(Sym^(2n)
(C^d)). This gives an affirmative answer to a conjecture by Weintraub (J.
Algebra, 129 (1):103114, 1990). Our investigation is motivated by questions of
geometric complexity theory and uses ideas from quantum information theory.

This paper has two agendas. Firstly, we exhibit new results for coverage
processes. Let $p(n,m,\alpha)$ be the probability that $n$ spherical caps of
angular radius $\alpha$ in $S^m$ do not cover the whole sphere $S^m$. We give
an exact formula for $p(n,m,\alpha)$ in the case $\alpha\in[\pi/2,\pi]$ and an
upper bound for $p(n,m,\alpha)$ in the case $\alpha\in [0,\pi/2]$ which tends
to $p(n,m,\pi/2)$ when $\alpha\to\pi/2$. In the case $\alpha\in[0,\pi/2]$ this
yields upper bounds for the expected number of spherical caps of radius
$\alpha$ that are needed to cover $S^m$. Secondly, we study the condition
number ${\mathscr{C}}(A)$ of the linear programming feasibility problem
$\exists x\in\mathbb{R}^{m+1}Ax\le0,x\ne0$ where
$A\in\mathbb{R}^{n\times(m+1)}$ is randomly chosen according to the standard
normal distribution. We exactly determine the distribution of
${\mathscr{C}}(A)$ conditioned to $A$ being feasible and provide an upper bound
on the distribution function in the infeasible case. Using these results, we
show that $\mathbf{E}(\ln{\mathscr{C}}(A))\le2\ln(m+1)+3.31$ for all $n>m$, the
sharpest bound for this expectancy as of today. Both agendas are related
through a result which translates between coverage and condition.

We perform a smoothed analysis of the GCCcondition number C(A) of the linear
programming feasibility problem \exists x\in\R^{m+1} Ax < 0. Suppose that
\bar{A} is any matrix with rows \bar{a_i} of euclidean norm 1 and,
independently for all i, let a_i be a random perturbation of \bar{a_i}
following the uniform distribution in the spherical disk in S^m of angular
radius \arcsin\sigma and centered at \bar{a_i}. We prove that E(\ln C(A)) =
O(mn / \sigma). A similar result was shown for Renegar's condition number and
Gaussian perturbations by Dunagan, Spielman, and Teng [arXiv:cs.DS/0302011].
Our result is robust in the sense that it easily extends to radially symmetric
probability distributions supported on a spherical disk of radius
\arcsin\sigma, whose density may even have a singularity at the center of the
perturbation. Our proofs combine ideas from a recent paper of B\"urgisser,
Cucker, and Lotz (Math. Comp. 77, No. 263, 2008) with techniques of Dunagan et
al.