Noticias en español
Robust Revenue Maximization Under Minimal Statistical Information
Abstract: We study the problem of multi-dimensional revenue maximization when selling $m$ items to a buyer that has additive valuations for them, drawn from a (possibly correlated) prior distribution. Unlike traditional Bayesian auction design, we assume that the seller has a very restricted knowledge of this prior: they only know the mean $\mu_j$ and an upper bound $\sigma_j$ on the standard deviation of each item’s marginal distribution. Our goal is to design mechanisms that achieve good revenue against an ideal optimal auction that has full knowledge of the distribution in advance....
Read MoreOn the Cycle Augmentation Problem: Hardness and Approximation Algorithms.
Abstract: In the k-Connectivity Augmentation Problem we are given a k-edge-connected graph and a set of additional edges called links. Our goal is to find a set of links of minimum cardinality whose addition to the graph makes it (k+1)-edge-connected. There is an approximation preserving reduction from the mentioned problem to the case k=1 (a.k.a. the Tree Augmentation Problem or TAP) or k=2 (a.k.a. the Cactus Augmentation Problem or CacAP). While several better-than-2 approximation algorithms are known for TAP, nothing better is known for CacAP (hence for k-Connectivity Augmentation in...
Read MoreREPLICATOR DYNAMICS: OLD AND NEW
Abstract: We introduce the unilateral version associated to the replicator dynamics and describe its connection to on-line learning procedures, in particular tomultiplicative weight algorithm. We show the interest of handling simultaneously discrete and continuous time analysis. We then survey recent results on extensions of this dynamics: regularization function and variable weights. This includes no regret algorithms, time average and link to best reply dynamics in two person games, application to equilibria and variational inequalities, convergence properties in potential and dissipative...
Read MoreConvex hierarchies, scheduling and symmetries
Abstract: The Sum of Squares (SoS) hierarchy provides a finite nested family K_1, K_2, … , K_n of convex relaxations for an integer program with n variables, that reaches the integer hull, i.e., K_n corresponds to the convex hull of the integer feasible solution. A natural question is to understand how the integrality gap evolves over the family. In particular, a rapid decay of the gap might yield good approximation algorithms. We show that for the classic problem of scheduling identical machines to minimize the makespan, the SoS hierarchy exhibits an integrality gap curve that remains at...
Read MoreComplexity of point-to-planar convex set distance
Abstract: In computer science, there are several equivalent ways to define a com- putable compact set in $\R^k$. One of them is the so called “locally com- putable compact set”, that is, being able to decide whether or not a given ball intersects the set – this is often referred to as the “pixel information” of the set because, loosely speaking, it allows us to know which pixels must be coloured when drawing a picture of the set on a screen. It is not hard to see that from the pixel information of a set one can compute the distance to a given point, but the computational cost of doing so may...
Read MoreOn Distributed Merlin-Arthur Decision Protocols
Abstract: In a distributed locally-checkable proof, we are interested in checking the legality of a given network configuration with respect to some Boolean predicate. To do so, the network enlists the help of a prover — a computationally-unbounded oracle that aims at convincing the network that its state is legal, by providing the nodes with certificates that form a distributed proof of legality. The nodes then verify the proof by examining their certificate, their local neighborhood and the certificates of their neighbors. In this talk we examine the power of a randomized form of...
Read More