
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.

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 design a deterministic polynomial time $c^n$ approximation algorithm for
the permanent of positive semidefinite matrices where $c=e^{\gamma+1}\simeq
4.84$. We write a natural convex relaxation and show that its optimum solution
gives a $c^n$ approximation of the permanent. We further show that this factor
is asymptotically tight by constructing a family of positive semidefinite
matrices.

Many physical parameters that can be estimated from space mission tracking
data influence both the translational dynamics and proper time rates of
observers. These different proper time rates cause a variability of the time
transfer observable beyond that caused by their translational (and rotational)
dynamics. With the nearfuture implementation of (interplanetary) transponder
laser ranging, these effects will become increasingly important, requiring a
reevaluation of the common data analysis practice of using a priori time
ephemerides, which is the goal of this paper.
We develop a framework for the simultaneous estimation of the initial
translational state and the initial proper time of an observer, with the goal
of facilitating robust tracking data analysis from nextgeneration space
missions carrying highly accurate clocks and tracking equipment. Using our
approach, the influence of physical parameters on both translational and time
dynamics are considered at the same level in the analysis, and mutual
correlations between the signatures of the two are automatically identified. We
perform a covariance analysis using our proposed method with simulated laser
data from Earthbased stations to both a Mars and Mercury lander.
Using four years of tracking data for the Mars lander simulations, we find a
difference between our results using the simultaneous spacetime dynamics
estimation and the classical analysis technique (with an ta priori time
ephemeris) of around 0.1 % in formal errors and correlation coefficients. For a
Mercury lander this rises to around 1% for a 1month mission and 10 % for a
4year mission. By means of Monte Carlo simulation, we find that using an a
priori time ephemeris of representative accuracy will result in estimation
errors that are orders of magnitude above the formal error when processing
highly accurate laser time transfer data.

Relativistic jets in active galactic nuclei (AGN) are among the most powerful
astrophysical objects discovered to date. Indeed, jetted AGN studies have been
considered a prominent science case for SKA, and were included in several
different chapters of the previous SKA Science Book (Carilli & Rawlings 2004).
Most of the fundamental questions about the physics of relativistic jets still
remain unanswered, and await highsensitivity radio instruments such as SKA to
solve them. These questions will be addressed specially through analysis of the
massive data sets arising from the deep, allsky surveys (both total and
polarimetric flux) from SKA1. Widefield verylongbaselineinterferometric
survey observations involving SKA1 will serve as a unique tool for
distinguishing between extragalactic relativistic jets and star forming
galaxies via brightness temperature measurements. Subsequent SKA1 studies of
relativistic jets at different resolutions will allow for unprecedented
cosmological studies of AGN jets up to the epoch of reionization, enabling
detailed characterization of the jet composition, magnetic field, particle
populations, and plasma properties on all scales. SKA will enable us to study
the dependence of jet power and star formation on other properties of the AGN
system. SKA1 will enable such studies for large samples of jets, while VLBI
observations involving SKA1 will provide the sensitivity for pcscale imaging,
and SKA2 (with its extraordinary sensitivity and dynamic range) will allow us
for the first time to resolve and model the weakest radio structures in the
most powerful radioloud AGN.

Adding VLBI capability to the SKA arrays will greatly broaden the science of
the SKA, and is feasible within the current specifications. SKAVLBI can be
initially implemented by providing phasedarray outputs for SKA1MID and
SKA1SUR and using these extremely sensitive stations with other radio
telescopes, and in SKA2 by realising a distributed configuration providing
baselines up to thousands of km, merging it with existing VLBI networks. The
motivation for and the possible realization of SKAVLBI is described in this
paper.

The vast collecting area of the Square Kilometre Array (SKA), harnessed by
sensitive receivers, flexible digital electronics and increased computational
capacity, could permit the most sensitive and exhaustive search for
technologicallyproduced radio emission from advanced extraterrestrial
intelligence (SETI) ever performed. For example, SKA1MID will be capable of
detecting a source roughly analogous to terrestrial highpower radars (e.g. air
route surveillance or ballistic missile warning radars, EIRP (EIRP = equivalent
isotropic radiated power, ~10^17 erg sec^1) at 10 pc in less than 15 minutes,
and with a modest four beam SETI observing system could, in one minute, search
every star in the primary beam out to ~100 pc for radio emission comparable to
that emitted by the Arecibo Planetary Radar (EIRP ~2 x 10^20 erg sec^1). The
flexibility of the signal detection systems used for SETI searches with the SKA
will allow new algorithms to be employed that will provide sensitivity to a
much wider variety of signal types than previously searched for.
Here we discuss the astrobiological and astrophysical motivations for radio
SETI and describe how the technical capabilities of the SKA will explore the
radio SETI parameter space. We detail several conceivable SETI experimental
programs on all components of SKA1, including commensal, primaryuser, targeted
and survey programs and project the enhancements to them possible with SKA2. We
also discuss target selection criteria for these programs, and in the case of
commensal observing, how the varied use cases of other primary observers can be
used to full advantage for SETI.

We give new lower and upper bounds on the permanent of a doubly stochastic
matrix. Combined with previous work, this improves on the deterministic
approximation factor for the permanent.
We also give a combinatorial application of the lower bound, proving S.
Friedland's "Asymptotic Lower Matching Conjecture" for the monomerdimer
problem.

The Xray transient MAXI J1836194 is a newlyidentified Galactic black hole
binary candidate. As most Xray transients, it was discovered at the beginning
of an Xray outburst. After the initial canonical Xray hard state, the
outburst evolved into a hard intermediate state and then went back to the hard
state. The existing RATAN600 radio monitoring observations revealed that it
was variable on a timescale of days and had a flat or inverted spectrum,
consistent with optically thick synchrotron emission, possibly from a
selfabsorbed jet in the vicinity of the central compact object. We observed
the transient in the hard state near the end of the Xray outburst with the
European VLBI Network (EVN) at 5 GHz and the Chinese VLBI Network (CVN) at 2.3
and 8.3 GHz. The 8.3 GHz observations were carried out at a recording rate of
2048 Mbps using the newlydeveloped Chinese VLBI data acquisition system
(CDAS), twice higher than the recording rate used in the other observations. We
successfully detected the lowdeclination source with a high confidence level
in both observations. The source was unresolved (<=0.5 mas), which is in
agreement with an AUscale compact jet.

We examine a twoperson game we call WillTesting in which the strategy space
for both players is a real number. It has no equilibrium. When an infinitely
large set of players plays this in all possible pairings, there is an
equilibrium for the distribution of strategies which requires all players to
use different strategies. We conjecture this solution could underlie some
phenomena (like pecking orders) observed in animals.

Let $A \in \Omega_n$ be doublystochastic $n \times n$ matrix. Alexander
Schrijver proved in 1998 the following remarkable inequality per(\widetilde{A})
\geq \prod_{1 \leq i,j \leq n} (1 A(i,j)); \widetilde{A}(i,j) =:
A(i,j)(1A(i,j)), 1 \leq i,j \leq n.
We use the above Shrijver's inequality to prove the following lower bound:
\frac{per(A)}{F(A)} \geq 1; F(A) =: \prod_{1 \leq i,j \leq n} (1 A(i,j))^{1
A(i,j)}.
We use this new lower bound to prove S.Friedland's Asymptotic Lower Matching
Conjecture(LAMC) on monomerdimer problem.
We use some ideas of our proof of (LAMC) to disprove [Lu,Mohr,Szekely]
positive correlation conjecture.
We present explicit doublystochastic $n \times n$ matrices $A$ with the
ratio $\frac{per(A)}{F(A)} = \sqrt{2}^{n}$; conjecture that
\max_{A \in \Omega_n}\frac{per(A)}{F(A)} \approx (\sqrt{2})^{n} and give some
examples supporting the conjecture.
If true, the conjecture (and other ones stated in the paper) would imply a
deterministic polytime algorithm to approximate the permanent of $n \times n$
nonnegative matrices within the relative factor $(\sqrt{2})^{n}$. The best
current such factor is $e^n$.

This paper has been withdrawn by the author as one of the coauthors needs
institutional permission.

An upper bound on the ergodic capacity of {\bf MIMO} channels was introduced
recently in arXiv:0903.1952. This upper bound amounts to the maximization on
the simplex of some multilinear polynomial $p(\lambda_1,...,\lambda_n)$ with
nonnegative coefficients. Interestingly, the coefficients are subpermanents of
some nonnegative matrix. In general, such maximizations problems are {\bf
NPHARD}. But if say, the functional $\log(p)$ is concave on the simplex and
can be efficiently evaluated, then the maximization can also be done
efficiently. Such logconcavity was conjectured in arXiv:0903.1952. We give in
this paper selfcontained proof of the conjecture, based on the theory of {\bf
HStable} polynomials.

We study multivariate entire functions and polynomials with nonnegative
coefficients. A class of {\bf Strongly LogConcave} entire functions,
generalizing {\it Minkowski} volume polynomials, is introduced: an entire
function $f$ in $m$ variables is called {\bf Strongly LogConcave} if the
function $(\partial x_1)^{c_1}...(\partial x_m)^{c_m} f$ is either zero or
$\log((\partial x_1)^{c_1}...(\partial x_m)^{c_m} f)$ is concave on
$R_{+}^{m}$. We start with yet another point of view (via {\it propagation}) on
the standard univarite (or homogeneous bivariate) {\bf Newton Inequlities}. We
prove analogues of (univariate) {\bf Newton Inequlities} in the (multivariate)
{\bf Strongly LogConcave} case. One of the corollaries of our new Newton(like)
inequalities is the fact that the support $supp(f)$ of a {\bf Strongly
LogConcave} entire function $f$ is discretely convex ($D$convex in our
notation). The proofs are based on a natural convex relaxation of the
derivatives $Der_{f}(r_1,...,r_m)$ of $f$ at zero and on the lower bounds on
$Der_{f}(r_1,...,r_m)$, which generalize the {\bf Van Der
WaerdenFalikmanEgorychev} inequality for the permanent of doublystochastic
matrices. A few open questions are posed in the final section.

Let ${\bf K} = (K_1, ..., K_n)$ be an $n$tuple of convex compact subsets in
the Euclidean space $\R^n$, and let $V(\cdot)$ be the Euclidean volume in
$\R^n$. The Minkowski polynomial $V_{{\bf K}}$ is defined as $V_{{\bf
K}}(\lambda_1, ... ,\lambda_n) = V(\lambda_1 K_1 +, ..., + \lambda_n K_n)$ and
the mixed volume $V(K_1, ..., K_n)$ as $$ V(K_1, ..., K_n) =
\frac{\partial^n}{\partial \lambda_1...\partial \lambda_n} V_{{\bf
K}}(\lambda_1 K_1 +, ..., + \lambda_n K_n). $$ Our main result is a polytime
algorithm which approximates $V(K_1, ..., K_n)$ with multiplicative error $e^n$
and with better rates if the affine dimensions of most of the sets $K_i$ are
small. Our approach is based on a particular approximation of $\log(V(K_1, ...,
K_n))$ by a solution of some convex minimization problem. We prove the mixed
volume analogues of the Van der Waerden and SchrijverValiant conjectures on
the permanent. These results, interesting on their own, allow us to justify the
abovementioned approximation by a convex minimization, which is solved using
the ellipsoid method and a randomized polytime time algorithm for the
approximation of the volume of a convex set.

Let $p$ be a homogeneous polynomial of degree $n$ in $n$ variables,
$p(z_1,...,z_n) = p(Z)$, $Z \in C^{n}$. We call such a polynomial $p$ {\bf
HStable} if $p(z_1,...,z_n) \neq 0$ provided the real parts $Re(z_i) > 0, 1
\leq i \leq n$. This notion from {\it Control Theory} is closely related to the
notion of {\it Hyperbolicity} used intensively in the {\it PDE} theory.
The main theorem in this paper states that if $p(x_1,...,x_n)$ is a
homogeneous {\bf HStable} polynomial of degree $n$ with nonnegative
coefficients; $deg_{p}(i)$ is the maximum degree of the variable $x_i$, $C_i =
\min(deg_{p}(i),i)$ and $$ Cap(p) = \inf_{x_i > 0, 1 \leq i \leq n}
\frac{p(x_1,...,x_n)}{x_1 ... x_n} $$ then the following inequality holds $$
\frac{\partial^n}{\partial x_1... \partial x_n} p(0,...,0) \geq Cap(p) \prod_{2
\leq i \leq n} (\frac{C_i 1}{C_i})^{C_{i}1}. $$
This inequality is a vast (and unifying) generalization of the Van der
Waerden conjecture on the permanents of doubly stochastic matrices as well as
the SchrijverValiant conjecture on the number of perfect matchings in
$k$regular bipartite graphs. These two famous results correspond to the {\bf
HStable} polynomials which are products of linear forms.
Our proof is relatively simple and ``noncomputational''; it uses just very
basic properties of complex numbers and the AM/GM inequality.

R. Pemantle conjectured, and T.M. Liggett proved in 1997, that the
convolution of two ultralogconcave is ultralogconcave. Liggett's proof is
elementary but long. We present here a short proof, based on the mixed volume
of convex sets.

We derive here the FriedlandTverberg inequality for positive hyperbolic
polynomials. This inequality is applied to give lower bounds for the number of
matchings in $r$regular bipartite graphs. It is shown that some of these
bounds are asymptotically sharp. We improve the known lower bound for the three
dimensional monomerdimer entropy. We present Ryserlike formulas for
computations of matchings in bipartite and general graphs. Additional
algorithmic applications are given.

Let $p(x_1,...,x_n) = p(X), X \in R^{n}$ be a homogeneous polynomial of
degree $n$ in $n$ real variables, $e = (1,1,..,1) \in R^n$ be a vector of all
ones . Such polynomial $p$ is called $e$hyperbolic if for all real vectors $X
\in R^{n}$ the univariate polynomial equation $P(te  X) = 0$ has all real
roots $\lambda_{1}(X) \geq ... \geq \lambda_{n}(X)$ . The number of nonzero
roots $\{i :\lambda_{i}(X) \neq 0 \}$ is called $Rank_{p}(X)$ . A
$e$hyperbolic polynomial $p$ is called $POS$hyperbolic if roots of vectors $X
\in R^{n}_{+}$ with nonnegative coordinates are also nonnegative (the orthant
$R^{n}_{+}$ belongs to the hyperbolic cone) and $p(e) > 0$ . Below
$\{e_1,...,e_n\}$ stands for the canonical orthogonal basis in $R^{n}$. The
main results states that if $p(x_1,x_2,...,x_n)$ is a $POS$hyperbolic
(homogeneous) polynomial of degree $n$, $Rank_{p} (e_{i}) = R_i$ and $
p(x_1,x_2,...,x_n) \geq \prod_{1 \leq i \leq n} x_i ; x_i > 0, 1 \leq i \leq n
, $ then the following inequality holds $$ \frac{\partial^n}{\partial
x_1...\partial x_n} p(0,...,0) \geq \prod_{1 \leq i \leq n} (\frac{G_{i}
1}{G_{i}})^{G_{i} 1} (G_i = \min(R_{i}, n+1i)) . $$ This theorem is a vast
(and unifying) generalization of as the van der Waerden conjecture on the
permanents of doubly stochastic matrices as well SchrijverValiant conjecture
on the number of perfect matchings in $k$regular bipartite graphs . The paper
is (almost) selfcontained, most of the proofs can be found in the {\bf
Appendices}.

Consider a homogeneous polynomial $p(z_1,...,z_n)$ of degree $n$ in $n$
complex variables . Assume that this polynomial satisfies the property : \\
$p(z_1,...,z_n) \geq \prod_{1 \leq i \leq n} Re(z_i)$ on the domain
$\{(z_1,...,z_n) : Re(z_i) \geq 0, 1 \leq i \leq n \}$ . \\
We prove that $\frac{\partial^n}{\partial z_1...\partial z_n} p  \geq
\frac{n!}{n^n}$ . Our proof is relatively short and selfcontained (i.e. we
only use basic properties of hyperbolic polynomials). As the van der Waerden
conjecture for permanents, proved by D.I. Falikman and G.P. Egorychev, as well
Bapat's conjecture for mixed discriminants, proved by the author, are
particular cases of this result. We also prove so called "small rank" lower
bound (in the permanents context it corresponds to sparse doublystochastic
matrices, i.e. with small number of nonzero entries in each column). The later
lower bound generalizes (with simpler proofs) recent lower bounds by
A.Schrijver for the number of perfect matchings of $k$regular bipartite
graphs.
We present some important algorithmic applications of the result, including a
polynomial time deterministic algorithm approximating the permanent of $n
\times n$ nonnegative entrywise matrices within multiplicative factor
$\frac{e^n}{n^m}$ for any fixed positive $m$ .

We show that for an mqubit quantum system, there is a ball of radius
asymptotically approaching kappa 2^{gamma m} in Frobenius norm, centered at
the identity matrix, of separable (unentangled) positive semidefinite matrices,
for an exponent gamma = (1/2)((ln 3/ln 2)  1), roughly .29248125. This is much
smaller in magnitude than the best previously known exponent, from our earlier
work, of 1/2. For normalized mqubit states, we get a separable ball of radius
sqrt(3^(m+1)/(3^m+3)) * 2^{(1 + \gamma)m}, i.e. sqrt{3^{m+1}/(3^m+3)}\times
6^{m/2} (note that \kappa = \sqrt{3}), compared to the previous 2 * 2^{3m/2}.
This implies that with parameters realistic for current experiments, NMR with
standard pseudopurestate preparation techniques can access only unentangled
states if 36 qubits or fewer are used (compared to 23 qubits via our earlier
results). We also obtain an improved exponent for mpartite systems of fixed
local dimension d_0, although approaching our earlier exponent as d_0
approaches infinity.

Let $p(x_1,...,x_n) =\sum_{(r_1,...,r_n) \in I_{n,n}} a_{(r_1,...,r_n)}
\prod_{1 \leq i \leq n} x_{i}^{r_{i}}$ be homogeneous polynomial of degree $n$
in $n$ real variables with integer nonnegative coefficients. The support of
such polynomial $p(x_1,...,x_n)$ is defined as $supp(p) = \{(r_1,...,r_n) \in
I_{n,n} : a_{(r_1,...,r_n)} \neq 0 \}$ . The convex hull $CO(supp(p))$ of
$supp(p)$ is called the Newton polytope of $p$ . We study the following
decision problems, which are farreaching generalizations of the classical
perfect matching problem : {itemize} {\bf Problem 1 .} Consider a homogeneous
polynomial $p(x_1,...,x_n)$ of degree $n$ in $n$ real variables with
nonnegative integer coefficients given as a black box (oracle) . {\it Is it
true that $(1,1,..,1) \in supp(p)$ ?} {\bf Problem 2 .} Consider a homogeneous
polynomial $p(x_1,...,x_n)$ of degree $n$ in $n$ real variables with
nonnegative integer coefficients given as a black box (oracle) . {\it Is it
true that $(1,1,..,1) \in CO(supp(p))$ ?} {itemize} We prove that for
hyperbolic polynomials these two problems are equivalent and can be solved by
deterministic polynomialtime oracle algorithms . This result is based on a
"hyperbolic" generalization of Rado theorem .

It is proved that the roots of combinations of matrix polynomials with real
roots can be recast as eigenvalues of combinations of real symmetric matrices,
under certain hypotheses. The proof is based on recent solution of the Lax
conjecture. Several applications and corollaries, in particular concerning
hyperbolic matrix polynomials, are presented.

We prove that the mixed discriminant of doubly stochastic $n$tuples of
semidefinite hermitian $n \times n$ matrices is bounded below by
$\frac{n!}{n^{n}}$ and that this bound is uniquely attained at the $n$tuple
$(\frac{1}{n} I,...,\frac{1}{n} I)$. This result settles a conjecture posed by
R. Bapat in 1989. We consider various generalizations and applications of this
result.

The main topic of this paper is various "hyperbolic" generalizations of the
EdmondsRado theorem on the rank of intersection of two matroids. We prove
several results in this direction and pose a few questions. We also give
generalizations of the Obreschkoff theorem and recent results of J. Borcea and
B. Shapiro.