• ### Operator scaling: theory and applications(1511.03730)

Jan. 24, 2019 quant-ph, math.AG, math.AC, cs.CC
In this paper we present a deterministic polynomial time algorithm for testing if a symbolic matrix in non-commuting 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 non-commutative 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 non-commuting variables, two problems which had only exponential-time 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 Brascamp-Lieb inequalities). Symbolic matrices in non-commuting 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 non-commutative algebra. We provide a detailed account of some of these sources and their interconnections.
• ### Algorithmic and optimization aspects of Brascamp-Lieb inequalities, via Operator Scaling(1607.06711)

April 13, 2018 math.CA, cs.DS, cs.CC
The celebrated Brascamp-Lieb (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 BL-datum, the optimal BL-constant and a weak separation oracle for the BL-polytope. The same result holds for the so-called 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 BL-datum 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 BL-constant in terms of the BL-data. To the best of our knowledge no such bounds were known, as past arguments relied on compactness. The continuity of BL-constants is important for developing non-linear BL inequalities that have recently found so many applications.
• ### Simply Exponential Approximation of the Permanent of Positive Semidefinite Matrices(1704.03486)

April 11, 2017 quant-ph, math.CO, math.PR, cs.DS
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.
• ### Space-time Dynamics Estimation from Space Mission Tracking Data(1512.06685)

Dec. 21, 2015 astro-ph.EP
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 near-future implementation of (interplanetary) transponder laser ranging, these effects will become increasingly important, requiring a re-evaluation 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 next-generation 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 Earth-based 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 space-time 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 1-month mission and 10 % for a 4-year 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.
• ### Studies of Relativistic Jets in Active Galactic Nuclei with SKA(1501.00420)

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 high-sensitivity 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, all-sky surveys (both total and polarimetric flux) from SKA1. Wide-field very-long-baseline-interferometric 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 re-ionization, 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 pc-scale 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 radio-loud AGN.
• ### Very Long Baseline Interferometry with the SKA(1412.5971)

Adding VLBI capability to the SKA arrays will greatly broaden the science of the SKA, and is feasible within the current specifications. SKA-VLBI can be initially implemented by providing phased-array outputs for SKA1-MID and SKA1-SUR 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 SKA-VLBI is described in this paper.
• ### Searching for Extraterrestrial Intelligence with the Square Kilometre Array(1412.4867)

Dec. 16, 2014 astro-ph.EP, astro-ph.IM
• ### Bounds on the permanent and some applications(1408.0976)

Aug. 5, 2014 math.CO
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 monomer-dimer problem.
• ### VLBI detection of the Galactic black hole binary candidate MAXI J1836-194(1208.2085)

Aug. 10, 2012 astro-ph.HE
The X-ray transient MAXI J1836-194 is a newly-identified Galactic black hole binary candidate. As most X-ray transients, it was discovered at the beginning of an X-ray outburst. After the initial canonical X-ray hard state, the outburst evolved into a hard intermediate state and then went back to the hard state. The existing RATAN-600 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 self-absorbed jet in the vicinity of the central compact object. We observed the transient in the hard state near the end of the X-ray 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 newly-developed Chinese VLBI data acquisition system (CDAS), twice higher than the recording rate used in the other observations. We successfully detected the low-declination source with a high confidence level in both observations. The source was unresolved (<=0.5 mas), which is in agreement with an AU-scale compact jet.
• ### The Social Will-Testing Game and its Solution(1206.6148)

June 27, 2012 q-bio.PE, cs.GT
We examine a two-person game we call Will-Testing 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.
• ### Unleashing the power of Schrijver's permanental inequality with the help of the Bethe Approximation(1106.2844)

June 20, 2012 math-ph, math.MP, math.CO, cs.IT, math.IT, cs.CC
Let $A \in \Omega_n$ be doubly-stochastic $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)(1-A(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 monomer-dimer problem. We use some ideas of our proof of (LAMC) to disprove [Lu,Mohr,Szekely] positive correlation conjecture. We present explicit doubly-stochastic $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 poly-time 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$.
• ### How much of quantum mechanics is really needed to defy Extended Church-Turing Thesis?(1103.2500)

March 16, 2011 quant-ph, cs.CC
This paper has been withdrawn by the author as one of the coauthors needs institutional permission.
• ### A proof of the log-concavity conjecture related to the computation of the ergodic capacity of MIMO channels(0911.0696)

Nov. 3, 2009 cs.IT, math.IT
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 non-negative coefficients. Interestingly, the coefficients are subpermanents of some non-negative matrix. In general, such maximizations problems are {\bf NP-HARD}. 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 log-concavity was conjectured in arXiv:0903.1952. We give in this paper self-contained proof of the conjecture, based on the theory of {\bf H-Stable} polynomials.
• ### On multivariate Newton-like inequalities(0812.3687)

May 14, 2009 math.CO, math.OC
We study multivariate entire functions and polynomials with non-negative coefficients. A class of {\bf Strongly Log-Concave} entire functions, generalizing {\it Minkowski} volume polynomials, is introduced: an entire function $f$ in $m$ variables is called {\bf Strongly Log-Concave} 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 Log-Concave} case. One of the corollaries of our new Newton(like) inequalities is the fact that the support $supp(f)$ of a {\bf Strongly Log-Concave} 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 Waerden-Falikman-Egorychev} inequality for the permanent of doubly-stochastic matrices. A few open questions are posed in the final section.
• ### A polynomial time algorithm to approximate the mixed volume within a simply exponential factor(cs/0702013)

Jan. 16, 2009 math.CO, cs.CG, cs.CC
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 poly-time 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 Schrijver-Valiant 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 poly-time time algorithm for the approximation of the volume of a convex set.
• ### Van der Waerden/Schrijver-Valiant like Conjectures and Stable (aka Hyperbolic) Homogeneous Polynomials : One Theorem for all(0711.3496)

May 13, 2008 math.CO, math.AG
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 H-Stable} 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 H-Stable} 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 Schrijver-Valiant conjecture on the number of perfect matchings in $k$-regular bipartite graphs. These two famous results correspond to the {\bf H-Stable} 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.
• ### A short, based on the mixed volume, proof of Liggett's theorem on the convolution of ultra-logconcave sequences(0804.1181)

April 8, 2008 math.CO, math.ST, stat.TH
R. Pemantle conjectured, and T.M. Liggett proved in 1997, that the convolution of two ultra-logconcave is ultra-logconcave. Liggett's proof is elementary but long. We present here a short proof, based on the mixed volume of convex sets.
• ### Generalized Friedland-Tverberg inequality: applications and extensions(math/0603410)

Aug. 24, 2006 math-ph, math.MP, math.CO
We derive here the Friedland-Tverberg 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 monomer-dimer entropy. We present Ryser-like formulas for computations of matchings in bipartite and general graphs. Additional algorithmic applications are given.
• ### Hyperbolic Polynomials Approach to Van der Waerden/Schrijver-Valiant like Conjectures : Sharper Bounds, Simpler Proofs and Algorithmic Applications(math/0510452)

Jan. 12, 2006 math.CO, math.OC
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+1-i)) .$$ This theorem is a vast (and unifying) generalization of as the van der Waerden conjecture on the permanents of doubly stochastic matrices as well Schrijver-Valiant conjecture on the number of perfect matchings in $k$-regular bipartite graphs . The paper is (almost) self-contained, most of the proofs can be found in the {\bf Appendices}.
• ### A proof of hyperbolic van der Waerden conjecture : the right generalization is the ultimate simplification(math/0504397)

Aug. 15, 2005 math.CO, math.OC
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 self-contained (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 doubly-stochastic matrices, i.e. with small number of non-zero 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 entry-wise matrices within multiplicative factor $\frac{e^n}{n^m}$ for any fixed positive $m$ .
• ### Better bound on the exponent of the radius of the multipartite separable ball(quant-ph/0409095)

June 13, 2005 quant-ph
We show that for an m-qubit 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 m-qubit 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 pseudopure-state 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 m-partite systems of fixed local dimension d_0, although approaching our earlier exponent as d_0 approaches infinity.
• ### Combinatorial and algorithmic aspects of hyperbolic polynomials(math/0404474)

April 13, 2005 math.CO, math.OC
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 far-reaching 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 polynomial-time oracle algorithms . This result is based on a "hyperbolic" generalization of Rado theorem .
• ### On Matrix Polynomials with Real Roots(math/0406419)

June 21, 2004 math.OC
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.
• ### Van der Waerden Conjecture for Mixed Discriminants(math/0406420)

June 21, 2004 math.CO
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.
• ### Combinatorics hidden in hyperbolic polynomials and related topics(math/0402088)

Feb. 5, 2004 math.CO, math.OC
The main topic of this paper is various "hyperbolic" generalizations of the Edmonds-Rado 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.