Speaker: Alexandre Nolin
Title: Coloring a Mostly Forgotten Graph
In recent years, results known as "palette sparsification" had implications for graph coloring problems in a diversity of algorithmic models. Such results are theorems of the form: (i) for each node v, \Xi(v) be the set of colors that it is allowed to take (its "palette"); (ii) let each node v independently restrict itself to only use some random subset of its palette (this is the "sparsification"); then (iii), with high probability, the graph can still be colored with this random restriction in place. The specific results can vary in the graph family considered, the initial palettes of nodes, the size and distribution of the nodes' random subsampling, and the difficulty of finding a coloring post-"sparsification". The appeal of such results is that the random palette restriction makes some edges non-constraining: where endpoints of an edge sample disjoint sets of colors. The catch, however, is that the random restrictions are constraints in themselves that might be hard to deal with. Also, in a distributed context, edges usually act both as constraints and communication links, and one might ask whether removing the constraint created by an edge also allows to forgo the communication link. In this talk, we will explore this latter question, seeing that in fact, some graph coloring problems can be computed in some distributed settings while ignoring a large fraction of the communication links. Based on joint work with Maxime Flin, Mohsen Ghaffari, Magnú Halldóon, Fabian Kuhn, and Tigran Tonoyan.
Speaker: Meike Neunwohner
Title: A better-than-k/2-approximation for weighted k-Set Packing
The weighted k-Set Packing problem is defined as follows: As input, we are given a collection S of sets, each of cardinality at most k, and a positive weight for each set. The task is to compute a subcollection A of S such that the sets in A are pairwise disjoint, and the total weight of A is maximum. The case k=2 is equivalent to the Maximum Weight Matching problem. For k >= 3, already the special case of unit weights, the unweighted k-Set Packing problem, is NP-hard. The technique that has proven most successful in designing approximation algorithms for both the unweighted and the weighted k-Set Packing problem is local search. For the unweighted problem, the state-of-the-art is a polynomial-time (k+1)/3+epsilon-approximation by Fünd Yu that takes into account certain local improvements of up to logarithmic size. For general weights, we showed that by considering a special class of local improvements of logarithmically bounded size, we can obtain a polynomial-time (k+epsilon_k)/2-approximation, where epsilon_k converges to 0 as k approaches infinity. We further proved that this result is asymptotically best possible: For general weights, one cannot achieve a better guarantee than k/2 by only considering local improvements of logarithmically bounded size. At a first glance, this seems to conclude the story of local improvement algorithms for the weighted k-Set Packing problem. However, in this talk we show how to employ a black box algorithm for the unweighted k-Set Packing problem to generate local improvements of super-logarithmic size and obtain a polynomial-time 0.4986*k+0.5194-approximation algorithm for weighted k-Set Packing. Our techniques further allow us to establish a general connection between the approximation guarantees achievable for unit and general weights.
Speaker: Oded Lachish
Title: A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification
Speaker: Denis Antipov
Title: Better Optimization through Understanding Evolutionary Processes
Random search heuristics (RSHs) are widely used in the real-world optimization problems, since they have proved themselves to be able to find good solutions in short time, even without prior knowledge about the problem they solve. One of the most popular classes of RSHs are the evolutionary algorithms (EAs), which evolve (in a randomized manner) a population of potential solutions. The application of EAs (and RSHs in general) is often guided by some empirical experience, but when they face a new unstudied problem, the best recommendations come from the theoretical analysis of these algorithms on simple benchmark problems. Theory of EAs has started at around 30 years ago, and during these three decades it delivered many valuable results which reinforced our understanding of the evolutionary optimization. However, many of those results consider algorithms which either do not use non-trivial populations (of size more than one), or do not use crossover, while these two features are considered to be essential by practitioners. The analysis of crossover-based algorithm was considered as an extremely hard task, and some questions (which seem trivial) are open for more than 25 years. The results which appeared in the last few years, however, have gave a much more understanding about how we can describe population dynamics. In this talk we will discuss, how those results made the analysis of crossover-based algorithms much more realistic.
Speaker: Nicolas Trotignon
Title: Everything you always wanted to know about layered wheels (but were afraid to ask)
Layered wheels are different constructions, all of the same flavor, originally motivated by the study of even-hole-free graphs. They turned out to be useful to disprove several conjectures. They were first discovered by Ni Luh Dewi Sintiari and the speaker. The goal of the talk is to present them and several of their applications that we list below. - Existence of (theta, triangle)-free graphs of high treewidth. - Existence of (even hole, K4)-free graphs of high treewidth (thus replying to a question of Cameron, Chaplick, and Hoang). - Existence of graph of high tree independence number with no K_3,4 induced minor (thus replying to a question Korhonen) - Existence of classes of graphs whose treewidth is bounded by a function of their clique number and where the dependence can be arbitrarily fast growing. - Existence of classes of graphs whose treewidth is bounded by a function of their clique number while their tree-independence number is unbounded (thus disproving a conjecture of Dallard, Milanic and Storgel) - Existence of classes of graphs of unbounded treewidth in which every k-degenerate graph has bounded treewidth (thus disproving a conjecture of Hajebi). The results presented in the talk are obtained in different articles, co-authored with Maria Chudnovsky, Meike Hatzel, Tuukka Korhonen Ni Luh Dewi Sintiari and Sebastian Wiederrecht.
Speaker: Pierre Aboulker
Title: Clique number of tournaments.
The dichromatic number of a digraph is the minimum integer k such that the vertex set of D can be partitioned into k acyclic subdigraphs. It is easy to see that the chromatic number of a graph G is equivalent to the dichromatic number of the digraph obtained from G by replacing each edge with a digon (two anti-parallel arcs). Based on this simple observation, many theorems concerning the chromatic number of undirected graphs have been generalized to digraphs via the dichromatic number. However, no concept analogous to the clique number for digraphs has been available. The purpose of this presentation is to explore such a concept and its relationship with the dichromatic number, mirroring the relationship between the clique number and the chromatic number in undirected graphs. We will focus, in particular, on studying the notion of chi-boundedness.
Speaker: Hubert Chan
Title: Symmetric Splendor: Unifying Framework via Vertex-Weighted Bipartite Graphs
We present a comprehensive framework that unifies several research areas within the context of vertex-weighted bipartite graphs, providing deeper insights and improved solutions. The fundamental solution concept for each problem involves refinement, where vertex weights on one side are distributed among incident edges. The primary objective is to identify a refinement pair with specific optimality conditions that can be verified locally. This framework connects existing and new problems that are traditionally studied in different contexts. We explore three main problems: (1) density-friendly hypergraph decomposition, (2) universally closest distribution refinements problem, and (3) symmetric Fisher Market equilibrium. Our framework presents a symmetric view of density-friendly hypergraph decomposition, wherein hyperedges and nodes play symmetric roles. This symmetric decomposition serves as a tool for deriving precise characterizations of optimal solutions for other problems and enables the application of algorithms from one problem to another. The universally closest distribution refinements problem has recently been examined in the context of composing differentially oblivious mechanisms. Our framework provides a constructive proof that there exists a refinement pair that simultaneously minimizes all divergence notions satisfying the data processing inequality. A significant finding is that a specific symmetric case of Fisher market equilibrium can be analyzed using our symmetric density decomposition, offering new insights into market equilibrium. This new connection allows existing algorithms for computing or approximating the Fisher market equilibrium to be adapted for the aforementioned problems. This adaptation enables the well-known iterative proportional response process to provide approximations for the corresponding problems with multiplicative error in distributed settings, for which only absolute error has been achieved before. In conclusion, this study contributes to the understanding of various problems within a unified framework, which may serve as a foundation for bridging other problems in the future.
Speaker: Noel Arteche
Title: From Proof Complexity to Circuit Complexity via Interactive Protocols
Proving strong circuit lower bounds is the central open question in computational complexity theory, yet an even harder task seems to await: proof complexity lower bounds. Folklore in complexity theory suspects that circuit lower bounds against NC¹ or P/poly, currently out or reach, are a necessary step towards proving strong proof complexity lower bounds for systems like Frege or Extended Frege. Establishing such a connection formally, however, is already daunting, as it would imply the breakthrough separation NEXP \not \subseteq P/poly (Pich-Santhanam, 2023). We show such a connection conditionally for the Implicit Extended Frege proof system (iEF) introduced by Krajicek, , capable of formalizing most of contemporary complexity theory. In particular, we show that if iEF proves efficiently the standard derandomization assumption that a concrete Boolean function in E is worst-case hard for subexponential-size circuits, then any superpolynomial lower bound on the length of iEF proofs implies #P \not \subseteq FP/poly (which would in turn imply, for example, PSPACe \not \subseteq P/poly. Our proof exploits a conditional self-provability of circuit upper bounds via the formalization inside iEF of the sum-check protocol of Lund, Fortnow, Karloff, and Nisan. Interestingly, further improving our result seems to require progress in some of the central open questions in the theory of interactive proof systems and hardness magnification.
Speaker: Philip Wellnitz
Title: On the Communication Complexity of Approximate Pattern Matching
The decades-old Pattern Matching with Edits (PMwE) problem, given a length-n string T (the text), a length-m string P (the pattern), and a positive integer (the threshold), asks to list all substrings of T that are at edit distance at most k from P. The one-way communication complexity of PMwE is the minimum amount of space needed to encode the answer so that it can be retrieved without access to the input strings P and T. The closely related Pattern Matching with Mismatches problem (defined in terms of Hamming distance instead of the edit distance) is already well understood from the communication complexity perspective: As shown by Clifford, Kociumaka, and Porat in 2019, \Omega (n/m * k log (m/k)) bits are necessary and O(n/m * k log (m |\Sigma|/k)) bits are sufficient to not only retrieve the occurrences of P and T with at most k mismatches but also the substitutions needed to make each occurrence exact. Despite recent improvements in the running time (Charalampopoulos, Kociumaka, and Wellnitz, 2020, 2022), the communication complexity of PMwE remained under-explored, with an \Omega (n/m * k log (m/k)) lower bounds and an O(n/m k^2 \log m) upper bound. In this work, we prove an upper bound of O(n/m * k \log (m|\Sigma|)) bits, thus establishing the optimal communication complexity up to logarithmic factors. We leverage our new result on the communication complexity to obtain quantum algorithms for PMwE with an optimal query complexity of \tilde{O}(n/m \sqrt{km}) and a quantum time of \tilde{O}(n/m \sqrt{k}m+k^3.5)). Based on joint work with Tomasz Kociumaka and Jakob Nogler.
Speaker: Philip Wellnitz
Title: Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs
We investigate how efficiently a well-studied family of domination-type problems can be solved on bounded treewidth graphs. For sets \sigma, \rho of non-negative integers, a (\sigma, \rho)-set of a graph G is a set S of vertices such that |N(u) \cap S| \in \sigma for every u \in S and |N(v) \cap S| \in \rho for every v \not in S. Finding such (\sigma,\rho) sets (of a certain size unifies standard problems such as Independent Set, Dominating Set, Independent Dominating Set, and many others. Based on joint work with Jacob Focke, Dáel Marx, Fionn Mc Inerney, Daniel Neuen, Govind S. Sankar, and Philipp Schepper.
Speaker: Bernadette Charron-Bost
Title: Know your audience (Communication model and function computability in anonymous networks)
Abstract: In this talk, we present several computability results in anonymous network with varying assumptions in the degree of awareness or control that a single agent has over its outneighbors. First, we characterize the computable functions in the "blind broadcast" model, i.e., when agents have no information on their outgoing neighborhoods. Then we enrich this communication model with either output port awareness, symmetric channels, or outdegree awareness: In each case, we prove that a function can be computed if and only it is frequency-based, namely, its value only depends on the frequencies of the different input values. This characterization holds for both exact and approximate computability. If one or several nodes are distinguished as leaders, or if the cardinality of the network is known, then under any of the above three assumptions it becomes possible to compute any symmetric function. Our approach relies on the notion of graph fibration in topological graph theory, and the key to our positive result is a linear-time and finite-state distributed algorithm by Boldi and Vigna that computes the minimum base of the network. Joint work with Patrick Lambein-Monette.
Speaker: Adil Deeksha
Title: Fast Algorithms for Regression Problems
Abstract: Increasing data sizes necessitate fast and efficient algorithms for analyzing them. Regression is one such essential tool that is widely used. In this talk, I will focus on the "p- norm regression problem", which is a generalization of the standard "linear regression problem", and captures several important problems including the maximum flow problem on graphs. Historically, obtaining fast, high- accuracy algorithms for this problem has been challenging due to the lack of smoothness and strong convexity of the function, however, recent breakthroughs have been able to get around these issues. I will present an overview of how these algorithms work and discuss some generalizations of these techniques to other regression problems.
Speaker: Reza Naserasr
Title: Balanced and circular chromatic number of signed graphs
Abstract: The relation between minor theory and coloring is one of the most challenging areas of research in graph theory. In this talk we will try to develop notions that help to stablish a stronger connection between the two concept. To this end, first we review the notion of signed graphs and minor theory for signed graphs. Then we present two notions of colorings for signed graphs: I. Balanced coloring, which is the minimum number of induced balanced sets to which vertices of a signed graph can be partitioned. II. Circular coloring of signed graphs, which is about mapping of the vertices to the points of a circle satisfying certain distance conditions depending on the sign of the edge. We then present "signed Hadwiger conjecture" and show that while seemingly it is a stronger conjecture than the original Hadwiger conjecture, in fact it is equivalent to it and has strong connection to the "odd Hadwiger conjecture". This will be followed with some other results and plenty of open questions. The result are mostly from the following joint works: I. Balanced-chromatic number and Hadwiger-like conjectures. Joint work with Andrea Jimenez, Jesscia McDonald, Kathryn Nurse, and Daniel A. Quiroz. available at: https://hal.science/hal-04174372 II. Circular Chromatic Number of Signed Graphs. Joint work with Zhouningxin Wang and Xuding Zhu. available at: https://www.combinatorics.org/ojs/index.php/eljc/article/view/v28i2p44/pdf
Speaker: Panagiotis Charalampopoulos
Title: Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs
Abstract: Efficient algorithms for computing and processing additively-weighted Voronoi diagrams on planar graphs have been instrumental in obtaining several recent breakthrough results, most notably almost optimal exact distance oracles for planar graphs [C. et al., JACM'23], and subquadratic algorithms for planar diameter [Cabello TALG'19, Gawrychowski et al., SICOMP'21]. In this work, we show how Voronoi diagrams can be useful in obtaining dynamic planar graph algorithms and apply them to classical problems such as dynamic single-source shortest paths and dynamic strongly-connected components. First, we give a fully-dynamic single-source shortest paths data structure for planar weighted digraphs with Õn^{4/5}) worst-case update time and O(\log^2{n}) query time. Here, a single update can either change the graph by inserting or deleting an edge, or reset the source s of interest. All known non-trivial planarity-exploiting exact dynamic single-source shortest paths algorithms to date had polynomial query time. Further, note that a data structure with strongly sublinear update time capable of answering distance queries between all pairs of vertices in polylogarithmic time would refute the APSP conjecture [Abboud and Dahlgaard, FOCS'16]. Somewhat surprisingly, the Voronoi diagram based approach we take for single-source shortest paths can also be used in the fully dynamic strongly connected components problem. In particular, we obtain a data structure maintaining a planar digraph under edge insertions and deletions, capable of returning the identifier of the strongly-connected component of any query vertex. The worst-case update and query time bounds are the same as for our single-source distance oracle. To the best of our knowledge, this is the first fully-dynamic strong-connectivity algorithm achieving both sublinear update time and poly-logarithmic query time for an important class of digraphs. This is joint work with Adam Karczmarz from [JCSS'22].
Speaker: Romain Cosson
Title: Collective Tree Exploration: a Competitive Analysis
Abstract: 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: 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.
Speaker: Hector Buffiere
Title: Blind cop-width and balanced minors of graphs
Abstract: Like the cops and robber characterization of treewidth, new graph parameters are recently begin defined using games on graphs. We introduce the blind cops and robber game with bounded speed of the robber to tackle a conjecture of Torunczyk on flipwidth, a dense graph parameter coming from reserach on model checking in finite graphs. By introducing balanced minors (minors where each bag of the minor model is of the same size), we show that this new parameter lies between treewidth and pathwidth and generalize previously known bounds on similar games.
Speaker: Jose Zamora
Title: Lines in quasi-metric spaces
Abstract: The notion of line has been defined for different spaces. We say that a n-point space has the De Bruijn Erdos (DBE) property if the space has at least n different lines or there is a line which contains all the points. It is a classical result that Euclidean spaces have the DBE property. In finite metric spaces Chen and Chvatáconjectured that all these spaces have the DBE property. This conjecture is still open. In this talk, we will extend the notion of line to quasi-metric spaces. This means, spaces where the distance between points is not necessarily symmetric. One example of these spaces are the quasi-metric spaces induced by digraphs. We will show that some quasi-metric spaces induced by digraphs have the DBE property. We will also show an example of a quasi-metric space that does not have the DBE property.
Speaker: Nidia Acosta Obscura
Title: Improved Pattern-Avoidance Bounds for Greedy BSTs via Matrix Decomposition
Abstract: Greedy BST (or simply Greedy) is an online self-adjusting binary search tree defined in the geometric view ([Lucas, 1988; Munro, 2000; Demaine, Harmon, Iacono, Kane, Patrascu, SODA 2009). Along with Splay trees (Sleator, Tarjan 1985), Greedy is considered the most promising candidate for being dynamically optimal, i.e., starting with any initial tree, their access costs on any sequence is conjectured to be within $O(1)$ factor of the offline optimal. However, in the past four decades, the question has remained elusive even for highly restricted input. In this paper, we prove new bounds on the cost of Greedy in the ''pattern avoidance'' regime. Our new results include: The (preorder) traversal conjecture for Greedy holds up to a factor of $O(2^{\alpha(n)})$, improving upon the bound of $2^{\alpha(n)^{O(1)}}$ in (Chalermsook et al., FOCS 2015). This is the best known bound obtained by any online BSTs. We settle the postorder traversal conjecture for Greedy. The deque conjecture for Greedy holds up to a factor of $O(\alpha(n))$, improving upon the bound $O(2^{\alpha(n)})$ in (Chalermsook, et al., WADS 2015). The split conjecture holds for Greedy up to a factor of $O(2^{\alpha(n)})$. Key to all these results is to partition (based on the input structures) the execution log of Greedy into several simpler-to-analyze subsets for which classical forbidden submatrix bounds can be leveraged. This is joint work with Parinya Chalermsook, Manoj Gupta, Wanchote Jiamjitrak, Akash Pareek, and Sorrachai Yingchareonthawornchai.
Speaker: Maria Chudnovsky
Abstract: A k-block in a graph is a set of k vertices every two of which are joined by k vertex disjoint paths. By a result of Weissauer, graphs with no k-blocks admit tree-decompositions with especially useful structure. While several constructions show that it is probably very difficult to characterize induced subgraph obstructions to bounded tree width, a lot can be said about graphs with no k-blocks. On the other hand, forbidding induced subgraphs places significant restrictions on the structure of a k-block in a graphs. We will discuss this phenomenon and its consequences on the study of tree-decompositions in classes of graphs defined by forbidden induced subgraphs.
Speaker: Raul Wayne Teixeira Lopes
Title: Adaptation of the Directed Grid Theorem into an FPT algorithm
Abstract: The Grid Theorem of Robertson and Seymour [JCTB, 1986] is one of the most important tools in the field of structural graph theory, finding numerous applications in the design of algorithms for undirected graphs. An analogous version of the Grid Theorem in digraphs was conjectured by Johnson et al. [JCTB, 2001], and proved by Kawarabayashi and Kreutzer [STOC, 2015]. They showed that there is a function f(k) such that every digraph of directed tree-width at least f(k) contains a cylindrical grid of order k as a butterfly minor. Their constructive proof can be turned into an XP algorithm, with parameter k, that either constructs a decomposition of the appropriate width or finds the claimed large cylindrical grid as a butterfly minor. In this talk, we present the ideas used in our adaptation of the Directed Grid Theorem into an FPT algorithm. We provide two FPT algorithms with parameter k. The first one either produces an arboreal decomposition of width 3k-2 or finds a (k-1)-linked set in a digraph D, improving on the original result for arboreal decompositions by Johnson et al. [JCTB, 2001]. The second one uses a bramble B that naturally occurs in digraphs of large directed tree-width to find a well-linked set of order k whose vertices appear in a path hitting all elements of B. As a tool to prove these results, we show how to solve a generalized version of the problem of finding balanced separators for a set of vertices T in FPT time with parameter |T|. Joint work with Victor Campos, Ana Karolinna Maia, and Ignasi Sau.
Speaker: François Sellier
Title: Generalizing the EDCS Matching Sparsifier to Integer-Weighted b-Matchings
Abstract: We consider the maximum weight b-matching problem, assuming all weights are small integers drawn from [1,W]. We design a generalized weighted version of edge-degree constrained subgraphs (EDCS), a matching sparsifier originally developed by Bernstein and Stein that have been used for dynamic and streaming matchings in graphs. Our new subgraph has bounded vertex degrees (hence uses only a small number of edges) and can be easily computed. Moreover, it contains a (2 - 1/(2W) + epsilon) approximation of the maximum weight matching.
Speaker: Simon Mauras
Title: Truthful Matching with Online Items and Offline Agents
Abstract: We study truthful mechanisms for online maximum weight bipartite matching. In our setting, every buyer is associated with a (possibly private) desired set of items, and has a private value for being assigned an item in her desired set. Unlike most online matching settings, where agents arrive online, in our setting the items arrive online in an adversarial order while the buyers are present for the entire duration of the process. This poses a significant challenge to the design of truthful mechanisms, due to the ability of buyers to strategize over future rounds. We provide an almost full picture of the competitive ratios in different scenarios, including myopic vs. non-myopic agents, tardy vs. prompt payments, and private vs. public desired sets. Among other results, we identify the frontier for which the celebrated e/(e-1) competitive ratio of vertex-weighted online matching of Karp, Vazirani, and Vazirani extends to truthful agents and online items.
Speaker: Joakim Blikstad
Title: Breaking the quadratic barrier for matroid intersection
Abstract: Joakim Blikstad will present recent developments in matroid intersection algorithms. Matroid intersection is a fundamental combinatorial optimization problem which can model a range of problems, e.g. bipartite matching or packing spanning-trees / arborescences. We obtain faster matroid intersection algorithms by studying a specific graph reachability problem, for which we show new and simple algorithms. The exact complexity of this reachability problem, however, remains open. Combining our graph reachability algorithms with recent approximation algorithms, we manage to obtain the first subquadratic matroid intersection algorithms, thus breaking the "quadratic barrier". No background about matroid intersection is needed for the talk. The talk is mostly based on the STOC'21 paper "Breaking the Quadratic Barrier for Matroid Intersection", (https://arxiv.org/abs/2102.05548. Joint work with Jan van den Brand, Sagnik Mukhopadhyay and Danupon Nanongkai) but also on the ICALP'21 paper "Breaking O(nr) for matroid intersection" and ICALP'22 paper "Sublinear-round parallel matroid intersection".