Lower bounds for linear forms in values of polylogarithms

In this paper, we use Hermite-Padé approximations of the second kind to obtain a lower bound for the absolute value of a linear form, with integer coefficients, in values of polylogarithmic functions at a rational point. This estimate takes into account the growth of all coefficients of the linear form.Translated from Matematicheskie Zametki, vol. 77, no. 4, 2005, pp. 623–629.Original Russian Text Copyright © 2005 by T. Hessami Pilehrood, H. Hessami Pilehrood.This revised version was published online in April 2005 with a corrected issue number.     

Lower bounds for linear forms in values of certain hypergeometric functions

By using Padé approximations of the first kind, a lower bound for the modulus of a linear form with integer coefficients in the values of certain hypergeometric functions at a rational point are obtained. This estimate depends on all the coefficients of the linear form. Translated fromMatematicheskie Zametki, Vol. 67, No. 3, pp. 441–451, March, 2000.     

Lower bounds of linear forms of values of G functions

Lower bounds are obtained for linear forms of values of Siegel's G functions. In particular, it is found that ifα ₁...,α _m are pairwise distinct nonzero rational numbers, then for any positive ? and a natural q>q₀(?,α ₁,...,α _m) we have for any nonzero set (x₀ x₁,..., x_m) of integers the inequality $$|x_0 + x_1 In(i + a_1 q^{ - 1} ) + ... + x_m In(i + a_m q^{ - 1} )|q^{ - \lambda } (h_1 ...h_m )^{ - 1 - \varepsilon } ,$$ where h_i=max(i, ¦x_i¦), andλ=λ (?,α ₁,...,α _m).     

Lower bounds and upper bounds for chromatic polynomials

In this paper we give lower bounds and upper bounds for chromatic polynomials of simple undirected graphs on n vertices having m edges and girth exceeding g © 1993 John Wiley & Sons, Inc.     

Lower bounds for Seshadri constants

One of Demailly's characterization of Seshadri constants on ample line bundles works with Lelong numbers of certain positive singular hermitian metrics. In this note this is translated into algebraic terms by using sections of multiples of the line bundle. The resulting formula for Seshadri constants is applied to compute Seshadri constants on blown up products of curves, to disprove a conjectured characterization of maximal rationally connected quotients and to introduce a new approach to Nagata's conjecture. (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Lower bounds for linear forms in the values of kummer functions with an irrational parameter

Translated from Matematicheskie Zametki, Vol. 49, No. 2, pp. 55–63, February, 1991.     

Lower bounds for the average genus

Two lower bounds are obtained for the average genus of graphs. The average genus for a graph of maximum valence at most 3 is at least half its maximum genus, and the average genus for a 2-connected simplicial graph other than a cycle is at least 1/16 of its cycle rank. © 1995 John Wiley & Sons, Inc.     

Lower bounds for lower Ramsey numbers

For any graph G, let i(G) and μ;(G) denote the smallest number of vertices in a maximal independent set and maximal clique, respectively. For positive integers m and n, the lower Ramsey number s(m, n) is the largest integer p so that every graph of order p has i(G) ≤ m or μ;(G) ≤ n. In this paper we give several new lower bounds for s (m, n) as well as determine precisely the values s(1, n).     

Lower complexity bounds for interpolation algorithms

We introduce and discuss a new computational model for the Hermite-Lagrange interpolation with nonlinear classes of polynomial interpolants. We distinguish between an interpolation problem and an algorithm that solves it. Our model includes also coalescence phenomena and captures a large variety of known Hermite-Lagrange interpolation problems and algorithms. Like in traditional Hermite-Lagrange interpolation, our model is based on the execution of arithmetic operations (including divisions) in the field where the data (nodes and values) are interpreted and arithmetic operations are counted at unit cost. This leads us to a new view of rational functions and maps defined on arbitrary constructible subsets of complex affine spaces. For this purpose we have to develop new tools in algebraic geometry which themselves are mainly based on Zariski’s Main Theorem and the theory of places (or equivalently: valuations). We finish this paper by exhibiting two examples of Lagrange interpolation problems with nonlinear classes of interpolants, which do not admit efficient interpolation algorithms (one of these interpolation problems requires even an exponential quantity of arithmetic operations in terms of the number of the given nodes in order to represent some of the interpolants).In other words, classic Lagrange interpolation algorithms are asymptotically optimal for the solution of these selected interpolation problems and nothing is gained by allowing interpolation algorithms and classes of interpolants to be nonlinear. We show also that classic Lagrange interpolation algorithms are almost optimal for generic nodes and values. This generic data cannot be substantially compressed by using nonlinear techniques.We finish this paper highlighting the close connection of our complexity results in Hermite-Lagrange interpolation with a modern trend in software engineering: architecture tradeoff analysis methods (ATAM).     

Lower bounds for off-line range searching

This paper proves three lower bounds for variants of the following rangesearching problem: Given n weighted points inR ^d andn axis-parallel boxes, compute the sum of the weights within each box: (1) if both additions and subtractions are allowed, we prove that Ω(n log logn) is a lower bound on the number of arithmetic operations; (2) if subtractions are disallowed the lower bound becomes Ω(n(logn/loglogn)^d-1), which is nearly optimal; (3) finally, for the case where boxes are replaced by simplices, we establish a quasi-optimal lower bound of Ω(n^2-2/(d+1))/polylog(n). A preliminary version of this paper appeared inProc. 27th Ann. ACM Symp. on Theory of Computing, May 1995, pp. 733–740. This work was supported in part by NSF Grant CCR-93-01254 and the Geometry Center, University of Minnesota, an STC funded by NSF, DOE, and Minnesota Technology, Inc.     

Lower complexity bounds for positive contactomorphisms

Let S*Q be the spherization of a closed connected manifold of dimension at least two. Consider a contactomorphism φ that can be reached by a contact isotopy that is everywhere positively transverse to the contact structure. In other words, φ is the time-1-map of a time-dependent Reeb flow. We show that the volume growth of φ is bounded from below by the topological complexity of the loop space of Q. Denote by ΩQ₀(q) the component of the based loop space that contains the constant loop.     

Lower bounds for algebraic decision trees

A topological method is given for obtaining lower bounds for the height of algebraic decision trees. The method is applied to the knapsack problem where an $\text{Ω(n}{}^2\text{)}$ bound is obtained for trees with bounded-degree polynomial tests, thus extending the Dobkin-Lipton result for linear trees. Applications to the convex hull problem and the distinct element problem are also indicated. Some open problems are discussed.     

Lower bounds for weak Byzantine agreement

Lower bounds for Byzantine agreement obtained by Dolev and Strong are shown, by a simpler method, also to be true for weak Byzantine agreement.This work was done while the author was studying at University of California, Santa Barbara, in 1984.