Category: seminars
Minimizing the number of unhappy singles
Abstract: We consider the problem of computing a large stable matching in a bipartite graph G = (A\cup B, E) where each vertex u \in A\cup B ranks its neighbors in an order of preference, perhaps involving ties. A matching M is said to be stable if there is ...
Euler Polytopes and Convex Matroid Optimization
We introduce a novel family of polytopes strengthening bounds relevant to combinatorial optimization and convex matroid optimization. Del Pia and Michini recently improved the upper bound of kd due to Kleinschmidt and Onn for the largest possible diameter of the convex hull of a set of points in dimension d ...
Prophet inequalities and secretary problem: a new approach.
In the setting of prophet inequalities and secretary problem, one observes a sequence of random objects and is allowed to stop the sequence at any time, claiming a reward equal to the most recent observation. The objective is to maximize the reward while observing the objects in an online manner ...
Complexité de comptage des opérateurs d'intégration
L'analyse récursive est un domaine qui s'attache à comprendre la notion de calcul sur des ensembles non dénombrables comme les nombres réels ou les fonctions réelles par exemple. Il permet entre autres de définir une notion de complexité sur de tels ensembles, mais les classes de complexité associées ...
Universal computation and asymptotic behaviour in symbolic dynamics.
Simulating universal computation in a given system has multiple uses: characterising the power of a model of computation, demonstrating the impossibility to predict the long-term behaviour or the properties of a physical model, forcing the system to adopt a given, computationally complex behaviour... The technical details of these simulations, corresponding ...
Highly Resource-limited Distributed Systems
In this talk I would like to advocate the study of non-classical distributed systems whose computing nodes can perform only simple computations under highly restricted communication mechanisms and memory capabilities. I will present two problems, we are currently working on, one from chip design and one from biology, showing that ...
Amortized Averaging Algorithms for Approximate Consensus
We introduce a new class of distributed algorithms for the approximate consensus problem in dynamic rooted networks, which we call amortized averaging algorithms. They are deduced from ordinary averaging algorithms by adding a value-gathering phase before each value update. This allows their decision time to drop from being exponential in ...
Choosing k best arms in adversarial bandit setting: application to inter-cell Interference Coordination
This talk address to Multi-Armed Bandit problem for Distributed Inter-Cell Interference Coordination. In order to achieve high data rates in future wireless packet switched cellular networks, aggressive frequency reuse is inevitable due to the scarcity of the radio resources. While intra-cell interference is mostly mitigated and can be ignored, inter-cell ...
Locating pairs of vertices on Hamiltonian cycles
We first introduce some of our recent results that generalises Dirac's theorem in Hamiltonian graph theory. Then we will focus on the following conjecture of Enomoto that states that, if \(G\) is a graph of order \(n\) with minimum degree \(delta(G)geq frac{n}{2}+1\), then for ...if (!document.getElementById('mathjaxscript_pelican_#%@#$@#')) { var align = "center", indent = "0em", linebreak = "false"; if (false) { align = (screen.width
Lire un programme ou l'exécuter : quelle différence ?
Que peut-on savoir d'une fonction si elle nous est présentée : - sous forme d'un programme calculant cette fonction, - sous forme d'une boîte noire permettant de connaître les valeurs de cette fonction sur toutes les entrées. Disposer d'un programme donne au moins autant d'information qu'avoir accès ...
Page 1 / 2 »