Noticias en español
Seminars appear in decreasing order in relation to date. To find an activity of your interest just go down on the list. Normally seminars are given in English. If not, they will be marked as Spanish Only.
Chance-constrained problems and rare events: an importance sampling approach.
Abstract: We study chance-constrained problems in which the constraints involve the probability of a rare event. We discuss the relevance of such problems and show that the existing sampling-based algorithms cannot be applied directly in this case, since they require an impractical number of samples to yield reasonable solutions. Using a Sample Average Approximation (SAA) approach combined with importance sampling (IS) techniques, we show how variance can be reduced uniformly over a suitable approximation of the feasibility set, and as a...
On the metric dimension for random graphs
The metric dimension of a graph G is the minimum number of vertices in a subset S of the vertex set of G such that all other vertices are uniquely determined by their distances to the vertices in S. In this paper we investigate the metric dimension of the random graph G(n,p) for a wide range of probabilities p=p(n).
First passage percolation and escape strategies
Abstract: Consider first passage percolation on Z^d with passage times given by i.i.d. random variables with common distribution F. Let t_\pi(u,v) be the time from u to v for a path \pi and t(u,v) the minimal time among all paths from u to v. We ask whether or not there exist points x,y \in Z^d and a semi-infinite path \pi=(y_0=y,y_1,\dots) such that t_\pi(y,y_{n+1})<t(x,y_n) for all n. Necessary and sufficient conditions on F are given for this to occur. When the support of F is unbounded, we also obtain results on the number of edges...
Hard-core predicate and list decoding
Abstract A hard-core predicate P of a one-way function f is a predicate of the input of f which is not leaked by f. There are many classical results regarding hard-core predicates of the most common cryptographically useful one-way functions such as RSA, discrete exponentiation or the Rabin function. A classical result by Goldreich and Levin states that every one-way function has a hard-core predicate. At FOCS 2003, Akavia, Goldwasser and Safra gave a coding theoretic interpretation of Goldreich and Levin’s result and an elegant list...
Is there a natural graph function that distinguishe non-isomorphic graphs?
Abstract We discuss this question and suggest a possible strategy for ‘YES’. This is based partly on joint work with Martin Klazar and Iain Moffatt, and partly on joint work with Jean-Sebastien Sereni.
Models of tumor growth and therapy
Abstract: Models of tumor growth are now commonly used to predict the evolution of cancers, based on images for instance. These models serve to predict the evolution of the disease in medical treatments, to understand the biological effects that permit tumor growth and decide of the optimal therapy. A more recent subject is to explain emergence of resistance to drug and its implication in therapeutic failures. These models contain several levels of complexity, both in terms of the biological and mechanical effects, and therefore in their...
Large Induced Subgraphs Via Triangulations and CMSO
Many classical graph problems consist in finding a maximum induced subgraph with some property. We can cite the Maximum Independent Set, Maximum Induced Forest, Longest Induced Path, Maximum Induced Matching, etc. We generalize them through the following optimization problem. Let φ be a Counting Monadic Second Order Logic formula and t be an integer. Given a graph G=(V,E), the task is to find a maximum induced subgraph G[F] of treewidth at most t, that models φ. Using the theory of potential maximal cliques, we show that the general problem...
The dynamics of optimal transportation
Given a cost function and two probability measures on a compact manifold, the Monge problem is concerned with the study of minimizers of a transportation cost among transport maps between these two measures while the Kantorovitch problem is concerned with optimal transport plans. We will explain the main difference between these two optimization problems. Then we will address the uniqueness of optimal transport plans for the Kantorovitch problem. We will show that the uniqueness issue is related with the properties of some dynamics associted...
IX Escuela de Verano en Matemáticas Discretas
La Escuela se lleva a cabo del 6 al 17 de enero de 2014 en el Instituto de Sistemas Complejos de Valparaíso (ISCV)
Límites de escala para paseos aleatorios en ambientes dinámicos (spanish only)
Resumen: Consideremos la siguiente dinámica. Comenzamos con un proceso de exclusión simple simétrico unidimensional (o el sistema de partículas conservativo favorito de la audiencia). Un paseo aleatorio se mueve con la siguiente regla: el paseo salta con tasa t; escoge saltar a la derecha si el proceso de exclusión tiene una partícula en su actual ubicación, y escoge saltar a la izquierda si el proceso de exclusión no tiene una partícula en la ubicación actual del paseo aleatorio. Mandando la tasa t a 0 con una velocidad adecuada, probaremos...
