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: -