Seminars 2016


Author: Luis Rademacher, UC Davis.

Where: CMM, Beauchef 851, Torre Norte, Sala Seminario von Neumann 7mo piso.

When: Wednesday, December 28, 14:30.

Title: Provably efficient high dimensional feature extraction

The goal of inference is to extract information from data. A basic building block in high dimensional inference is feature extraction, that is, to compute functionals of given data that represent it in a way that highlights some underlying structure. For example, Principal Component Analysis is an algorithm that finds a basis to represent data that highlights the property of data being close to a low-dimensional subspace. A fundamental challenge in high dimensional inference is the design of algorithms that are provably efficient and accurate as the dimension grows. In this context, I will describe two well-established feature extraction techniques: column subset selection (CSS) and independent component analysis (ICA). I will also present work by my coauthors and myself on CSS with optimal approximation guarantees, new applications of ICA and ICA for heavy-tailed distributions.


Author: Cristobal Guzman, PUC.

Where: DII, Av. República 701, Sala 33.

When: Wednesday, December 21, 14:30.

Title: Statistical Query Algorithms for Stochastic Convex Optimization

Statistical query (SQ) algorithms are the class of learning algorithms that can be implemented using approximate expectations of any given function of the input distribution, as opposed to direct access to i.i.d. samples. This computational model has a number of applications, ranging from noise-tolerant learning to differential privacy, and it has been used to obtain unconditional lower bounds on conjectured hard problems over distributions.

In this talk I will give an introduction to the theory of SQ algorithms, and we will see some recent developments in the case of stochastic convex optimization. Our main contribution is establishing nearly optimal SQ algorithms for mean vector estimation (this includes stochastic linear programming), which serves as a basis to obtain SQ versions of various gradient-type and polynomial time algorithms for stochastic convex optimization. Time permitting, I will show some consequences of our results for learning of halfspaces, differential privacy, and proving unconditional lower bounds on the power of convex relaxations for random constraint satisfaction problems.

This talk is based on joint work with Vitaly Feldman and Santosh Vempala, to appear in SODA 2017.


Author: Fábio Botler, U Chile.

Where: DII, Av. República 701, Sala 33.

When: Wednesday, December 07, 14:30.

Title: Decomposing 8-regular graphs into paths of length 4

A T-decomposition of a graph G is a set of edge-disjoint copies of T in G that cover the edge set of G. Graham and Häggkvist (1989) conjectured that any 2\ell-regular graph G admits a T-decomposition if T is a tree with \ell edges. Kouider and Lonc (1999) conjectured that, in the special case where T is the path with \ell edges, G admits a T-decomposition D where every vertex of G is the end-vertex of exactly two paths of D, and proved that this statement holds when G has girth at least (\ell + 3)/2. In this talk we verify Kouider and Lonc’s Conjecture (and, consequently, Graham-Häggkvist’s Conjecture) for paths of length 4.


Author: Monaldo Mastrolilli, IDSIA.

Where: DII, Av. República 701, Sala 33.

When: Wednesday, November 30, 14:30.

Title: High degree Sum of Squares proofs/hierarchy for 0/1 problems

The Lasserre/Sum-of-Squares (SOS) hierarchy is a systematic procedure for constructing a sequence of increasingly tight semidefinite relaxations. It is known that the hierarchy converges to the 0/1 polytope in n levels and captures the convex relaxations used in the best available approximation algorithms for a wide variety of optimization problems.
In this talk I will give a gentle introduction of the SOS framework for 0/1 problems from a more general point of view.
I will point it out that this more general definition is needed for certain class of problems e removes some of the weakness of the standard SOS approach.


Author: Vianney Perchet, ENS Cachan.

Where: DII, Av. República 701, Sala 33.

When: Wednesday, November 23, 14:30.

Title: Bandits in Auctions. New perspectives in sequential learning

Multi-armed bandit is a standard tool on sequential learning to optimize sequences of decisions when the outcomes of non-chosen decisions are unavailable. The first, traditional application was random clinical trial. Recently, they gained a lot of interest because of all the possible applications coming from internet, such as product recommendations, ads displays, etc. The objectives were simple: give the best treatment to as many patients as possible, or recommend/display the product with the highest probability of being clicks. However, the objectives have changed radically recently and, for instance, all those processes start nowadays by a phase of repeated auctions.

In this talk, I will introduce the classical theory of multi-armed bandits, a field at the junction of statistics, optimization, game theory and machine learning, discuss the possible applications, and highlights the new perspectives and open questions that they propose.


Author: Bruno Ziliotto, Paris Dauphine University (CNRS).

Where: DII, Av. República 701, Sala 33.

When: Wednesday, November 16, 14:30.

Title: Limit value in zero-sum stochastic games

We consider a model of repeated game involving two adversary players, and where the state of nature is imperfectly observed. An old conjecture by Mertens (1986) predicted that in this model, when the game is repeated over and over, the optimal payoff of players should converge. We provide a counterexample to this conjecture.
No game theory prerequisite of any kind is needed to understand the talk.


Author: Victor Verdugo, École Normale Supérieure and U Chile.

Where: DII, Av. República 701, Sala 33.

When: Wednesday, November 9, 14:30.

Title: How large is your graph?

The estimation of graph properties such as the size, average degree and the
conductance received ample attention during the past decade. However, much
of this work is in the more applied literature, without precise definitions
of the model of query access to the graph. The focus of this work is on
one of the most fundamental properties, the number of nodes. We formally
define a query model involving (not necessarily random) walks on the graph.
In this model, an algorithm has information about a \emph{seed} node and
then can make queries about neighbours of nodes it has already seen. In the
case of undirected graphs, an estimator of Katzir et al. (2014) based on a
sample from the stationary distribution $\pi$ uses
$O\left(\frac{1}{\twonorm{\pi}} + \davg\right)$ queries; we show that this
is essentially tight.
This is joint work with Varun Kanade (Oxford) and Frederik Malmann-Trenn (ENS-SFU).


Author: Lin Chen, Hungarian Academy of Science.

Where: DII, Av. República 701, Sala 33.

When: Wednesday, November 2, 14:30.

Title: N-fold integer programming and scheduling

Abstract: N-fold integer programming is shown to admit an $O(n^3)$ FPT time algorithm by Hemmecke, Onn and Romanchuck (Math. Programming 2013). Very recently, it is observed by Knop and Koutecky (arxiv:1603.02611v1, 2016) that it has a close relationship with the scheduling problem. Indeed, they show that $R||Cmax$ and $R||sum w_jC_j$ could be formulated as an n-fold integer programming, whereas an FPT time algorithm follows by choosing proper parameters. It also implies an 2^{O(1/\epsilon^2)}+O(n^3) time EPTAS for P||Cmax without using configuration ILP.

In this talk, I will talk about the basic idea of the FPT time algorithm for n-fold integer programming and its relationship with scheduling. I will then talk about one of my recent work (with Daniel Marx), which extends n-fold integer programming to a more general form. Using this general form, we derive FPT algorithms for routing on a tree.


Author: Raimundo Briceño, Tel Aviv U.

Where: DII, Av. República 701, Sala 33.

When: Wednesday, October 26, 14:30.

Title: Strong spatial mixing in homomorphism spaces

Abstract: Over the last few decades, spatial mixing properties in spin systems have been of interest because of their many applications. The property known as weak spatial mixing (WSM) is related with uniqueness of Gibbs measures on countable graphs and the absence of phase transitions. On the other hand, strong spatial mixing (SSM), which is a strengthening of WSM, has been connected with the existence of efficient approximation algorithms for thermodynamic quantities, FPTAS for counting problems which are #P-hard, and mixing time of the Glauber dynamics in some particular systems.

Given a countable graph G and a finite graph H, we consider Hom(G,H) the set of graph homomorphisms from G to H and we study Gibbs measures supported on Hom(G,H). We develop some sufficient and other necessary conditions on Hom(G,H) for the existence of Gibbs specifications satisfying SSM. We relate this with previous work of G. Brightwell and P. Winkler, who showed that a graph H has a combinatorial property called dismantlability if and only if for every G of bounded degree, there exists a Gibbs specification with unique Gibbs measure. We strengthen their result by showing that this unique Gibbs measure can be chosen to have WSM, but we also show that there exist dismantlable graphs for which no Gibbs measure has SSM. Time permitting, we also show how to use these results to generalize the sequential cavity method developed by D. Gamarnik and D. Katz for free energy approximation in lattice systems.

Most of this talk is joint work with Ronnie Pavlov.


Author: Miguel Dumett, U Utah.

Where: DII, Av. República 701, Sala 33.

When: Wednesday, October 18, 14:30.

Title: Orbitas Periodicas Estables en el Ciclo del Hierro Biotico de la Pirita

Abstract: En este trabajo, se construye un sistema de ecuaciones diferenciales que modela el del ciclo del hierro de la pirita catalizado por la bacteria Acidithiobacilus ferrooxidans. Las velocidades de reacción y la dinámica de crecimiento poblacional de la bacteria se toman de las literaturas de ingeniería química y de microbiologia. Utilizando técnicas de Sistemas Dinámicos se determina la estabilidad de los puntos de equilibrio del sistema y se observa la aparición de un parámetro de bifurcación. Se estudia también la estabilidad de las órbitas periódicas que surgen cerca de los valores de bifurcación. Este es un trabajo conjunto con James Keener del Departamento de Matematicas de la Universidad de Utah. Posibles nuevos caminos en este trabajo se discuten al final de la exposición.


Author: Qiaoxi Zhang, U Chile.

Where: DII, Av. República 701, Sala 33.

When: Wednesday, October 05, 14:30.

Title: Vagueness in multidimensional proposals

Abstract: I study how the option of being vague shapes proposals in a delegation environment. Two agents compete for a decision maker (DM)’s approval to implement a multidimensional action. Based on their knowledge of the consequences of actions, agents propose their future actions but can be vague about any dimension. The DM, uncertain about the consequences of actions, chooses one of the agents to act. All players are known for their most desired consequences. It is shown that vagueness on the dimension on which one stands closer to the DM than his opponent (i.e. one’s advantageous dimension) preserves such an advantage, while preciseness on one’s advantageous dimension undermines it. Vagueness therefore tends to occur on agents’ advantageous dimensions.


Author: Jannik Matuschke, TU Munich.

Where: DII, Av. República 701, Sala 33.

When:  Wednesday, September 28, 14:30.

Title: Minimizing Congestion in Virtual Private Ring Networks.

Abstract:  Given a network with a set of n terminals we want to setup a virtual private network (VPN) that allows communication between the terminals. For any two terminals, we have to decide on a route via which the two terminals communicate with each other. Our goal is to minimize the congestion of the resulting VPN, i.e., the worst-case load any link can receive in any possible communication profile between the terminals (a communication profile is a fractional matching on the terminals specifying how much data is transmitted between each pair).

We observe that for the case of ring networks, this problem is equivalent to bounding the size of a maximum matching in a sequence of graphs arising from iteratively inverting the incidence vectors of the terminals. We show how to construct a routing template of congestion n/3 by partitioning the terminals into three groups, and prove that this solution is optimal. We conjecture that a similar partitioning technique yields an optimal solution in the case that links have distinct capacities. However, if we allow the terminals to have distinct data demands, the problem becomes NP-hard.

This is joint work with Neil Olver and Kristóf Bérczi.


Author: Pablo Pérez-Lantero, USACH.

Where: DII, Av. República 701, Sala 33.

When:  Wednesday, September 21, 14:30.

Title: The intersection graph of the disks with diameters the sides of a convex n-gon.

Abstract:  Given a convex polygon of n sides, one can draw n disks (called side disks) where each disk has a different side of the polygon as diameter and the midpoint of the side as its center. The intersection graph of such disks is the undirected graph with vertices the n disks and two disks are adjacent if and only if they have a point in common. We prove that for every convex polygon this graph is planar. Particularly, for n=5, this shows that for any convex pentagon there are two disks among the five side disks that do not intersect, which means that K_5 is never the intersection graph of such five disks. For n=6, we then have that for any convex hexagon the intersection graph of the side disks does not contain K_3,3 as subgraph.


Author: Andreas Wiese, DII and CMM.

Where: DII, Av. República 701, Sala 33.

When:  Wednesday, September 7, 14:30.

Title: Independent set of convex polygons: from n^eps to 1+eps via shrinking

Abstract:  In the Independent Set of Convex Polygons problem we are given a set of weighted convex polygons in the plane and we want to compute a maximum weight subset of non-overlapping polygons. This is a very natural and well-studied problem with applications in many different areas. Unfortunately, there is a very large gap between the known upper and lower bounds for this problem. The best polynomial time algorithm we know has an approximation ratio of n^epsilon and the best known lower bound shows only strong NP-hardness.
In this paper we close this gap completely, assuming that we are allowed to shrink the polygons a little bit, by a factor 1-delta for an arbitrarily small constant delta>0, while the compared optimal solution cannot do this (resource augmentation). In this setting, we improve the approximation ratio from n^epsilon to 1+epsilon which matches the above lower bound that still holds if we can shrink the polygons.


Author: Andreas Wierz, RWTH Aachen.

Where: DII, Av. República 701, Sala 33.

When:  Wednesday, August 24, 14:30.

Title: A General Model for Capacitated Covering Problem

Abstract: In this talk we will consider covering integer programs, which are of the form min{ cx | Ax >= D, x >= 0, x integral}, where A is a non-negative matrix, c is a non-negative cost function and D is a demand vector. There is a wide range of combinatorial optimization problems which can be modeled in this form. These include, for example, easy problems like Matroids or the shortest path problem, but also harder problems like set cover or knapsack-cover. For some covering problems, a very simple primal-dual greedy algorithm yields optimum or good approximate solutions. For example, matroids can be solved to optimality by such methods and for knapsack-cover there is a 2-approximation.

Usually, the analysis of such approximation algorithms is very problem specific. Even if two problems are similar and admit the same approximation factor using the same greedy algorithm, an adapted proof is required. We are interested in properties of the constraint system $Ax \geq D$ which imply that a simple primal-dual greedy algorithm yields good approximate solutions to the underlying covering program. We will discuss some positive results and limits of this approach.

This is joint work with Britta Peis and José Verschae.


Author: Taísa Martins, Warwick U.

Where: DII, Av. República 701, Sala 33.

When:  Wednesday, August 17, 14:30.

Title: Graph Limits – Finite Forcibility and Computability

Abstract:  The theory of graph limits provide analytic tools to analyse large graphs. Large dense graphs can be represented by an analytic object called graphon. Because of its close relation to extremal combinatorics, finitely forcible graphons, i.e. graphons that are defined uniquely by finitely many subgraph densities, have been an object of intensive study. Lovasz and Szegedy conjectured that all finitely forcible graphons have simple structure in several different meanings, which is now known to be false. Here, we present a general way of constructing finitely forcible graphons with non-trivial properties, which unifies and generalizes earlier results. This is a joint work with Jacob Cooper and Dan Kral.


Author: Neil Olver, VU Amsterdam.

Where: DII, Av. República 701, Sala 33.

When:  Wednesday, August 10, 14:30.

Title: A faster and simpler strongly polynomial algorithm for generalized flow maximization

Abstract:  The maximum generalized flow problem, a classical generalization of maximum flow where flow is scaled as it traverses each arc, has been intensively studied for the past few decades. Only recently did Végh obtain a strongly polynomial time algorithm for it. We give a new strongly polynomial algorithm that is both substantially faster and dramatically simpler than the algorithm of Végh. It is in many cases slightly faster than even the best weakly polynomial algorithm due to Radzik. We also demonstrate an important application of our result to the classical net present value problem in project scheduling.

(Joint work with J. Correa, A. Schulz and L. Végh.)


Author: Daniel Espinoza, Gurobi.

Where: DII, Av. República 701, Sala 21.

When:  Wednesday, June 15, 14:30.

Title: Desigualdades subadditivas y separacion

Abstract:  En 1971 Gomory y Johnson encontraron una descripcion (casi) completa de las facetas que describen la envoltura convexa de

P = {x,y >=0, x entero : ax + cy = b}

Las desigualdades MIR, y de Gomory pueden entenderse en este marco. En esta charla explicare la teoria basica, y varios problemas abiertos, centrandome en los temas de separacion, asi como explicar su relevancia.


Author: Hiep Han, PUCV.

Where: DII, Av. República 701, Sala 21.

When:  Wednesday, June 08, 14:30.

Title: Sharp threshold of the van der Waerden property

Abstract:  In recent years one popular line of research in extremal and probabilistic combinatorics concerns problems that arise when one takes a notable combinatorial theorem and tries to prove that the same theorem holds in a sparse random subset of the ground set.

Consider [n]_p, the random subset of the first n integers obtained by picking each element with probability p independently. As a random version of van der Waerden’s theorem Rödl and Ruciński showed that if p>>n^{-1/(k-1)} then, with probability tending to 1 as n tends to infinity, every 2-coloring of [n]_p yields a monochromatic arithmetic progression of length k\geq 3, whereas the conclusion fails if p<<n^{-1/(k-1)}.
With Friedgut, Person, and Schacht we improve this result in the setting of Z/nZ and show that the change in the behavior already occurs within a multiplicative constant of (1+o(1)), hence establishing a sharp threshold for the van der Waerden property.

The talk will be introductory with emphasis on the tools, most notably the Friedgut-Bourgain criterion for coarse threshold and the container theorem for independent sets in hypergraphs.


Author: Ivan Rapaport, DIM, U Chile.

Where: DII, Av. República 701, Sala 21.

When:  Wednesday, June 01, 14:30.

Title: Distributed Testing of Excluded Subgraphs

Abstract:  We study property testing in the context of distributed computing, under the classical CONGEST model. It is known that testing whether a graph is triangle-free can be done in a constant number of rounds, where the constant depends on how far the input graph is from being triangle-free. We show that, for every connected 4-node graph H , testing whether a graph is H -free can be done in a constant number of rounds too. The constant also depends on how far the input graph is from being H -free, and the dependence is identical to the one in the case of testing triangles. Hence, in particular, testing whether a graph is K4 -free, and testing whether a graph is C4 -free can be done in a constant number of rounds (where Kk denotes the k -node clique, and Ck denotes the k -node cycle). On the other hand, we show that testing Kk -freeness and Ck -freeness for k \geq 5 appear to be much harder. Specically, we investigate two natural types of generic algorithms for testing H -freeness, called DFS tester and BFS tester. The latter captures the previously known algorithm to test the presence of triangles, while the former captures our generic algorithm to test the presence of a 4-node graph pattern H . We prove that both DFS and BFS testers fail to test Kk -freeness and Ck -freeness in a constant number of rounds for k \geq 5.


Author: Pedro Montealegre, Univ. Orléans.

Where: DII, Av. República 701, Sala 21.

When:  Wednesday, May 18, 14:30.

Title: Deterministic graph connectivity in the broadcast congested clique

Abstract:  In this talk, I will present a deterministic constant-round protocol for the graph connectivity problem in the model where each of the n nodes of a graph receives a row of the adjacency matrix, and broadcasts a single sublinear size message to all other nodes. Communication rounds are synchronous. This model is sometimes called the broadcast congested clique. Specifically, we exhibit a deterministic protocol that computes the connected components of the input graph in three rounds, each player communicating O(√n · log n) bits per round. The result is based on a d-pruning protocol, which consists in successively removing nodes of degree at most d until obtaining a graph with minimum degree larger than d.


Author: Richard Lang, DIM, U Chile.

Where: DII, Av. República 701, Sala 21.

When:  Wednesday, May 11, 14:30.

Title: Chromatic index, treewidth and maximum degree

Abstract:  We conjecture that any graph G with treewidth k and
maximum degree \Delta(G) >= k + \sqrt{k} satisfies
\chi’(G)=\Delta(G). In support of the conjecture we prove its
fractional version.

This is joint work with Henning Bruhn and Laura Gellert


Author: Jeremy Barbay, DCC, U Chile.

Where: DII, Av. República 701, Sala 33.

When:  Wednesday, May 04, 14:30.

Title: Selenite Towers move faster than Hanoi Towers, but still require exponential time

Abstract:  The Hanoi Tower problem is a classic exercise in recursive programming: the solution has a simple recursive definition, and its complexity and the matching lower bound correspond to the solution of a simple recursive function (the solution is so simple that most students memorize it and regurgitate it at exams without truly understanding it). We describe how some minor change in the rules of the Hanoi Tower yields various increases of difficulty in the solution, so that to require a deeper mastery of recursion than the classical Hanoi Tower problem. In particular, we analyze the Selenite Tower problem, where just changing the insertion and extraction positions from the top to the middle of the tower results in a surprising increase in the intricacy of the solution: such a tower of n disks can be optimally moved in a sqrt(3)^n moves for n even (i.e. less than a Hanoi Tower of same height), via five recursive functions following three distinct patterns.


Author: Bastián Bahamondes, DIM, U Chile.

Where: DII, Av. República 701, Sala 33.

When:  Wednesday, April 27, 14:30.

Title: A fare evasion model with non-independent inspection probabilities.

Abstract: A fare evader wants to travel without paying the ticket between two nodes s and t in a network represented by a directed graph. In one edge, there is an inspector controlling fare evasion, whose location is known by the evader just to the extent of a probability distribution on the edges (inspection probabilities). The evader chooses a path from s to t, and if it contains the edge where the inspector is located at, he must pay a fine and then continues his journey through a shortest path from the next node to t. Given the inspection probabilities, the travel times on the edges and the value of the fine, the evader attemps to choose a path from s to t of minimum expected cost. The complexity of this problem is currently open. In this talk, we devise pseudopolynomial algorithms both in acyclic and general graphs, as well as a FPTAS for general graphs.

This is joint work with José Correa and Jannik Matuschke.


Author: Tim Oosterwijk, Maastricht U, The Netherlands.

Where: DII, Av. República 701, Sala 33.

When:  Wednesday, April 20, 14:30.

Title: A Logarithmic Approximation for Polymatroid Congestion Games

Abstract: We study the problem of computing a social optimum (minimum cost solution) in polymatroid congestion games, where the strategy space of every player consists of the set of vectors in a player-specific integral polymatroid base polyhedron defined on the ground set of resources. For general non-decreasing cost functions we devise an H_{rk}-approximation algorithm, where rk is the sum of the ranks of the player-specific polymatroids and H_{rk} denotes the rk-th harmonic number. The main idea of our algorithm is to iteratively increase resource utilization in a greedy fashion and to invoke a polynomial covering oracle that checks feasibility of every computed resource utilization. The approximation guarantee is best possible up to a constant factor. As a special case, our result (partially) settles an open problem of Ackermann et al., where the complexity of computing a socially optimal solution for matroid congestion games with non-decreasing cost functions is considered. Here, the approximation guarantee is best possible up to a constant factor if the number of resources is polynomially bounded in the number of players.

In this talk I will shortly introduce the basis of congestion games and matroids, which generalize e.g. spanning trees. After introducing matroid congestion games (which is a special case of the polymatroid congestion games mentioned above), I will present the ideas and results, and mention some open research directions.


Author: Alain Jean-Marie, Inria, Montpellier, France.

Where: DII, Av. República 701, Sala 33.

When:  Wednesday, April 13, 14:30.

Title: Well-balanced designs for unreliable data placement

Abstract: The problem of replicating and placing data on distributed servers, can be modeled using Combinatorial Designs. The blocks of these designs are set of servers on which
a given document is replicated. When servers are unreliable, a metric of interest is
the number of available documents, for which at least one copy is accessible.
The average value of this random variable does not depend on the placement, but
the variance does. We therefore introduce the problem of minimizing this variance.
We define the family of “well balanced” designs and show that they are a solution to
this problem. The construction of well balanced designs for blocks of size 2 and 3 is
closed. But the construction of solutions for larger blocks is still open.


Author: Mabel Tidball, INRA.

Where: DII, Av. República 701, Sala 33.

When:  Wednesday, April 6, 14:30.

Title: Does environmental connotation affect coordination issues in an
experimental stag hunt game?

Abstract: We introduce illustration identifying environmental degradation or
improvement into a 2×2 coordination game with two Pareto-ranked equilibria.
Theoretical and experimental investigations do not give a clear cut about
coordination in this kind of game. Results show that environmental
connotation has an influence in terms of strategy choice, and that positive
or negative nature of the environmental connotation positively or
negatively affects the frequency of players’ choices. Our analysis suggests
that environmental negative signals impact more on players’ behaviour than
positive signals. Incentives based on sensitization campaigns for
environmental issues can be a valid alternative to economic instruments for
environmental management.

This is joint work with:
D. Dubois, CNRS, UMR5474 LAMETA, F-34000 Montpellier, France.
S. Farolfi, CIRAD, UMR 183 G EAU, F-34000 Montpellier, France.
M. Tidball, INRA, UMR 1135 LAMETA, F-34000 Montpellier, France.
M. Désolé, Montpellier SupAgro, UMR 1135 LAMETA, F-34000 Montpellier, France.
A. Hofstetter, INRA, UMR 1135 LAMETA, F-34000 Montpellier, France.


Author: Jeremy Barbay, DCC, U Chile.

Where: DII, Av. República 701, Sala 33.

When:  Wednesday, March 30, 14:30.

Title: Optimal Prefix Free Codes with Partial Sorting

Abstract: We describe an algorithm computing an optimal prefix free code for $n$ unsorted positive weights in time within $O(n(1+\lg \alpha))\subseteq O(n\lg n)$, where the alternation $\alpha\in[1..n-1]$ measures the amount of sorting required by the computation. This asymptotical complexity is within a constant factor of the optimal in the algebraic decision tree computational model, in the worst case over all instances of size $n$ and alternation $\alpha$. Such results refine the state of the art complexity of $\Theta(n\lg n)$ in the worst case over instances of size $n$ in the same computational model, a landmark in compression and coding since 1952, by the mere combination of van Leeuwen’s algorithm to compute optimal prefix free codes from sorted weights (known since 1976), with Deferred Data Structures to partially sort a multiset depending on the queries on it (known since 1988).


Author: Julie Meissner, TU Berlin.

Where: Av República 779 B, 2nd floor.

When:  Wednesday, March 23, 14:30.

Title: Computing an MST under Uncertainty

Abstract: We study a network design model where uncertain data is given in the form of intervals and exact data can be explored at a certain cost. The goal is to find the optimal network minimizing the exploration cost. We will discuss lower bounds as well as a randomized algorithm for the minimum spanning tree problem under uncertainty.

This is joint work with Nicole Megow and Martin Skutella.


Author: Pierre Fraigniaud,  Institut de Recherche en Informatique Fondamentale, CNRS.

Where: Sala 33, DII, Av República 701 .

When:  Wednesday, March 16, 14:30.

Title: Fault-Tolerant Decentralized Runtime Monitoring

Abstract: Runtime verification  is aiming at extracting information from a running system, and using it to detect and possibly react to  behaviors violating a given correctness property. Decentralized runtime verification involves a set of monitors observing the behavior of  the underlying system. In this talk, the investigation of decentralized runtime verification in which not only the elements of the observed system, but also the monitors themselves are subject to failures will be presented. In this context, it is unavoidable that the unreliable monitors may have different views of the underlying system, and therefore may have different valuations of the correctness property. We characterize the number of valuations required for monitoring a given correctness property in a decentralized manner. Our lower bound is independent of the logic used for specifying the correctness property, as well as of the way the set of valuations returned by the monitors is globally interpreted. Moreover, our lower bound is tight in the sense that we design a distributed protocol enabling any given set of monitors to verify any given correctness property using as many different valuations as the one given by this lower bound.

Joint work with: Sergio Rajsbaum (UNAM, Mexico) and Corentin Travers (LaBRI, Bordeaux)

Author: Srinivasa Rao Satti,  Seoul National University.

Where: Auditorio Ramon Picarte, Piso 3, Beauchef 851, Edificio Norte.

When:  Wednesday, March 9, 14:30.

Title: Space-efficient encodings for various range queries.

Abstract: An encoding of a given data with respect to a set of queries is any data structure that stores enough information about the data in order to support the queries, without having access to the input data at query time. A classic example is a 2n-bit encoding of an integer array of size n that supports range minimum queries — a range minimum query (RMQ) asks for a position of the smallest element in the given query range.
This result on RMQ encoding has been extended in two ways – (i) by supporting leftmost, rightmost and median positions among the minimum values in the query range, using ~2.54n bits, and (ii) by supporting both range minimum and range maximum queries, using 3n bits.
In this talk, first I will present further extensions of these results by describing encodings that support a wide range of queries (range queries mentioned above, and some related queries). Then I will describe some encodings of two-dimensional integer arrays that support range top-k queries – given a 4-sided range, a range top-k query returns the positions of the k largest elements in the query range.


Author: Itai Ashlagi, Stanford U.

Where: Sala 33 DII.

When:  Wednesday, January 13, 14:30.

Title: Communication Complexity in Stable Matching Algorithms.