Concept

Least-upper-bound property

Related publications (102)

A Polynomial-Time Solution Scheme for Quadratic Stochastic Programs

We consider quadratic stochastic programs with random recourse—a class of problems which is perceived to be computationally demanding. Instead of using mainstream scenario tree-based techniques, we reduce computational complexity by restricting the space o ...

2013

Topological Complexity Of H-Spaces

Jérôme Scherer

Let X be a (not-necessarily homotopy-associative) H-space. We show that TCn+1(X) = cat(X-n), for n >= 1, where TCn+1(-) denotes the so-called higher topological complexity introduced by Rudyak, and cat(-) denotes the Lusternik-Schnirelmann category. We als ...

Amer Mathematical Soc2013

Upper bounds for the Euclidean minima of abelian fields of odd prime power conductor

Eva Bayer Fluckiger, Piotr Aleksander Maciak

The aim of this paper is to give upper bounds for the Euclidean minima of abelian fields of odd prime power conductor. In particular, these bounds imply Minkowski's conjecture for totally real number fields of conductor p(r), where p is an odd prime number ...

Springer Verlag2013

A Lower Bound on Achievable Rates by Polar Codes with Mismatch Polar Decoding

Mine Alsan

In this paper we show that mismatched polar codes over symmetric B-DMCs symmetrized under the same permutation can achieve rates of at least I (W, V) bits whenever I (W, V) > 0, where W denotes the communication channel, V the mismatched channel used in th ...

Ieee2013

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

Expected loss bounds for authentication in constrained channels

Serge Vaudenay, Christos Dimitrakakis, Aikaterini Mitrokotsa

We derive bounds on the expected loss for authenti-cation protocols in channels which are constrained due to noisyconditions and communication costs. This is motivated by anumber of authentication protocols, where at least some partof the authentication is ...

Ieee2012

Vectors in a box

Doemoetoer Palvoelgyi

For an integer d a parts per thousand yen 1, let tau(d) be the smallest integer with the following property: if v (1), v (2), . . . , v (t) is a sequence of t a parts per thousand yen 2 vectors in [-1, 1] (d) with , then there is a set of indices, 2 a part ...

Springer2012

Early Deciding Synchronous Renaming in O( logf ) Rounds or Less

Rachid Guerraoui, Dan Alistarh, Hagit Albo Attiya

Renaming is a fundamental problem in distributed computing, in which a set of n processes need to pick unique names from a namespace of limited size. In this paper, we present the first early-deciding upper bounds for synchronous renaming, in which the run ...

Springer Berlin Heidelberg2012

Tight Approximation Algorithms for Scheduling with Fixed Jobs and Nonavailability

Ola Nils Anders Svensson, Klaus Jansen

We study two closely related problems in nonpreemptive scheduling of jobs on identical parallel machines. In these two settings there are either fixed jobs or nonavailability intervals during which the machines are not available; in both cases, the objecti ...

Assoc Computing Machinery2012

Local Sampling Analysis for Quadratic Embeddings of Riemannian Manifolds

Hemant Tyagi

In this work we do a theoretical analysis of the local sampling conditions for points lying on a quadratic embedding of a Riemannian manifold in a Euclidean space. The embedding is assumed to be quadratic at a reference point

P

. Our analysis is based on ...

2011

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.

Local Sampling Analysis for Quadratic Embeddings of Riemannian Manifolds

Hemant Tyagi

P

. Our analysis is based on ...

2011