Search

Hyperbolicity cones are convex algebraic cones arising from hyperbolic polynomials. A well-understood subclass of hyperbolicity cones is that of spectrahedral cones and it is conjectured that every hyperbolicity cone is spectrahedral. In this paper we prove a weaker version of this conjecture by showing that every smooth hyperbolicity cone is the linear projection of a spectrahedral cone, that is, a spectrahedral shadow. [ABSTRACT FROM AUTHOR]

It was shown by Griggs and Wu that a graph of minimal degree 4 on n vertices has a spanning tree with at least $$ \frac{2}{5} $$ n leaves, which is asymptomatically the best possible bound for this class of graphs. In this paper, we present a polynomial time algorithm that finds in any graph with k vertices of degree greater than or equal to 4 and k′ vertices of degree 3 a spanning tree with $$ \left[ {\frac{2}{5} \cdot k + \frac{2}{{15}} \cdot k'} \right] $$ leaves. [ABSTRACT FROM AUTHOR]

We deal with the functional equation motivated by quadrature rules of approximate integration. In previous results the solutions of this equation were found only in some particular cases. For example the coefficients λ were supposed to be rational or the equation in question was solved only for n=2. In the current paper we do not assume any particular form of coefficients occurring in this equation and we allow n to be any positive integer. Moreover, we obtain a solution of our equation without any regularity assumptions concerning the functions f and F. [ABSTRACT FROM AUTHOR]

We consider a model of recommendation systems, where each member from a given set of players has a binary preference to each element in a given set of objects: intuitively, each player either likes or dislikes each object. However, the players do not know their preferences. To find his preference of an object, a player may probe it, but each probe incurs unit cost. The goal of the players is to learn their complete preference vector (approximately) while incurring minimal cost. This is possible if many players have similar preference vectors: such a set of players with similar “taste” may split the cost of probing all objects among them, and share the results of their probes by posting them on a public billboard. The problem is that players do not know a priori whose taste is close to theirs. In this paper we present a distributed randomized peer-to-peer algorithm in which each player outputs a vector which is close to the best possible approximation of the player’s real preference vector after a polylogarithmic number of rounds. The algorithm works under adversarial preferences. Previous algorithms either made severely limiting assumptions on the structure of the preference vectors, or had polynomial overhead. [ABSTRACT FROM AUTHOR]

The domination polynomial of a graph is the polynomial whose coefficients count the number of dominating sets of each cardinality. A recent question asks which graphs are uniquely determined (up to isomorphism) by their domination polynomial. In this paper, we completely describe the complete $$r$$ -partite graphs which are; in the bipartite case, this settles in the affirmative a conjecture of Aalipour et al. (Ars Comb, ). [ABSTRACT FROM AUTHOR]

In this paper, we establish a novel duality relationship between node-capacitated multiflows and tree-shaped facility locations. We prove that the maximum value of a tree-distance-weighted maximum node-capacitated multiflow problem is equal to the minimum value of the problem of locating subtrees in a tree, and the maximum is attained by a half-integral multiflow. Utilizing this duality, we show that a half-integral optimal multiflow and an optimal location can be found in strongly polynomial time. These extend previously known results in the maximum free multiflow problems. We also show that the set of tree-distance weights is the only class having bounded fractionality in maximum node-capacitated multiflow problems. [ABSTRACT FROM AUTHOR]

The paper is devoted to the composition method of constructing families of irreducible polynomials over finite fields. [ABSTRACT FROM AUTHOR]

The authors mainly concern the set U of c ∈ ℂ such that the power deformation $$ z(\frac{{f(z)}} {z})^c $$ is univalent in the unit disk | z| < 1 for a given analytic univalent function f( z) = z + a z + ... in the unit disk. It is shown that U is a compact, polynomially convex subset of the complex plane ℂ unless f is the identity function. In particular, the interior of U is simply connected. This fact enables us to apply various versions of the λ-lemma for the holomorphic family $$ z(\frac{{f(z)}} {z})^c $$ of injections parametrized over the interior of U. The necessary or sufficient conditions for U to contain 0 or 1 as an interior point are also given. [ABSTRACT FROM AUTHOR]

We discuss computability of impressions of prime ends of compact sets. In particular, we construct quadratic Julia sets which possess explicitly described non-computable impressions. [ABSTRACT FROM AUTHOR]

The restricted parameter range set cover problem is a weak form of the NP-hard set cover problem with the restricted range of parameters. We give a polynomial time algorithm for this problem by lattices. [ABSTRACT FROM AUTHOR]

Let G be a simple graph. The domination polynomial of a graph G of order n is the polynomial $${D(G,x)=\sum_{i=0}^{n} d(G,i) x^{i}}$$ , where d( G, i) is the number of dominating sets of G of size i. In this article we investigate the domination polynomial at −1. We give a construction showing that for each odd number n there is a connected graph G with D( G, −1) = n. [ABSTRACT FROM AUTHOR]

Let ${\mathcal {P}_{n}^{d}}$ denote the space of polynomials on ℝ of total degree n. In this work, we introduce the space of polynomials ${\mathcal {Q}_{2 n}^{d}}$ such that ${\mathcal {P}_{n}^{d}}\subset {\mathcal {Q}_{2 n}^{d}}\subset\mathcal{P}_{2n}^{d}$ and which satisfy the following statement: Let h be any fixed univariate even polynomial of degree n and $\mathcal{A}$ be a finite set in ℝ. Then every polynomial P from the space ${\mathcal {Q}_{2 n}^{d}}$ may be represented by a linear combination of radial basis functions of the form h(∥ x+ a∥), $a\in \mathcal{A}$, if and only if the set $\mathcal{A}$ is a uniqueness set for the space ${\mathcal {Q}_{2 n}^{d}}$. [ABSTRACT FROM AUTHOR]

We estimate the degree of comonotone polynomial approximation of continuous functions f, on [−1,1], that change monotonicity s≥1 times in the interval, when the degree of unconstrained polynomial approximation E( f)≤ n, n≥1. We ask whether the degree of comonotone approximation is necessarily ≤ c( α, s) n, n≥1, and if not, what can be said. It turns out that for each s≥1, there is an exceptional set A of α's for which the above estimate cannot be achieved. [ABSTRACT FROM AUTHOR]

We obtain asymptotically sharp estimates for the best (α, β) -approximations of the classes $ W_{1;\upgamma, \updelta }^r $ with natural r by algebraic polynomials in the mean. [ABSTRACT FROM AUTHOR]

We propose two admissible closures $${\mathbb{A}({\sf PTCA})}$$ and $${\mathbb{A}({\sf PHCA})}$$ of Ferreira's system PTCA of polynomial time computable arithmetic and of full bounded arithmetic (or polynomial hierarchy computable arithmetic) PHCA. The main results obtained are: (i) $${\mathbb{A}({\sf PTCA})}$$ is conservative over PTCA with respect to $${\forall\exists\Sigma^b_1}$$ sentences, and (ii) $${\mathbb{A}({\sf PHCA})}$$ is conservative over full bounded arithmetic PHCA for $${\forall\exists\Sigma^b_{\infty}}$$ sentences. This yields that (i) the $${\Sigma^b_1}$$ definable functions of $${\mathbb{A}({\sf PTCA})}$$ are the polytime functions, and (ii) the $${\Sigma^b_{\infty}}$$ definable functions of $${\mathbb{A}({\sf PHCA})}$$ are the functions in the polynomial time hierarchy. [ABSTRACT FROM AUTHOR]

Abstract  Assume that a set of imprecise points is given, where each point is specified by a region in which the point may lie. We study the problem of computing the smallest and largest possible convex hulls, measured by length and by area. Generally we assume the imprecision region to be a square, but we discuss the case where it is a segment or circle as well. We give polynomial time algorithms for several variants of this problem, ranging in running time from O(nlog n) to O(n 13), and prove NP-hardness for some other variants. [ABSTRACT FROM AUTHOR]

The class TFNP, defined by Megiddo and Papadimitriou, consists of multivalued functions with values that are polynomially verifiable and guaranteed to exist. Do we have evidence that such functions are hard, for example, if TFNP is computable in polynomial-time does this imply the polynomial-time hierarchy collapses? By computing a multivalued function in deterministic polynomial-time we mean on every input producing one of the possible values of the function on that input. We give a relativized negative answer to this question by exhibiting an oracle under which TFNP functions are easy to compute but the polynomial-time hierarchy is infinite. We also show that relative to this same oracle, P≠UP and TFNPNP functions are not computable in polynomial-time with an NP oracle. [ABSTRACT FROM AUTHOR]

The bipartite density of a graph G is max {| E( H)|/| E( G)|: H is a bipartite subgraph of G}. It is NP-hard to determine the bipartite density of any triangle-free cubic graph. A biased maximum bipartite subgraph of a graph G is a bipartite subgraph of G with the maximum number of edges such that one of its partite sets is independent in G. Let $$ \mathcal{H} $$ denote the collection of all connected cubic graphs which have bipartite density $$ \tfrac{4} {5} $$ and contain biased maximum bipartite subgraphs. Bollobás and Scott asked which cubic graphs belong to $$ \mathcal{H} $$. This same problem was also proposed by Malle in 1982. We show that any graph in $$ \mathcal{H} $$ can be reduced, through a sequence of three types of operations, to a member of a well characterized class. As a consequence, we give an algorithm that decides whether a given graph G belongs to $$ \mathcal{H} $$. Our algorithm runs in polynomial time, provided that G has a constant number of triangles that are not blocks of G and do not share edges with any other triangles in G. [ABSTRACT FROM AUTHOR]

Abstract.  The central question in quantum multi-prover interactive proof systems is whether or not entanglement shared among provers affects the verification power of the proof system. We study for the first time positive aspects of prior entanglement and show how it can be used to parallelize any multi-prover quantum interactive proof system to a one-round system with perfect completeness, soundness bounded away from one by an inverse-polynomial in the input size, and one extra prover. Alternatively, we can also parallelize to a three-turn system with the same number of provers, where the verifier only broadcasts the outcome of a coin flip. This “public-coin” property is somewhat surprising, since in the classical case public-coin multi-prover interactive proofs are equivalent to single-prover ones. [ABSTRACT FROM AUTHOR]

The article investigates the asymptotic behavior of a convolution of a function with a measure. Conditions which ensure that the exact rate of the convolution function can be determined using a positive weight function related to the given function and measure are given. Limit formulas used by the researchers in this study applicable to subexponential functions, tail equivalent distributions, and polynomial-type convolutions. Many related results conducted by other researchers are included and generalized.

A pattern class is a set of permutations closed under the formation of subpermutations. Such classes can be characterized as those permutations not involving a particular set of forbidden permutations. A simple collection of necessary and sufficient conditions on sets of forbidden permutations which ensure that the associated pattern class is of polynomial growth is determined. A catalogue of all such sets of forbidden permutations having three or fewer elements is provided together with bounds on the degrees of the associated enumerating polynomials. [ABSTRACT FROM AUTHOR]

Given an ( H,R)-Lie coalgebra Γ, we construct ( H,R T )-Lie coalgebra ΓT through a right cocycle T, where ( H,R) is a triangular Hopf algebra, and prove that there exists a bijection between the set of ( H,R)-Lie coalgebras and the set of ordinary Lie coalgebras. We also show that if ( L, [, ], Δ, R) is an ( H,R)-Lie bialgebra of an ordinary Lie algebra then ( L T , [, ], ΔT, R T ) is an ( H,R T )-Lie bialgebra of an ordinary Lie algebra. [ABSTRACT FROM AUTHOR]