Probabilistic bounds and algorithms for the maximum satisfiability problem

In this paper we present a new method to analyze and solve the maximum satisfiability problem. We randomize the Boolean variables, assign probabilities to their possible values and, by using recently developed probabilistic bounds of the authors, present a deterministic procedure to obtain solution to the maximum satisfiability problem. Our algorithm generalizes the heuristic procedure given by Johnson, 1974.Research supported by AFOSR Grants 0271, 0066 and by NSF Grant 85-03212.     

Worst-case time bounds for coloring and satisfiability problems

We consider worst case time bounds for certain NP-complete problems. In particular, we consider the (k,2)-satisfiability problem which includes as special cases some canonical problems such as graph coloring and satisfiability. For the (k,2)-satisfiability problem, we present a randomized algorithm that runs in time O^*((k!)^n/k).² This bound is equivalent to O((k/c_k)ⁿ) with c_k increasing to the asymptotic limit e. For k11, we improve upon the O((0.4518k)ⁿ) randomized bound of Eppstein [Proceedings of the 12th Annual ACM–SIAM Symposium on Discrete Algorithms, pp. 329–337]. A special case of (k,2)-satisfiability is k-colorability; here we achieve the above time bound for a slightly larger c_k that has the same asymptotic behavior.     

Simple proofs of occupancy tail bounds

We give a simple proof of an occupancy tail bound in the balls and bins experiment using the method of bounded differences in expected form. We also indicate how a short, calculation-free proof of another occupancy tail bound follows from an extension of the standard Chernoff–Hoeffding bounds to variables that satisfy some general notions of negative dependence. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 11 , 119–123 (1997)     

The satisfiability threshold for randomly generated binary constraint satisfaction problems

We study two natural models of randomly generated constraint satisfaction problems. We determine how quickly the domain size must grow with n to ensure that these models are robust in the sense that they exhibit a non‐trivial threshold of satisfiability, and we determine the asymptotic order of that threshold. We also provide resolution complexity lower bounds for these models. One of our results immediately yields a theorem regarding homomorphisms between two random graphs. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

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.     

Tail bounds for the joint distribution of the surplus prior to and at ruin

For the classical risk model with Poisson arrivals, we study the (bivariate) tail of the joint distribution of the surplus prior to and at ruin. We obtain some exact expressions and new bounds for this tail, and we suggest three numerical methods that may yield upper and lower bounds for it. As a by-product of the analysis, we obtain new upper and lower bounds for the probability and severity of ruin. Many of the bounds in the present paper improve and generalise corresponding bounds that have appeared earlier. For the numerical bounds, their performance is also compared against bounds available in the literature.     

Tail bounds for the distribution of the deficit in the renewal risk model

We obtain upper and lower bounds for the tail of the deficit at ruin in the renewal risk model, which are (i) applicable generally; and (ii) based on reliability classifications. We also derive two-side bounds, in the general case where a function satisfies a defective renewal equation, and we apply them to the renewal model, using the function Λ_u introduced by [Psarrakos, G., Politis, K., 2007. A generalisation of the Lundberg condition in the Sparre Andersen model and some applications (submitted for publication)]. Finally, we construct an upper bound for the integrated function and an asymptotic result when the adjustment coefficient exists.     

Using a computer to obtain Chebotarev bounds in the nonhomogeneous Minkowski's conjecture

The Chebotarev method in Skubenko's form [7] is applied in order to generate by computer improved upper bounds on the product of n real linear nonhomogeneous forms of n variables.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 151, pp. 7–25, 1986.     

Tail bounds for the height and width of a random tree with a given degree sequence

Fix a sequence c = (c₁,…,c_n) of non‐negative integers with sum n ? 1. We say a rooted tree T has child sequence c if it is possible to order the nodes of T as v₁,…,v_n so that for each 1 ≤ i ≤ n, v_i has exactly c_i children. Let ${\mathcal T}Fix a sequence c = (c₁,…,c_n) of non‐negative integers with sum n ? 1. We say a rooted tree T has child sequence c if it is possible to order the nodes of T as v₁,…,v_n so that for each 1 ≤ i ≤ n, v_i has exactly c_i children. Let ${\mathcal T}$ be a plane tree drawn uniformly at random from among all plane trees with child sequence c . In this note we prove sub‐Gaussian tail bounds on the height (greatest depth of any node) and width (greatest number of nodes at any single depth) of ${\mathcal T}$. These bounds are optimal up to the constant in the exponent when c satisfies $\sum_{i=1}^n c_i^2=O(n)$; the latter can be viewed as a “finite variance” condition for the child sequence. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

Improving the bounds of the multiplicity conjecture: The codimension 3 level case

The Multiplicity Conjecture (MC) of Huneke and Srinivasan provides upper and lower bounds for the multiplicity of a Cohen-Macaulay algebra A in terms of the shifts appearing in the modules of the minimal free resolution (MFR) of A. All the examples studied so far have lead to conjecture (see [J. Herzog, X. Zheng, Notes on the multiplicity conjecture. Collect. Math. 57 (2006) 211-226] and [J. Migliore, U. Nagel, T. Römer, Extensions of the multiplicity conjecture, Trans. Amer. Math. Soc. (preprint: math.AC/0505229) (in press)]) that, moreover, the bounds of the MC are sharp if and only if A has a pure MFR. Therefore, it seems a reasonable-and useful-idea to seek better, if possibly ad hoc, bounds for particular classes of Cohen-Macaulay algebras.In this work we will only consider the codimension 3 case. In the first part we will stick to the bounds of the MC, and show that they hold for those algebras whose h-vector is that of a compressed algebra.In the second part, we will (mainly) focus on the level case: we will construct new conjectural upper and lower bounds for the multiplicity of a codimension 3 level algebra A, which can be expressed exclusively in terms of the h-vector of A, and which are better than (or equal to) those provided by the MC. Also, our bounds can be sharp even when the MFR of A is not pure.Even though proving our bounds still appears too difficult a task in general, we are already able to show them for some interesting classes of codimension 3 level algebras A: namely, when A is compressed, or when its h-vector h(A) ends with (…,3,2). Also, we will prove our lower bound when h(A) begins with (1,3,h₂,…), where h₂≤4, and our upper bound when h(A) ends with (…,h_c−1,h_c), where h_c−1≤h_c+1.     

A proof of Niederreiter's conjecture concerning error bounds for quasi-Monte Carlo integration

In this paper Niederreiter's error bound for quasi-Monte Carlo integration on bounded Jordan measurable subsets of the k-dimensional unit cube E^k is improved. The new error bound, which has been conjectured by Niederreiter, reduces to the corresponding error bound given by Zaremba in case of integration on convex subsets of E^k.     

A new algorithm for the propositional satisfiability problem

A new enumeration algorithm is proposed for the propositional satisfiability problem. Such algorithm is based on a hypergraph formulation of the problem. Two different implementations of the algorithm are presented together with the results of an experimentation intended to compare their performance with the performance of other known methods. The computational results obtained are quite promising.     

Delaying satisfiability for random 2SAT

Let (C₁,C′_(*)),(C₂,C′_(*)),…,(C _m,C′_(*)) be a sequence of ordered pairs of 2CNF clauses chosen uniformly at random (with replacement) from the set of all 4 \begin{align*}\binom{n}{2}\end{align*} clauses on n variables. Choosing exactly one clause from each pair defines a probability distribution over 2CNF formulas. The choice at each step must be made on‐line, without backtracking, but may depend on the clauses chosen previously. We show that there exists an on‐line choice algorithm in the above process which results whp in a satisfiable 2CNF formula as long as m/n ≤ (1000/999)^1/4. This contrasts with the well‐known fact that a random m ‐clause formula constructed without the choice of two clauses at each step is unsatisfiable whp whenever m/n > 1. Thus the choice algorithm is able to delay satisfiability of a random 2CNF formula beyond the classical satisfiability threshold. Choice processes of this kind in random structures are known as “Achlioptas processes.” This paper joins a series of previous results studying Achlioptas processes in different settings, such as delaying the appearance of a giant component or a Hamilton cycle in a random graph. In addition to the on‐line setting above, we also consider an off‐line version in which all m clause‐pairs are presented in advance, and the algorithm chooses one clause from each pair with knowledge of all pairs. For the off‐line setting, we show that the two‐choice satisfiability threshold for k ‐SAT for any fixed k coincides with the standard satisfiability threshold for random 2k ‐SAT.© 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

Tail index estimation for heavy tails: accommodation of bias in the excesses over a high threshold

In statistics of extremes, inference is often based on the excesses over a high random threshold. Those excesses are approximately distributed as the set of order statistics associated to a sample from a generalized Pareto model. We then get the so-called “maximum likelihood” estimators of the tail index γ. In this paper, we are interested in the derivation of the asymptotic distributional properties of a similar “maximum likelihood” estimator of a positive tail index γ, based also on the excesses over a high random threshold, but with a trial of accommodation of bias in the Pareto model underlying those excesses. We next proceed to an asymptotic comparison of the two estimators at their optimal levels. An illustration of the finite sample behaviour of the estimators is provided through a small-scale Monte Carlo simulation study. Research partially supported by FCT/POCTI and POCI/FEDER.     

Generalizations of the image conjecture and the Mathieu conjecture

We first propose a generalization of the image conjecture Zhao (submitted for publication) [31] for the commuting differential operators related with classical orthogonal polynomials. We then show that the non-trivial case of this generalized image conjecture is equivalent to a variation of the Mathieu conjecture Mathieu (1997) [21] from integrals of G-finite functions over reductive Lie groups G to integrals of polynomials over open subsets of Rⁿ with any positive measures. Via this equivalence, the generalized image conjecture can also be viewed as a natural variation of the Duistermaat and van der Kallen theorem Duistermaat and van der Kallen (1998) [14] on Laurent polynomials with no constant terms. To put all the conjectures above in a common setting, we introduce what we call the Mathieu subspaces of associative algebras. We also discuss some examples of Mathieu subspaces from other sources and derive some general results on this newly introduced notion.     

Lower bounds for centered and wrap-around L2-discrepancies and construction of uniform designs by threshold accepting

We study the uniformity of two- and three-level U-type designs based on the centered and wrap-around L₂-discrepancies. By analyzing the known formulae, we find it possible to reexpress them as functions of column balance, and also as functions of Hamming distances of the rows. These new representations allow to obtain two kinds of lower bounds, which can be used as bench marks in searching uniform U-type designs. An efficient updating procedure for the local search heuristic threshold accepting is developed based on these novel formulations of the centered and wrap-around L₂-discrepancies. Our implementation of this heuristic for the two- and three-level case efficiently generates low discrepancy U-type designs. Their quality is assessed using the available lower bounds.