Concept

Upper and lower bounds

Related publications (171)

Ramsey-Type Results For Semi-Algebraic Relations

A k-ary semi-algebraic relation E on R-d is a subset of R-kd, the set of k-tuples of points in R-d, which is determined by a finite number of polynomial inequalities in kd real variables. The description complexity of such a relation is at most t if d, k < ...

Amer Mathematical Soc2014

Second-order sensitivity of parallel shear flows and optimal spanwise-periodic flow modifications

François Gallaire, Edouard Boujo, Andrea Fani

We perform a second-order sensitivity analysis of the linear temporal stability of a parallel flow subject to small spanwise periodic modification. The need for a second-order analysis results from the fact that spanwise-periodic flow modifications have a ...

2014

Torsion homology of arithmetic lattices and K-2 of imaginary fields

Vincent Emery

Let be a symmetric space of noncompact type. A result of Gelander provides exponential upper bounds in terms of the volume for the torsion homology of the noncompact arithmetic locally symmetric spaces . We show that under suitable assumptions on this resu ...

Springer Heidelberg2014

Linear Programming Decoding of Spatially Coupled Codes

Rüdiger Urbanke, Badih Ghazi

For a given family of spatially coupled codes, we prove that the linear programming (LP) threshold on the binary-symmetric channel (BSC) of the tail-biting graph cover ensemble is the same as the LP threshold on the BSC of the derived spatially coupled ens ...

Ieee-Inst Electrical Electronics Engineers Inc2014

On the Configuration LP for Maximum Budgeted Allocation

Ola Nils Anders Svensson, Christos Kalaitzis, Lukas Polacek, Aleksander Madry

We study the Maximum Budgeted Allocation problem, i.e., the problem of selling a set of m indivisible goods to n players, each with a separate budget, such that we maximize the collected revenue. Since the natural assignment LP is known to have an integral ...

Springer2014

Bounds for the Euclidean minima of function fields

Piotr Aleksander Maciak

In this paper, we define Euclidean minima for function fields and give some bound for this invariant. We furthermore show that the results are analogous to those obtained in the number field case. (C) 2013 The Authors. Published by Elsevier Inc. All rights ...

Academic Press Inc Elsevier Science2014

Bin Packing via Discrepancy of Permutations

Friedrich Eisenbrand, Thomas Rothvoss, Doemoetoer Palvoelgyi

A well-studied special case of bin packing is the 3-partition problem, where n items of size > 1/4 have to be packed in a minimum number of bins of capacity one. The famous Karmarkar-Karp algorithm transforms a fractional solution of a suitable LP relaxati ...

Association for Computing Machinery2013

From Discrete Measurements to Bounded Gradient Estimates: A Look at Some Regularizing Structures

Dominique Bonvin, Grégory François, Gene Bunin

Obtaining a reliable gradient estimate for an unknown function when given only its discrete measurements is a common problem in many engineering disciplines. While there are many approaches to obtaining an estimate of a gradient, obtaining lower and upper ...

American Chemical Society2013

Lyapunov Exponents of Random Walks in Small Random Potential: The Lower Bound

Thomas Mountford, Jean-Christophe Mourrat

We consider the simple random walk on , d > 3, evolving in a potential of the form beta V, where are i.i.d. random variables taking values in [0, + a), and beta > 0. When the potential is integrable, the asymptotic behaviours as beta tends to 0 of the asso ...

Springer Berlin Heidelberg2013

Monte-Carlo utility estimates for Bayesian reinforcement learning

Christos Dimitrakakis

This paper introduces a set of algorithms for Monte-Carlo Bayesian reinforcement learning. Firstly, Monte-Carlo estimation of upper bounds on the Bayes-optimal value function is employed to construct an optimistic policy. Secondly, gradient-based algorithm ...

2013

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.