New degree bounds for polynomial threshold functions

A real multivariate polynomial p(x ₁, …, x _n ) is said to sign-represent a Boolean function f: {0,1} ⁿ →{−1,1} if the sign of p(x) equals f(x) for all inputs x∈{0,1} ⁿ . We give new upper and lower bounds on the degree of polynomials which sign-represent Boolean functions. Our upper bounds for Boolean formulas yield the first known subexponential time learning algorithms for formulas of superconstant depth. Our lower bounds for constant-depth circuits and intersections of halfspaces are the first new degree lower bounds since 1968, improving results of Minsky and Papert. The lower bounds are proved constructively; we give explicit dual solutions to the necessary linear programs.     

Strong bounds on perturbations

This paper provides strong bounds on perturbations over a collection of independent random variables, where ‘strong’ has to be understood as uniform w.r.t. some functional norm. Our analysis is based on studying the concept of weak differentiability. By applying a fundamental result from the theory of Banach spaces, we show that weak differentiability implies norm Lipschitz continuity. This result leads to bounds on the sensitivity of finite products of probability measures, in norm sense. We apply our results to derive bounds on perturbations for the transient waiting times in a G/G/1 queue. This research is supported by the Technology Foundation STW, applied science division of NWO and the technology programme of the Ministry of Economic Affairs.     

Componentwise perturbation bounds for some matrix decompositions

Componentwise perturbation bounds for the Cholesky,LDL ^H ,QR andLU decompositions are derived. The bounds improve known results of the same type and reveal the structural characteristics of the perturbations.This subject was supported by the Institute of Information Processing of the University of Umeå and the Swedish Natural Science Research Council.     

On error bounds for lower semicontinuous functions

We give some sufficient conditions for proper lower semicontinuous functions on metric spaces to have error bounds (with exponents). For a proper convex function f on a normed space X the existence of a local error bound implies that of a global error bound. If in addition X is a Banach space, then error bounds can be characterized by the subdifferential of f. In a reflexive Banach space X, we further obtain several sufficient and necessary conditions for the existence of error bounds in terms of the lower Dini derivative of f. Received: April 27, 2001 / Accepted: November 6, 2001?Published online April 12, 2002     

Evolving sets, mixing and heat kernel bounds

We show that a new probabilistic technique, recently introduced by the first author, yields the sharpest bounds obtained to date on mixing times of Markov chains in terms of isoperimetric properties of the state space (also known as conductance bounds or Cheeger inequalities). We prove that the bounds for mixing time in total variation obtained by Lovász and Kannan, can be refined to apply to the maximum relative deviation |pⁿ(x,y)/π(y)−1| of the distribution at time n from the stationary distribution π. We then extend our results to Markov chains on infinite state spaces and to continuous-time chains. Our approach yields a direct link between isoperimetric inequalities and heat kernel bounds; previously, this link rested on analytic estimates known as Nash inequalities.Research supported in part by NSF Grants #DMS-0104073 and #DMS-0244479.     

Constructions and bounds on linear error-block codes

We obtain new bounds on the parameters and we give new constructions of linear error-block codes. We obtain a Gilbert–Varshamov type construction. Using our bounds and constructions we obtain some infinite families of optimal linear error-block codes over . We also study the asymptotic of linear error-block codes. We define the real valued function α _q,m,a (δ), which is an analog of the important real valued function α _q (δ) in the asymptotic theory of classical linear error-correcting codes. We obtain both Gilbert–Varshamov and algebraic geometry type lower bounds on α _q,m,a (δ). We compare these lower bounds in graphs.      

Error bounds for multistep methods revisited

For linear multistep methods with constant stepsize we consider error bounds in terms of weightedL ₂-norms ofh ^px^(p) rather than ofh ^px^(p+1). The bounds apply to stiff systemsx'=Ax+f(t,x) where the spectrum ofA lies in a sector andf is of moderate size.     

Perturbation bounds for the Cholesky andQR factorizations

LetA, A+E be Hermitian positive definite matrices. Suppose thatA=LL ^H andA+E=(L+G)(L+G)^H are the Cholesky factorizations ofA andA+E, respectively. In this paper lower bounds and upper bounds on |G|/|L| in terms of |E|/|A| are given. Moreover, perturbation bounds are given for the QR factorization of a complexm ×n matrixA of rankn.This research was supported by the National Science Foundation of China and the Department of Mathematics of Linköping University in Sweden.     

Sharp bounds on distance spectral radius of graphs

Let D(G) denote the distance matrix of a connected graph G. The largest eigenvalue of D(G) is called the distance spectral radius of a graph G, denoted by ?(G). In this article, we give sharp upper and lower bounds for the distance spectral radius and characterize those graphs for which these bounds are best possible.     

Upper bounds for parent-identifying set systems

We derive new upper bounds on the size set families having the c-identifiable parent property (c-IPP) and the c-traceability property (c-TA) and compare these bounds to similar results on parent-identifying codes. An earlier version of this paper appeared in [4]. Sandia National Laboratories—This is a multiprogram laboratory operated by Sandia Corporation, a Lockheed Martin Company, for the United States Department of Energy’s National Nuclear Security Administration under contract DE-AC04-94AL85000.     

Improving eigenvalue bounds using extra bounds

Bounds for various functions of the eigenvalues of a Hermitian matrix A, based on the traces of A and A², are improved. A technique is presented whereby these bounds can be improved by combining them with other bounds. In particular, the diagonal of A, in conjunction with majorization, is used to improve the bounds. These bounds all require O(n²) multiplications.     

Eigenvalue bounds for Hill's equation

For Hill's equation the lowest eigenvalue a₀ of the boundary value problem y(x + 1) = y(x) is considered. Introducing L_p norms of the function f (x), lower bounds for a₀ which depend only on this norm are derived for p = 1,2 and ∞ by solving a variational principle. For these lower bounds analytical expressions are obtained. The quality of the approximations thus obtained is discussed for Mathieu's equation and an application in magnetohydrodynamics is considered.     

Component-wise perturbation analysis and error bounds for linear least squares solutions

Perturbation bounds for the linear least squares problem min _x Ax –b₂ corresponding tocomponent-wise perturbations in the data are derived. These bounds can be computed using a method of Hager and are often much better than the bounds derived from the standard perturbation analysis. In particular this is true for problems where the rows ofA are of widely different magnitudes. Generalizing a result by Oettli and Prager, we can use the bounds to compute a posteriori error bounds for computed least squares solutions.     

Obtaining upper bounds of heat kernels from lower bounds

We show that a near‐diagonal lower bound of the heat kernel of a Dirichlet form on a metric measure space with a regular measure implies an on‐diagonal upper bound. If in addition the Dirichlet form is local and regular, then we obtain a full off‐diagonal upper bound of the heat kernel provided the Dirichlet heat kernel on any ball satisfies a near‐diagonal lower estimate. This reveals a new phenomenon in the relationship between the lower and upper bounds of the heat kernel. © 2007 Wiley Periodicals, Inc.     

Eigenvalue bounds for elliptic operators

Lower bounds for the real parts of the points in the spectrum of elliptic equations are derived. These bounds, depending only on the diameter L of the domain G and on the maximum norm M of the coefficients a, b, are optimal. They are always positive and thus the spectrum is bounded away from the imaginary axis. This result is then used to prove an “anti-dynamo theorem” for magnetic fields with plane symmetry in the case of a compressible steady flow surrounded by a perfect conductor.     

Upper bounds of a stabilizer order for linear finite-dimensional systems

The problem of stabilizing linear dynamic systems by a stabilizer (a dynamic system) is considered. The upper bounds of a stabilizer order obtained using two Hidenori Kimura results are studied. The bound k ₀ is shown to be better than the bounds k ₁ and k ₂ only in one case. In addition, all possible relations between three bounds k ₀, k ₁, and k ₂ are proven to be realized in the space of parameters of observability and controllability indices, i.e., there is a dynamic system with the respective observability and controllability indices.     

Fair upper bounds for the curvature in univariate convex interpolation

In convex interpolation the curvature of the interpolants should be as small as possible. We attack this problem by treating interpolation subject to bounds on the curvature. In view of the concexity the lower bound is equal to zero while the upper bound is assumed to be piecewise constant. The upper bounds are called fair with respect to a function class if the interpolation problem becomes solvable for all data sets in strictly convex position. We derive fair a priori bounds for classes of quadraticC ¹, cubicC ², and quarticC ³ splines on refined grids.     

Best-possible bounds on sets of bivariate distribution functions

The fundamental best-possible bounds inequality for bivariate distribution functions with given margins is the Fréchet–Hoeffding inequality: If H denotes the joint distribution function of random variables X and Y whose margins are F and G, respectively, then max(0,F(x)+G(y)−1)H(x,y)min(F(x),G(y)) for all x,y in [−∞,∞]. In this paper we employ copulas and quasi-copulas to find similar best-possible bounds on arbitrary sets of bivariate distribution functions with given margins. As an application, we discuss bounds for a bivariate distribution function H with given margins F and G when the values of H are known at quartiles of X and Y.     

Tail bounds for occupancy and the satisfiability threshold conjecture

The classical occupancy problem is concerned with studying the number of empty bins resulting from a random allocation of m balls to n bins. We provide a series of tail bounds on the distribution of the number of empty bins. These tail bounds should find application in randomized algorithms and probabilistic analysis. Our motivating application is the following well-known conjecture on threshold phenomenon for the satisfiability problem. Consider random 3-SAT formulas with cn clauses over n variables, where each clause is chosen uniformly and independently from the space of all clauses of size 3. It has been conjectured that there is a sharp threshold for satisfiability at c* ≈? 4.2. We provide a strong upper bound on the value of c*, showing that for c > 4.758 a random 3-SAT formula is unsatisfiable with high probability. This result is based on a structural property, possibly of independent interest, whose proof needs several applications of the occupancy tail bounds.     

On error bounds of polynomial complementarity problems with structured tensors

The recently introduced polynomial complementarity problem (PCP) is an interesting generalization of the tensor complementarity problem (TCP) studied extensively in the literature. In this paper, we make a contribution to analysing the error bounds of PCPs with structured tensors. Specifically, we first show that the solution set of PCPs with a leading ER-tensor is nonempty and compact. Then, we analyse lower bounds of solutions of PCPs under the strict semicopositiveness, thereby gainfully establishing error bounds of PCPs, which, to the best of our knowledge, are not studied in the current PCPs and TCPs literature. Moreover, it is noteworthy that, due to the special structure of PCPs, our error bounds are better than the direct results obtained by applying the theory of non-linear complementarity problems to PCPs.