We give simply exponential lower bounds on the probabilities of a given strongly Rayleigh distribution, depending only on its expectation. This resolves a weak version of a problem left open by Karlin-Klein-Oveis Gharan in their recent breakthrough work on metric TSP, and this resolution leads to a minor improvement of their approximation factor for metric TSP. Our results also allow for a more streamlined analysis of the algorithm. To achieve these new bounds, we build upon the work of Gurvits-Leake on the use of the productization technique for bounding the capacity of a real stable polynomial. This technique allows one to reduce certain inequalities for real stable polynomials to products of affine linear forms, which have an underlying matrix structure. In this paper, we push this technique further by characterizing the worst-case polynomials via bipartitioned forests. This rigid combinatorial structure yields a clean induction argument, which implies our stronger bounds. In general, we believe the results of this paper will lead to further improvement and simplification of the analysis of various combinatorial and probabilistic bounds and algorithms.

We give a sharp lower bound on the capacity of a real stable polynomial, depending only on the value of its gradient at x = 1. This result implies a sharp improvement to a similar inequality proved by Linial-Samorodnitsky-Wigderson in 2000, which was crucial to the analysis of their permanent approximation algorithm. Such inequalities have played an important role in the recent work on operator scaling and its generalizations and applications, and in fact we use our bound to construct a new scaling algorithm for real stable polynomials. Our bound is also quite similar to one used very recently by Karlin-Klein-Oveis Gharan to give an improved approximation factor for metric TSP.

We design a deterministic polynomial time cn approximation algorithm for the permanent of positive semidefinite matrices where c =γ+1≃ 4:84. We write a natural convex relaxation and show that its optimum solution gives a cn approximation of the permanent. We further show that this factor is asymptotically tight by constructing a family of positive semidefinite matrices. We also show that our result implies an approximate version of the permanent-ontop conjecture, which was recently refuted in its original form; we show that the permanent is within a cn factor of the top eigenvalue of the Schur power matrix.

The celebrated Brascamp-Lieb (BL) inequalities [BL76, Lie90], and their reverse form of Barthe [Bar98], are an important mathematical tool, unifying and generalizing numerous in- equalities in analysis, convex geometry and information theory, with many used in computer science. While their structural theory is very well understood, far less is known about computing their main parameters below (which we later define). Prior to this work, the best known algorithms for any of these optimization tasks required at least exponential time. In this work, we give polynomial time algorithms to compute:

Symbolic matrices in non-commuting variables, andthe related structural and algorithmic questions, have a remarkablenumber of diverse origins and motivations. They ariseindependently in (commutative) invariant theory and representationtheory, linear algebra, optimization, linear system theory,quantum information theory, and naturally in non-commutativealgebra.

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. We also give a combinatorial application of the lower bound, proving S. Friedland's "Asymptotic Lower Matching Conjecture"for the monomer-dimer problem.

Let p(x1,...,xn) = p(X) , X ∈ Rn be a homogeneous polynomial of degree n in n real variables, e = (1,1,..,1) ∈ Rn be a vector of all ones . Such a polynomial p is called e-hyperbolic if for all real vectors X ∈ Rn the univariate polynomial equation p(te - X) = 0 has all real roots λ1(X) ≥ ... ≥ λn(X). The number of nonzero roots |i :λi(X) ≠ 0 | is called Rankp(X). An e-hyperbolic polynomial p is called POS-hyperbolic if roots of vectors X ∈ Rn+ with nonnegative coordinates are also nonnegative (the orthant Rn+ belongs to the hyperbolic cone) and p(e) > 0. Below e1,...,en stands for the canonical orthogonal basis in Rn. The main results of this paper states that if p(x1,x2,...,xn) is a POS-hyperbolic (homogeneous) polynomial of degree n, Rankp (ei) = Ri and p(x1,x2,...,xn) ≥ ∏1 ≤ i ≤ n xi ; xi > 0, 1 ≤ i ≤ n, then the following inequality holds ∂n/∂ x1...∂ xn p(0,...,0) ≥ ∏1 ≤ i ≤ n (Gi-1/Gi)Gi-1, where Gi = min(Ri , n+1-i) . 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 POS-hyperbolic polynomials which are products of linear forms with nonnegative coefficients.Our proof is relatively simple and "noncomputational"; it actually slightly improves Schrijver's lower bound, and uses very basic (more or less centered around Rolle's theorem) properties of hyperbolic polynomials. We present some important algorithmic applications of the result, including a polynomial time deterministic algorithm approximating the permanent of n x n entry-wise non-negative matrices within a multiplicative factor en/nm for any fixed positive m; and a deterministic poly-time algorithm approximating the permanent of n x n matrix A having at most k nonzero entries in each column to within a multiplicative factor (k-1/k)(k-1)n.This paper introduces a new powerful "polynomial" technique , which allows us to simplify and unify hard and key known results as well as to prove new important theorems and get new algorithms.

This paper continues research initiated in quant-ph/0201022 . The main subject here is the so-called Edmonds' problem of deciding if a given linear subspace of square matrices contains a nonsingular matrix . We present a deterministic polynomial time algorithm to solve this problem for linear subspaces satisfying a special matroids motivated property, called in the paper the Edmonds-Rado property . This property is shown to be very closely related to the separability of bipartite mixed states . One of the main tools used in the paper is the Quantum Permanent introduced in quant-ph/0201022 .

Abstract Using multiple independent networks (also known as rails) is an emerging technique which is being used to overcome bandwidth limitations and enhance fault tolerance of current high‐performance parallel computers. In this paper, we present and analyze various algorithms to allocate multiple communication rails, including static and dynamic allocation schemes. An analytical lower bound on the number of rails required for static rail allocation is shown. We also present an extensive experimental comparison of the behavior of various algorithms in terms of bandwidth and latency. We show that striping messages over multiple rails can substantially reduce network latency, depending on average message size, network load and allocation scheme. The methods compared include a static rail allocation, a basic round‐robin rail allocation, a local‐dynamic allocation based on local knowledge and a dynamic rail allocation that reserves both communication endpoints of a message before sending it. The last method is shown to perform better than the others at higher loads: up to 49% better than local‐knowledge allocation and 37% better than the round‐robin allocation. This allocation scheme also shows lower latency and it saturates at higher loads (for long enough messages). Most importantly, this proposed allocation scheme scales well with the number of rails and message size. In addition we propose a hybrid algorithm that combines the benefits of the local‐dynamic allocation for short messages with those of the dynamic algorithm for large messages. Copyright © 2003 John Wiley & Sons, Ltd.

Using multiple independent networks (also known as rails) is an emerging technique to overcome bandwidth limitations and enhance fault tolerance of current high-performance clusters. We present an extensive experimental comparison of the behavior of various allocation schemes in terms of bandwidth and latency. We show that striping messages over multiple rails can substantially reduce network latency, depending on average message size, network load, and allocation scheme. The compared methods include a basic round-robin rail allocation, a local-dynamic allocation based on local knowledge, and a dynamic rail allocation that reserves both communication endpoints of a message before sending it. The last method is shown to perform better than the others at higher loads: up to 49% better than local-knowledge allocation and 37% better than the round-robin allocation. This allocation scheme also shows lower latency and it saturates on higher loads (for messages large enough). Most importantly, this proposed allocation scheme scales well with the number of rails and message sizes. In addition we propose a hybrid algorithm that combines the benefits of the local-dynamic for short messages with those of the dynamic algorithm for large messages.

We present a deterministic polynomial algorithm that computes the mixed discriminant of an n-tuple of positive semidefinite matrices to within a multiplicative factor of e ~.To this end we extend the notion of doubly stochastic matrix scaling to a larger class of n-tuples of positive semidefinite matrices, and provide a polynomial-time algorithm for this scaling.We obtain tight upper and lower bounds on the mixed discriminant of doubly stochasic n-tuples, proving a conjecture of Bapat, and generalizing the van der Waerden -Falikman -Egorychev theorem.As a corollary, we obtain a deterministic polynomial algorithm that computes the mixed volume of n convex bodies in 1~ ~ to within a multiplicative factor of n °(').This answers a question of Dyer, Gritzmann and Hufnagel.

We describe an efficient method for localizing a mobile robot in an environment with landmarks. We assume that the robot can identify these landmarks and measure their bearings relative to each other. Given such noisy input, the algorithm estimates the robot's position and orientation with respect to the map of the environment. The algorithm makes efficient use of our representation of the landmarks by complex numbers. The algorithm runs in time linear in the number of landmarks. We present results of simulations and propose how to use our method for robot navigation.

Article A note on VC-dimension and measures of sets of reals Share on Authors: Shai Ben-David Computer Science Department, Technion, Haifa 32000, Israel Computer Science Department, Technion, Haifa 32000, IsraelView Profile , Leonid Gurvits NEC Research Institute, Princeton, NJ NEC Research Institute, Princeton, NJView Profile Authors Info & Claims COLT '95: Proceedings of the eighth annual conference on Computational learning theoryJuly 1995 Pages 454–462https://doi.org/10.1145/225298.225353Online:05 July 1995Publication History 0citation200DownloadsMetricsTotal Citations0Total Downloads200Last 12 Months1Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

We describe an efficient algorithm for localizing a mobile robot in an environment with landmarks. We assume that the robot has a camera and maybe other sensors that enable it to both identify landmarks and measure the angles subtended by these landmarks. We show how to estimate the robot's position using a new technique that involves a complex number representation of the landmarks. Our algorithm runs in time linear in the number of landmarks. We present results of our simulations and propose how to use our method for robot navigation.>

The set of functions which a single hidden layer neural network can approximate is increasingly well understood, yet our knowledge of how the approximation error depends upon the number of hidden units, i.e. the rate of approximation, remains relatively primitive.Barron [1991] and Jones [1992] give bounds on the rate of approximation valid for Hilbert spaces.We derive bounds for L spaces, 1 < p < m, recovering the 0(1 /&) bounds of Barron and Jones for the case p = 2.The results were motivated in part by the desire to understand approximation in the more "robust" (resistant to exemplar noise) LP, 1 ~p <2 norms.

The authors formulate the dynamic equations of a system consisting of a 3-degree-of-freedom Puma-like manipulator attached to a space platform (e.g. a space station or a satellite) as an NMP (nonholonomic motion planning) problem and discuss controllability of the system. They describe the application of a simple algorithm for obtaining approximate optimal solutions. They conclude with results of a simulation experiment.>

The author considers the problem of motion planning for a nonholonomic system with drift. Open-loop and feedback solutions for nonholonomic motion planning (NMP) are constructed by using the averaging technique that is well known in applied mathematics. An algorithm for open-loop and feedback solutions of NMP is introduced. The main step in the algorithm is the case of first order Lie brackets. This case, as is shown, is equivalent to NMP for Brockett's system considered over functional commutative algebra. Feedback solutions are constructed in the same manner. From a robotics point of view, it is shown that NMP can be reduced to the holonomic problem. As linear algebra plays a crucial role in linear control theory, polylinear algebra is crucial for NMP. The rolling disk example is used to illustrate the feedback algorithm.>

Nonholonomic motion planning (NMP) problems arise not only from the classical nonholonomic constraints, but also from symmetries and conservation laws of holonomic systems. In NMP problems an admissible configuration space path is constrained to a given nonholonomic distribution. Thus, NMP deals with the problem of (optimal) path finding subject to a nonholonomic distribution and possibly to additional holonomic constraints. The authors first study several representative NM systems and formulate the NMP problem. Variational principles are used to characterize optimal solutions to these problems. A simple algorithm solving an NMP problem is proposed, and simulation results are presented.>