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: Many statistical tasks are accomplished using range counting queries. In modern-day data analysis, datasets are often represented as high-dimensional vector spaces, necessitating approximation to ensure computationally feasible range counting. Even when query answers are approximate, such analysis comes with privacy risks. These may be mitigated using local differential privacy (LDP), a variant of differential privacy in which noise is added directly to user inputs, allowing for analysis without requiring a trusted central third party. Differentially private range counting specifically for the high-dimensional setting is a relatively recent area of research, particularly so in the distributed model.

In this paper, we propose the LocalTop-1 data structure for the Approximate Near Neighbor Counting (ANNC) problem under (ε, δ)-LDP, a modification of the recently presented Top-1 data structure by Aumüller et al. (FORC 2025). At construction time, LocalTop-1 takes an LDP mechanism which it uses to encode user data before aggregating the encodings in the data structure. Based on extreme order and concomitant statistics theory, we present a simple framework for estimating the accuracy of ANNC query answers when LocalTop-1 is used with some LDP encoding mechanism, and we provide a number of tools for bounding the sensitivity of such mechanisms when the LDP privacy guarantee is restricted to data points which are similar enough to lie within some user-specified “protection radius”. Using these tools, we design a proof-of-concept mechanism for use with LocalTop-1. Numerical evaluation suggests that for limited choices of parameters, this mechanism provides improved accuracy when compared to a baseline.

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: