A parallel algorithmic version of the local lemma

The Lovasz Local Lemma is a tool that enables one to show that certain events hold with positive, though very small probability. It often yields existence proofs of results without supplying any efficient way of solving the corresponding algorithmic problems. J. Beck recently has found a method for converting some of these existence proofs into efficient algorithmic procedures, at the cost of losing a little in the estimates. His method does not seem to be parallelizable. Here we modify his technique and achieve an algorithmic version that can be parallelized, thus obtaining deterministic NC^l algorithms for several interesting algorithmic problems.     

An algorithmic hypergraph regularity lemma

Szemerédi 's Regularity Lemma is a powerful tool in graph theory. It asserts that all large graphs admit bounded partitions of their edge sets, most classes of which consist of uniformly distributed edges. The original proof of this result was nonconstructive, and a constructive proof was later given by Alon, Duke, Lefmann, Rödl, and Yuster. Szemerédi's Regularity Lemma was extended to hypergraphs by various authors. Frankl and Rödl gave one such extension in the case of 3‐uniform hypergraphs, which was later extended to k‐uniform hypergraphs by Rödl and Skokan. W.T. Gowers gave another such extension, using a different concept of regularity than that of Frankl, Rödl, and Skokan. Here, we give a constructive proof of a regularity lemma for hypergraphs.     

An algorithmic approach to the Lovász local lemma. I

The Lovász Local Lemma is a remarkable sieve method to prove the existence of certain structures without supplying any efficient way of finding these structures. In this article we convert some of the applications of the Local Lemma into polynomial time sequential algorithms (at the cost of a weaker constant factor in the “exponent”). Our main example is the following: assume that in an n-uniform hypergraph every hyperedge intersects at most 2^n/48 other hyperedges, then there is a polynomial time algorithm that finds a two-coloring of the points such that no hyperedge is monochromatic.     

A version of Zabrodsky's lemma

Zabrodsky's Lemma says: Suppose given a fibrant space and a homotopy fiber sequence with connected. If the map which is induced by is a weak equivalence, then is a weak equivalence. This has been generalized by Bousfield. We improve on Bousfield's generalization and give some applications.

     

A new version of algorithmic information theory

We present a much more concrete version of algorithmic information theory in which one can actually run on a computer the algorithms in the proofs of a number of key information-theoretic incompleteness theorems.     

A local version of the closed graph lemma of Kelley

The paper concerns the local, metric version of a closed graph result of Kelley.     

An inner product lemma

Given the operator product BA in which both A and B are symmetric positive‐definite operators, for which symmetric positive‐definite operators C is BA symmetric positive‐definite in the C inner product 〈x, y〉C? This question arises naturally in preconditioned iterative solution methods, and will be answered completely here. Copyright © 2004 John Wiley & Sons, Ltd.     

An extension of the mountain pass lemma

We present a more general form of the mountain pass lemma. It asserts that a C¹ functional which satisfies the Palais–Smale condition admits a critical value when the connectedness of certain level sets changes. We also give an improved form of a theorem given in [A. Bahri, H. Berestycki, A perturbation method in critical point theory and applications, Trans. Amer. Math. Soc. 267 (1) (1981) 1–32], which characterizes the existence of the critical value by means of contractibility properties of the level sets.     

An operator analogue of the Schwarz-Loewner lemma

Translated from Teoriya Funktsii, Funktsional'nyi Analiz i Ikh Prilozheniya, No. 48, pp. 71–74, 1987.     

An algorithmic Littlewood-Richardson rule

We introduce a Littlewood-Richardson rule based on an algorithmic deformation of skew Young diagrams and present a bijection with the classical rule. The result is a direct combinatorial interpretation and proof of the geometric rule presented by Coskun (2000). We also present a corollary regarding the Specht modules of the intermediate diagrams.     

An improved sectional-Anosov closing lemma

We prove that all nonwandering points of a sectional-Anosov flow on a compact 3-manifold can be approximated by periodic points or by points for which the omega-limit set is a singularity. This improves the closing lemma in Morales (Mich. Math. J. 56(1):29?C53, 2008). We also describe a sectional-Anosov flow for which the recurrent points are not dense in the nonwandering set.     

An algorithmic approach to Hermite-Birkhoff-interpolation

Summary This paper deals with an algorithmic approach to the Hermite-Birkhoff-(HB)interpolation problem. More precisely, we will show that Newton's classical formula for interpolation by algebraic polynomials naturally extends to HB-interpolation. Hence almost all reasons which make Newton's method superior to just solving the system of linear equations associated with the interpolation problem may be repeated. Let us emphasize just two: Newton's formula being a biorthogonal expansion has a well known permanence property when the system of interpolation conditions grows. From Newton's formula by an elementary argument due to Cauchy an important representation of the interpolation error can be derived. All of the above extends to HB-interpolation with respect to canonical complete ebyev-systems and naturally associated differential operators [7]. A numerical example is given.     

An algorithmic characterization of total digraphs

We consider total digraphs of digraphs and present: (i) a structural characterization, (ii) an algorithmic characterization based on a labeling procedure, and (iii) an efficient recognition algorithm. The computational complexity of the algorithm is dominated by the complexity of finding the square of a Boolean (adjacency) matrix of a digraph.     

An extension lemma and homogeneous programming

An extension lemma, which is equivalent to the generalized Gordan's theorem of the alternative, due to Fan, Glicksberg, and Hoffman, is applied to present a duality theory for a general class of homogeneous programs, with and without a constraint qualification of Slater type. In addition, an existence theorem for optimal solutions of homogeneous programs is given.The author thanks an anonymous referee for valuable suggestions about an earlier draft of this paper.     

An adjacency lemma for critical multigraphs

In edge colouring it is often useful to have information about the degree distribution of the neighbours of a given vertex. For example, the well-known Vizing's Adjacency Lemma provides a useful lower bound on the number of vertices of maximum degree adjacent to a given one in a critical graph. We consider an extension of this problem, where we seek information on vertices at distance two from a given vertex in a critical graph. We extend and, simultaneously, generalize to multigraphs two results proved, respectively, by Zhang [Every planar graph with maximum degree seven is Class 1, Graphs Combin. 16 (2000) 467-495] and Sanders and Zhao [Planar graphs of maximum degree seven are Class 1, J. Combin. Theory Ser. B 83 (2001) 201-212].     

An application of the neyman-pearson lemma to gaussian processes

Letξ _i (t),i=1,2,t ∈ [0, 1], be Gaussian zero mean processes with continous sample paths. Bounds for the probabilitiesβ _i =P{ξ _i -α _i ∈B},i=1,2, are given, where a_iε C0, 1., and B is a Borel subset of C[0, 1] Bibliography: 5 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 207, pp. 5–12, 1993. Translated by V. Sudakov.