The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
We design a deterministic polynomial time cn approximation algorithm for the permanent of positive semidefinite matrices where c = e+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...
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 present a fairly general method for constructing classes of functions of finite scale-sensitive dimension (the scale-sensitive dimension is a generalization of the Vapnik-Chervonenkis dimension to real-valued functions). The construction is as follows: start from a class F of functions of finite VC dimension, take the convex hull coF of F, and then take the closure $${\cal L}$$ of coF in...
We apply linear algebra(polynomial) techniques to various VC-Dimension based inequalities. We explore connections between the sample compression and this technique for so called maximum classes and prove that maximum classes are connected subgraphs of a Boolean cube.We provide a fast (linear in the cardinality of the class for the fixed VC-dimension) interpolational algorithm for maximum classes.A...
We show that “B is of type p > 1” is a necessary and sufficient condition for a learnability of a class of linear bounded functionals with norm ≤ 1 restrited to the unit ball in Banach Space B. On the way we give very short probabilistic proof for Vapnik's result (Hilbert Space and improved) and improve our result with Pascal Koiran for convex halls of indicator functions. The approach we use in...
We prove that it is #P-hard to compute the mixed discriminant of rank 2 positive semidefinite matrices. We present poly-time algorithms to approximate the ”beast”. We also prove NP-hardness of two problems related to mixed discriminants of rank 2 positive semidefinite matrices. One of them, the so called Full Rank Avoidance problem, had been conjectured to be NP-Complete in [23] and in [25]. We also...
The radio sky at frequencies below ∼30 MHz is virtually unobservable from Earth due to ionospheric disturbances and the opaqueness of the ionosphere below ∼10MHz, and also due to strong terrestrial radio interference. Deploying a radio observatory in space would open up this largely unexplored frequency band for science in astronomy, cosmology, geophysics, and space science. A Chinese-European team...
We study multivariate entire functions and polynomials with non-negative coefficients. A class of Strongly Log-Concave entire functions, generalizing Minkowski volume polynomials, is introduced: an entire function f in m variables is called 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...
Motivated by questions in robust control and switched linear dynamical systems, we consider the problem checking whether every element of a polytope of n×n matrices A is stable. We show that this can be done in polynomial-time in n when the number of extreme points of A is constant, but becomes NP-Hard when the number of extreme points grows as Θ(n). This result has two useful corollaries: (i) for...
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.
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.