A refinement of multivariate value set bounds

Over finite fields, if the image of a polynomial map is not the entire field, then its cardinality can be bounded above by a significantly smaller value. Earlier results bound the cardinality of the value set using the degree of the polynomial, but more recent results make use of the powers of all monomials.In this paper, we explore the geometric properties of the Newton polytope and show how they allow for tighter upper bounds on the cardinality of the multivariate value set. We then explore a method which allows for even stronger upper bounds, regardless of whether one uses the multivariate degree or the Newton polytope to bound the value set. Effectively, this provides improvement of a degree matrix-based result given by Zan and Cao, making our new bound the strongest upper bound thus far.     

On conformal measures for infinitely renormalizable quadratic polynomials

We study a conformal measure for an infinitely renormalizable quadratic poly- nomial.We prove that the conformal measure is ergodic if the polynomial is unbranched and has complex bounds.The main technique we use in the proof is the three-dimensional puzzle for an infinitely renormalizable quadratic polynomial.     

A note on the Lasserre hierarchy for different formulations of the maximum independent set problem

In this note, we consider several polynomial optimization formulations of the maximum independent set problem and the use of the Lasserre hierarchy with these different formulations. We demonstrate using computational experiments that the choice of formulation may have a significant impact on the resulting bounds. We also provide theoretical justifications for the observed behavior.     

On the refinement of Cauchy's theorem and Pellet's theorem

Using the relationship of a polynomial and its associated polynomial, we derived a necessary and sufficient condition for determining all roots of a given polynomial on the circumference of a circle defined by its associated polynomial. By employing the technology of analytic inequality and the theory of distribution of zeros of meromorphic function, we refine two classical results of Cauchy and Pellet about bounds of modules of polynomial zeros. Sufficient conditions are obtained for the polynomial whose Cauchy's bound and Pellet's bounds are strict bounds. The characteristics is given for the polynomial whose Cauchy's bound or Pellet's bounds can be achieved by the modules of zeros of the polynomial.     

Feedback Vertex Sets in Tournaments

We study combinatorial and algorithmic questions around minimal feedback vertex sets (FVS) in tournament graphs. On the combinatorial side, we derive upper and lower bounds on the maximum number of minimal FVSs in an n‐vertex tournament. We prove that every tournament on n vertices has at most 1.6740ⁿ minimal FVSs, and that there is an infinite family of tournaments, all having at least 1.5448ⁿ minimal FVSs. This improves and extends the bounds of Moon (1971). On the algorithmic side, we design the first polynomial space algorithm that enumerates the minimal FVSs of a tournament with polynomial delay. The combination of our results yields the fastest known algorithm for finding a minimum‐sized FVS in a tournament.     

Infinitely Renormalizable Quadratic Polynomials

We prove that the Julia set of a quadratic polynomial which admits an infinite sequence of unbranched, simple renormalizations with complex bounds is locally connected. The method in this study is three-dimensional puzzles.

     

A strongly polynomial FPTAS for the symmetric quadratic knapsack problem

The symmetric quadratic knapsack problem (SQKP), which has several applications in machine scheduling, is NP-hard. An approximation scheme for this problem is known to achieve an approximation ratio of (1 + ?) for any ? > 0. To ensure a polynomial time complexity, this approximation scheme needs an input of a lower bound and an upper bound on the optimal objective value, and requires the ratio of the bounds to be bounded by a polynomial in the size of the problem instance. However, such bounds are not mentioned in any previous literature. In this paper, we present the first such bounds and develop a polynomial time algorithm to compute them. The bounds are applied, so that we have obtained for problem (SQKP) a fully polynomial time approximation scheme (FPTAS) that is also strongly polynomial time, in the sense that the running time is bounded by a polynomial only in the number of integers in the problem instance.     

A MacWilliams type identity for matroids

In this paper, we consider the coboundary polynomial for a matroid as a generalization of the weight enumerator of a linear code. By describing properties of this polynomial and of a more general polynomial, we investigate the matroid analogue of the MacWilliams identity. From coding-theoretical approaches, upper bounds are given on the size of circuits and cocircuits of a matroid, which generalizes bounds on minimum Hamming weights of linear codes due to I. Duursma.     

Critical and near-critical values in polynomial control problems,I: One-dimensional case

For an input-to-state mapping of a polynomial one-dimensional control system we study the geometry of critical and near-critical controls, trajectories and values. Quantitative bounds, depending only on the degree of the polynomial involved, are obtained. Examples are considered, showing these bounds to be essentially sharp.     

The Complexity of Computing the Hilbert Polynomial of Smooth Equidimensional Complex Projective Varieties

We continue the study of counting complexity begun in [13], [14], [15] by proving upper and lower bounds on the complexity of computing the Hilbert polynomial of a homogeneous ideal. We show that the problem of computing the Hilbert polynomial of a smooth equidimensional complex projective variety can be reduced in polynomial time to the problem of counting the number of complex common zeros of a finite set of multivariate polynomials. The reduction is based on a new formula for the coefficients of the Hilbert polynomial of a smooth variety. Moreover, we prove that the more general problem of computing the Hilbert polynomial of a homogeneous ideal is polynomial space hard. This implies polynomial space lower bounds for both the problems of computing the rank and the Euler characteristic of cohomology groups of coherent sheaves on projective space, improving the #P-lower bound in Bach [1].     

A posteriori error bounds for the zeros of a polynomial

Summary An algorithm for the computation of error bounds for the zeros of a polynomial is described. This algorithm is derived by applying Rouché's theorem to a Newton-like interpolation formula for the polynomial, and so it is suitable in the case where the approximations to the zeros of the polynomial are computed successively using deflation. Confluent and clustered approximations are handled easily. However bounds for the local rouding errors in deflation, e.g. in Horner's scheme, must be known. In practical application the method can, especially in some ill-conditioned cases, compete with other known estimates.     

Accurate Enclosure of the Zero Set of Multivariate Polynomials

The zero set of one general multivariate polynomial is enclosed by unions and intersections of funnel-shaped unbounded sets. There are sharper enclosures for the zero set of a polynomial in two complex variables with complex interval coefficients. Common zeros of a polynomial system can be located by an appropriate intersection of these enclosure sets in an appropriate space. The resulting domain is directly brought into polynomial equation solvers.     

Upper and Lower Bounds on the Dimension of Superspline Spaces

Upper and lower bounds are provided on the dimension of bivariate polynomial superspline spaces which are defined by enforcing smoothness conditions across the interior edges of the underlying triangulation. The results generalize known bounds for classical spline spaces. As an example of the usefulness of such bounds, we show how they can be applied to analyze a new macroelement.     

A remark on simultaneous inclusions of the zeros of a polynomial by Gershgorin's theorem

Summary By using Gershgorin's theorem and the theorems on minimal Gershgorin disks a posteriori error bounds for the zeros of a polynomial are deduced, from which the bounds given in [1] by Braess and Hadeler are easily obtained.     

Lower bounds for the zeros of analytic functions

Summary In the present work the problem of finding lower bounds for the zeros of an analytic function is reduced by a Hilbert space technique to the well-known problem of finding upper bounds for the zeros of a polynomial. Several lower bounds for all the zeros of analytic functions are thus found, which are always better than the well-known Carmichael-Mason inequality. Several numerical examples are also given and a comparison of our bounds with well-known bounds in literature and/or the exact solution is made.     

Combinatorics on update digraphs in Boolean networks

Boolean networks have been used as models of gene regulation and other biological networks. One key element in these models is the update schedule, which indicates the order in which states have to be updated. In Aracena et al. (2009) [1], the authors define equivalence classes that relate deterministic update schedules that yield the same update digraph and thus the same dynamical behavior of the network. In this paper we study algorithmical and combinatorial aspects of update digraphs. We show a polynomial characterization of these digraphs, which enables us to characterize the corresponding equivalence classes. We prove that the update digraphs are exactly the projections, on the respective subgraphs, of a complete update digraph with the same number of vertices. Finally, the exact number of complete update digraphs is determined, which provides upper and lower bounds on the number of equivalence classes.     

Hybrid rounding techniques for knapsack problems

We address the classical knapsack problem and a variant in which an upper bound is imposed on the number of items that can be selected. We show that appropriate combinations of rounding techniques yield novel and more powerful ways of rounding. Moreover, we present a linear-storage polynomial time approximation scheme (PTAS) and a fully polynomial time approximation scheme (FPTAS) that compute an approximate solution, of any fixed accuracy, in linear time. These linear complexity bounds give a substantial improvement of the best previously known polynomial bounds [A. Caprara, et al., Approximation algorithms for knapsack problems with cardinality constraints, European J. Oper. Res. 123 (2000) 333-345].     

Error Bounds for the Solution Sets of Quadratic Complementarity Problems

In this article, two types of fractional local error bounds for quadratic complementarity problems are established, one is based on the natural residual function and the other on the standard violation measure of the polynomial equalities and inequalities. These fractional local error bounds are given with explicit exponents. A fractional local error bound with an explicit exponent via the natural residual function is new in the tensor/polynomial complementarity problems literature. The other fractional local error bounds take into account the sparsity structures, from both the algebraic and the geometric perspectives, of the third-order tensor in a quadratic complementarity problem. They also have explicit exponents, which improve the literature significantly.     

Sparse effective membership problems via residue currents

We use residue currents on toric varieties to obtain bounds on the degrees of solutions to polynomial ideal membership problems. Our bounds depend on (the volume of) the Newton polytope of the polynomial system and are therefore well adjusted to sparse polynomial systems. We present sparse versions of Max N?ther??s AF?+?BG Theorem, Macaulay??s Theorem, and Kollár??s Effective Nullstellensatz, as well as recent results by Hickel and Andersson?CG?tmark.     

The spread of matrices and polynomials

The spread of a matrix (or polynomial) is the maximum distance between any two of its eigenvalues (or its zeros). E. Deutsch has recently given upper bounds for the spread of matrices and polynomials. We obtain sharper, simpler upper bounds and observe that they are also upper bounds for the sum of the absolute values of the two largest eigenvalues (or zeros).