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".