Theory of Computing Report

Authors: Panagiotis Aivasiliotis, Andreas Göbel, Marc Roth

We study the complexity of the parameterised counting constraint satisfaction problem: given a set of constraints over a set of variables and a positive integer $k$, how many ways are there to assign $k$ variables to 1 (and the others to 0) such that all constraints are satisfied. Existing work has so far exclusively focused on restricted settings such as finding and counting homomorphisms between relational structures due to Grohe (JACM 2007) and Dalmau and Jonsson (TCS 2004), or the case of finite constraint languages due to Creignou and Vollmer (SAT 2012), and Bulatov and Marx (SICOMP 2014). In this work, we tackle a more general setting of Valued Parameterised Counting Constraint Satisfaction Problems (VCSPs) with infinite constraint languages. In this setting we are able to model significantly more general problems such as (weighted) parameterised factor problems on hypergraphs and counting weight-$k$ solutions of systems of linear equations, not captured by existing complexity classifications. We express parameterised VCSPs as parameterised \emph{Holant problems} on uniform hypergraphs, and we establish complete and explicit complexity dichotomy theorems. For resolving the $\mathrm{P}$ vs.\ $\#\mathrm{P}$ question, we mainly rely on hypergraph gadgets, the existence of which we prove using properties of degree sequences necessary for realisability in uniform hypergraphs. For the $\mathrm{FPT}$ vs.\ $\#\mathrm{W}[1]$ question, we mainly rely on known hardness results for the special case of graphs by Aivasiliotis et al. (ICALP 2025) and on an extension of the framework of the homomorphism basis due to Curticapean, Dell and Marx (STOC 17) to uniform hypergraphs. As a technical highlight, we also employ Curticapean's ``CFI Filters'' (SODA 2024) to establish polynomial-time algorithms for isolating vectors in the homomorphism basis.

Authors: Melissa Antonelli, Arnaud Durand, Juha Kontinen

Implicit computational complexity is a lively area of theoretical computer science, which aims to provide machine-independent characterizations of relevant complexity classes. % for uniformity with subsequent uses >> 1960s (but feel free to modify it) % One of the seminal works in this field appeared in the 1960s, when Cobham introduced a function algebra closed under bounded recursion on notation to capture polynomial time computable functions ($FP$). Later on, several complexity classes have been characterized using \emph{limited} recursion schemas. In this context, an original approach has been recently introduced, showing that ordinary differential equations (ODEs) offer a natural tool for algorithmic design and providing a characterization of $FP$ by a new ODE-schema. In the present paper we generalize this approach by presenting original ODE-characterizations for the small circuit classes $AC^0$ and $FTC^0$.

Authors: Florian Frick, Pranav Rajbhandari

The geodesic complexity of a length space $X$ quantifies the required number of case distinctions to continuously choose a shortest path connecting any given start and end point. We prove a local lower bound for the geodesic complexity of $X$ obtained by embedding simplices into $X\times X$. We additionally create and prove correctness of an algorithm to find cut loci on surfaces of convex polyhedra, as the structure of a space's cut loci is related to its geodesic complexity. We use these techniques to prove the geodesic complexity of an octahedron is four. Our method is inspired by earlier work of Recio-Mitter and Davis, and thus recovers their results on the geodesic complexity of the $n$-torus and the tetrahedron, respectively.

Authors: Alvin Chiu, Thomas Depian, David Eppstein, Michael T. Goodrich, Martin Nöllenburg

A witness drawing of a graph is a visualization that clearly shows a given property of a graph. We study and implement various drawing paradigms for witness drawings to clearly show that graphs have bounded pathwidth or treewidth. Our approach draws the tree decomposition or path decomposition as a tree of bags, with induced subgraphs shown in each bag, and with ''tracks'' for each graph vertex connecting its copies in multiple bags. Within bags, we optimize the vertex layout to avoid crossings of edges and tracks. We implement a visualization prototype for crossing minimization using dynamic programming for graphs of small width and heuristic approaches for graphs of larger width. We introduce a taxonomy of drawing styles, which render the subgraph for each bag as an arc diagram with one or two pages or as a circular layout with straight-line edges, and we render tracks either with straight lines or with orbital-radial paths.

Authors: Michael A. Bekos, Giordano Da Lozzo, Fabrizio Frati, Giuseppe Liotta, Antonios Symvonis

A well-known result by Kant [Algorithmica, 1996] implies that n-vertex outerplane graphs admit embedding-preserving planar straight-line grid drawings where the internal faces are convex polygons in $O(n^2)$ area. In this paper, we present an algorithm to compute such drawings in $O(n^{1.5})$ area. We also consider outerplanar drawings in which the internal faces are required to be strictly-convex polygons. In this setting, we consider outerplanar graphs whose weak dual is a path and give a drawing algorithm that achieves $\Theta(nk^2)$ area, where $k$ is the maximum size of an internal facial cycle.

Authors: Sarita de Berg, Ivor van der Hoog, Eva Rotenberg, Emil Toftegaard Gæde

Range reporting is a classical problem in computational geometry. A (rectangular) reporting data structure stores a point set $P$ of $n$ points, such that, given a (rectangular) query region $\Delta$, it returns all points in $P \cap \Delta$. A variety of data structures support such queries with differing asymptotic guarantees such as $k$-d trees, range trees, $R$-trees, and quadtrees. A common variant of range queries are distance reporting queries, where the input is a query point $q$ and a radius $\delta$, and the goal is to report all points in $P$ within distance $\delta$ of $q$. Such queries frequently arise as subroutines in geometric data structure construction and in Fr\'echet distance computations. Modern implementations typically reduce distance queries to rectangular range queries using the data structures listed above. We revisit a simple and practical heuristic for distance reporting. The approach is straightforward: sort the input point set $P$ along a space-filling curve. Queries then reduce to scanning at most four contiguous ranges along the sorted curve. We show extensive experimental evaluation of modern distance and range reporting data structures. In a static scenario, we show that this simple technique is competitive with all but the most highly optimised range reporting data structures. Notably, these involved structures use space-filling curves themselves to speed up computation. In a dynamic setting, our simpler method even becomes the preferred technique. This leads to a perhaps unexpected insight: while modern data structures invest heavily in leveraging space-filling curves for optimising their layout and traversal, it is the curve itself, rather than the surrounding machinery, that delivers much of the performance.

Authors: Eleni Katsanou, Tamara Mchedlidze, Antonios Symvonis, Thanos Tolias

"Metaphorical maps" or "contact representations" are visual representations of vertex-weighted graphs that rely on the geographic map metaphor. The vertices are represented by countries, the weights by the areas of the countries, and the edges by contacts/ boundaries among them. The accuracy with which the weights are mapped to areas and the simplicity of the polygons representing the countries are the two classical optimization goals for metaphorical maps. Mchedlidze and Schnorr [Metaphoric Maps for Dynamic Vertex-weighted Graphs, EuroVis 2022] presented a force-based algorithm that creates metaphorical maps that balance between these two optimization goals. Their maps look visually simple, but the accuracy of the maps is far from optimal - the countries' areas can vary up to 30% compared to required. In this paper, we provide a multi-fold extension of the algorithm in [Metaphoric Maps for Dynamic Vertex-weighted Graphs, EuroVis 2022]. More specifically: 1. Towards improving accuracy: We introduce the notion of region stiffness and suggest a technique for varying the stiffness based on the current pressure of map regions. 2. Towards maintaining simplicity: We introduce a weight coefficient to the pressure force exerted on each polygon point based on whether the corresponding point appears along a narrow passage. 3. Towards generality: We cover, in contrast to [Metaphoric Maps for Dynamic Vertex-weighted Graphs, EuroVis 2022], non-triangulated graphs. This is done by either generating points where more than three regions meet or by introducing holes in the metaphorical map. We perform an extended experimental evaluation that, among other results, reveals that our algorithm is able to construct metaphorical maps with nearly perfect area accuracy with a little sacrifice in their simplicity.

Authors: Hariharan Narayanan, Sourav Roy

We study the problem of approximating the mixed volume $V(P_1^{(\alpha_1)}, \dots, P_k^{(\alpha_k)})$ of an $k$-tuple of convex polytopes $(P_1, \dots, P_k)$, each of which is defined as the convex hull of at most $m_0$ points in $\mathbb{Z}^n$. We design an algorithm that produces an estimate that is within a multiplicative $1 \pm \epsilon$ factor of the true mixed volume with a probability greater than $1 - \delta.$ Let the constant $ \prod_{i=2}^{k} \frac{(\alpha_{i}+1)^{\alpha_{i}+1}}{\alpha_{i}^{\,\alpha_{i}}}$ be denoted by $\tilde{A}$. When each $P_i \subseteq B_\infty(2^L)$, we show in this paper that the time complexity of the algorithm is bounded above by a polynomial in $n, m_0, L, \tilde{A}, \epsilon^{-1}$ and $\log \delta^{-1}$. In fact, a stronger result is proved in this paper, with slightly more involved terminology. In particular, we provide the first randomized polynomial time algorithm for computing mixed volumes of such polytopes when $k$ is an absolute constant, but $\alpha_1, \dots, \alpha_k$ are arbitrary. Our approach synthesizes tools from convex optimization, the theory of Lorentzian polynomials, and polytope subdivision.

Authors: Giordano Andreola, Susanna Caroppo, Giuseppe Di Battista, Fabrizio Grosso, Maurizio Patrignani, Allegra Strippoli

Several algorithms for the construction of orthogonal drawings of graphs, including those based on the Topology-Shape-Metrics (TSM) paradigm, tend to prioritize the minimization of crossings. This emphasis has two notable side effects: some edges are drawn with unnecessarily long sequences of segments and bends, and the overall drawing area may become excessively large. As a result, the produced drawings often lack geometric uniformity. Moreover, orthogonal crossings are known to have a limited impact on readability, suggesting that crossing minimization may not always be the optimal goal. In this paper, we introduce a methodology that 'subverts' the traditional TSM pipeline by focusing on minimizing bends. Given a graph $G$, we ideally seek to construct a rectilinear drawing of $G$, that is, an orthogonal drawing with no bends. When not possible, we incrementally subdivide the edges of $G$ by introducing dummy vertices that will (possibly) correspond to bends in the final drawing. This process continues until a rectilinear drawing of a subdivision of the graph is found, after which the final coordinates are computed. We tackle the (NP-complete) rectilinear drawability problem by encoding it as a SAT formula and solving it with state-of-the-art SAT solvers. If the SAT formula is unsatisfiable, we use the solver's proof to determine which edge to subdivide. Our implementation, DOMUS, which is fairly simple, is evaluated through extensive experiments on small- to medium-sized graphs. The results show that it consistently outperforms OGDF's TSM-based approach across most standard graph drawing metrics.

Authors: Chaya Keller, Micha A. Perles

Finite unions of convex sets are a central object of study in discrete and computational geometry. In this paper we initiate a systematic study of complements of such unions -- i.e., sets of the form $S=\mathbb{R}^d \setminus (\cup_{i=1}^n K_i)$, where $K_i$ are convex sets. In the first part of the paper we study isolated points in $S$, whose number is related to the Betti numbers of $\cup_{i=1}^n K_i$ and to its non-convexity properties. We obtain upper bounds on the number of such points, which are sharp for $n=3$ and significantly improve previous bounds of Lawrence and Morris (2009) for all $n \ll \frac{2^d}{d}$. In the second part of the paper we study coverings of $S$ by well-behaved sets. We show that $S$ can be covered by at most $g(d,n)$ flats of different dimensions, in such a way that each $x \in S$ is covered by a flat whose dimension equals the `local dimension' of $S$ in the neighborhood of $x$. Furthermore, we determine the structure of a minimum cover that satisfies this property. Then, we study quantitative aspects of this minimum cover and obtain sharp upper bounds on its size in various settings.

Authors: Thomas Bläsius, Henrik Csöre, Max Göttlicher, Elly Schmidt, Wendy Yi

Motivated by hierarchical networks, we introduce the Flow-weighted Layered Metric Euclidean Capacitated Steiner Tree (FLaMECaST) problem, a variant of the Euclidean Steiner tree with layered structure and capacity constraints per layer. The goal is to construct a cost-optimal Steiner forest connecting a set of sources to a set of sinks under load-dependent edge costs. We prove that FLaMECaST is NP-hard to approximate, even in restricted cases where all sources lie on a circle. However, assuming few additional constraints for such instances, we design a dynamic program that achieves a $\left(1 + \frac{1}{2^n}\right)$-approximation in polynomial time. By generalizing the structural insights the dynamic program is based on, we extend the approach to certain settings, where all sources are positioned on a convex polygon.

Authors: Shaul Rosner, Tami Tamir

Let $G=(U \cup V, E)$ be a bipartite graph, where $U$ represents jobs and $V$ represents machines. We study a new variant of the bipartite matching problem in which each job in $U$ can be matched to at most one machine in $V$, and the number of jobs that can be assigned to a machine depends on the specific jobs matched to it. These pair-dependent bounds reflect systems where different jobs have varying tolerance for congestion, determined by the specific machine they are assigned to. We define a bipartite PD-matching as a set of edges $M \subseteq E$ that satisfies these job-to-machine tolerance constraints. This variant of matching extends well-known matching problems, however, despite its relevance to real-world systems, it has not been studied before. We study bipartite PD-matchings with the objective of maximizing the matching size. As we show, the problem exhibits significant differences from previously studied matching problems. We analyze its computational complexity both in the general case and for specific restricted instances, presenting hardness results alongside optimal and approximation algorithms.

Authors: Yannic Maus, Tijn de Vos

We give new, improved bounds for approximating the sparsest cut value or in other words the conductance $\phi$ of a graph in the CONGEST model. As our main result, we present an algorithm running in $O(\log^2 n/\phi)$ rounds in which every vertex outputs a value $\tilde \phi$ satisfying $\phi \le \tilde \phi \le \sqrt{2.01\phi}$. In most regimes, our algorithm improves significantly over the previously fastest algorithm for the problem [Chen, Meierhans, Probst Gutenberg, Saranurak; SODA 25]. Additionally, our result generalizes to $k$-way conductance. We obtain these results, by approximating the eigenvalues of the normalized Laplacian matrix $L:=I-\rm{Deg}^{-1/2}A\rm{Deg}^ {-1/2}$, where, $A$ is the adjacency matrix and $\rm{Deg}$ is the diagonal matrix with the weighted degrees on the diagonal. The previous state of the art sparsest cut algorithm is in the technical realm of expander decompositions. Our algorithms, on the other hand, are relatively simple and easy to implement. At the core, they rely on the well-known power method, which comes down to repeatedly multiplying the Laplacian with a vector. This operation can be performed in a single round in the CONGEST model. All our algorithms apply to weighted, undirected graphs. Our lower bounds apply even in unweighted graphs.

Authors: Alexander Dobler, Tim Hegemann, Martin Nöllenburg, Alexander Wolff

A storyline visualization shows interactions between characters over time. Each character is represented by an x-monotone curve. Time is mapped to the x-axis, and groups of characters that interact at a particular point $t$ in time must be ordered consecutively in the y-dimension at $x=t$. The predominant objective in storyline optimization so far has been the minimization of crossings between (blocks of) characters. Building on this work, we investigate another important, but less studied quality criterion, namely the minimization of wiggle, i.e., the amount of vertical movement of the characters over time. Given a storyline instance together with an ordering of the characters at any point in time, we show that wiggle count minimization is NP-complete. In contrast, we provide algorithms based on mathematical programming to solve linear wiggle height minimization and quadratic wiggle height minimization efficiently. Finally, we introduce a new method for routing character curves that focuses on keeping distances between neighboring curves constant as long as they run in parallel. We have implemented our algorithms, and we conduct a case study that explores the differences between the three optimization objectives. We use existing benchmark data, but we also present a new use case for storylines, namely the visualization of rolling stock schedules in railway operation.

Authors: Barbara Geissmann, Stefano Leucci, Chih-Hung Liu, Paolo Penna

We consider the problem of sorting $n$ elements subject to persistent random comparison errors. In this problem, each comparison between two elements can be wrong with some fixed (small) probability $p$, and comparing the same pair of elements multiple times always yields the same result. Sorting perfectly in this model is impossible, and the objective is to minimize the dislocation of each element in the output sequence, i.e., the difference between its position in the sequence and its true rank. In this paper, we present the first $O(n\log n)$-time sorting algorithm that guarantees both $O(\log n)$ maximum dislocation and $O(n)$ total dislocation with high probability when $p<\frac{1}{4}$. This settles the time complexity sorting with persistent comparison errors in the given range of $p$ and shows that comparison errors do not increase its computational difficulty. Indeed, $\Omega(n\log n)$ time is necessary to archive a maximum dislocation of $O(\log n)$ even without comparison errors. Moreover, we prove that no algorithm can guarantee a maximum dislocation of $o(\log n)$ with high probability, nor a total dislocation of $o(n)$ in expectation. To develop our sorting algorithm, we solve two related sub-problems, which might be of independent interest. More precisely, we show that $O(\log n)$ time suffices to find a position in which to insert a new element $x$ in an almost-sorted sequence $S$ of $n$ elements having dislocation at most $d=\Omega(\log n)$, so that the dislocation of $x$ in the resulting sequence is $O(d)$ with high probability (which can be equivalently thought as the problem of estimating the rank of $x$ in $S$). We also show that the maximum (resp. total) dislocation of an approximately sorted sequence $S$ of $n$ elements can be lowered to $O(\log n)$ (resp. $O(n)$) in $O(nd)$ time, w.h.p., where $d$ is an upper bound on the maximum dislocation of $S$.

Authors: Stephen Arndt, Benjamin Moseley, Kirk Pruhs, Michael Zlatin

This paper shows a polynomial-time algorithm, that given a general matroid $M_1 = (X, \mathcal{I}_1)$ and $k-1$ partition matroids $ M_2, \ldots, M_k$, produces a coloring of the intersection $M = \cap_{i=1}^k M_i$ using at most $1+\sum_{i=1}^k \left(\chi(M_i) -1\right)$ colors. This is the first polynomial-time $O(1)$-approximation algorithm for matroid intersection coloring where one of the matroids may be a general matroid. Leveraging the fact that all of the standard combinatorial matroids reduce to partition matroids at a loss of a factor of two in the chromatic number, this algorithm also yields a polynomial-time $O(1)$-approximation algorithm for matroid intersection coloring in the case where each of the matroids $ M_2, \ldots, M_k$ are one of the standard combinatorial types.

This will be one of a series of posts that I've always wanted to write but I needed to wait until I was no longer an academic administrator.

By Lance Fortnow

Start with an arc of a circle, like the red-to-red semicircle below. Then recursively subdivide it, at each step replacing a single arc of angle \(\theta\) by a piecewise-circular curve of five congruent arcs of angle \(\theta/3\). Keep in place the endpoints of the replaced arc and the tangent directions there. Make four of the five replacement arcs bend the same way as the arc they replaced, but bend the middle arc the opposite way.

The arcs get very flat as this construction progresses. I tried adding a fourth level to the drawing above and the inaccuracies of my drawing became bigger and more visible than the actual differences between the curves at the third and fourth level. (Maybe I should have written a script to draw it for me rather than trying to do it by hand.)

Any individual arc is replaced by sequences of arcs that remain within its convex hull, with four collinear new endpoints. Because both the diameters and aspect ratio of these convex hulls rapidly decrease for arcs at later levels of the construction, we get a well-defined curve as its limiting shape. I call it a fractal because it has a self-similar recursive construction like a fractal, but really it’s just a curve: its fractal dimension is one, not anything exotic.

Once we place an endpoint of an arc, at some level of the construction, all subsequent levels pass through the same point with the same tangent line. More, there is a unique tangent line at any point along the curve, and this tangent line varies continuously as you move along the curve. This is because, for any point on the curve and for any \(\varepsilon\), we can find a small enough neighborhood (the limit curve for an arc of turning angle less than \(\varepsilon\)) within which all tangents have angles bounded within \(\varepsilon\) of each other. The existence of a continuously varying tangent means that this is a \(C^1\) curve: it is continuously differentiable when expressed as a parameterized curve with its natural parameterization by arc length.

However, this curve does not contain any convex arcs. In the terminology of Cibulka, Kynčl, and Valtr, it is convex-arc-free. This is also easy to see: any arc of the curve contains some two consecutive endpoints at the same level of subdivision; call these \(p\) and \(q\) (for instance, these might be the two red points of the figure). Between \(p\) and \(q\) there are four endpoints from the next level; let \(p'\) and \(q'\) be the two middle of these four endpoints (the middlemost two yellow points). And in the same way let \(p''\) and \(q''\) be the two middle endpoints at the next level of subdivision between \(p'\) and \(q'\) (the middlemost two green points). But then \(p''\) and \(q''\) are interior to the convex hull of the four points \(p\), \(p'\), \(q'\), \(q\), an impossibility if these six points are to all lie on a convex arc.

Because it has no convex arcs, it also does not have a continuous second derivative: it is not \(C^2\)-smooth. If it were \(C^2\)-smooth, but not collinear, it would have a point of nonzero curvature, and within a small enough neighborhood of this point the curvature would keep the same sign. This neighborhood (or a small enough arc of it to have total turning angle at most \(\pi\)) would be a convex arc. Because no convex arc exists, the curvature and second derivative, if they exist anywhere, are not continuous. But having no convex arcs is stronger than not having a continuous second derivative: A stadium, formed by capping a rectangle by two semicircles, does not have a second derivative at the points where the semicircles meet the rectangle, but it is still convex.

The existence of a \(C^1\)-smooth curve with no convex arcs is related to my new preprint, “Stabbing faces by a convex curve”, arXiv:2508.17549 (to appear at Graph Drawing 2025). The main result of the paper is that for every \(C^1\)-smooth convex arc, and every planar graph, there is a straight-line drawing of the graph all of whose faces are crossed by the arc. It’s not necessarily a very nice drawing: this construction is intended more as a counterexample (in a line of research involving universal point sets) than as a useful way of drawing graphs. Here’s an example: the graph of an octahedron, drawn with all faces crossed by a semicircle.

The proof in the preprint really only uses the continuity of tangent lines, rather than anything sophisticated from differential geometry, but I don’t think the graph drawing community and the differential geometry community have a lot in common. One reviewer appeared to think that the superscript digit in \(C^1\) was the marker to a missing footnote. But more relevant to this post is a comment of a second reviewer, suggesting that this drawing method extends to any smooth curve (without assuming convexity), by finding a convex arc within it. Well, no. The five-arc fractal meets the \(C^1\) smoothness assumption of my preprint but the preprint’s construction does not apply, because it has no convex arc. You could apply this construction with the stronger assumption of \(C^2\) smoothness, though. It seems plausible that the construction in my preprint can be extended to \(C^1\)-smooth curves that are not convex, but it would take more care and could not be done simply by finding convex arcs.

Presumably the existence of \(C^1\) curves without convex arcs has been long known. Many similar constructions of pathological curves were found already in the late 19th and early 20th centuries by Cantor, Minkowski, and the like. However, my attempts to guess search keywords that would find these past constructions were unsuccessful.

(Discuss on Mastodon)

By David Eppstein

Authors: Orr Fischer, Rotem Oshman, Adi Rosen, Tal Roth

Pointer-chasing is a central problem in two-party communication complexity: given input size $n$ and a parameter $k$, the two players Alice and Bob are given functions $N_A, N_B: [n] \rightarrow [n]$, respectively, and their goal is to compute the value of $p_k$, where $p_0 = 1$, $p_1 = N_A(p_0)$, $p_2 = N_B(p_1) = N_B(N_A(p_0))$, $p_3 = N_A(p_2) = N_A(N_B(N_A(p_0)))$ and so on, applying $N_A$ in even steps and $N_B$ in odd steps, for a total of $k$ steps. It is trivial to solve the problem using $k$ communication rounds, with Alice speaking first, by simply ``chasing the function'' for $k$ steps. Many works have studied the communication complexity of pointer chasing, although the focus has always been on protocols with $k-1$ communication rounds, or with $k$ rounds where Bob (the ``wrong player'') speaks first. Many works have studied this setting giving sometimes tight or near-tight results. In this paper we study the communication complexity of the pointer chasing problem when the interaction between the two players is unlimited, i.e., without any restriction on the number of rounds. Perhaps surprisingly, this question was not studied before, to the best of our knowledge. Our main result is that the trivial $k$-round protocol is nearly tight (even) when the number of rounds is not restricted: we give a lower bound of $\Omega(k \log (n/k))$ on the randomized communication complexity of the pointer chasing problem with unlimited interaction, and a somewhat stronger lower bound of $\Omega(k \log \log{k})$ for protocols with zero error. When combined with prior work, our results also give a nearly-tight bound on the communication complexity of protocols using at most $k-1$ rounds, across all regimes of $k$; for $k > \sqrt{n}$ there was previously a significant gap between the upper and lower bound.

Authors: Anastasis Kratsios, Dennis Zvigelsky, Bradd Hart

A main open question in contemporary AI research is quantifying the forms of reasoning neural networks can perform when perfectly trained. This paper answers this by interpreting reasoning tasks as circuit emulation, where the gates define the type of reasoning; e.g. Boolean gates for predicate logic, tropical circuits for dynamic programming, arithmetic and analytic gates for symbolic mathematical representation, and hybrids thereof for deeper reasoning; e.g. higher-order logic. We present a systematic meta-algorithm that converts essentially any circuit into a feedforward neural network (NN) with ReLU activations by iteratively replacing each gate with a canonical ReLU MLP emulator. We show that, on any digital computer, our construction emulates the circuit exactly--no approximation, no rounding, modular overflow included--demonstrating that no reasoning task lies beyond the reach of neural networks. The number of neurons in the resulting network (parametric complexity) scales with the circuit's complexity, and the network's computational graph (structure) mirrors that of the emulated circuit. This formalizes the folklore that NNs networks trade algorithmic run-time (circuit runtime) for space complexity (number of neurons). We derive a range of applications of our main result, from emulating shortest-path algorithms on graphs with cubic--size NNs, to simulating stopped Turing machines with roughly quadratically--large NNs, and even the emulation of randomized Boolean circuits. Lastly, we demonstrate that our result is strictly more powerful than a classical universal approximation theorem: any universal function approximator can be encoded as a circuit and directly emulated by a NN.

Authors: MIT Hardness Group, Josh Brunner, Lily Chung, Erik D. Demaine, Jenny Diomidova, Della Hendrickson, Jayson Lynch

We prove PSPACE-completeness of Push-1: given a rectangular grid of 1 x 1 cells, each possibly occupied by a movable block, can a robot move from a specified location to another, given the ability to push up to one block at a time? In particular, we remove the need for fixed (unmovable) blocks in a previous result (FUN 2022), which seems to require a completely different reduction. This fundamental model of block pushing, introduced in 1999, abstracts the mechanics of many video games. It was shown NP-hard in 2000, but its final complexity remained open for 24 years. Our result uses a new framework for checkable gadgets/gizmos, extending a prior framework for checkable gadgets to handle reconfiguration problems, at the cost of requiring a stronger auxiliary gadget. We also show how to unify the motion-planning-through-gadgets framework (with an agent) with Nondeterministic Constraint Logic (with no agent), or more generally any Graph Orientation Reconfiguration Problem (GORP), by defining corresponding gadgets/gizmos.

Authors: Giuseppe Di Battista, Giuseppe Liotta, Maurizio Patrignani, Antonios Symvonis, Ioannis G. Tollis

We study a question that lies at the intersection of classical research subjects in Topological Graph Theory and Graph Drawing: Computing a drawing of a graph with a prescribed number of crossings on a given set $S$ of points, while ensuring that its curve complexity (i.e., maximum number of bends per edge) is bounded by a constant. We focus on trees: Let $T$ be a tree, $\vartheta(T)$ be its thrackle number, and $\chi$ be any integer in the interval $[0,\vartheta(T)]$. In the tangling phase we compute a topological linear embedding of $T$ with $\vartheta(T)$ edge crossings and a constant number of spine traversals. In the untangling phase we remove edge crossings without increasing the spine traversals until we reach $\chi$ crossings. The computed linear embedding is used to construct a drawing of $T$ on $S$ with $\chi$ crossings and constant curve complexity. Our approach gives rise to an $O(n^2)$-time algorithm for general trees and an $O(n \log n)$-time algorithm for paths. We also adapt the approach to compute RAC drawings, i.e. drawings where the angles formed at edge crossings are $\frac{\pi}{2}$.

Authors: Jakob Steininger, Sergey Yurkevich

A three-dimensional convex body is said to have Rupert's property if its copy can be passed through a straight hole inside that body. In this work we construct a polyhedron which is provably not Rupert, thus we disprove a conjecture from 2017. We also find a polyhedron that is Rupert but not locally Rupert.

Authors: Oswin Aichholzer, Sofia Brenner, Joseph Dorfer, Hung P. Hoang, Daniel Perz, Christian Rieck, Francesco Verciani

We study the problem of reconfiguring odd matchings, that is, matchings that cover all but a single vertex. Our reconfiguration operation is a so-called flip where the unmatched vertex of the first matching gets matched, while consequently another vertex becomes unmatched. We consider two distinct settings: the geometric setting, in which the vertices are points embedded in the plane and all occurring odd matchings are crossing-free, and a combinatorial setting, in which we consider odd matchings in general graphs. For the latter setting, we provide a complete polynomial time checkable characterization of graphs in which any two odd matchings can be reconfigured into each another. This complements the previously known result that the flip graph is always connected in the geometric setting [Aichholzer, Br\"otzner, Perz, and Schnider. Flips in odd matchings]. In the combinatorial setting, we prove that the diameter of the flip graph, if connected, is linear in the number of vertices. Furthermore, we establish that deciding whether there exists a flip sequence of length $k$ transforming one given matching into another is NP-complete in both the combinatorial and the geometric settings. To prove the latter, we introduce a framework that allows us to transform partial order types into general position with only polynomial overhead. Finally, we demonstrate that when parameterized by the flip distance $k$, the problem is fixed-parameter tractable (FPT) in the geometric setting when restricted to convex point sets.

Authors: Jeroen Gardeyn, Tony Wauters

This paper addresses the two-dimensional bin packing problem with guillotine constraints. The problem requires a set of rectangular items to be cut from larger rectangles, known as bins, while only making use of edge-to-edge (guillotine) cuts. The goal is to minimize the total bin area needed to cut all required items. This paper also addresses variants of the problem which permit 90{\deg} rotation of items and/or a heterogeneous set of bins. A novel heuristic is introduced which is based on the ruin and recreate paradigm combined with a goal-driven approach. When applying the proposed heuristic to benchmark instances from the literature, it outperforms the current state-of-the-art algorithms in terms of solution quality for all variants of the problem considered.

Authors: Wei Xuan, Yan Liang, Huawei Cao, Ning Lin, Xiaochun Ye, Dongrui Fan

Triangle counting is a fundamental problem in graph mining, essential for analyzing graph streams with arbitrary edge orders. However, exact counting becomes impractical due to the massive size of real-world graph streams. To address this, approximate algorithms have been developed, but existing distributed streaming algorithms lack adaptability and struggle with edge deletions. In this article, we propose DTC, a novel family of single-pass distributed streaming algorithms for global and local triangle counting in fully dynamic graph streams. Our DTC-AR algorithm accurately estimates triangle counts without prior knowledge of graph size, leveraging multi-machine resources. Additionally, we introduce DTC-FD, an algorithm tailored for fully dynamic graph streams, incorporating edge insertions and deletions. Using Random Pairing and future edge insertion compensation, DTC-FD achieves unbiased and accurate approximations across multiple machines. Experimental results demonstrate significant improvements over baselines. DTC-AR achieves up to $2029.4\times$ and $27.1\times$ more accuracy, while maintaining the best trade-off between accuracy and storage space. DTC-FD reduces estimation errors by up to $32.5\times$ and $19.3\times$, scaling linearly with graph stream size. These findings highlight the effectiveness of our proposed algorithms in tackling triangle counting in real-world scenarios. The source code and datasets are released and available at \href{https://github.com/wayne4s/srds-dtc.git}{https://github.com/wayne4s/srds-dtc.git}.

Authors: Hiroshi Fujiwara, Rina Atsumi, Hiroaki Yamamoto

In the (1-dimensional) bin packing problem, we are asked to pack all the given items into bins, each of capacity one, so that the number of non-empty bins is minimized. Zhu~[Chaos, Solitons \& Fractals 2016] proposed an approximation algorithm $MM$ that sorts the item sequence in a non-increasing order by size at the beginning, and then repeatedly packs, into the current single open bin, first as many of the largest items in the remaining sequence as possible and then as many of the smallest items in the remaining sequence as possible. In this paper we prove that the asymptotic approximation ratio of $MM$ is at most 1.5. Next, focusing on the fact that $MM$ is at the intersection of two algorithm classes, max-min algorithms and 1-bounded space algorithms, we comprehensively analyze the theoretical performance bounds of each subclass derived from the two classes. Our results include a lower bound of 1.25 for the intersection of the two classes. Furthermore, we extend the theoretical analysis over algorithm classes to the cardinality constrained bin packing problem.

Authors: Saswata Jana, Giuseppe F. Italiano, Partha Sarathi Mandal

This paper considers the Hamiltonian walk problem in the multi-agent coordination framework, referred to as $k$-agents Hamiltonian walk problem ($k$-HWP). In this problem, a set of $k$ connected agents collectively compute a spanning walk of a given undirected graph in the minimum steps. At each step, the agents are at $k$ distinct vertices and the induced subgraph made by the occupied vertices remains connected. In the next consecutive steps, each agent may remain stationary or move to one of its neighbours.To the best of our knowledge, this problem has not been previously explored in the context of multi-agent systems with connectivity. As a generalization of the well-known Hamiltonian walk problem (when $k=1$), $k$-HWP is NP-hard. We propose a $(3-\frac{1}{21})$-approximation algorithm for 2-HWP on arbitrary graphs. For the tree, we define a restricted version of the problem and present an optimal algorithm for arbitrary values of $k$. Finally, we formalize the problem for $k$-uniform hypergraphs and present a $2(1+\ln k)$-approximation algorithm. This result is also adapted to design an approximation algorithm for $k$-HWP on general graphs when $k = O(1)$.

Authors: Karthekeyan Chandrasekaran, Chandra Chekuri, Shubhang Kulkarni

B\'erczi, Chandrasekaran, Kir\'aly, and Kulkarni (ICALP 2024) recently described a splitting-off procedure in hypergraphs that preserves local-connectivity and outlined some applications. In this note we give an alternative proof via element-connectivity preserving reduction operations in graphs.

Authors: Peter T. Breuer

Because it is so unusual, or hard to find, or expository, a truly tiny 8- or 12-bit block AES (Rijndael) cipher is documented here, along with Java source code.

Authors: Ahan Mishra, Parker Rho, Robert Kleinberg

The density bound for schedulability for general pinwheel instances is $\frac{5}{6}$, but density bounds better than $\frac{5}{6}$ can be shown for cases in which the minimum element $m$ of the instance is large. Several recent works have studied the question of the 'density gap' as a function of $m$, with best known lower and upper bounds of $O \left( \frac{1}{m} \right)$ and $O \left( \frac{1}{\sqrt{m}} \right)$. We prove a density bound of $0.84$ for $m = 4$, the first $m$ for which a bound strictly better than $\frac{5}{6} = 0.8\overline{3}$ can be proven. In doing so, we develop new techniques, particularly a fast heuristic-based pinwheel solver and an unfolding operation.

Authors: Thomas Kesselheim, Marco Molinaro, Kalen Patton, Sahil Singla

Online Set Cover and Load Balancing are central problems in online optimization, and there is a long line of work on developing algorithms for these problems with convex objectives. Although we know optimal online algorithms with $\ell_p$-norm objectives, recent developments for general norms and convex objectives that rely on the online primal-dual framework apply only to fractional settings due to large integrality gaps. Our work focuses on directly designing integral online algorithms for Set Cover and Load Balancing with convex objectives, bypassing the convex-relaxation and the primal-dual technique. Some of the main implications are: 1. For Online Set Cover, we can extend the results of Azar et. al. (2016) for convex objectives and of Kesselheim, Molinaro, and Singla (2024) for symmetric norms from fractional to integral settings. 2. Our results for convex objectives and symmetric norms even apply to the online generalized scheduling problem, which generalizes both Set Cover and Load Balancing. Previous works could only handle the offline version of this problem with norm objectives (Deng, Li, and Rabani 2023). 3. Our methods easily extend to settings with disjoint-composition of norms. This allows us to recover or improve the norm-composition results of Nagarajan and Shen (2020), and Kesselheim, Molinaro, and Singla (2024), and to extend our results to a large class of norms beyond symmetric. Our approach is to first reduce these problems to online packing problems, and then to design good approximation algorithms for the latter. To solve these packing problems, we use two key ideas. First, we decouple the global packing problem into a series of local packing problems on different machines. Next, we choose random activation thresholds for machines such that conditional on a machine being activated, the expected number of jobs it covers is high compared to its cost.

So I promised you a syllabus for graduate machine learning! Well, here’s one for this semester that I reserve the right to change as the course plays out.

As always, this course takes a narrow view of machine learning, casting it as building predictions from examples. The main turn this year, which has been super helpful, is grounding everything in how we evaluate these predictions. This theme of evaluation was already implicit in Patterns, Predictions, and Actions, but making it explicit coherently ties the semester together.

Declaring how we will evaluate our predictions determines how we make the predictions. This Metrical Determinism will be a recurring theme in the class. If I tell you the metric, you can determine the optimal decision rule. More often than not, predictive engineering just targets this optimum. To make this clear, we’ll cover the basics of decision theory, where this metrical determinism is explicit. Decision theory tells us what the optimal predictions would be if we could see all of the data in advance. If you force yourself to make predictions with a fixed format of data, what would be the best predictions you could make? We’ll build this theory based on samples, not probabilities. Not much changes in this sample-based, actuarial view, but it resolves the paradoxes posed in Meehl’s Clinical versus Statistical Decisions. We’ll discuss all the different error metrics you might set for predictions and decisions, and learn about impossibility results like the Neyman-Pearson Lemma and orthogonality theorems from the fairness literature.

We’ll then transition from decision theory to supervised learning, which we can think of as an approximate form of decision theory. Decision theory tells us what the optimal predictions would be if we could see all of the data in advance. Supervised learning tries to find them when we only see a subset of the data. We’ll focus on what’s most relevant in machine learning, specifically a non-exhaustive survey of how we represent and transform data and the rudiments of stochastic gradient descent.

Next, we’ll discuss how we evaluate the predictions of supervised learning. This is, of course, through competitive testing on benchmark data sets. We’ll go over the train-test split and the motivations for it (both cultural and statistical). We’ll discuss the many successful benchmarks in machine learning and consider what made these useful for the predictive engineers of their respective eras. We’ll also discuss what happens when the data we test on is different from the data we trained on.

We’ll then turn to other proposed evaluations, getting into my favorite topic: arguing with statisticians.1 We’ll talk about putting error bars on evaluations and predictions, and what these mean (Spoiler Alert: the answer is not much). But by understanding the principles of error bars, we can discuss AB Tests and RCTs. Such randomized evaluations are prevalent tools used to evaluate not just machine learning, but all sorts of policies and decision systems. It’s a short hop from the AB Test to the multi-armed bandit, and this will let us touch on the basics of bandits and sequential prediction.

Finally, the class ends with reinforcement learning. Now, in the past, this was an easy handoff, moving from sequential prediction to “sequential prediction with dynamics.” When I wrote this survey in 2018, that’s all more or less what reinforcement learning was. But contemporary reinforcement learning, the kind people are all excited about in LLM-land, is not this at all. It is a reformist reinforcement learning that uses all of the old words from Sutton and Barto, but has almost nothing to do with this older work. So rather than presenting conservative RL, which doesn’t work, we’re just going to take a total tangent and dive into this reformist RL, explaining what it is so we can get a sense for what people are writing all these papers about. You can do this without ever learning dynamic programming. You can do this without knowing what an MDP is. You can do this without ever saying “advantage function” or “cost-to-go.” Reformist RL is essentially “guess and check.” It is a way to inefficiently flail around looking for supervised learning signals in a world where they are a scarce resource. Reformist RL is not as cleanly analyzable as the perceptron (yet). But maybe there’s a simple analysis and algorithm for how to do it. Let’s see if we can find one before the ICML deadline.

This syllabus is not exactly what I want yet, but it’s getting there. I would like to fit in a few more lectures on the “modeling zoo” to help decide between the various optimizers and models available to the intrepid vibe coder. Some organizing principles for navigating the vast ML toolbox would be nice, no? I might try to squeeze that in depending on how the semester goes. In the sequential prediction unit, I’d like to mention some of the basic concepts of Defensive Forecasting from my survey with Juanky Perdomo. We’ll see how it goes and what time allows.

Most of the material I’ve discussed here is already in PPA, but some is new. In particular, I finally feel like I can teach this course without ever imagining a hypothetical “data-generating distribution” that feeds us independent, identically distributed samples (famous last words). I’ll be supplementing parts with new notes that I’ll link off this blog. They will be filled with errors, so help me find them. I’ll post what I actually cover, including all of the readings, here on the blog. In particular, I haven’t quite figured out the readings for the latter third of the course. I’ll draw what I can from PPA, but will also supplement with my own notes and a few external sources.

One additional thing I’ll post here this semester are problem sets. We’re going to try a new experiment in this class: frontloading the work on the final project. Each problem set will involve some questions about the project, and I’ll post those here. The only way to really learn machine learning and the metrical determinism of predictive optimization is by applying it to predictions that matter to you.

Subscribe now

By Ben Recht

Authors: Eric Alsmann, Martin Lange

We analyse the complexity of the satisfiability problem ssmSAT for State Space Models (SSM), which asks whether an input sequence can lead the model to an accepting configuration. We find that ssmSAT is undecidable in general, reflecting the computational power of SSM. Motivated by practical settings, we identify two natural restrictions under which ssmSAT becomes decidable and establish corresponding complexity bounds. First, for SSM with bounded context length, ssmSAT is NP-complete when the input length is given in unary and in NEXPTIME (and PSPACE-hard) when the input length is given in binary. Second, for quantised SSM operating over fixed-width arithmetic, ssmSAT is PSPACE-complete resp. in EXPSPACE depending on the bit-width encoding. While these results hold for diagonal gated SSM we also establish complexity bounds for time-invariant SSM. Our results establish a first complexity landscape for formal reasoning in SSM and highlight fundamental limits and opportunities for the verification of SSM-based language models.

Authors: Zachary DeStefano, Bufang Liang

Push-1 is one of the simplest abstract frameworks for motion planning; however, the complexity of deciding if a Push-1 problem can be solved was a several-decade-old open question. We resolve the complexity of the motion planning problem Push-1 by showing that it is PSPACE-complete, and we formally verify the correctness of our constructions. Our results build upon a recent work which demonstrated that Push-1F (a variant of Push-1 with fixed blocks) and Push-k for $k \geq 2$ (a variant of Push-1 where the agent can push $k$ blocks at once) are PSPACE-complete and more generally on the motion-planning-though-gadgets framework. In the process of resolving this open problem, we make two general contributions to the motion planning complexity theory. First, our proof technique extends the standard motion planning framework by assigning the agent a state. This state is preserved when traversing between gadgets but can change when taking transitions in gadgets. Second, we designed and implemented a system, GADGETEER, for computationally verifying the behavior of systems of gadgets. This system is agnostic to the underlying motion planning problem, and allows for formally verifying the correspondence between a low-level construction and a high-level system of gadgets as well as automatically synthesizing gadgets from low-level constructions. In the case of Push-1, we use this system to formally prove that our constructions match our high-level specifications of their behavior. This culminates in the construction and verification of a self-closing door, as deciding reachability in a system of self-closing doors is PSPACE-complete.

Authors: David Eppstein

We prove that, for every plane graph $G$ and every smooth convex curve $C$ not on a single line, there exists a straight-line drawing of $G$ for which every face is crossed by $C$.

Authors: Carla Binucci, Sabine Cornelsen, Walter Didimo, Seok-Hee Hong, Eleni Katsanou, Maurizio Patrignani, Antonios Symvonis, Samuel Wolf

We address the problem of computing a dynamic visualization of a geometric graph $G$ as a sequence of frames. Each frame shows only a portion of the graph but their union covers $G$ entirely. The two main requirements of our dynamic visualization are: $(i)$ guaranteeing drawing stability, so to preserve the user's mental map; $(ii)$ keeping the visual complexity of each frame low. To satisfy the first requirement, we never change the position of the vertices. Regarding the second requirement, we avoid edge crossings in each frame. More precisely, in the first frame we visualize a suitable subset of non-crossing edges; in each subsequent frame, exactly one new edge enters the visualization and all the edges that cross with it are deleted. We call such a sequence of frames a planar story of $G$. Our goal is to find a planar story whose minimum number of edges contemporarily displayed is maximized (i.e., a planar story that maximizes the minimum frame size). Besides studying our model from a theoretical point of view, we also design and experimentally compare different algorithms, both exact techniques and heuristics. These algorithms provide an array of alternative trade-offs between efficiency and effectiveness, also depending on the structure of the input graph.

Authors: Ivor van der Hoog, Henrik Reinstädtler, Eva Rotenberg

Convex hull data structures are fundamental in computational geometry. We study insertion-only data structures, supporting various containment and intersection queries. When $P$ is sorted by $x$- or $y$-coordinate, convex hulls can be constructed in linear time using classical algorithms such as Graham scan. We investigate a variety of methods tailored to the insertion-only setting. We explore a broad selection of trade-offs involving robustness, memory access patterns, and space usage, providing an extensive evaluation of both existing and novel techniques. Logarithmic-time methods rely on pointer-based tree structures, which suffer in practice due to poor memory locality. Motivated by this, we develop a vector-based solution inspired by Overmars' logarithmic method. Our structure has worse asymptotic bounds, supporting queries in $O(\log^2 n)$ time, but stores data in $O(\log n)$ contiguous vectors, greatly improving cache performance. Through empirical evaluation on real-world and synthetic data sets, we uncover surprising trends. Let $h$ denote the size of the convex hull. We show that a na\"ive $O(h)$ insertion-only algorithm based on Graham scan consistently outperforms both theoretical and practical state-of-the-art methods under realistic workloads, even on data sets with rather large convex hulls. While tree-based methods with $O(\log h)$ update times offer solid theoretical guarantees, they are never optimal in practice. In contrast, our vector-based logarithmic method, despite its theoretically inferior bounds, is highly competitive across all tested scenarios. It is optimal whenever the convex hull becomes large.

Authors: Yasuaki Kobayashi, Yuto Okada

In this paper, we give a polynomial-time algorithm for deciding whether an input bipartite graph admits a 2-layer fan-planar drawing, resolving an open problem posed in several papers since 2015.

Authors: Todor Antić, Martin Balko, Birgit Vogtenhuber

For a finite set $P$ of points in the plane in general position, a \emph{crossing family} of size $k$ in $P$ is a collection of $k$ line segments with endpoints in $P$ that are pairwise crossing. It is a long-standing open problem to determine the largest size of a crossing family in any set of $n$ points in the plane in general position. It is widely believed that this size should be linear in $n$. Motivated by results from the theory of partitioning complete geometric graphs, we study a variant of this problem for point sets $P$ that do not contain a \emph{non-crossing family} of size $m$, which is a collection of 4 disjoint subsets $P_1$, $P_2$, $P_3$, and $P_4$ of $P$, each containing $m$ points of $P$, such that for every choice of 4 points $p_i \in P_i$, the set $\{p_1,p_2,p_3,p_4\}$ is such that $p_4$ is in the interior of the triangle formed by $p_1,p_2,p_3$. We prove that, for every $m \in \mathbb{N}$, each set $P$ of $n$ points in the plane in general position contains either a crossing family of size $n/2^{O(\sqrt{\log{m}})}$ or a non-crossing family of size $m$, by this strengthening a recent breakthrough result by Pach, Rubin, and Tardos (2021). Our proof is constructive and we show that these families can be obtained in expected time $O(nm^{1+o(1)})$. We also prove that a crossing family of size $\Omega(n/m)$ or a non-crossing family of size $m$ in $P$ can be found in expected time $O(n)$.

Authors: Artur Bikeev, Andrey Kupavskii, Maxim Turevskii

For a given metric space $(P,\phi)$, a tree cover of stretch $t$ is a collection of trees on $P$ such that edges $(x,y)$ of trees receive length $\phi(x,y)$, and such that for any pair of points $u,v\in P$ there is a tree $T$ in the collection such that the induced graph distance in $T$ between $u$ and $v$ is at most $t\phi(u,v).$ In this paper, we show that, for any set of points $P$ on the Euclidean plane, there is a tree cover consisting of two trees and with stretch $O(1).$ Although the problem in higher dimensions remains elusive, we manage to prove that for a slightly stronger variant of a tree cover problem we must have at least $(d+1)/2$ trees in any constant stretch tree cover in $\mathbb R^d$.

Authors: Robert Scheffler

We consider two different problem families that deal with domination in graphs. On the one hand, we focus on dominating sequences. In such a sequence, every vertex dominates some vertex of the graph that was not dominated by any earlier vertex in the sequence. The problem of finding the longest dominating sequence is known as $\mathsf{Grundy~Domination}$. Depending on whether the closed or the open neighborhoods are used for domination, there are three other versions of this problem. We show that all four problem variants are $\mathsf{W[1]}$-hard when parameterized by the solution size. On the other hand, we consider the family of Zero forcing problems which form the parameterized duals of the Grundy domination problems. In these problems, one looks for the smallest set of vertices initially colored blue such that certain color change rules are able to color all other vertices blue. Bhyravarapu et al. [IWOCA 2025] showed that one of these problems, known as $\mathsf{Zero~Forcing~Set}$, is in $\mathsf{FPT}$ when parameterized by the treewidth or the solution size. We extend their treewidth result to the other three variants of zero forcing and their respective Grundy domination problems. Our algorithm also implies an $\mathsf{FPT}$ algorithm for $\mathsf{Grundy~Domination}$ when parameterized by the number of vertices that are not in the dominating sequence.

Authors: Enqiang Zhu, Qiqi Bao, Yu Zhang, Pu Wu, Chanjuan Liu

The Minimum Dominating Set (MDS) problem is a well-established combinatorial optimization problem with numerous real-world applications. Its NP-hard nature makes it increasingly difficult to obtain exact solutions as the graph size grows. This paper introduces ParDS, an exact algorithm developed to address the MDS problem within the branch-and-bound framework. ParDS features two key innovations: an advanced linear programming technique that yields tighter lower bounds and a set of novel reduction rules that dynamically simplify instances throughout the solving process. Compared to the leading exact algorithms presented at IJCAI 2023 and 2024, ParDS demonstrates theoretically superior lower-bound quality. Experimental results on standard benchmark datasets highlight several significant advantages of ParDS: it achieves fastest solving times in 70% of graph categories, especially on large, sparse graphs, delivers a speed-up of up to 3,411 times on the fastest individual instance, and successfully solves 16 out of 43 instances that other algorithms were unable to resolve within the 5-hour time limit. These findings establish ParDS as a state-of-the-art solution for exactly solving the MDS problem.

Authors: Nicholas Kocurek, Peter Manohar

We study the problem of strongly refuting semirandom $k$-LIN$(\mathbb{F})$ instances: systems of $k$-sparse inhomogeneous linear equations over a finite field $\mathbb{F}$. For the case of $\mathbb{F} = \mathbb{F}_2$, this is the well-studied problem of refuting semirandom instances of $k$-XOR, where the works of [GKM22,HKM23] establish a tight trade-off between runtime and clause density for refutation: for any choice of a parameter $\ell$, they give an $n^{O(\ell)}$-time algorithm to certify that there is no assignment that can satisfy more than $\frac{1}{2} + \varepsilon$-fraction of constraints in a semirandom $k$-XOR instance, provided that the instance has $O(n) \cdot \left(\frac{n}{\ell}\right)^{k/2 - 1} \log n /\varepsilon^4$ constraints, and the work of [KMOW17] provides good evidence that this tight up to a $\mathrm{polylog}(n)$ factor via lower bounds for the Sum-of-Squares hierarchy. However for larger fields, the only known results for this problem are established via black-box reductions to the case of $\mathbb{F}_2$, resulting in an $|{\mathbb{F}}|^{3k}$ gap between the current best upper and lower bounds. In this paper, we give an algorithm for refuting semirandom $k$-LIN$(\mathbb{F})$ instances with the "correct" dependence on the field size $|{\mathbb{F}}|$. For any choice of a parameter $\ell$, our algorithm runs in $(|{\mathbb{F}}|n)^{O(\ell)}$-time and strongly refutes semirandom $k$-LIN$(\mathbb{F})$ instances with at least $O(n) \cdot \left(\frac{|{\mathbb{F}^*}| n}{\ell}\right)^{k/2 - 1} \log(n |{\mathbb{F}^*}|) /\varepsilon^4$ constraints. We give good evidence that this dependence on the field size $|{\mathbb{F}}|$ is optimal by proving a lower bound for the Sum-of-Squares hierarchy that matches this threshold up to a $\mathrm{polylog}(n |{\mathbb{F}^*}|)$ factor. Our results also extend to the more general case of finite Abelian groups.

Authors: Emilio Cruciani, Sebastian Forster, Tijn de Vos

We study a multi-call variant of the classic PUSH&PULL rumor spreading process where nodes can contact $k$ of their neighbors instead of a single one during both PUSH and PULL operations. We show that rumor spreading can be made faster at the cost of an increased amount of communication between the nodes. As a motivating example, consider the process on a complete graph of $n$ nodes: while the standard PUSH&PULL protocol takes $\Theta(\log n)$ rounds, we prove that our $k$-PUSH&PULL variant completes in $\Theta(\log_{k} n)$ rounds, with high probability. We generalize this result in an expansion-sensitive way, as has been done for the classic PUSH&PULL protocol for different notions of expansion, e.g., conductance and vertex expansion. We consider small-set vertex expanders, graphs in which every sufficiently small subset of nodes has a large neighborhood, ensuring strong local connectivity. In particular, when the expansion parameter satisfies $\phi > 1$, these graphs have a diameter of $o(\log n)$, as opposed to other standard notions of expansion. Since the graph's diameter is a lower bound on the number of rounds required for rumor spreading, this makes small-set expanders particularly well-suited for fast information dissemination. We prove that $k$-PUSH&PULL takes $O(\log_{\phi} n \cdot \log_{k} n)$ rounds in these expanders, with high probability. We complement this with a simple lower bound of $\Omega(\log_{\phi} n+ \log_{k} n)$ rounds.

Authors: Anupam Gupta, Haim Kaplan, Alexander Lindermayr, Jens Schlöter, Sorrachai Yingchareonthawornchai

We revisit the classical problem of minimizing the total flow time of jobs on a single machine in the online setting where jobs arrive over time. It has long been known that the Shortest Remaining Processing Time (SRPT) algorithm is optimal (i.e., $1$-competitive) when the job sizes are known up-front [Schrage, 1968]. But in the non-clairvoyant setting where job sizes are revealed only when the job finishes, no algorithm can be constant-competitive [Motwani, Phillips, and Torng, 1994]. We consider the $\varepsilon$-clairvoyant setting, where $\varepsilon \in [0,1]$, and each job's processing time becomes known once its remaining processing time equals an $\varepsilon$ fraction of its processing time. This captures settings where the system user uses the initial $(1-\varepsilon)$ fraction of a job's processing time to learn its true length, which it can then reveal to the algorithm. The model was proposed by Yingchareonthawornchai and Torng (2017), and it smoothly interpolates between the clairvoyant setting (when $\epsilon = 1$) and the non-clairvoyant setting (when $\varepsilon = 0$). In a concrete sense, we are asking: how much knowledge is required to circumvent the hardness of this problem? We show that a little knowledge is enough, and that a constant competitive algorithm exists for every constant $\varepsilon > 0$. More precisely, for all $\varepsilon \in (0,1)$, we present a deterministic $\smash{\lceil \frac{1}{\varepsilon}\rceil}$-competitive algorithm, which is optimal for deterministic algorithms. We also present a matching lower bound (up to a constant factor) for randomized algorithms. Our algorithm to achieve this bound is remarkably simple and applies the ``optimism in the face of uncertainty'' principle. The proof relies on maintaining a matching between the jobs in the optimum's queue and the algorithm's queue, with small prefix expansion.

Authors: Paweł Gawrychowski, Adam Górkiewicz

We revisit the complexity of building, given a two-dimensional string of size $n$, an indexing structure that allows locating all $k$ occurrences of a two-dimensional pattern of size $m$. While a structure of size $\mathcal{O}(n)$ with query time $\mathcal{O}(m+k)$ is known for this problem under the additional assumption that the pattern is a square [Giancarlo, SICOMP 1995], a popular belief was that for rectangular patterns one cannot achieve such (or even similar) bounds, due to a lower bound for a certain natural class of approaches [Giancarlo, WADS 1993]. We show that, in fact, it is possible to construct a very simple structure of size $\mathcal{O}(n\log n)$ that supports such queries for any rectangular pattern in $\mathcal{O}(m+k\log^{\varepsilon}n)$ time, for any $\varepsilon>0$. Further, our structure can be constructed in $\tilde{\mathcal{O}}(n)$ time.

Authors: Lior Gishboliner, Asaf Shapira

Property testers are fast, randomized "election polling"-type algorithms that determine if an input (e.g., graph or hypergraph) has a certain property or is $\varepsilon$-far from the property. In the dense graph model of property testing, it is known that many properties can be tested with query complexity that depends only on the error parameter $\varepsilon$ (and not on the size of the input), but the current bounds on the query complexity grow extremely quickly as a function of $1/\varepsilon$. Which properties can be tested efficiently, i.e., with $\mathrm{poly}(1/\varepsilon)$ queries? This survey presents the state of knowledge on this general question, as well as some key open problems.

Join our strong and active Theory Group! The Department of Computer Science at UVic invites applications for a tenure-track Assistant Professor in theoretical computer science. We seek candidates with a strong research record and a compelling plan for future work. UVic is dedicated to equity, diversity, and inclusion; we strongly encourage applications from members of marginalized groups.

Website: https://www.uvic.ca/ecs/computerscience/assets/docs/employment/cosi_theory_reseach-faculty-ad_2025_26.pdf
Email: skoroth@uvic.ca

By shacharlovett

If you want to enclose a bounded subset of the plane with the shortest possible fence (the perimeter of your enclosure), use its convex hull. If you want to enclose it with the minimum possible total area, use the set itself. This might be disconnected, but it doesn’t make any difference to ask for the minimum-area connected enclosure: for well-behaved subsets you can connect the pieces with a spanning tree or Steiner tree with zero additional area.

My recent preprint “Bicriteria polygon aggregation with arbitrary shapes” (arXiv:2507.11212, with Lotte Blank, Jan-Henrik Haunert, Herman Haverkort, Benedikt Kolbe, Philip Mayer, Petra Mutzel, Alexander Naumann, and Jonas Sauer) asks: what if you measure the quality of your enclosure by a linear combination of area and perimeter? For this to make sense you need scale factor, in units of length, so that you can add the area to the product of the perimeter with this factor. In this way, the results of this enclosure can be seen as a multi-scale way of studying the shape of a subset. It can also be viewed as a clustering method, where the clusters are the parts of a disconnected input (like a point set) that become connected in the optimal enclosure.

Here’s an example from Fig. 1 of the paper: the buildings of the village of Bokeloh, in Lower Saxony (shown in blue) clustered at three different scale factors (shades of orange). Actually, there’s a fourth level of clustering: the buildings themselves form their own clusters for scale factors small enough that the perimeter part of the quality becomes negligible and all you’re left with is area.

What you might already see in this figure is that the boundaries of the clusters form circular arcs, all the same radius. This is closely related to the fact that two-dimensional soap bubbles and foams also consist of circles and circular arcs. The endpoints of the arcs are either input vertices or tangencies with the sides of input polygons, and they can be connected by segments of cluster boundary that lie along the polygon sides edges. If the input were a point set, you would still get a picture like this, but with cluster boundaries consisting only of circular arcs, meeting at some of the points.

It turns out that this analysis of the optimal cluster shape is enough to lead to a polynomial time algorithm. An input consisting of \(n\) points, or of polygons with \(n\) total sides, has \(O(n^2)\) circular arcs of the correct radius ending at vertices or tangencies. If all of these arcs are overlaid, they subdivide the plane into \(O(n^4)\) regions, large but still polynomial. One can then set up a minimum cut problem (following prior work by an overlapping set of authors) where the input polygons are connected to a source terminal, the cost of cutting one region from another is the scaled length of their shared boundary, and the cost of cutting an outside region from the destination terminal is its area. Because minimum cut can be solved in polynomial time, so can this clustering problem.

Earlier work on this clustering problem approached it more heuristically, using constrained Delaunay triangulation instead of circular arcs to divide the free space into regions, and then setting up the same min cut problem to enclose some of the regions with minimum total cost. But there’s no clear connection between Delaunay triangulation and this optimizal enclosure problem, so that did not provide any guarantee of solution quality. The circular arc boundaries of the optimal enclosure might be seen as a drawback of our solution, though, so in the preprint we also find a polygonal approximation to it. (This part was one focus of the work of Petra and myself when she visited on sabbatical last year; we then joined forces with the rest of the coauthors, who had already been working on the same problems.)

(Discuss on Mastodon)

By David Eppstein