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: While geometric spanners have been researched for decades, directed versions have only been considered more recently. This is surprising since, in many applications, edges may be directed or even oriented if two-way connections are not permitted. Oriented spanners were first introduced in ESA'23. Since then, a variety of problems have been considered in the setting of oriented spanners.

This talk gives an overview of the results on oriented spanners gained in the last three years. We will take a closer look on the first algorithm that computes a sparse oriented spanner whose oriented dilation is bounded by a constant (SoCG'25).

Abstract:

Abstract: The diameter of a polytope is a fundamental geometric parameter that plays a crucial role in understanding the efficiency of the simplex method. Despite its central nature, the computational complexity of computing the diameter of a given polytope is poorly understood. Already in 1994, Frieze and Teng [Comp. Compl.] recognized the possibility that this task could potentially be harder than NP-hard, and asked whether the corresponding decision problem is complete for the second stage of the polynomial hierarchy, i.e. \Pi^p_2-complete. In the following years, partial results could be obtained. In a cornerstone result, Frieze and Teng themselves proved weak NP-hardness for a family of custom defined polytopes. Sanità [FOCS18] in a break-through result proved that already for the much simpler fractional matching polytope the problem is strongly NP-hard. Very recently, Steiner and Nöbel [SODA25] generalized this result to the even simpler bipartite perfect matching polytope and the circuit diameter. In this work, we finally show that computing the diameter of the bipartite perfect matching polytope is \Pi^p_2-hard. Since the corresponding decision problem is also trivially contained in \Pi^p_2, this decidedly answers Frieze and Teng's 30 year old question. 

Abstract: Valiant's conjecture from 1979 asserts that the circuit complexity classes VP and VNP are distinct meaning that the permanent does not admit polynomial-size algebraic circuits. As it is the case in many branches of complexity theory, the unconditional separation of these complexity classes seems elusive. In stark contrast, the symmetric analogue of Valiant's conjecture has been proven by Dawar and Wilsenach (2020): the permanent does not admit symmetric algebraic circuits of polynomial size, while the determinant does. Symmetric algebraic circuits are both a powerful computational model and amenable to proving unconditional lower bounds.

In this paper, we develop a symmetric algebraic complexity theory by introducing symmetric analogues of the complexity classes VP, VBP, and VF called symVP, symVBP, and symVF. They comprise polynomials that admit symmetric algebraic circuits, skew circuits, and formulas, respectively, of polynomial orbit size. Having defined these classes, we show unconditionally that

symVF⊊symVBP⊊symVP.

To that end, we characterise the polynomials in symVFsymVF and symVBPsymVBP as those that can be written as linear combinations of homomorphism polynomials for patterns of bounded treedepth and pathwidth, respectively. This extends a previous characterisation by Dawar, Pago, and Seppelt (2025) of symVPsymVP. The separation follows via model-theoretic techniques and the theory of homomorphism indistinguishability.

Although symVBP and symVP admit strong lower bounds, we are able to show that these complexity classes are rather powerful: They contain homomorphism polynomials which are VBP- and VP-complete, respectively. Vastly generalising previous results, we give general graph-theoretic criteria for homomorphism polynomials and their linear combinations to be VBP-, VP-, or VNP-complete. These conditional lower bounds drastically enlarge the realm of natural polynomials known to be complete for VNPVNP, VPVP, or VBPVBP. Under the assumption VFPT≠VW[1], we precisely identify the homomorphism polynomials that lie in VP as those whose patterns have bounded treewidth and thereby resolve an open problem posed by Saurabh (2016).

Joint work with Prateek Dwivedi (ITU) and Benedikt Pago (U Cambridge).

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: