The well-known k-disjoint paths problem involves finding pairwise vertex-disjoint paths between k specified pairs of vertices within a given graph if they exist. In the shortest k-disjoint paths problem one looks for such paths of minimum total length. Despite nearly 50 years of active research on the k-disjoint paths problem, many open problems and complexity gaps still persist. A particularly well-defined scenario, inspired by VLSI design, focuses on infinite rectangular grids where the terminals are placed at arbitrary grid points. While the decision problem in this context remains NP-hard, no prior research has provided any positive results for the optimization version. The main result of this paper is a fixed-parameter tractable (FPT) algorithm for this scenario. It is important to stress that this is the first result achieving the FPT complexity of the shortest disjoint paths problem in any, even very restricted classes of graphs where we do not put any restriction on the placements of the terminals.
We study the capacitated vehicle routing problem in graphic metrics (graphic CVRP). Our main contribution is a new lower bound on the cost of an optimal solution. For graphic metrics, this lower bound is tight and significantly stronger than the well-known bound for general metrics. The proof of the new lower bound is simple and combinatorial. Using this lower bound, we analyze the approximation ratio of the classical iterated tour partitioning algorithm combined with the TSP algorithms for graphic metrics of Christofides [1976], of Mömke-Svensson [JACM 2016], and of Sebő-Vygen [Combinatorica 2014]. In particular, we obtain a 1.95-approximation for the graphic CVRP. This is joint work with Tobias Mömke.
We consider the problem of minimizing the discrepancy of a set system, which is an important problem in combinatorics that has recently witnessed a lot of progress, mostly stemming from the Theoretical Computer Science community.
In this talk I will present an elementary proof of Spencer's celebrated theorem, based on LP duality and a simple incompressibility argument. This parallels and simplifies the convex geometric approach of [Eldan-Singh '14], and is roughly inspired from recent work on matrix discrepancy [Hopkins, Raghavendra, Shetty '21].
Time permitting, I will also discuss some ideas for using these techniques to attack a series of exciting open problems in the field.
As a staple of data analysis and unsupervised learning, the problem of private k-means clustering has been widely studied, under various privacy models.
My goal in this talk is to give an introduction to this area of research: I will introduce the notion of differential privacy, one of the most popular model for privacy.
Then, I will give an overview of the different algorithm for solving k-means, under this differential privacy constraint: in particular, I will try to show how a 20 years-old greedy algorithm can be slightly modified to work privately, and can be easily extended to several variants of Differential Privacy. In (very) short, this algorithm reduces k-means clustering to compute simple histograms.
I will conclude with some related open questions.
The problem of airports and railways is a combination of capacitated facility location and network design problems, where we are given a complete graph G = (V, E) with weights on the vertices a : V → R+, lengths of the edges l : E → R+, and a positive integer k as the capacity parameter. The goal is to compute a spanning forest R of G and a subset A ⊆ V of minimum cost such that each connected component in R has one open facility and the number of cities in each component is at most k (the capacity constraint). The cost of the solution (A, R) is measured as \sum_{v \in A}a(v) + \sum_{e \in E(R)}l(e). In the unsplittable demand version of the problem (ARUD), additionally, we are given a function b : V → R+ that defines a non-zero demand for each city and the goal is to find a network of trees with minimum cost such that the total demand in each component is at most k. In this talk, we will discuss different versions of the problem (when the problem is defined on different networks), bi-factor approximation algorithms for the metric AR and ARUD problems which violate the capacity constraints by O(k), and complexity results of the problem.
Matroid intersection is a classical optimization problem where, given two matroids over the same ground set, the goal is to find the largest common independent set. In this paper, we show that there exists a certain ``sparsifer'': a subset of elements, of size $O(|S^{opt}| \cdot 1/\varepsilon)$, where $S^{opt}$ denotes the optimal solution, that is guaranteed to contain a $3/2 + \varepsilon$ approximation, while guaranteeing certain robustness properties. We call such a small subset a \emph{Density Constrained Subset} (DCS), which is inspired by the \emph{Edge-Degree Constrained Subgraph} (EDCS) [Bernstein and Stein, 2015], originally designed for the maximum cardinality matching problem in a graph. Our proof is constructive and hinges on a greedy decomposition of matroids, which we call the \emph{density-based decomposition}. We show that this sparsifier has certain robustness properties that can be used in one-way communication and random-order streaming models.
In Collective Tree Exploration, a team of k mobile agents, initially located at the root of a tree must go through all of its edges by traversing one edge at each time step. The problem is online in the sense that the agents do not know the tree structure initially — instead the team discovers the existence of an edge only when it is reached by an agent. The runtime of an exploration algorithm is typically compared to OPT, the optimal offline runtime that can be achieved when the agents know the tree in advance. Fraigniaud, Gasieniec, Kowalski and Pelc defined the problem in 2004 and provided an online algorithm with competitive ratio of order k/log(k). Due to the limited progress on this quantity (upper or lower-bounds), Brass, Mora, Gasparri and Xiao proposed in 2014 a different type of competitive analysis; with a runtime of the form OPT + O(D^k), where D is the tree depth and D^k is called the competitive overhead. In this talk, I will present recent improvements to the competitive overhead analysis, which in turn lead to an improved competitive ratio for collective tree exploration.
In on-line TSP, a sequence of initially unknown requests arrive over time at points (locations) of a metric space. The goal is, starting from a particular point of the metric space, to serve all these requests while minimizing the total time spent. The server moves with unit speed or is "waiting" (zero speed) at some location. In this talk we consider the problem where the locations of requests are initially known, while their release dates are not. The goal is to find competitive algorithms with the best possible ratio, in the general case as in specific metric spaces (like lines, trees,...). We will also tackle the case where the locations are not precisely known (predictions) and study how the competitive ratios evolve with these possible errors in the predictions of locations.
In this talk, we consider the k-Covering Canadian Traveller Problem (k-CCTP), which can be seen as a variant of the Travelling Salesperson Problem. The goal of k-CCTP is finding the shortest tour for a traveller to visit a set of locations in a given graph and return to the origin. Crucially, unknown to the traveller, up to k edges of the graph are blocked and the traveller only discovers blocked edges online at one of their respective endpoints. The previously best known competitive ratio for k-CCTP was O(\sqrt{k}) [Huang and Liao, ISAAC '12]. We improve this polynomial bound to a logarithmic one by demonstrating a connection with the Online Graph Exploration Problem.
Graph compression or sparsification is a fundamental question in information theory and computer science. Given a graph with a special set of vertices called terminals, we ask if it is possible to find a smaller graph, named sparsifier, which preserves some property of the graph with respect to the terminals.
A major open problem in this area is to find small sparsifiers which preserve cuts between sets of terminals, that is, sparsifiers in which the minimum cut separating any two sets of terminals is the same as in the original graph.
In this talk, we look at sparsifiers for the closely related setting of c-connectivity. For a fixed value of c, a c-connectivity sparsifier preserves the number of edge-disjoint paths between any two sets of terminals, unless the number of such paths is at least c in both the original graph and the sparsifier.
We show that c-connectivity sparsifiers with O(kc^4) edges exist, where k is the number of terminals, and describe two algorithms for this problem: the first algorithm finds a sparsifier with O(kc^4) edges in time O(m(c \log n)^O(c)), while the second finds a slightly worse sparsifier with k O(c)^2c edges, in time O(m c^O(c) log^O(1) n).
Our results lead to new data structures for dynamic c-connectivity problems, as well as more efficient algorithms for network design problems.
Let H a graph class and k be a positive integer. The Vertex Deletion problem asks, given a graph G, whether it is possible to remove k vertices from so that the remaining graph belong to H. We propose an algorithm running in time 2^{poly(k)}.n² to solve this problem when H is a minor-closed graph class, improving the previous best running time of 2^{poly(k)}.n³ [ICALP 2020]. Additionally, we provide various algorithmic results concerning another modification problem, namely Elimination Distance to H, which asks for the minimum number of rounds required to reduce each connected component of G to a graph in H by removing one vertex from each connected component in each round.
Find a feasible set of items of smallest total weight. Item weights belong to given intervals. The weight of inclusion of a given item e, is the largest weight for e, such that e belongs to every optimal solution. The weight of exclusion of a given item e, is the smallest weight for e, such that e does not belong to any optimal solution. We study the complexity of this problem for some combinatorial optimization problems.
Over the last year, foundation models have taken an important role in modern machine learning research and beyond. Training and using these models has led to new fundamental question. I'll review some of the recent work on this: From model compression, to data selection, via efficient querying, basic tasks around foundation models can be cast as optimization problems. What can the TCS community say about these new problems?
How does the brain learn concepts that are based on other concepts? How does the brain recognizes a girl with a mandolin in the Picasso painting with the same name? In this talk we’ll explore how hierarchically-structured data can be represented, learned, and recognized in feed-forward layered Spiking Neural Networks. Specifically, we provide formal definitions for concept hierarchies and layered neural networks.
The celebrated model of auctions with interdependent valuations, introduced by Milgrom and Weber in 1982, has been studied almost exclusively under private signals $s_1, ... , s_n$ of the $n$ bidders and public valuation functions $v_i(s_1, ... , s_n)$.
Recent work in computer science has shown that this setting admits a constant approximation to the optimal social welfare if the valuations satisfy a natural property called submodularity over signals (SOS). More recently, Eden et al. (2022) have extended the analysis of interdependent valuations to include settings with private signals and private valuations, and established $O(log^2 n)$-approximation for SOS valuations.
In this paper we show that this setting admits a constant factor approximation, which is (asymptotically) tight, even for settings with private signals and public valuations.
Michel de Rougemont: DISTRIBUTED TESTING
Distribution Testing is the problem of testing if a probability distribution satisfies some property such as uniformity, independence, identity, when we can sample the distribution.
A frequency distribution in a stream of data is the monotone distribution which gives the most frequent items among the $n$ distinct objects of the stream of length $m$. We ask if we can test if a frequency distribution is close to a predefined distribution such as a power law for example, in O(poly(log n)) space. We show it is not possible for the uniform distribution, but possible for a decreasing distribution and the relative Frechet distance between distributions.
In-context learning is a relatively widely studied phenomenon in recent years, where LLMs can seemingly work well on tasks that they were not trained on, just based on the context given to them. This can be viewed as a meta-learning phenomenon where these models are learning learning algorithms. We will discuss a stylised setting that will allow us to understand to what extent these models are actually learning new function using in-context information. We also discuss how the performance of these models can be improved using curated in-context data. While the talk will mostly discuss experimental results, we will point to open theory questions that arise.
Based on joint work with Satwik Bhattamishra, Arkil Patel and Phil Blunsom.