Noticias en español
Aggregating opinions — do we need (Kolmogorov) complexity?
Abstract: Imagine a group of people that need each day to make some collective decision (for the entire group), choosing one of two options A and B. Some people prefer A, some prefer B, and others are OK with any of the two options. (The next day the preferences may change arbitrarily, and a new group choice is made.) The group management needs to choose A or B, in both cases making some people unhappy. This cannot be avoided completely (if someone wants A and someone else wants B, one of them will be unhappy), so the goal is more modest: each person should not be unhappy too many times....
Read MoreTariff Zone Assignment: Complexity Results ans Solution Approaches.
Abstract: In the Tariff Zone Assignment problem, an operator is tasked with partitioning a transport network (i.e., a graph) into tariff zones in order to maximize revenue under a linear pricing model. In this model, customers pay a price proportional to the number of zones traveled through, up to some maximum accepted price. If this price gets exceeded, customers drop out of the model and thus generate no revenue at all. In this talk, first we will look at the complexity of this problem and show APX-hardness on star graphs and strong NP-hardness on paths. These complexity results motivate...
Read MoreOracle-Augmented Prophet Inequalities.
Abstract: In the top-1-of-k prophet inequality setting, a gambler is given a sequence of n random variables X_1, …, X_n, taken from known distributions, observes their values in an adversarial order, and selects up to k of them, immediately after they are observed, so that the top value selected is as high as possible, comparing against a prophet who always selects the maximum realization. For k = 1, one recovers the classical prophet inequality, and thus this model serves as a generalization. In this talk, we look at a new approach to solve the top-1-of-k model. We generalize the...
Read MoreAbstract: In this talk, I will give an introduction to linear programming hierarchies, with a particular focus on the hierarchy by Sherali & Adams. I will discuss some limitations of the tool, but also ways to get useful and stronger relaxations.
Read MoreThe Limitations of Machine Learning & Us.
Abstract: Machine learning (ML), particularly deep learning, is being used everywhere. However, not always is used well, ethically and scientifically. In this talk we first do a deep dive in the limitations of supervised ML and data, its key component. We cover small data, datification, bias, predictive optimization issues, evaluating success instead of harm, and pseudoscience, among other problems. The second part is about our own limitations using ML, including different types of human incompetence: cognitive biases, unethical applications, no administrative competence, copyright...
Read MoreOnline learning with consistency oracle.
Abstract: A binary classification game is being played between a learner and an adversary. At each round, the adversary selects a natural number x and the learner has to predict its label h(x). Is there a bound on the number of mistakes made by the learner, assuming that h comes from some class H? Littlestone gave a learning algorithm which achieves an optimal mistake bound d, provided H has a certain combinatorial property. However, Littlestone’s algorithm is believed to be computationally demanding. Can we have a feasible strategy for the learner and if so, how many mistakes would...
Read More