ITU Seminar on Algorithms and Complexity 

Abstract:

Abstract:

Abstract: Geometric graphs play a central role in computational geometry, graph algorithms, and applications ranging from network design to geometric data analysis. While worst-case models often fail to capture the structure observed in practice, several realistic models have been proposed in recent years to bridge this gap. In this work, we concentrate on two prominent models: c-packed graphs and λ-low-density graphs. For both models, we survey and present recent algorithmic advances for constructing fundamental tools, including separators, well-separated pair decompositions, single-source shortest path algorithms, and distance oracles. 

Abstract:

Abstract: We will consider a new style of optimization, where instead of returning one solution to an optimization problem, the goal is to return k>1 many solutions that are as diverse as possible. After a brief survey of existing results on this topic on fundamental graph objects such as spanning trees, matchings, etc., I will describe some recent work that focuses on geometric objects such as triangulations and maximum independent sets in planar graphs. This style of optimization is relatively recent, and the hope is for the audience to discover other interesting problems whose applications would benefit from computing diverse solutions. 

Abstract:

Abstract:  Valiant's Holant theorem is a powerful tool for algorithms and reductions for counting problems. It states that if two sets F and G of tensors (a.k.a. signatures) are related by a holographic transformation, then F and G are Holant-indistinguishable, i.e., every tensor network using tensors from F, resp. from G,  contracts to the same value. Xia (ICALP 2010) conjectured the converse of the Holant theorem, but a counterexample was found based on vanishing signatures, those which are Holant-indistinguishable from 0. 

We prove two near-converses of the Holant theorem using techniques from invariant theory. (I) Holant-indistinguishable F and G always admit two sequences of holographic transformations mapping them arbitrarily close to each other, i.e., their GL_q-orbit closures intersect. (II) We show that vanishing signatures are the only true obstacle to a converse of the Holant theorem. As corollaries of the two theorems we obtain the first characterization of homomorphism-indistinguishability over graphs of bounded degree, a long standing open problem, and show that two graphs with invertible adjacency matrices are isomorphic if and only if they are homomorphism-indistinguishable over graphs with maximum degree at most three.

Abstract:

Abstract: Many recent works have studied how analogue models work, compared to classical digital ones. By “analogue” models of computation, we mean computing over continuous quantities, while “digital” models work on discrete structures. It led to a broader use of Ordinary Differential Equation (ODE) in computability theory. From this point of view, the field of implicit complexity has also been widely studied and developed.

We show here, using arguments from computable analysis, that we can algebraically characterise PTIME and PSPACE for functions over the reals. Also, we will see how we can relate polynomial space with the reachability in dynamical systems and tilings.

Abstract:

Abstract:

Abstract:

Abstract:

Abstract:

Abstract:

Abstract: In this work we revisit the elementary scheduling problem 1|| \sum p_j U_j. The goal is to select, among n jobs with processing times and due dates, a subset of jobs with maximum total processing time that can be scheduled in sequence without violating their due dates. This problem is NP-hard, but a classical algorithm by Lawler and Moore from the 60s solves this problem in pseudo-polynomial time O(nP), where P is the total processing time of all jobs. With the aim to develop best-possible pseudo-polynomial-time algorithms, a recent wave of results has improved Lawler and Moore's algorithm for 1||\sum p_j U_j: First to time \tilde O(P^{7/4}) [Bringmann, Fischer, Hermelin, Shabtay, Wellnitz; ICALP'20], then to time \tilde O(P^{5/3}) [Klein, Polak, Rohwedder; SODA'23], and finally to time \tilde O(P^{7/5}) [Schieber, Sitaraman; WADS'23]. It remained an exciting open question whether these works can be improved further.

In this work we develop an algorithm in near-linear time \tilde\O(P) for the 1||\sum p_j U_j problem. This running time not only significantly improves upon the previous results, but also matches conditional lower bounds based on the Strong Exponential Time Hypothesis or the Set Cover Hypothesis and is therefore likely optimal (up to subpolynomial factors). Our new algorithm also extends to the case of m machines in time \tilde\Order(P^m). In contrast to the previous improvements, we take a different, more direct approach inspired by the recent reductions from Modular Subset Sum to dynamic string problems. We thereby arrive at a satisfyingly simple algorithm.

Abstract: