Abstract for "Breaking the Barrier of 2 for Approximating Weighted Throughput Maximization via the Sherali-Adams Hierarchy": We study the Weighted (Non-Preemptive) Throughput Maximization problem which is a natural and fundamental problem in scheduling. Given a set of jobs with release times, deadlines, processing times, and weights, our goal is to schedule a subset of them non-preemptively on a given machine, in order to maximize the total weight of the selected jobs. The best known results for the problem are a polynomial time (2+ε)-approximation algorithm and a pseudo-polynomial time 2-approximation. These ratios (essentially) match the integrality gap of the natural LP-relaxation of the problem. These approximation factors are the best known results even for quasi-polynomial running time. We break the barrier of 2 for Weighted Throughput Maximization and improve this approximation ratio substantially: We present a (4/3+ε)-approximation algorithm for it with quasi-polynomial running time. We obtain this ratio also in the more general setting of an arbitrary number of (identical) machines.

Abstract for "An O(log log n)-Approximation Algorithm for Submodular Unsplittable Flow on a Path": Unsplittable Flow on a Path (UFP) is a well-studied problem in which we are given a path with edge capacities and a set of tasks, where each task is characterized by a subpath and a demand. The goal is to select a subset of the input tasks such that on each edge e the total demand of the selected tasks using e is bounded by the capacity of e. In the setting of a linear objective function, a long line of research finally culminated in a PTAS. However, there are natural variations and generalizations of UFP that are not captured by this. For example, each task could have a time window during which we can schedule it flexibly, due to fairness considerations we might be able to select only a bounded number of tasks from certain subsets of tasks, or each task might serve a subset of some given customers and we want to maximize the total number of customers we serve. All these settings are captured by the submodular UFP problem in which we are given the same input as in UFP but we want to maximize a given submodular function that we assume to be non-negative and monotone. The best known approximation algorithm for submodular UFP is an O(log n)-approximation. Even for the much simpler special case of bag UFP, where the tasks are partitioned into bags and we can select at most one task per bag, the best known approximation factor is only O(log n/ log log n). We present a polynomial time O(log log n)- approximation algorithm for submodular UFP. Our result directly yields O(log log n)-approximation algorithms for several special cases, for example bag UFP and UFP with a linear objective function but with an additional matroid constraint (matroid UFP). We believe that our new ideas might be useful also for future work in the area of submodular optimization.

We study models for multivariate time series evolving on networks with latent group structure under two complementary network-density regimes. When the network is sparse, we focus on the Grouped Network Vector Autoregression (GNAR) model, capturing dynamics through group-specific transition coefficients. We consider joint estimation of the unobserved network, group memberships, and coefficients. When the network is dense, the GNAR model is akin to a weak factor model with group-specific loadings. We develop a likelihood-based framework for loadings estimation in this setting, covering both known and latent group structures, as well as suitable PCA-based alternatives. This is joint work with Changryong Baek and Vladas Pipiras.

Interacting systems where particles duplicate and mutate are ubiquitous in many application domains, including biological modeling, evolutionary optimization, and multimodal sampling. In the talk, we review the paradigmatic example of the replicator-mutator particle system and show its convergence towards a PDE with a source term and a diffusive term. The central, novel tool is a Wasserstein distance with bounded ground cost, resembling the Wasserstein-Fisher-Rao distance.

tbd

Unlike finite-state Markov chains, interacting particle systems on infinite graphs may admit multiple stationary measures, and even convergence to one of these is not guaranteed. One particular obstruction is the existence of time-periodic orbits, where the system returns to its initial distribution after a fixed period without being stationary, thereby spontaneously breaking the continuous time-translation symmetry. The conditions under which such noisy systems can maintain sufficient spatial order to sustain such time-periodic behaviour have been a contentious issue in the physics literature and a mathematical treatment of such broken-symmetry, macroscopically time-dependent states has been mostly limited to mean-field like approximations.

In this talk, we present some recent progress on two questions: (a) in which spatial dimensions d is such time-periodic behaviour possible? (b) What quantitative properties, such as the rate of decay of truncated correlations, can we infer from the existence of a time-periodic orbit?

tbd

TBA

Estimating the distribution of a d-dimensional random variable (i.e., a d-dimensional probability measure) from data is a fundamental instance of the curse of dimensionality. In this talk, we explore whether structural knowledge about the data-generating process which gives rise to the distribution can help overcome this curse. More precisely, we work with the set of distributions of probabilistic graphical models for a known directed acyclic graph. We establish that this knowledge is only helpful if it holds in a suitably quantitative way, which is formalized via smoothness conditions on the stochastic kernels in the disintegration according to the graph. We provide explicit estimators which can leverage the graphical structure, and we measure the estimation error in Wasserstein distance. We show that the rate of estimation becomes faster the fewer edges are in the graph and is sharp in many cases. The results are compared to existing works focusing on knowledge of smooth densities instead of graphical structures. Very briefly, we will also give an outlook on the relation to LLM pretraining.