
In this paper we present a deterministic polynomial time algorithm for
testing if a symbolic matrix in noncommuting variables over $\mathbb{Q}$ is
invertible or not. The analogous question for commuting variables is the
celebrated polynomial identity testing (PIT) for symbolic determinants. In
contrast to the commutative case, which has an efficient probabilistic
algorithm, the best previous algorithm for the noncommutative setting required
exponential time (whether or not randomization is allowed). The algorithm
efficiently solves the "word problem" for the free skew field, and the identity
testing problem for arithmetic formulae with division over noncommuting
variables, two problems which had only exponentialtime algorithms prior to
this work.
The main contribution of this paper is a complexity analysis of an existing
algorithm due to Gurvits, who proved it was polynomial time for certain classes
of inputs. We prove it always runs in polynomial time. The main component of
our analysis is a simple (given the necessary known tools) lower bound on
central notion of capacity of operators (introduced by Gurvits). We extend the
algorithm to actually approximate capacity to any accuracy in polynomial time,
and use this analysis to give quantitative bounds on the continuity of capacity
(the latter is used in a subsequent paper on BrascampLieb inequalities).
Symbolic matrices in noncommuting variables, and the related structural and
algorithmic questions, have a remarkable number of diverse origins and
motivations. They arise independently in (commutative) invariant theory and
representation theory, linear algebra, optimization, linear system theory,
quantum information theory, approximation of the permanent and naturally in
noncommutative algebra. We provide a detailed account of some of these sources
and their interconnections.

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.

The celebrated BrascampLieb (BL) inequalities (and their extensions) are an
important mathematical tool, unifying and generalizing numerous inequalities in
analysis, convex geometry and information theory. While their structural theory
is very well understood, far less is known about computing their main
parameters.
We give polynomial time algorithms to compute feasibility of BLdatum, the
optimal BLconstant and a weak separation oracle for the BLpolytope. The same
result holds for the socalled Reverse BL inequalities of Barthe. The best
known algorithms for any of these tasks required at least exponential time.
The algorithms are obtained by a simple efficient reduction of a given
BLdatum to an instance of the Operator Scaling problem defined by Gurvits, for
which the present authors have provided a polynomial time algorithm. This
reduction implies algorithmic versions of many of the known structural results,
and in some cases provide proofs that are different or simpler than existing
ones.
Of particular interest is the fact that the operator scaling algorithm is
continuous in its input. Thus as a simple corollary of our reduction we obtain
explicit bounds on the magnitude and continuity of the BLconstant in terms of
the BLdata. To the best of our knowledge no such bounds were known, as past
arguments relied on compactness. The continuity of BLconstants is important
for developing nonlinear BL inequalities that have recently found so many
applications.

We propose a new secondorder method for geodesically convex optimization on
the natural hyperbolic metric over positive definite matrices. We apply it to
solve the operator scaling problem in time polynomial in the input size and
logarithmic in the error. This is an exponential improvement over previous
algorithms which were analyzed in the usual Euclidean, "commutative" metric
(for which the above problem is not convex). Our method is general and
applicable to other settings.
As a consequence, we solve the equivalence problem for the leftright group
action underlying the operator scaling problem. This yields a deterministic
polynomialtime algorithm for a new class of Polynomial Identity Testing (PIT)
problems, which was the original motivation for studying operator scaling.

Design matrices are sparse matrices in which the supports of different
columns intersect in a few positions. Such matrices come up naturally when
studying problems involving point sets with many collinear triples. In this
work we consider design matrices with block (or matrix) entries. Our main
result is a lower bound on the rank of such matrices, extending the bounds
proved in {BDWY12,DSW12} for the scalar case. As a result we obtain several
applications in combinatorial geometry. The first application involves
extending the notion of structural rigidity (or graph rigidity) to the setting
where we wish to bound the number of `degrees of freedom' in perturbing a set
of points under collinearity constraints (keeping some family of triples
collinear). Other applications are an asymptotically tight SylvesterGallai
type result for arrangements of subspaces (improving {DH16}) and a new
incidence bound for high dimensional line/curve arrangements.
The main technical tool in the proof of the rank bound is an extension of the
technique of matrix scaling to the setting of block matrices. We generalize the
definition of doubly stochastic matrices to matrices with block entries and
derive sufficient conditions for a doubly stochastic scaling to exist.

In the automation of many kinds of processes, the observable outcome can
often be described as the combined effect of an entire sequence of actions, or
controls, applied throughout its execution. In these cases, strategies to
optimise control policies for individual stages of the process might not be
applicable, and instead the whole policy might have to be optimised at once. On
the other hand, the cost to evaluate the policy's performance might also be
high, being desirable that a solution can be found with as few interactions as
possible with the real system. We consider the problem of optimising control
policies to allow a robot to complete a given race track within a minimum
amount of time. We assume that the robot has no prior information about the
track or its own dynamical model, just an initial valid driving example.
Localisation is only applied to monitor the robot and to provide an indication
of its position along the track's centre axis. We propose a method for finding
a policy that minimises the time per lap while keeping the vehicle on the track
using a Bayesian optimisation (BO) approach over a reproducing kernel Hilbert
space. We apply an algorithm to search more efficiently over highdimensional
policyparameter spaces with BO, by iterating over each dimension individually,
in a sequential coordinate descentlike scheme. Experiments demonstrate the
performance of the algorithm against other methods in a simulated car racing
environment.

In outdoor environments, mobile robots are required to navigate through
terrain with varying characteristics, some of which might significantly affect
the integrity of the platform. Ideally, the robot should be able to identify
areas that are safe for navigation based on its own percepts about the
environment while avoiding damage to itself. Bayesian optimisation (BO) has
been successfully applied to the task of learning a model of terrain
traversability while guiding the robot through more traversable areas. An
issue, however, is that localisation uncertainty can end up guiding the robot
to unsafe areas and distort the model being learnt. In this paper, we address
this problem and present a novel method that allows BO to consider localisation
uncertainty by applying a Gaussian process model for uncertain inputs as a
prior. We evaluate the proposed method in simulation and in experiments with a
real robot navigating over rough terrain and compare it against standard BO
methods.

We develop several efficient algorithms for the classical \emph{Matrix
Scaling} problem, which is used in many diverse areas, from preconditioning
linear systems to approximation of the permanent. On an input $n\times n$
matrix $A$, this problem asks to find diagonal (scaling) matrices $X$ and $Y$
(if they exist), so that $X A Y$ $\varepsilon$approximates a doubly
stochastic, or more generally a matrix with prescribed row and column sums.
We address the general scaling problem as well as some important special
cases. In particular, if $A$ has $m$ nonzero entries, and if there exist $X$
and $Y$ with polynomially large entries such that $X A Y$ is doubly stochastic,
then we can solve the problem in total complexity $\tilde{O}(m + n^{4/3})$.
This greatly improves on the best known previous results, which were either
$\tilde{O}(n^4)$ or $O(m n^{1/2}/\varepsilon)$.
Our algorithms are based on tailormade first and second order techniques,
combined with other recent advances in continuous optimization, which may be of
independent interest for solving similar problems.

In this paper we give subexponential size hitting sets for bounded depth
multilinear arithmetic formulas. Using the known relation between blackbox PIT
and lower bounds we obtain lower bounds for these models.
For depth3 multilinear formulas, of size $\exp(n^\delta)$, we give a hitting
set of size $\exp(\tilde{O}(n^{2/3 + 2\delta/3}))$. This implies a lower bound
of $\exp(\tilde{\Omega}(n^{1/2}))$ for depth3 multilinear formulas, for some
explicit polynomial.
For depth4 multilinear formulas, of size $\exp(n^\delta)$, we give a hitting
set of size $\exp(\tilde{O}(n^{2/3 + 4\delta/3}))$. This implies a lower bound
of $\exp(\tilde{\Omega}(n^{1/4}))$ for depth4 multilinear formulas, for some
explicit polynomial.
A regular formula consists of alternating layers of $+,\times$ gates, where
all gates at layer $i$ have the same fanin. We give a hitting set of size
(roughly) $\exp\left(n^{1 \delta} \right)$, for regular depth$d$ multilinear
formulas of size $\exp(n^\delta)$, where $\delta = O(\frac{1}{\sqrt{5}^d})$.
This result implies a lower bound of roughly
$\exp(\tilde{\Omega}(n^{\frac{1}{\sqrt{5}^d}}))$ for such formulas.
We note that better lower bounds are known for these models, but also that
none of these bounds was achieved via construction of a hitting set. Moreover,
no lower bound that implies such PIT results, even in the whitebox model, is
currently known.
Our results are combinatorial in nature and rely on reducing the underlying
formula, first to a depth4 formula, and then to a readonce algebraic
branching program (from depth3 formulas we go straight to readonce algebraic
branching programs).

Two polynomials $f, g \in \mathbb{F}[x_1, \ldots, x_n]$ are called
shiftequivalent if there exists a vector $(a_1, \ldots, a_n) \in \mathbb{F}^n$
such that the polynomial identity $f(x_1+a_1, \ldots, x_n+a_n) \equiv
g(x_1,\ldots,x_n)$ holds. Our main result is a new randomized algorithm that
tests whether two given polynomials are shift equivalent. Our algorithm runs in
time polynomial in the circuit size of the polynomials, to which it is given
black box access. This complements a previous work of Grigoriev (Theoretical
Computer Science, 1997) who gave a deterministic algorithm running in time
$n^{O(d)}$ for degree $d$ polynomials.
Our algorithm uses randomness only to solve instances of the Polynomial
Identity Testing (PIT) problem. Hence, if one could derandomize PIT (a
longstanding open problem in complexity) a derandomization of our algorithm
would follow. This establishes an equivalence between derandomizing
shiftequivalence testing and derandomizing PIT (both in the blackbox and the
whitebox setting). For certain restricted models, such as Read Once Branching
Programs, we already obtain a deterministic algorithm using existing PIT
results.