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.
Machine Covering in the Random-Order Model.
Abstract: In the Online Machine Covering problem, jobs, defined by their sizes, arrive one by one and have to be assigned to m parallel and identical machines, with the goal of maximizing the load of the least-loaded machine. Unfortunately, the classical model allows only fairly pessimistic performance guarantees: The best possible deterministic ratio of m is achieved by the Greedy-strategy, and the best known randomized algorithm has competitive ratio Õ(m^(1/2)), which cannot be improved by more than a logarithmic factor. In this talk, we...
Variable polynomials and joint ergodicity for functions of polynomial growth.
RESUMEN: The ergodic theoretical proof of Szemerédi’s theorem on arithmetic progressions by Furstenberg, in 1977, led to a thorough study of multiple ergodic averages; which in turn gave numerous far-reaching extensions of Szemerédi’s result. More specifically, we have polynomial (Bergelson-Leibman, 1996) and Hardy field (Frantzikinakis-Wierdl, 2009, Frantzikinakis, 2015) extensions of the latter. In general, if the multiple average under consideration has the “expected limit”, then one obtains, via Furstenberg’s Correspondence Principle,...
Uso de modelos basados en imágenes Landsat para planificar el consumo de agua de coberturas vegetales.
RESUMEN: Desde aproximadamente inicio de los 2000, se han desarrollado una serie de modelos basados en imágenes de satélite y datos meteorológicos, que permiten calcular los flujos de vapor de agua desde la superficie de la Tierra hasta la capa baja de la atmósfera. Estos modelos, se han enfocado principalmente hacia fines académicos, presentando resultados interesantes para aplicarlos en la estimación del consumo de agua de una serie de coberturas vegetales, como cultivos, frutales y viñas. La ventaja del uso de estos modelos con respecto a...
Augmenting Online Algorithms with ε-Accurate Predictions.
Abstract: The growing body of work in learning-augmented online algorithms studies how online algorithms can be improved when given access to ML predictions about the future. Motivated by ML models that give a confidence parameter for their predictions, we study online algorithms with predictions that are $\epsilon$-accurate: namely, each prediction is correct with probability (at least) $\epsilon$, but can be arbitrarily inaccurate with the remaining probability. We show that even with predictions that are accurate with a small probability...
Differentially Private Stationary Points in Stochastic Nonconvex Optimization.
Abstract: Differentially private (DP) stochastic nonconvex optimization (SNCO) is a fundamental problem, where the goal is to approximate stationary points (i.e points with small norm of the gradient) of the population loss, given a dataset of i.i.d. samples from a distribution, while satisfying differential privacy with respect to the dataset. Most of the existing works in the literature have addressed either the convex version of this problem (DP-SCO) or the closely related problem of Private Non-Convex Empirical Risk Minimization, where...
A nonlocal isoperimetric problem: density perimeter.
Abstract: We will discuss a variant of a classical geometric minimization problem, known as the “nonlocal isoperimetric problem”, which arises from studies in Nuclear Physics by Gamow in the 1930’s. By introducing a density in the perimeter functional, we obtain features that differ substantially from existing results in the framework of the classical problem without densities. In the regime of “small” non-local contribution, we completely characterize the minimizer, in the case the density is a monomial radial weight.
Computing buyer-optimal Walrasian prices in multi-unit matching markets via a sequence of max flow computations.
Abstract: Given a market where discrete indivisible items of different types are sold to a set of buyers. There is a given supply of each type and each buyer has a given (maximum) demand. Each buyer valuates the items linearly in our setting. We aim for competitive prices, i.e. prices such that an allocation exists where every buyer gets one of his preferred bundles. The prices should be as small as possible and as much as possible should be sold. We show how to compute these buyer-optimal Walrasian prices. We present an ascending auction...
The AGM Bound.
Abstract: In several computer science applications one encounters the following problem: Given two edge-labeled graphs G and H, how many homomorphic images of H can be found in G? Atserias, Grohe, and Marx developed a tight bound for this number, denoted #Hom(H,G), which is now known as the AGM bound. The bound relates #Hom(H,G) with the fractional edge covers of H in a very elegant and direct way. We will present a self-contained and simple proof of this result using Shearer’s inequality.
