ITU Seminar on Algorithms and Complexity 

Abstract: -

Abstract: -

Abstract: Finite variable logics play a central role in finite model theory, serving as a foundational framework for analyzing the complexity of finite structures. A combinatorial perspective characterizes equivalence in these logics via homomorphism indistinguishability: for certain graph classes, two graphs agree on all homomorphism counts from the class if and only if they satisfy the same sentences in a corresponding logic. This viewpoint often reveals connections between structural properties of graph classes and the expressive power of logical fragments. We extend this perspective to logics with restricted requantification, thereby refining the stratification of syntactic resources in finite variable counting logics. By parameterizing the number of requantifiable variables, we obtain distinct logical fragments and investigate their interaction with homomorphism counts and computational complexity. 

Abstract: -

Abstract: -

Abstract: Recently, a natural variant of the Art Gallery problem, known as the Contiguous Art Gallery problem, was proposed. Given a simple polygon $P$, the goal is to partition its boundary $\partial P$ into the smallest number of contiguous segments such that each segment is completely visible from some point in~$P$ (the guard). Unlike the classical Art Gallery problem, which is NP-hard, this variant is polynomial-time solvable. 

At SoCG 2025, three independent works presented algorithms for this problem, each achieving a running time of $O(k n^5 \log n)$ (or $O(n^6\log n)$), where $k$ is the size of an optimal solution. Interestingly, these results were obtained using entirely different approaches, yet all led to roughly the same asymptotic complexity, suggesting that such a running time might be inherent to the problem.

We show that this is not the case. We present an $O(n \log n)$-time algorithm, achieving an $O(k n^4)$ factor speed-up over the previous state-of-the-art. We also give a straightforward lower bound reduction from the set intersection problem. We thus show that the Contiguous Art Gallery problem is in $\Theta(n \log n)$.

Abstract: The Exact matching problem is an infamous problem for which we know a randomized poly-time algorithm since 1987, but finding a deterministic counterpart has evaded the research community for almost 40 years. Formally stated, we are given a bipartite graph, whose edges are 0-1 weighted, and some number k. The question is if there exists a perfect matching of weight exactly equal to k. In this talk, I will highlight some of my own research, which achieves deterministic (combinatorial) algorithms for special restricted graph classes, or deterministic approximations. I also highlight interesting open questions, that may be easier to achieve than tackling the full problem. 

Abstract: -

Abstract: -

Abstract: A central question in algebraic complexity theory is understanding the behaviour of polynomial computation models under basic algebraic operations. While closure under addition and multiplication holds for most of the standard models like algebraic circuits, closure under factorisation remains subtle. In this talk, we will discuss a new result which proves that the well-studied model called read-once oblivious algebraic branching programs (ROABPs) is not closed under factoring. This result offers a contrasting perspective to recent breakthrough work that gave a unified framework for proving closure under factorisation in other regimes. We will also discuss similar non-closure properties of ROABPs under other natural operations such as powering and symmetric composition.

This is based on joint work with Andrews, Armand, Hansen, Limaye, Srinivasan, and Tavenas. [paper]

Abstract: -

Abstract: For some geometric graph classes, tractability of testing first-order formulas is precisely characterised by the graph parameter twin-width. This was first proved for interval graphs among others in [BCKKLT, IPEC '22], where the equivalence is called delineation, and more generally holds for circle graphs, rooted directed path graphs, and H-graphs when H is a forest. Delineation is based on the key idea that geometric graphs often admit natural vertex orderings, allowing to use the very rich theory of twin-width for ordered graphs.

Answering two questions raised in their work, we prove that delineation holds for intersection graphs of non-degenerate axis-parallel unit segment graphs, but fails for visibility graphs of 1.5D terrains. We also prove delineation for intersection graphs of circular arcs.

Abstract: Surprisingly, the question of bounding the maximum number of operations undergone by each individual element in an algorithm -- known as the fragile complexity of the algorithm -- has not received much attention. In a foundational paper, Afshani et al. (2019) developed the concept of fragility and explored classic problems such as sorting and selection from this perspective. Motivated by a suggestion for future research by Afshani et al., we initiate a study of fragile complexity in computational geometry. We obtain bounds on several time-honored questions in 2D such as computing the maxima, closest pair, convex hull, triangulation, and approximate Euclidean Minimum Spanning Tree (apx-EMST).

Abstract: -

Abstract: -

Abstract: -

Abstract: Learned indexes are a class of index data structures that enable fast search by approximating the cumulative distribution function (CDF) using machine learning models (Kraska et al., SIGMOD'18). However, recent studies have shown that learned indexes are vulnerable to poisoning attacks, where injecting a small number of poison keys into the training data can significantly degrade model accuracy and reduce index performance (Kornaropoulos et al., SIGMOD'22). In this work, we provide a rigorous theoretical analysis of poisoning attacks targeting linear regression models over CDFs, one of the most basic regression models and a core component in many learned indexes. Our main contributions are as follows: (i) We present a theoretical proof characterizing the optimal single-point poisoning attack and show that the existing method yields the optimal attack. (ii) We show that in multi-point attacks, the existing greedy approach is not always optimal, and we rigorously derive the key properties that an optimal attack should satisfy. (iii) We propose a method to compute an upper bound of the multi-point poisoning attack's impact and empirically demonstrate that the loss under the greedy approach is often close to this bound. Our study deepens the theoretical understanding of attack strategies against linear regression models on CDFs and provides a foundation for the theoretical evaluation of attacks and defenses on learned indexes.

Abstract: How should a principal design incentives when the effort of agents is costly and unobservable? Contract theory studies this question through performance-based payments. In many modern environments, however, the challenge is also computational: the space of possible actions or teams can be enormous, and finding the right contract becomes an algorithmic problem. This perspective has led to the emerging area of algorithmic contract design.

In this talk I will discuss recent progress on combinatorial contracts, where complexity arises from the many possible ways actions can be combined. Such settings naturally appear when a single agent can undertake multiple tasks or when several agents must coordinate their efforts. I will present several models capturing these scenarios and highlight the algorithmic and complexity questions they raise. The results reveal a rich landscape that includes polynomial-time algorithms under structured reward functions, approximation guarantees in more general settings, and hardness barriers. Overall, these results illustrate how tools from algorithms and economic theory interact in the study of incentives, and point to a range of open problems at the frontier of algorithmic contract design.

Abstract: Given a set of strings over a specified alphabet, identifying a median or consensus string that minimizes the total distance to all input strings is a fundamental data aggregation problem. When the Hamming distance is considered as the underlying metric, this problem has extensive applications, ranging from bioinformatics to pattern recognition. However, modern applications often require the generation of multiple (near-)optimal yet diverse median strings to enhance flexibility and robustness in decision-making.

In this study, we address this need by focusing on two prominent diversity measures: sum dispersion and min dispersion. We first introduce an exact algorithm for the diameter variant of the problem, which identifies pairs of near-optimal medians that are maximally diverse. Subsequently, we propose a (1 − ε)-approximation algorithm (for any ε > 0) for sum dispersion, as well as a bi-criteria approximation algorithm for the more challenging min dispersion case, allowing the generation of multiple (more than two) diverse near-optimal Hamming medians. Our approach primarily leverages structural insights into the Hamming median space and also draws on techniques from error-correcting code construction to establish these results.

Abstract: Many fundamental problems in computational geometry admit no algorithm running in  time for Many fundamental problems in computational geometry admit no algorithm running in o(n log n) time for n planar input points, via classical reductions from sorting. Prominent examples include the computation of convex hulls, quadtrees, onion layer decompositions, Euclidean minimum spanning trees, KD-trees, Voronoi diagrams, and decremental closest-pair.

A classical result shows that, given n points sorted along a single direction, the convex hull can be constructed in linear time. Subsequent works established that for all of the other above problems, this information does not suffice. In 1989, Aggarwal, Guibas, Saxe, and Shor asked: Under which conditions can a Voronoi diagram be computed in o(n log n) time? Since then, the question of whether sorting along TWO directions enables a o(n log n)-time algorithm for such problems has remained open and has been repeatedly mentioned in the literature.

In this paper, we introduce the Presort Hierarchy: A problem is 1-Presortable if, given a sorting along one axis, it permits a (possibly randomised) o(n log n)-time algorithm. It is 2-Presortable if sortings along both axes suffice. It is Presort-Hard otherwise. Our main result is that quadtrees, and by extension Delaunay triangulations, Voronoi diagrams, and Euclidean minimum spanning trees, are 2-Presortable: we present an algorithm with expected running time O(n sqrt(log n)). This addresses the longstanding open problem posed by Aggarwal, Guibas, Saxe, and Shor (albeit randomised). We complement this result by showing that some of the other above geometric problems are also 2-Presortable or Presort-Hard.