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.     

Tail Asymptotics for HOL Priority Queues Handling a Large Number of Independent Stationary Sources

In this paper we study the asymptotics of the tail of the buffer occupancy distribution in buffers accessed by a large number of stationary independent sources and which are served according to a strict HOL priority rule. As in the case of single buffers, the results are valid for a very general class of sources which include long-range dependent sources with bounded instantaneous rates. We first consider the case of two buffers with one of them having strict priority over the other and we obtain asymptotic upper bound for the buffer tail probability for lower priority buffer. We discuss the conditions to have asymptotic equivalents. The asymptotics are studied in terms of a scaling parameter which reflects the server speed, buffer level and the number of sources in such a way that the ratios remain constant. The results are then generalized to the case of M buffers which leads to the source pooling idea. We conclude with numerical validation of our formulae against simulations which show that the asymptotic bounds are tight. We also show that the commonly suggested reduced service rate approximation can give extremely low estimates.     

On martingale tail sums for the path length in random trees

For a martingale (X_n) converging almost surely to a random variable X, the sequence (X_n– X) is called martingale tail sum. Recently, Neininger (Random Structures Algorithms 46 (2015), 346–361) proved a central limit theorem for the martingale tail sum of Régnier's martingale for the path length in random binary search trees. Grübel and Kabluchko (in press) gave an alternative proof also conjecturing a corresponding law of the iterated logarithm. We prove the central limit theorem with convergence of higher moments and the law of the iterated logarithm for a family of trees containing binary search trees, recursive trees and plane‐oriented recursive trees. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 493–508, 2017     

New Maximal Numbers of Equilibria in Bimatrix Games

This paper presents a new lower bound of on the maximal number of Nash equilibria in d×d bimatrix games, a central concept in game theory. The proof uses an equivalent formulation of the problem in terms of pairs of polytopes with 2d facets in d -space. It refutes a recent conjecture that 2 ^d -1 is an upper bound, which was proved for d≤4. The first counterexample is a 6×6 game with 75 equilibria. The case d=5 remains open. The result carries the lower bound closer to the previously known upper bound of . Received July 23, 1997, and in revised form June 26, 1998.     

Quantitative multiple recurrence for two and three transformations

We observe a subadditivity property for the noise sensitivity of subsets of Gaussian space. For subsets of volume 1/2, this leads to an almost trivial proof of Borell’s Isoperimetric Inequality for ρ = cos( π/2?), ? ∈ N. Rotational sensitivity also easily gives the Gaussian Isoperimetric Inequality for volume-1/2 sets and a.8787-factor UG-hardness for Max-Cut (within 10^?4 of the optimum). As another corollary we show the Hermite tail bound \(||{f^{ > k}}||_2^2 \geqslant \Omega (Var[f]).\frac{1}{{\sqrt k }}for:{R^n} \to \{ - 1,1\} \). Combining this with the Invariance Principle shows the same Fourier tail bound for any Boolean f: {?1, 1} ⁿ → {?1, 1} with all its noisy-influences small, or more strongly, that a Boolean function with tail weight smaller than this bound must be close to a junta. This improves on a result of Bourgain, where the bound on the tail weight was only \(\frac{1}{{{k^{1/2 + o(1)}}}}\). We also show a simplification of Bourgain’s proof that does not use Invariance and obtains the bound \(\frac{1}{{\sqrt k {{\log }^{1.5}}k}}\).     

A semidefinite bound for mixing rates of Markov chains

We study general geometric techniques for bounding the spectral gap of a reversible Markov chain. We show that the best bound obtainable using these techniques can be computed in polynomial time via semidefinite programming, and is off by at most a factor of order log²n, where n is the number of states. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 11 , 299–313 (1997)     

Point‐wise decay estimate for the global classical solutions to quasilinear hyperbolic systems

In this paper, we first consider the Cauchy problem for quasilinear strictly hyperbolic systems with weak linear degeneracy. The existence of global classical solutions for small and decay initial data was established in (Commun. Partial Differential Equations 1994; 19 :1263–1317; Nonlinear Anal. 1997; 28 :1299–1322; Chin. Ann. Math. 2004; 25B :37–56). We give a new, very simple proof of this result and also give a sharp point‐wise decay estimate of the solution. Then, we consider the mixed initial‐boundary‐value problem for quasilinear hyperbolic systems with nonlinear boundary conditions in the first quadrant. Under the assumption that the positive eigenvalues are weakly linearly degenerate, the global existence of classical solution with small and decay initial and boundary data was established in (Discrete Continuous Dynamical Systems 2005; 12 (1):59–78; Zhou and Yang, in press). We also give a simple proof of this result as well as a sharp point‐wise decay estimate of the solution. Copyright © 2008 John Wiley & Sons, Ltd.     

Improved Bounds for Planar k -Sets and Related Problems

We prove an O(n(k+1) ^1/3 ) upper bound for planar k -sets. This is the first considerable improvement on this bound after its early solution approximately 27 years ago. Our proof technique also applies to improve the current bounds on the combinatorial complexities of k -levels in the arrangement of line segments, k convex polygons in the union of n lines, parametric minimum spanning trees, and parametric matroids in general. <lsiheader> <onlinepub>26 June, 1998 <editor>Editors-in-Chief: &lsilt;a href=../edboard.html#chiefs&lsigt;Jacob E. Goodman, Richard Pollack&lsilt;/a&lsigt; <pdfname>19n3p373.pdf <pdfexist>yes <htmlexist>no <htmlfexist>no <texexist>yes <sectionname> </lsiheader> Received May 31, 1997, and in revised form June 30, 1997.     

Effective Rates of Convergence for the Resolvents of Accretive Operators

We extract explicit, computable, and highly uniform rates for the strong convergence of the resolvents of set-valued, m-accretive, and uniformly accretive at zero/?-expansive operators on general real Banach spaces to the zero of each operator. This is achieved through proof mining on the proof of a theorem by García–Falset the motivation of which originates from a classical work by Reich. For the bound extraction we make use of a modulus of accretivity at zero, a notion introduced recently by Kohlenbach and the author, as well as a modulus of ?-expansivity, a notion introduced analogously here.     

On Weak Solutions to the Non-stationary van Roosbroeck's System with Discontinuous Permittivities

In this paper we prove the existence of a weak solution to the non-stationary drift–diffusion equations (van Roosbroeck's system) of semiconductor theory involving discontinuous permittivities. The proof is based on an approximation of these equations by a system with bounded non-linearities, deriving a priori estimates on the approximate solutions and then carrying out the passage to limit. The discussion is completed by some regularity results for the weak solution under consideration. © 1997 by B. G. Teubner Stuttgart–John Wiley & Sons Ltd. Math. Meth. Appl. Sci., Vol. 20, 689–706 (1997).     

G ∞-Formality Theorem in Terms of Graphs and Associated Chevalley–Eilenberg–Harrison Cohomology #

In 1997, M. Kontsevich proved the L _∞-formality conjecture (which implies the existence of star-products for any Poisson manifold) using graphs. A year later, D. Tamarkin gave another proof of a more general conjecture (for G _∞-structures) using operads and cohomological methods. In this article, we show how Tamarkin's construction can be written using graphs. For that, we introduce a generalization of Kontsevich graphs on which we define a “Chevalley–Eilenberg–Harrison” complex. We show that this complex on graphs is related to the “Chevalley–Eilenberg–Harrison” complex for maps on polyvector fields, which is trivial and give Tamarkin's formality theorem as a consequence. This formality reduces to an L _∞-formality.     

Line Transversals of Balls and Smallest Enclosing Cylinders in Three Dimensions

We establish a near-cubic upper bound on the complexity of the space of line transversals of a collection of n balls in three dimensions, and show that the bound is almost tight, in the worst case. We apply this bound to obtain a near-cubic algorithm for computing a smallest infinite cylinder enclosing a given set of points or balls in 3-space. We also present an approximation algorithm for computing a smallest enclosing cylinder. Received May 23, 1997, and in revised form October 20, 1997.     

Rates of convergence of random walk on distance regular graphs

When run on any non-bipartite q-distance regular graph from a family containing graphs of arbitrarily large diameter d, we show that d steps are necessary and sufficient to drive simple random walk to the uniform distribution in total variation distance, and that a sharp cutoff phenomenon occurs. For most examples, we determine the set on which the variation distance is achieved, and the precise rate at which it decays. The upper bound argument uses spectral methods – combining the usual Cauchy-Schwarz bound on variation distance with a bound on the tail probability of a first-hitting time, derived from its generating function. Received: 2 April 1997 / Revised version: 10 May 1998     

Tail probability of random variable and Laplace transform

We investigate the exponential decay of the tail probability P(X?>?x) of a continuous type random variable X. Let ?(s) be the Laplace–Stieltjes transform of the probability distribution function F(x)?=?P(X?≤?x) of X, and σ₀ be the abscissa of convergence of ?(s). We will prove that if ?∞?0?s) on the axis of convergence are only a finite number of poles, then the tail probability decays exponentially. For the proof of our theorem, Ikehara's Tauberian theorem will be extended and applied.     

Maxima in hypercubes

We derive a Berry‐Esseen bound, essentially of the order of the square of the standard deviation, for the number of maxima in random samples from (0,1)^d. The bound is, although not optimal, the first of its kind for the number of maxima in dimensions higher than two. The proof uses Poisson processes and Stein's method. We also propose a new method for computing the variance and derive an asymptotic expansion. The methods of proof we propose are of some generality and applicable to other regions such as d‐dimensional simplex. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005     

Clark formula and logarithmic Sobolev inequalities for Bernoulli measures

Using a Clark formula for the predictable representation of random variables in discrete time and adapting the method presented in [Electron. Commun. Probab. 2 (1997) 71–81] in the Brownian case, we obtain a proof of modified and L¹ logarithmic Sobolev inequalities for Bernoulli measures. We also prove a bound that improves these inequalities as well as the optimal constant inequality of [J. Funct. Anal. 156 (2) (1998) 347–365]. To cite this article: F. Gao, N. Privault, C. R. Acad. Sci. Paris, Ser. I 336 (2003).     

Exponential and double exponential tails for maximum of two-dimensional discrete Gaussian free field

We study the tail behavior for the maximum of discrete Gaussian free field on a 2D box with Dirichlet boundary condition after centering by its expectation. We show that it exhibits an exponential decay for the right tail and a double exponential decay for the left tail. In particular, our result implies that the variance of the maximum is of order 1, improving an $o(\log n)$ bound by Chatterjee (Chaos, concentration, and multiple valleys, 2008) and confirming a folklore conjecture. An important ingredient for our proof is a result of Bramson and Zeitouni (Commun. Pure Appl. Math, 2010), who proved the tightness of the centered maximum together with an evaluation of the expectation up to an additive constant.     

Pebbling in diameter two graphs and products of paths

Results regarding the pebbling number of various graphs are presented. We say a graph is of Class 0 if its pebbling number equals the number of its vertices. For diameter d we conjecture that every graph of sufficient connectivity is of Class 0. We verify the conjecture for d = 2 by characterizing those diameter two graphs of Class 0, extending results of Pachter, Snevily and Voxman. In fact we use this characterization to show that almost all graphs have Class 0. We also present a technical correction to Chung's alternate proof of a number theoretic result of Lemke and Kleitman via pebbling. © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 119–128, 1997     

Lower Bounds for Shellsort

We show lower bounds on the worst-case complexity of Shellsort. In particular, we give a fairly simple proof of an Ω(n (lg² n)/(lg lg n)²) lower bound for the size of Shellsort sorting networks for arbitrary increment sequences. We also show an identical lower bound for the running time of Shellsort algorithms, again for arbitrary increment sequences. Our lower bounds establish an almost tight trade-off between the running time of a Shellsort algorithm and the length of the underlying increment sequence.     

An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle

We prove lower bounds of the form exp(n^{ε d}), ε_d > 0, on the length of proofs of an explicit sequence of tautologies, based on the Pigeonhole Principle, in proof systems using formulas of depth d, for any constant d. This is the largest lower bound for the strongest proof system, for which any superpolynomial lower bounds are known.