Week 14.10.2024 – 20.10.2024

In the balanced allocation problem we wish to allocate m balls (jobs) into n bins (servers) by allowing each ball to choose from some bins sampled uniformly at random. The goal is to maintain a small gap between the maximum load and average load.

For the one-choice protocol, where each ball is allocated to a random bin, the gap diverges for large m. However, for the two-choice protocol, where each ball samples two bins and is placed in the least loaded of the two, it was shown that gap is only O(log log n) for all m. This dramatic improvement is widely known as ``power of two choices’’, and similar effects have been observed in hashing and routing.

In this talk, we will first give some intuition why two-choice maintains such a good balance in theory and practice. Then we will present our results in settings where the load information is incomplete or subject to some noise.

This is based on joint works with Dimitrios Los and John Sylvester.

In this talk, we will discuss a novel result establishing that risk-constrained functional optimization problems with general integrable nonconvex instantaneous reward/constraint functions exhibit strong duality, regardless of nonconvexity.

We consider risk constraints featuring convex and positively homogeneous risk measures admitting dual representations with bounded risk envelopes, generalizing expectations. Popular risk measures supported within our setting include the conditional value-at-risk (CVaR), the mean-absolute deviation (MAD, including the non-monotone case), certain distributionally robust representations and more generally all real-valued coherent risk measures on the space L1. We highlight the usefulness of our results by further discussing various generalizations of our base model, extensions for risk measures supported on $L_p$ (>1), implications in the context of mean-risk tradeoff models, as well as more specific applications in wireless systems resource allocation, and supervised constrained learning.

Our core proof technique appears to be new and relies on
risk conjugate duality in tandem with J. J. Uhl’s weak extension of A. A. Lyapunov’s convexity theorem for vector measures taking values in general infinite-dimensional Banach spaces.

The talk will start from the elementary fact that positive rational numbers can be expanded as finite continued fractions with positive integer coefficients. The positive integer coefficients have combinatorial interpretations in the sense that ‘’they count something’’. I will present combinatorial interpretations based on the Farey graph. Introducing a formal parameter q, I will then make a deformations of the objects and refine the countings. This will bring notions of q-rationals, q-continued fractions, q-SL(2,Z). I will explain the constructions and give the main properties of all these q-analogs. Finally, I will connect this theory to the Burau representation of the braid group B3, and give a partial answer to the question of faithfulness of the complex specialisations of this representation.

By introducing progressively finer perturbations to a spectral problem in a controlled manner — an example of a procedure known as homogenisation — one hopes to uncover properties of the problem by exhibiting it as the limit of a family of other ones. In this work, we employ this strategy to show that the spectrum of a Schrödinger eigenvalue problem posed on a Riemannian manifold M can be approached by that of a family of Robin eigenvalue problems posed on domains in M with many small perforations.
As an application, we identify the range of Sobolev spaces in whose dual we have a flexibility result for optimal Schrödinger potentials, in which a sequence of potentials which come close to optimising some eigenvalue may nevertheless remain bounded away from an optimiser.