Theory of Computing Report

Holy crap … yesterday I was elected to the US National Academy of Sciences! If you don’t believe me, click the link and keep scrolling down until you hit the name “Aaronson.” But then continue scrolling to see 144 other inductees, including my IAS postdoctoral classmate Maria Chudnovsky, my longtime friend and colleague Salil Vadhan, and even Janet Yellen. I’m humbled to be in such company.

Years ago, somewhere on this blog, I mused that, if I were ever invited to join NAS, I hoped I’d follow the wisdom of Richard Feynman, who famously resigned his NAS membership, comparing it to an honor society back at his high school that spent most of its time debating who should be a member of the honor society. Feynman was also annoyed at having to pay dues.

But now that I’m actually faced with the choice, it’s like, dude! At my advanced age of 44, I’ve encountered so many people who dislike me or even sneer at me, and so many clubs that won’t have me as a member, that I feel mostly gratitude and warmth toward a fine club like NAS that will have me as a member. Anyway, I’ll certainly try it out to see what it’s like—even Feynman did that!

A few hours after I started getting congratulatory emails, for which I was thankful, someone from UT Austin’s press office asked me how I feel about this “culmination” and “capstone” of my entire research career. I replied, look, I know I’ve slowed down a lot since my nubile twenties, but I still hold out the hope that this isn’t any kind of “capstone”!

In any case, I’m ridiculously grateful to all the friends, family, colleagues, and readers who believed in me and helped me reach wherever this is.

---

Now for a totally different topic, but that will ultimately loop back to the first one:

Last week, I did an Ask Me Anything about quantum computing and blockchain for stacker.news, a forum devoted to bitcoin. Thanks to Will Scoresby for organizing it.

As a longer-term commitment, I also collaborated with my colleagues Dan Boneh, Justin Drake, Sreeram Kannan, Yehuda Lindell, and Dahlia Malkhi, in a panel convened by Coinbase, to put out a detailed position paper about the quantum threat to cryptocurrencies and how best to respond to it. Take a look!

Notably, the situation evolved even while we were writing our position paper—for example, with the major recent papers from Google and Caltech/Oratomic that I blogged about a month ago.

I’d now like to add a few words of my own, not presuming to speak for my fellow Coinbase panelists.

See, some of the most reputable people in quantum hardware and quantum error-correction—people whose judgment I trust more than my own on those topics—are now telling me that a fault-tolerant quantum computer able to break deployed cryptosystems ought to be possible by around 2029.

Maybe they’re overoptimistic. Maybe it will take longer. I dunno. I’m not a timing guy.

But here’s what I do know: the companies racing to scale up fault-tolerant QC, have no plans to slow down in order to “give cybersecurity time to adapt” or whatever. The way they see it, cryptographically relevant QCs will plausibly be built sometime soon: indeed, it’s ultimately unavoidable, even if people’s only interest in QC was to do quantum simulations for materials science and chemistry. So, given that reality, isn’t it better that it be done first by mostly US-based companies in the open, than by (let’s say) Chinese or Russian intelligence in secret? And besides, haven’t there already been years of warnings and meetings about the quantum threat to RSA, Diffie-Hellman, and elliptic curve cryptography? Aren’t many in cybersecurity still in denial about the threat?

Haven’t these slumberers shown that won’t wake up until dramatic achievements in fault-tolerant QC roust them—the way Anthropic’s Mythos model has now jolted even the most ostrich-like about the cybersecurity risks of AI? So, mixing metaphors, mightn’t we just as well rip this Band-Aid off ASAP, rather than giving foreign intelligence agencies extra years to catch up? Indeed, when you think about it that way, isn’t racing to build a cryptographically relevant QC, as quickly as possible, the most ethical, socially responsible thing for an American QC company to do?

Is the above line of reasoning suspiciously self-serving and convenient? Does it remind you of the galaxy-brained arguments that AI company after AI company offered over the last decade for why “really, if you think about it, accelerating toward dangerous superintelligence is the safest course that we could possibly take”? I.e., the arguments that underpinned the current frenzied AI race, which some believe is imperiling all life on earth?

It’s not my place here to answer such questions; I leave all further ethical and geopolitical debate to the comment section! My point here is simply: whether or not anyone likes it, this is how some of the leading QC companies are now thinking about the Shor of Damocles that they genuinely believe now hangs over the Internet.

And I’d say that that makes my own moral duty right now ironically simple and clear: namely, to use my unique soapbox, as the writer of The Internet’s Most Trusted Quantum Computing Blog Since 2005^TM, to sound the alarm.

So, here it is: if quantum computers start breaking cryptography a few years from now, don’t you dare come to this blog and tell me that I failed to warn you. This post is your warning. Please start switching to quantum-resistant encryption, and urge your company or organization or blockchain or standards body to do the same.

Yea, heed my warning, for it comes not from some WordPress-using rando, but from the inventor of BosonSampling and PostBQP and shadow tomography, the Schlumberger Centennial Chair and Founding Director of the Quantum Information Center at the University of Texas at Austin, and (wait for it) new member of the US National Academy of Sciences, that august and distinguished body brought into being by President Abraham Lincoln in 1863.

Because, you know, none of this is about me. It’s only about you. And whether you’ll listen to me.

By Scott

Authors: Albert Atserias, Moritz Müller

We prove that the bounded arithmetic theory $S^1_2$ is consistent with EXP $\not\subseteq$ P/poly. More generally, we show that certain separations of $V^1_2$ from a theory $T$ imply the consistency of $T$ with EXP $\not\subseteq$ P/poly. For $T=S^1_2$, Takeuti (1988) established such a separation using a variant of Gödel's consistency statement. Analogous results hold for PSPACE $\not\subseteq$ P/poly but the required separations of theories are yet unknown. Finally, we give magnification results for the hardness of proving almost-everywhere versions of these lower bounds.

Authors: Jakub Jagiełła, Joachim Jelisiejew

We introduce the concise secant varieties, which are, informally speaking, modular partial desingularisations of secant varieties to Segre embeddings. More precisely, they are projective and birational to the abstract secant varieties, yet each of their points corresponds to a concise tensor of appropriate border rank (that is, to a minimal border rank tensor). We discuss implications throughout the theory of tensors, including a characterisation of border rank $\leq r$ tensors as unrestrictions of minimal border rank $r$ tensors (also in the Veronese and Segre-Veronese cases), a characterisation of tensors with cactus rank $\leq r$, concise versions of border apolarity including the fixed point theorem, concise Varieties of Sums of Powers, counting points on the second secant variety, connections to defectivity and identifiability in the Segre case, to the Salmon conjecture etc.

Authors: Yefan Zhi, Yao Lu, Masoud Akbarzadeh

Symmetry is an implicit objective in structural form-finding that often reconciles efficiency and aesthetics. This paper identifies the symmetry of polyhedral diagrams in three-dimensional graphic statics (3DGS) as point groups and formulates them as constraints, enabling the optimization and manipulation of polyhedral diagrams that preserve such symmetry. 3DGS has been an efficient and effective tool for the form-finding of funicular structures. However, when modifying complex diagrams for design exploration or optimization, one can easily break the symmetry of the reciprocal design input, rendering the result undesirable for practical use. To address this problem, this paper investigates symmetry transformations and introduces point groups, an abstract algebra tool commonly used in crystallography to represent the symmetry and equivalence between a network of atoms (points with labels). It then discusses the hierarchy of symmetry in the geometry types of a polyhedral diagram, and proposes the constraint of symmetry through edge lengths. Based on the crystal symmetry search algorithm by spglib and pymatgen, a fast fingerprinting algorithm is developed to identify the point group of a polyhedral diagram and sort equivalent edges into sets. Finally, the paper shows that the necessary and sufficient condition for preserving the point group symmetry is that each set of edges has the same length. This constraint is compatible with the algebraic formulation of 3DGS and effectively preserves symmetry while reducing the dimension of the solution space. The method is implemented in the PolyFrame 2 plug-in for Rhino and Grasshopper.

Authors: Sarita de Berg, Ivor van der Hoog, Eva Rotenberg, Johanne M. Vistisen, Sampson Wong

We maintain a $(1+\varepsilon)$-spanner over the disk intersection graph of a dynamic set of disks. We restrict all disks to have their diameter in $[4,Ψ]$ for some fixed and known $Ψ$. The resulting $(1+\varepsilon)$-spanner has size $O(n \varepsilon^{-2} \log Ψ\log (\varepsilon^{-1}))$, where $n$ is the present number of disks. We develop a novel use of persistent data structures to dynamically maintain our $(1+\varepsilon)$-spanner. Our approach requires $O(\varepsilon^{-2} n \log^4 n \log Ψ)$ space and has an $O( \left( \fracΨ{\varepsilon} \right)^2 \log^4 n \log^2 Ψ\log^2 (\varepsilon^{-1}))$ expected amortised update time. For constant $\varepsilon$ and $Ψ$, this spanner has near-linear size, uses near-linear space and has polylogarithmic update time. Furthermore, we observe that for any $\varepsilon < 1$, our spanner also serves as a connectivity data structure. With a slight adaptation of our techniques, this leads to better bounds for dynamically supporting connectivity queries in a disk intersection graph. In particular, we improve the space usage when compared to the dynamic data structure of (Baumann et al., DCG'24), replacing the linear dependency on $Ψ$ by a polylogarithmic dependency. Finally, we generalise our results to $d$-dimensional hypercubes.

Authors: Tian Bai, Fedor V. Fomin, Petr A. Golovach, Yash Hiren More, Simon Wietheger

Rank aggregation seeks a representative permutation for a collection of rankings and plays a central role in areas such as social choice, information retrieval, and computational biology. Two fundamental aggregation tasks are the center and median problems, which minimize the maximum and the total distance to the input permutations, respectively. While these problems are well understood under Kendall's tau and related distances, their parameterized complexity under the Ulam metric, an edit-distance-based metric on permutations, has remained largely unexplored. In this work, we initiate a systematic study of the parameterized complexity of rank aggregation under the Ulam metric. We consider both the center and median problems, as well as their generalizations to the $k$-center and $k$-median clustering settings, parameterized by the number of centers $k$ and the distance budget $d$ (corresponding to the maximum distance for center variants and the total distance for median variants). Both problems are known to be NP-hard already for $k=1$. We show that the Ulam $k$-center problem remains NP-hard when $d=1$, but is fixed-parameter tractable when parameterized by $k + d$. Our algorithm is based on a novel local-search framework tailored to the non-local nature of Ulam distances. We complement this by proving that no polynomial kernel exists for the $k+d$ parameterization unless NP $\subseteq$ coNP/poly. For the Ulam $k$-median problem parameterized by the total distance $d$, we establish W[1]-hardness and provide an XP algorithm. We also provide a polynomial kernel for the parameter $k + d$, which in turn yields a fixed-parameter tractable algorithm.

Authors: Benjamin Bergougnoux, Vera Chekan, Stefan Kratsch

In this work we contribute to the study of the fine-grained complexity of problems parameterized by multi-clique-width, which was initiated by Fürer [ITCS 2017] and pursued further by Chekan and Kratsch [MFCS 2023]. Multi-clique-width is a parameter defined analogously to clique-width but every vertex is allowed to hold multiple labels simultaneously. This parameter is upper-bounded by both clique-width and treewidth (plus a constant), hence it generalizes both of them without an exponential blow-up. Conversely, graphs of multi-clique-width $k$ have clique-width at most $2^k$, and there exist graphs with clique-width at least $2^{Ω(k)}$. Thus, while the two parameters are functionally equivalent, the fine-grained complexity of problems may differ relative to them. As our first and main result we show that under ETH the Max Cut problem cannot be solved in time $n^{2^{o(k)}} \cdot f(k)$ on graphs of multi-clique-width $k$ for any computable function $f$. For clique-width $k$ an $n^{\mathcal{O}(k)}$ algorithm by Fomin et al. [SIAM J. Comput. 2014] is tight under ETH. This makes Max Cut the first known problem for which the tight running times differ for parameterization by clique-width and multi-clique-width and it contributes to the short list of known lower bounds of form $n^{2^{o(k)}} \cdot f(k)$. As our second contribution we show that Hamiltonian Cycle and Edge Dominating Set can be solved in time $n^{\mathcal{O}(k)}$ on graphs of multi-clique-width $k$ matching the tight running time for clique-width. These results answer three questions left open by Chekan and Kratsch [MFCS 2023].

Authors: Johannes Breitling, Ragnar Groot Koerkamp, Marvin Williams

Priority queues are data structures that maintain a dynamic collection of elements and allow inserting new elements and removing the smallest element. The most widely known and used priority queue is likely the implicit binary heap, even though it is has frequent cache misses and is hard to optimize using e.g. SIMD instructions. We introduce the SimdQuickHeap, a variant of the QuickHeap that was introduced by Navarro and Paredes in 2010. As suggested by the name, the data structure bears some similarity to QuickSort. We modify the data layout of the original QuickHeap to have all \emph{pivots} adjacent in memory, with elements between consecutive pivots stored in dedicated \emph{buckets}. This allows efficient SIMD implementations for both partitioning of buckets and scanning the list of pivots to find the bucket to append newly inserted elements to. The SimdQuickHeap has amortized expected complexity $O(\log n)$ per operation, which improves to $O(\frac 1W\log n)$ in non-degenerate cases, where $W$ is the number of words in a SIMD register. In this case, the I/O-complexity is amortized $O(\frac 1B)$ per push and $O(\frac 1B \log_2 \frac nM)$ per pop. In synthetic benchmarks, the SimdQuickHeap is up to twice as fast as the next-best competitor, including the non-comparison radix heap, and needs around $1.5\log_2 n$ comparisons and $\log_2 n$ nanoseconds per pair of push and pop operations. On graph benchmarks with Dijkstra's shortest path algorithm and Jarnik-Prim's minimum spanning tree algorithm, the SimdQuickHeap is consistently the fastest.

Authors: Jesper Larsson Träff

Parallel scan primitives compute element-wise inclusive or exclusive prefix sums of input vectors contributed by $p$ consecutively ranked processors under an associative, possibly expensive, binary operator $\oplus$. In message-passing systems with bounded, one-ported communication capabilities, at least $\lceil\log_2 p\rceil$ or $\lceil\log_2 (p-1)\rceil$ send-receive communication rounds are required to perform the scans. While there are well-known, simple algorithms for the inclusive scan that solve the problem in $\lceil\log_2 p\rceil$ send-receive communication rounds with $\lceil\log_2 p\rceil$ applications of the $\oplus$ operator, the exclusive scan is different and has been much less addressed. By considering natural invariants for the exclusive prefix sums problem, we present two different algorithms that are efficient in the number of communication rounds and in the number of applications of the $\oplus$ operator. The first algorithm consists of an inclusive scan phase and an exclusive scan phase and trades the number of communication rounds against the number of applications of the $\oplus$ operator. The smallest number of inclusive scan rounds with $q=\lceil\log_2 p\rceil$ rounds in total is $q'\geq q-\log_2(2^q-p+1)$. The other algorithm is a modification of a round-optimal all-reduce algorithm, and the number of additional applications of the $\oplus$ operator is dependent on the number of bits set (popcount of) in $p-1$. Both algorithms are relevant for small(er) input vectors where performance is dominated by the number of communication rounds. For large input vectors, other (pipelined, fixed-degree tree) algorithms must be used.

Authors: Riccardo Dondi, Mohammad Mehdi Hosseinzadeh

This paper addresses the problem of identifying time interval separators in temporal networks. We introduce d-MinIntSep, a new variant of the temporal separator problem, which models failures as time intervals assigned to vertices and aims to block all temporal paths between a source and a target that can be completed within a given deadline d. We prove that the d-MinIntSep problem is NP-hard and hard to approximate within a logarithmic function of the size of the vertex set, assuming P is not equal to NP, and we propose an Integer Linear Programming (ILP) formulation to compute minimum interval separators. This latter method is evaluated on synthetic and real-world temporal networks derived from transportation datasets. The experimental results show that the running time is strongly influenced by the temporal dimension, the imposed deadline, and the density of temporal paths.

Authors: Afrouz Jabal Ameli, Tomohiro Koana, Jesper Nederlof, Shengzhe Wang

The Strongly Connected Steiner Subgraph (SCSS) problem is a well-studied network design problem that asks for a minimum subgraph that strongly connects a given set of terminals. In this paper, we present several new algorithmic and complexity results for SCSS. As our main result, we show that SCSS can be solved in time $17^{\mathrm{tw}} n^{O(1)}$ on directed graphs with $n$ vertices when a tree decomposition of the underlying graph of width $\mathrm{tw}$ is provided. This improves over a natural $\mathrm{tw}^{O(\mathrm{tw})}n^{O(1)}$ time algorithm, and is the first algorithm with this kind of running time for a problem involving strong connectivity. Second, we give an exact exponential-time algorithm that solves SCSS in $2^n n^{O(1)}$ time, improving the known bounds for general directed graphs. Finally, we investigate kernelization with respect to vertex cover. We prove that SCSS does not admit a polynomial kernel when parameterized by the size of a vertex cover, unless the polynomial hierarchy collapses. In contrast, we show that the closely related Strongly Connected Spanning Subgraph problem does admit a polynomial kernel under the same parameterization.

Authors: Georgios Stamoulis

We study the rainbow matching (RM) problem: given an edge-colored graph, find a maximum matching with at most one edge of each color. Rainbow matchings correspond to stable sets in the \emph{augmented} graph $H$ obtained from the line graph by completing each color class into a clique. For a hereditary graph class $\mathcal{X}$, we introduce the parameter $κ_{\mathcal{X}}$ to be the minimum number of colors whose deletion places the \emph{residual} augmented graph in $\mathcal{X}$. We show that this parameter has two complementary flavors. From a polyhedral side, if $\mathcal{X}$ is uniformly rank-$r$ exact, then deleting $k$ colors to obtain a residual augmented graph in $\mathcal{X}$ implies exactness of the Lasserre hierarchy at level $k+r$. This yields, in particular, exactness at level $k+1$ for deletion to perfect, and exactness at level $k+r$ for deletion to $h$-perfect residual graphs of bounded odd-hole rank $r$. Our second result is structural. We show that the right object in this case is the \emph{color-intersection} graph $Γ$ that impacts the topology of the conflict graph $H$ as follows: articulation colors in $Γ$ induce clique-sum decompositions in $H$, so residual obstructions for clique-sum-local hereditary classes $\mathcal{X}$ are embedded in individual blocks. Thus we can test membership of the residual graph in these target classes in a blockwise manner. As a consequence, we give an exact dynamic programming algorithm for computing the deletion parameter when $Γ$ has blocks of bounded size. Finally, once such a deletion set is given, RM can be solved by branching over the deleted color classes and solving residual instances. We also show that computing this parameter is \textbf{NP}-hard already in the chordal targets but it is FPT for classes $\mathcal{X}$ characterized by a set of forbidden induced subgraphs of bounded size.

Authors: Marco Bressan, T-H. Hubert Chan, Qipeng Kuang, Mauro Sozio

In recent years, the problem of computing the frequencies of the induced $k$-vertex subgraphs of a graph, or \emph{$k$-graphlets}, has become central. One approach for this problem is to sample $k$-graphlets randomly. Classic algorithms for $k$-graphlet sampling require loading the entire graph into main memory, making them impractical for massive graphs. To bypass this limitation, Bourreau et al. (NeurIPS 2024) introduced a \emph{streaming} algorithm that through nontrivial techniques makes only $O(\log n)$ passes using $O(n \log n)$ memory. In this work we break their $O(\log n)$-pass bound by giving an algorithm that, for any fixed $c>0$, makes $O(1/c)$ passes using $\tilde O(n^{1+c})$ memory. As a consequence of their lower bound, our algorithm is optimal up to a factor of $\tilde{O}(n^c)$ in the memory usage. We use this sampling algorithm to obtain an efficient method of approximating $k$-graphlet distributions. Experiments on real-world and synthetic graphs show that our algorithm is always at least as good as the one of Bourreau et al., and outperforms it by orders of magnitude on mildly dense graphs.

Authors: Benedikt Peterseim, Milan Lopuhaä-Zwakenberg

Discrete probabilistic programs (DPPs) provide a highly expressive formalism for compactly defining arbitrary finite probabilistic models. This expressivity comes at a price: DPP inference is PSPACE-hard. In this work, we show that DPP inference only takes polynomial time for programs that are 'structurally simple'. More precisely, inference can be performed in polynomial time when the primal graph of each function appearing in the probabilistic program has bounded treewidth, and the inverse acceptance probability is at most exponential in the size of the probabilistic program. Existing algorithms do not achieve this performance guarantee. Our method relies on finding suitable decompositions, algebraisations, of the string diagrams underlying DPPs, employing existing algorithms for tree decompositions. This is independent of the probabilistic setting of DPPs and has direct applications to many problems, such as evaluating queries on relational databases and cybersecurity risk assessment via attack trees.

Authors: Eric Balkanski, Jason Chatzitheodorou, Flore Sentenac

For the classical maximum coverage problem, the greedy algorithm achieves a worst-case $1-1/e$ approximation, which is optimal unless $\text{P} = \text{NP}$. The notion of coverage appears in a wide range of optimization tasks, where empirical evaluations indicate approximation ratios close to $1$ for the greedy algorithm on real data. Random models have provided average-case justifications for the empirical performance of many well-known algorithms, but little is known about the average-case performance of greedy for maximum coverage. We analyze the expected approximation ratio of the greedy algorithm in a random model, which we call the left-regular random model. We first show that, for all parameter settings of this model, the expected approximation ratio of the greedy algorithm improves by a constant over its worst-case $1-1/e$ guarantee. We then identify two simple conditions, either of which ensures that the expected approximation ratio is close to $1$ for sufficiently large graphs. Finally, we show that there is a regime where greedy does not achieve an expected approximation better than $0.94$. To obtain these results, we develop analytical tools, including a novel application of the differential equation method and a connection to maximum matching in Erdős-Rényi graphs, which may be of independent interest for other random models.

Good news: Email from Knuth. Bad news: It begins “is there a bug in your paper?” The paper in question is “The traveling salesman problem for cubic graphs” (WADS 2003 and JGAA 2007). Of course the bug report is accurate, but fortunately it can be easily patched.

My paper has algorithms for finding a minimum-weight Hamiltonian cycle (when it exists), in an \(n\)-vertex graph of maximum degree three, in time \(O(2^{n/3})\), and for listing all Hamiltonian cycles in time \(O(2^{3n/8})\). Both have since been improved by others. Maciej Liśkiewicz and Martin R. Schuster gave an algorithm for the minimum-weight cycle with time \(O(1.2553^n)\) in their paper “A new upper bound for the traveling salesman problem in cubic graphs” [J. Discrete Algorithms 2014], and Heidi Gebauer gave an algorithm for listing all cycles in time \(O(1.276^n)\) in her paper “Enumerating all Hamilton cycles and bounding the number of Hamilton cycles in 3-regular graphs” [Elect. J. Combinatorics 2011]. Despite these improvements, I think it’s interesting enough to examine what the issue was with my paper and how to work around it.

The bug is in the case analysis for the algorithm to list all Hamiltonian cycles. The minimum-weight algorithm includes a case where a triangle is contracted into a single vertex. However, for some reason the cycle-listing algorithm omitted that case, and then later tried to assume there were no triangles, but without a valid justification for this assumption. It’s not impossible that the rest of the analysis goes through without using the assumption of no triangles, but working out the details looks messy.

Both algorithms in the paper work with a more general problem in which, together with an input graph, one is given “forced edges” which are required to be included in any Hamiltonian cycle. This allows certain simplifications in which, for instance, paths through degree-two vertices or paths of multiple forced edges can be compressed into single forced edges. It’s important when listing cycles that the input is a simple graph, not a multigraph, because multigraphs can have as many as \(O(2^{n/2})\) Hamiltonian cycles. So, when this sort of compression produces a forced edge that’s parallel to an unforced edge, the unforced edge can be deleted, and when it produces two parallel forced edges, there can be no Hamiltonian cycle and the algorithm backtracks. After these simplifications, one can assume that the graph is simple and 3-regular rather than merely having maximum degree three, and that no two forced edges are adjacent. But it might still have some triangles.

With that as background, it is indeed possible to eliminate the triangles. Here are the missing cases to do so.

• If a triangle includes a forced edge, then the opposite edge entering the triangle should also become forced. (The paper included a case with the opposite implication, but this direction is needed to preserve the forcing information after the contraction of a triangle, below.) So in the image below, if either of the two thick edges is forced, the other one should be too.

• If there exists a triangle that does not share any of its edges with another triangle, contract it. Hamiltonian cycles in the contracted graph correspond one-for-one with Hamiltonian cycles in the uncontracted graph, and (with no shared edges) this contraction will not create any parallel edges.

• If there exist two triangles that share an edge, then there are two paths through their four vertices that might extend to Hamiltonian cycles. If only one of these two paths is consistent with the forced edges within this subgraph, add the rest of its edges to the forced set; their contraction will eliminate the triangles. Otherwise, make two recursive branches, each with one of the two paths added to the forced set. Each branch eliminates four previously-unforced edges, consistent with the analysis of the other cases in this part of the paper.

As far as I know, another problem from the same paper remains open. The paper constructs a family of cubic graphs that have \(2^{n/3}\) Hamiltonian cycles, but the cycle-listing algorithm proves only that the number of cycles is always \(O(2^{3n/8})\), a bigger number. Gebauer’s paper improves the upper bound, but it still does not match the lower bound. Is \(2^{n/3}\) the maximum number of Hamiltonian cycles in an \(n\)-vertex 3-regular graph?

(Discuss on Mastodon)

By David Eppstein

June 14-18, 2026 Hebrew University, Israel https://iias.huji.ac.il/event/25th-midrasha-mathematicae-groups-expanders-and-codes In the past few years, there has been several exciting developments at the confluence of pure mathematics and theoretical computer science. These include: The refutations of Connes’ embedding problem and the Aldous–Lyons conjecture using tools from group stability, complexity theory and quantum information theory. The construction of good … Continue reading Groups, Expanders and Codes – Celebrating the 70’s birthday of Alex Lubotzky

By shacharlovett

Authors: Nirmit Joshi, Roey Magen, Nathan Srebro, Nikolaos Tsilivis, Gal Vardi

We study learning with Chain-of-Thought (CoT) supervision from multiple thinkers, all of whom provide correct but possibly systematically different solutions, e.g., step-by-step solutions to math problems written by different thinkers, or step-by-step execution traces of different programs solving the same problem. We consider classes that are computationally easy to learn using CoT supervision from a single thinker, but hard to learn with only end-result supervision, i.e., without CoT (Joshi et al. 2025). We establish that, under cryptographic assumptions, learning can be hard from CoT supervision provided by two or a few different thinkers, in passive data-collection settings. On the other hand, we provide a generic computationally efficient active learning algorithm that learns with a small amount of CoT data per thinker that is completely independent of the target accuracy $\varepsilon$, a moderate number of thinkers that scales as $\log \frac{1}{\varepsilon}\log \log \frac{1}{\varepsilon}$, and sufficient passive end-result data that scales as $\frac{1}{\varepsilon}\cdot poly\log\frac{1}{\varepsilon}$.

Authors: Olivier Bournez

What do recurrent neural networks, polynomial ODEs, and discrete polynomial maps each bring to computation, and what do they lack? All three operate over the continuum--real-valued states evolved by real-valued dynamics--even when the target functions are discrete. We study them through primitive recursion. We prove that primitive recursion admits equivalent characterizations in all three frameworks: bounded iteration of a fixed recurrent ReLU network, robust computation by a fixed polynomial ODE, and iteration of a fixed polynomial map with an externally supplied step-size parameter. In each, the time bound is itself primitive recursive, composition emerges from the dynamics rather than as a closure rule, and inputs are raw integer vectors. Every primitive recursive function is first compiled into bounded iteration of a single threshold-affine normal form, then interpreted as a ReLU computation and as a polynomial ODE. The equivalences expose a structural asymmetry: no fixed polynomial map can round uniformly to the nearest integer or realize exact phase selection--operations polynomial ODEs perform robustly via continuous-time flow. Each formalism compensates for a limitation the others lack: the ReLU gate provides exact branching, continuous time provides autonomous rounding and control, and the step-size parameter recovers both at the cost of discretization precision. This opens dynamical characterizations of subrecursive hierarchies and complexity classes by restricting time bounds, polynomial degrees, or discretization resources within one framework. More broadly, these models do not compute by composing subroutines: they shape the trajectory of a dynamical system through clocks, phase selectors, and error correction built into the dynamics. This differs structurally from symbolic programming, and our theorem gives a precise framework to study the difference.

Authors: Srijan Chakraborty, Samir Datta, Aryan Kusre, Partha Mukhopadhyay, Amit Sinhababu

Understanding the power of space-bounded computation with access to catalytic space has been an important theme in complexity theory over the recent years. One of the key algorithmic results in this area is that bipartite maximum matching can be computed in catalytic logspace with a polynomial-time bound, Agarwala and Mertz (2025). In this paper, we show that we can construct a \emph{maximum matching} in \emph{general graphs} in CL, and, in fact, in CLP. We first show that the size of a \emph{maximum matching} in \emph{general graphs} can be determined in CL. Our algorithm is based on the linear-algebraic algorithm for maximum matching by Geelen (2000). We then show that this algorithm, along with some new ideas, can be used to \emph{find} a maximum matching in general graphs. Using a similar algorithm of Geelen (1999), we also solve the \emph{maximum rank completion problem} in CLP, which was previously known to be solvable in deterministic polynomial time, Geelen. This problem turns out to be equivalent to the \emph{linear matroid intersection} problem (shown by Murota, 1995) which has been shown to be in CLP by Agarwala, Alekseev, and Vinciguerra (2026). Finally, using a PTAS algorithm Bläser, Jindal and Pandey (2018), for approximating the rank in Edmond's problem, we derive a CLP algorithm that can approximate the rank given by any instance of the \emph{Edmond's problem} upto a factor of $(1-\eps)$ for any $\eps\in(0,1)$. An application of this is a CLP bound for approximating the maximum independent matching in the \emph{linear matroid matching} problem.

Authors: Marius Bozga, Radu Iosif, Florian Zuleger

Series-parallel (SP) graphs are binary edge-labeled graphs with a designated source and target vertex, built using serial and parallel composition. A set of graphs is recognizable if membership depends only on its image under a homomorphism into a finite algebra. For SP-graphs, and more generally, for graphs of bounded tree-width, recognizability coincides with definability in Counting Monadic Second-Order (CMSO) logic. Despite this strong logical characterization, the conciseness and algorithmic effectiveness of syntactic representations of recognizable sets of SP (and bounded-tree-width) graphs remain poorly understood. Building on previously introduced regular grammars for SP-graphs, we show that recognizable sets admit concise and effective syntactic representations. The main contribution is an improved construction of finite recognizer algebras whose size is singly-exponential in the size of a regular grammar, improving upon the previously known double-exponential bound. As a consequence, the problems of intersection and language inclusion for sets represented by regular grammars are shown to be ExpTime-complete, thus improving on a previously known 2ExpTime upper bound.

Authors: Aleksandr Koshkarov, Nadia Tahiri

Comparative analyses of phylogenetic trees typically require identical taxon sets, however, in practice, trees often include distinct but overlapping taxa. Pruning non-shared leaves discards phylogenetic signal, whereas tree completion can preserve both taxa and branch-length information. This work introduces a polynomial-time algorithm for set-wide completion of phylogenetic trees with partial taxon overlap. The proposed method identifies and extracts maximal completion subtrees that frequently appear across the source trees and constructs a weighted majority-rule consensus. Branch lengths are scaled using rates derived from common leaves. Each consensus subtree is inserted at the position that minimizes the quadratic distance error measured against information from the source trees, with candidate positions restricted to the original branches of the target tree. We demonstrate that the algorithm runs in polynomial time and preserves distances among the original taxa, yielding a unique completion that is order-independent with respect to the processing order of target trees. An experimental evaluation on amphibians, mammals, sharks, and squamates shows that the proposed method consistently achieves the lowest distance to the subset reference trees across subsets among all methods, in both topology and branch lengths. An open-source Python implementation of the proposed algorithm and the biological datasets utilized in this study are publicly available at: https://github.com/tahiri-lab/overlap-treeset-completion/.

Authors: Marco Carmosino, Ngu Dang, Tim Jackman

Gate elimination is the primary technique for proving explicit lower bounds against general Boolean circuits, including Li and Yang's state-of-the-art $3.1n - o(n)$ bound for affine dispersers (STOC 2022). Every circuit lower bound is implicitly existential: every circuit that is too small to compute $f$ must err on some input. This raises a natural question: are these lower bounds \emph{constructive}? That is, can we efficiently produce such errors? Chen, Jin, Santhanam, and Williams showed that constructivity plays a central role in many longstanding open problems in complexity theory, and explicitly raised the question of which circuit lower bound techniques can be made constructive (FOCS 2021). We show that a variety of gate elimination arguments yield refuters -- efficient algorithms that, when given a circuit that is too small to compute a function $f$, produce an input on which the circuit errs. Our results range from elementary lower bounds for $XOR$ and the multiplexer to more sophisticated arguments for affine dispersers. Underlying these results is a shift in perspective: gate elimination arguments \emph{are} algorithms. Each step either simplifies the circuit or reveals a violation of some structural or functional property, from which, with a little additional work, explicit counterexamples can be extracted. We further strengthen the $XOR$ result to handle circuits that \emph{match} the lower bound: given any DeMorgan circuit of size $3(n-1)$ that fails to compute $XOR_n$, we can efficiently produce a counterexample. While refuters follow from the gate elimination arguments themselves, this refinement requires a complete characterization of the set of optimal circuits computing $XOR$ -- a requirement rarely met by other explicit functions.

Authors: Arnaud Casteigts, Christian Komusiewicz, Nils Morawietz

Temporal graphs are graphs whose edges are only present at certain points in time. Reachability in these graphs relies on temporal paths, where edges are traversed chronologically. A temporal graph that offers all-pairs reachability is said to be temporally connected (or TC). For temporal graphs that are not TC, a natural question is whether they admit a TC subgraph (a.k.a. closed temporal component) of a given size $k$. This question was one of the earliest in the field, shown to be NP-hard by Bhadra and Ferreira in 2003. We strengthen this result dramatically, showing that deciding if a TC subgraph exists on at least $3$ vertices is already NP-hard in all the standard temporal graph settings (directed/undirected and strict/non-strict through simple and proper reductions). This implies a strong separation between closed temporal components and open temporal components (where temporal paths can travel outside the component), for which inclusion-maximal components can be found in polynomial time. As a by-product, our reductions strengthen a number of existing results and establish new derived results. They imply that the size of the largest TC subgraph cannot be approximated within a factor of $(1-ε)n$ in directed graphs, and within a factor of $(1-ε)\frac{n}{2}$ in undirected graphs. One of the reductions also completes the complexity landscape for TC subgraphs of size exactly $k$ when parameterized by $k$ (answering the missing non-strict case). Finally, on the structural side, our results imply that there exist arbitrarily large TC graphs of constant lifetime without nontrivial TC subgraphs, and we also show that there exist TC graphs of arbitrary girth, both facts being of independent interest.

Authors: Kenta Watanabe

For a smooth irreducible curve $C$, its second gonality $d_2$ is defined to be the minimum integer $d$ such that $C$ admits a linear series $g_d^2$. In this paper, we compute the second gonality of a smooth aCM curve $C$ lying on a smooth quartic surface in $\mathbb{P}^3$, whose Clifford index is computed by a net on $C$.

Authors: Jacobus Conradi, Ivor van der Hoog, Frederikke Uldahl, Eva Rotenberg

The Fréchet distance is a popular distance measure between trajectories or curves in space, or between walks in graphs. We study computing the Fréchet distance between walks in the $d$-dimensional grid graphs, i.e. $\mathbb{Z}^d$ where points share an edge if they differ by one in one coordinate. We give an algorithm, that for two simple paths on $n$ vertices, $(1+\varepsilon)$-approximates the Fréchet distance in time $\widetilde{O}((\frac{n}{\varepsilon})^{2-2/d} +n)$. We complement this by a near-matching fine-grained lower bound: for constant dimensions $d \geq 3$, there is no $O((\varepsilon^{2/d}(\frac{n}{\varepsilon})^{2-2/d})^{1-δ})$ algorithm for any $δ>0$ unless the Orthogonal Vector Hypothesis fails. Thus, our results are tight up to a factor $\varepsilon^{2/d}$ and $\log(n)$-factors. We extend our results to imbalanced lower and upper bounds, where the curves have $n$ and $m$ vertices respectively, and also obtain near-tight bounds. Driemel, Har-Peled and Wenk [DCG'12] studied \emph{realistic assumptions} for curves to speed up Fréchet distance computation. One of these assumptions is $λ$-low density and they can compute a $(1+\varepsilon)$-approximation between $λ$-low dense curves in time $\widetilde{O}( \varepsilon^{-2} λ^2 n^{2(1-1/d)})$. By adapting our lower bound, we show that their algorithm has a tight dependency on $n$ and a tight dependency on $\varepsilon$ as $d$ goes to infinity. A gap remains in terms of $λ$.

Authors: Daniel Bertschinger, Henry Förster, Fabian Klute, Irene Parada, Patrick Schnider, Birgit Vogtenhuber

We study the common intersection of arrangements of double-wedges. We consider arrangements where double-wedges may be either bowties (which do not contain a vertical line) or hourglasses (which contain a vertical line), in contrast to earlier studies that focused on arrangements of only bowties. This generalization changes the setting drastically, in particular, with respect to all arguments involving the point-line duality. Namely, a point in the intersection of all double-wedges is equivalent to a line that stabs a set of segments $\mathcal{S}$ (corresponding to the bowties) while it avoids a different set of segments $\mathcal{A}$ (corresponding to the complement of the hourglasses). We show that in this general setting, the intersection of $n$ double-wedges may consist of $Ω(n^2)$ interior-disjoint regions. Further, we discuss Gallai-type results for arrangements of segments and anti-segments, and we provide algorithms for computing the intersection of such arrangements with worst-case optimal running time. Finally, we also prove that we can find a single intersection point in almost optimal running time, assuming that 3SUM admits no truly subquadratic-time algorithm.

Authors: Sariel Har-Peled

Consider a stream of $n$ random points (say, from the unit square) arriving one by one, where a player has to make an irreversible immediate decision for each arriving point whether to pick it. The player has to pick a single point, and the payoff is the area of the cell of the picked point, in the final Voronoi diagram of \emph{all} the points. We show that there is a simple strategy so that with probability $\geq 1 - \tilde O(1/\sqrt{n})$, the player's payoff is only a constant factor smaller than the optimal choice (i.e., the one made by the prophet). This competitiveness is somewhat surprising, as this payoff is larger by a factor of $Θ( \log n)$ than the average payoff.

Authors: Petr A. Golovach, Laure Morelle, Daniël Paulusma

An identification of two vertices $u$ and $v$ in a graph replaces them with a new vertex whose neighborhood is the union of the neighborhoods of $u$ and $v$. We study the {\sc ${\cal H}$-Identification} problem, which is to decide whether a given graph $G$ can be transformed (``identified'') to a graph in ${\cal H}$ by applying at most $k$ vertex identifications. We determine the classical and parameterized complexity of this problem for various subclasses ${\cal H}$ of chordal graphs, obtaining an almost complete picture for two parameters: $k$ and $n-k$. We also consider the {\sc Identification} problem, which is to test for two given graphs $G$ and $H$ if $G$ can be identified to $H$. We determine the parameterized complexity of this problem when $H$ is a graph from one of our testbed classes, taking the number of simplicial vertices of $H$ as the parameter.

Authors: Tala Eagling-Vose, Barnaby Martin, Daniël Paulusma, Nicolas Trotignon

We consider the $H$-Induced Minor problem: for a fixed graph~$H$, decide whether a given graph $G$ contains $H$ as an induced minor. While the problem is known to be NP-complete for some trees~$H$ on more than $2^{300}$ vertices, the complexity for small trees remains unresolved. In particular, the case where $H$ is the $7$-vertex tree consisting of a path on five vertices with a pendant vertex attached to the second and fourth vertex was a long-standing open problem. We show that this case is polynomial-time solvable by developing algorithms that detect a sequence of carefully chosen substructures. Complementing this, we prove that detecting some of these substructures individually is NP-hard. We also give polynomial-time algorithms for three cases where $H$ is a graph on five vertices (that is not a tree). In this way, we completed the classification of $H$-Induced Minor for graphs $H$ on five vertices and answered an open problem of Dallard, Dumas, Hilaire and Perez (2025).

Authors: Mark de Berg, Bart M. P. Jansen, Jeroen S. K. Lamme

We study SINGLE-SOURCE SHORTEST PATH (SSSP) on unweighted intersection graphs whose node set corresponds to a set of $n$ constant-complexity objects in the plane. We prove SSSP can be solved in $O(U(n)\ \mathrm{polylog}\,n)$ expected time for any class of objects whose union complexity is $U(n)$. In particular, we obtain an $O(n 2^{α(n)}\log^2 n)$ algorithm for arbitrary pseudodisks, and an $O(λ_{s+2}(n)2^{O(\log^* n)} \log^2 n)$ algorithm for locally fat objects. This significantly extends the class of objects for which SSSP can be solved in $O(n\ \mathrm{polylog}\, n)$ time: so far, $O(n\ \mathrm{polylog}\, n)$ SSSP algorithms were not even known for pseudodisks that are fat and convex and similarly-sized. Our second result concerns the DIAMETER problem, which asks for the maximum distance between any two nodes in a graph. Even for intersection graphs, near-quadratic algorithms are difficult to obtain, and the $O(n^2\ \mathrm{polylog}\, n)$ running time that follows from our SSSP algorithm is the first near-quadratic running time for such general classes of intersection graphs. Obtaining subquadratic running time is even more challenging. We prove that the diameter of a set of arbitrary pseudodisks can be computed almost exactly, namely up to an additive error of 2, in $\tilde{O}(n^{2-1/14})$ expected time. This generalizes and speeds up a recent algorithm by Chang, Gao, and Le~(SoCG 2024) that works for similarly-sized disks (or similarly-sized pseudodisks that are fat and satisfy a strong monotonicity assumption) and runs in $\tilde{O}(n^{2-1/18})$ time. To this end, we develop a so-called star-based $r$-clustering for intersection graphs of pseudodisks, which is interesting in its own right. Our star-based $r$-clustering can also be used to obtain an almost exact distance oracle for pseudodisks that uses $O(n^{2-1/13})$ storage and has $O(1)$ query time.

Authors: Jugal Garg, Shayan Taherijam, Vijay V Vazirani

Our main contribution is a strongly polynomial algorithm for computing an equilibrium for the Arctic Auction, which is the quasi-linear extension of the linear Fisher market model. We build directly on Orlin's strongly polynomial algorithm for the linear Fisher market (Orlin, 2010). The first combinatorial polynomial algorithm for the linear Fisher market was based on the primal-dual paradigm (Devanur et al., 2008). This was followed by Orlin's scaling-based algorithms. The Arctic Auction (Klemperer 2018) was developed for the Government of Iceland to allow individuals to exchange blocked offshore assets. It is a variant of the product-mix auction (Klemperer 2008, 2010, 2018) that was designed for, and used by, the Bank of England, to allocate liquidity efficiently across banks pledging heterogeneous collateral of varying quality. Our work was motivated by the fact that banks often need to run Arctic Auctions under many different settings of the parameters in order to home in on the right one, making it essential to find a time-efficient algorithm for Arctic Auction.

Authors: Petr A. Golovach, Diptapriyo Majumdar, Saket Saurabh

Given a connected undirected graph $G$, a spanning tree is a subgraph $T$ of $G$ such that $V(T) = V(G)$ and $T$ is a tree. A collection of $\ell$ spanning trees $T_1,\ldots,T_\ell$ is pairwise $k$-diverse if for every $i \neq j$, $|E(T_i) \triangle E(T_j)| \geq k$. Given a connected undirected graph $G$ and integers $p, q, k, \ell$, Leaf & Internal-Constrained Diverse Spanning Trees asks whether there are $\ell$ distinct spanning trees $T_1,\ldots,T_{\ell}$ of $G$ that are pairwise $k$-diverse such that each tree has at least $p$ leaves and at least $q$ internal vertices. Similarly, Leaf & Non-terminal-Constrained Diverse Spanning Trees takes a connected undirected graph $G$, $V_{NT}\subseteq V(G)$, and three integers $p, k, \ell$, and asks if $G$ has $\ell$ spanning trees that are pairwise $k$-diverse, and each has at least $p$ leaves and conains the vertices of $V_{NT}$ as internal. We consider these two problems from the kernelization perspective and provide polynomial kernels for Leaf & Internal-Constrained Diverse Spanning Trees and Leaf & Non-terminal-Constrained Diverse Spanning Trees, when parameterized by $p + q + k + \ell$ and $p + |V_{\rm NT}| + k + \ell$, respectively.

Authors: Yuexin Su, Chenyi Zhang, Peiyuan Huang, Tongyang Li, Yinyu Ye

Computing approximate Karush--Kuhn--Tucker (KKT) points for constrained nonconvex programs is a fundamental problem in mathematical programming. Interior-point trust-region (IPTR) methods are particularly attractive for such problems because they maintain strictly feasible iterates throughout the iterative process and converge to a first-order and second-order KKT solution. Their scalability, however, is limited by the repeated computation of trust-region search directions. In this paper, we propose an approximate first-order IPTR framework that addresses this bottleneck by replacing exact trust-region subproblem solves with an approximate projector maintained through low-rank updates. The resulting method preserves feasibility and the global convergence guarantees of standard IPTR schemes while substantially reducing the per-iteration cost. We further extend the framework to obtain approximate second-order KKT points using only first-order information by integrating a gradient-based negative-curvature routine, thus avoiding explicit Hessian computations. We conduct numerical experiments to demonstrate the scalability of our approximate first-order IPTR framework in large-scale settings, where it achieves up to a $2.48\times$ speedup over the existing first-order IPTR algorithm.

Authors: Paweł Rafał Bieliński, Marta Piecyk, Paweł Rzążewski

The complexity of classical computational problems in graph classes defined by forbidding induced subgraphs is one of the central topics of algorithmic graph theory. Recently, there has been a growing interest in the complexity of such problems in ordered graphs, i.e., graphs with a fixed linear ordering of vertices. Such an approach allows us to investigate the boundary of tractability more closely. However, most results so far concern coloring problems. In this paper, we focus on the complexity of the Maximum Weight Independent Set (MWIS) problem in classes of ordered graphs. For every ordered graph $H$, we classify the complexity of MWIS in ordered graphs that exclude $H$ as an induced subgraph into one of the following cases: (1) solvable in polynomial time, (2) solvable in quasipolynomial time, (3) solvable in subexponential time, (4) NP-hard. Notably, case (3) contains only one well-structured family of $H$ obtained from two nested edges by adding isolated vertices in a specific way. Thus, our results yield an almost complete complexity dichotomy for MWIS in classes of ordered graphs defined by a single forbidden induced subgraph into cases solvable in quasipolynomial time and those that are NP-hard.

Authors: Luca Becchetti, Andrea Clementi, Luciano Gualà, Emanuele Natale, Luca Pepè Sciarria, Alessandro Straziota

The Approximate Near Neighbor (ANN) problem is a cornerstone in high-dimensional data analysis, with applications ranging from information retrieval to data mining. Among the most successful paradigms for solving ANN in high-dimensional metric spaces is Locality Sensitive Hashing (LSH), alongside the more recent Locality Sensitive Filtering (LSF). Since the seminal work of Indyk and Motwani, literature has expanded into a complex landscape of variants, often presented under different perspectives and adopting different notation. In this work, we address the technical challenge of navigating this landscape, by providing a self-contained, unified view of the essential algorithmic ingredients governing LSH-based and LSF-based solutions for angular distance -- a case of particular relevance in modern applications. In doing so, we touch on deep connections between LSF and LSH strategies. Our contribution is twofold. First, we design and analyze an LSF-based data structure for the Angular ANN problem, serving as a "guided tour" through fundamental techniques and results in the area. Second, we provide a streamlined analysis that, piecing together technical ingredients and results appeared throughout previous literature, proves optimality of the proposed data structure. In doing so, we revisit and strengthen a key technical lemma central to this body of work. The result is a critical and cohesive review that identifies core mechanisms of proximity search, offering both a streamlined entry point for researchers and a refined perspective on the state of the art.

Authors: Nguyen Khoa Tran, Lin Mu, Martin Papenberg, Gunnar W. Klau

The $k$-Maximum Dispersion Problem with Cardinality Constraints ($k$-MDCC) asks for a partition of a given item set with pairwise dissimilarities into $k$ cardinality-constrained groups such that the minimum pairwise intra-group dissimilarity, which is also known as the dispersion, is maximized. The problem arises in the context of anticlustering, where the goal is to create maximally heterogeneous groups of items with applications in psychological research, bioinformatics, and data science. It is known that $k$-MDCC is NP-hard for $k \geq 3$ but it has been an open question whether it can be solved in polynomial time for $k = 2$. We give a positive answer to this question by showing that $2$-MDCC can be solved by a quadratic number of cardinality-constrained 2-coloring problem instances ($2$-COLCC). We solve these instances by transforming them into a restricted class of subset sum instances. Although subset sum is NP-complete in general, for this restricted class the input values are bounded, ensuring that the pseudopolynomial dynamic programming algorithm runs in polynomial time. As a consequence, we obtain a polynomial-time algorithm for $2$-MDCC. We demonstrate that a publicly available open-source implementation of our new algorithm outperforms the previous integer linear programming solution by several orders of magnitude so that even large datasets ($n = 10{,}000$) can be processed in less than a second.

Authors: Simeon Pawlowski, Vincent Froese

We study an interval ordering problem introduced by Dürr et al. [Discrete Appl. Math. 2012] which is motivated by applications in bioinformatics. The task is to order a given set of n intervals with the goal of minimizing a certain objective which is defined via a given cost function $f$ which assigns a cost to the exposed part of each interval (that is, the pieces not covered by previous intervals). We develop a dynamic programming approach which solves the problem with $O(2^n\text{poly}(n))$ oracle calls to $f$ and arithmetic operations. Moreover, our approach yields polynomial-time algorithms for all cost functions $f$ such that $f-f(0)$ is subadditive or superadditive. This answers an open question for the function $f(x)=2^x$. We contrast these results by proving a running time lower bound of $2^{n-1}$ for any algorithm that solves the problem for every function $f$ (with oracle access only) and further proving NP-hardness for very restricted classes of functions. Thus, we significantly narrow the gap regarding the computational complexity of the problem.

Authors: Marta Piecyk, R. B. Sandeep

Subdividing an edge $uv$ in a graph replaces it by a path $u w v$ with one new vertex. For a graph $H$, the \textsc{$H$-free Subdivision} problem asks whether, given a graph $G$ and an integer $k$, one can destroy all induced copies of $H$ in $G$ by at most $k$ edge subdivisions. We show that the problem is polynomial-time solvable when every component of $H$ is a subdivided star or a subdivided bistar, and at most one component is a subdivided bistar. On the other hand, we prove that \textsc{$H$-free Subdivision} is NP-complete and, assuming the Exponential Time Hypothesis, admits no $2^{o(k)} n^{O(1)}$-time algorithm whenever $H$ satisfies any of the following conditions: \begin{itemize} \item $H$ has minimum degree at least $2$, and the neighborhood of every degree-$2$ vertex induces a $K_2$; \item the vertices of degree at least $3$ in $H$ induce a graph with at least two edges; \item $H$ has a triangle with two vertices of degree at least $3$; \item $H$ contains, as an induced subgraph, the graph obtained from two vertex-disjoint triangles by adding one edge between them; \item $H$ contains exactly one triangle; \item $H$ has girth at least $4$; \item $H$ is a tree with exactly two vertices of degree at least $3$ at distance $2$ or at least $4$. \end{itemize} A simple bounded search-tree algorithm for the problem runs in $2^{O(k)} n^{O(1)}$ time. Thus, for all hardness cases above, this running time is essentially optimal under ETH.

Authors: Arnaud Casteigts, Hendrik Molter, Meirav Zehavi

Temporal graphs have edge sets that change over discrete time steps. Such graphs are temporally connected (TC) if all pairs of vertices can reach each other using paths that traverse the edges in a time-respecting way (temporal paths). Given a TC temporal graph it, a natural question is to find a minimum spanning subgraph of it that preserves temporal connectivity. These structures, known as temporal spanners, are fundamental and their properties (especially size) have been studied thoroughly in the past decade. In particular, the problem of minimizing the size of a temporal spanner is known to be hard. However, the existing results establish hardness for several incomparable settings and versions of the problem. In this article, we unify and strengthen these results by showing that this problem is NP-hard even on temporal graphs that are simple and proper (also known as "happy"), i.e., where every edge appears only one time, and a vertex cannot be incident to several edges simultaneously. Proving hardness in this extremely restricted setting implies, at once, that the problem is NP-hard for all the previously considered settings and versions of the problem, resolving Open Question 4 in [Casteigts et al. TCS, 2024]. We also initiate the parameterized study of this problem, showing that in the happy setting, the problem can be solved in polynomial time if the underlying graph has a constant-size vertex cover, this result being actually the first positive result on temporal spanners in general. We also show that in the non-happy setting, the problem is W[1]-hard when parameterized by the feedback vertex number of the underlying graph.

Authors: Ivor van der Hoog, John Iacono, Eva Rotenberg, Daniel Rutschmann

A heap is a dynamic data structure that stores a set of labeled values under the following operations: pop returns the minimum value of the heap, Push($x_i$) pushes a new value $x_i$ onto the heap, and DecreaseKey($i$, $v$) decreases the value $x_i$ to $v$. A working-set heap is a heap that supports the $x_i \gets$ pop$()$ operation in $O(\log Γ(x_i) )$ time where $Γ(x_i)$ is the size of the \emph{working set}: the number of elements that were pushed onto the heap while $x_i$ was in the heap. The goal of working set heap design is to maintain the working set property while minimizing the overhead of the Push and DecreaseKey operations. On a word RAM, there exist working set heaps that support Push and DecreaseKey in amortized constant time. In this paper, we show via a simple construction that pointer machines, one of the most general and least-assuming computational models, support working set heaps that support Push in amortized constant time and DecreaseKey in inverse-Ackermann time. A by-product of this analysis is that Dijkstra's shortest path algorithm can be near-universally optimal on a pointer machine -- incurring only an additive $O(m \, α(m))$ overhead compared to the optimal running time for distance ordering, where $m$ denotes the number of edges in the graph.

Authors: Jean Cardinal, Kevin Mann, Akira Suzuki, Takahiro Suzuki, Yuma Tamura, Xiao Zhou

We initiate the study of the shortest reconfiguration problem for independent sets under the adjacency relation derived from the independent set polytope. Given a graph and two independent sets, the problem asks for a shortest sequence transforming one into the other such that the subgraph induced by the symmetric difference of any two consecutive sets is connected. This is equivalent to finding a shortest path on the $1$-skeleton of the independent set polytope. We prove that the problem is NP-hard even on planar graphs of bounded degree, as well as on split graphs. Notably, the hardness for planar graphs of bounded degree still holds even when deciding whether the target can be reached in at most two steps. For split graphs, we further show the W[2]-hardness when parameterized by the number of steps, as well as the inapproximability of the optimal length. As a consequence, we prove that the length of a shortest path between two vertices of a 0/1 polytope in $\mathbb{R}^n$ described by $O(n)$ linear inequalities is hard to approximate within a factor of $(1-\varepsilon)\ln n$ for any constant $ε>0$, unless $P=NP$. On the positive side, we provide polynomial-time algorithms for block graphs, cographs, and bipartite chain graphs. Moreover, for paths and cycles, we show that the optimal length of the shortest reconfiguration sequence exactly matches a trivial upper bound.

Authors: Yuda Feng, Weijiang Hu, Shi Li

We propose a new convex programming relaxation for the weighted Nash social welfare (NSW) problem that achieves a matching $(e^{1/e}\approx 1.445)$-approximation via the rounding algorithm of Feng and Li. Unlike the exponential-size configuration LP used in prior work, our formulation can be converted into a compact linear program of polynomial size, incurring only an additive loss of $\ln(1+ε)$ in the objective. This allows the program to be solved directly using standard LP solvers, without the ellipsoid method or dual separation oracles. In the unweighted case, we show that our convex program is equivalent to the restricted-spending Fisher market convex program of Cole and Gkatzelis, yielding a constructive proof that its integrality gap is exactly $e^{1/e}$. With a minor modification, our analysis also gives a simple proof of the $e^{1/e}$ EF1 gap for the identical agent setting. Finally, we show that our convex programming technique extends to two unrelated machine scheduling problems, recovering the best-known approximation ratios with simpler analyses.

Authors: Andrew Au

We prove that any algorithm for detecting cycles in an $m \times n$ grid graph, where cells are colored and adjacency is defined by matching colors, must read all $mn$ cells in the worst case for all grids with $m \geq 2$ and $n \geq 2$. The proof is by adversary argument: we construct an adaptive adversary that maintains ambiguity -- one completion containing a cycle and one without -- until the final cell is read. The construction proceeds by tiling the grid with $2 \times 2$, $2 \times 3$, $3 \times 2$, and $3 \times 3$ blocks, each equipped with an independent block adversary, composed via a checkerboard isolation scheme.

Authors: Ryuki Tsukuba, Kazutoshi Ando

Hierarchical clustering is a fundamental task in data analysis, yet for a long time it lacked a principled objective function. Dasgupta [STOC 2016] initiated a formal framework by introducing a discrete objective function for cluster trees. This framework was subsequently expanded by Cohen-Addad et al. [J. ACM 2019], who introduced the notion of admissibility -- a criterion ensuring that, whenever the input similarities admit consistent hierarchical representations, the minimizers of an objective function recover them. They also provided a necessary and sufficient condition for admissibility within a broad class of objective functions, which we refer to as sum-type objective functions. Our contributions are twofold. First, we characterize admissible sum-type objective functions when the scaling function g is a symmetric polynomial of degree at most two, together with sufficient conditions in the degree-three case. For admissible objective functions in this class, we show that the recursive sparsest cut algorithm achieves an O($φ$)-approximation ratio, where $φ$ denotes the approximation factor of the sparsest cut subroutine. Second, we introduce a new class of objective functions for hierarchical clustering, which we term max-type objective functions, where cluster interactions are measured by maximum rather than aggregate similarity. For this class, we establish a general characterization of admissibility for arbitrary scaling functions g, and a complete characterization when g is a symmetric polynomial of degree at most two. These results provide new theoretical insights into admissible objective functions for hierarchical clustering and clarify the scope of algorithmic guarantees for optimizing them.

Authors: Pradipta Mitra

We propose a simple, projection-based algorithm for clustering mixtures of discrete (Bernoulli) distributions. Unlike previous approaches that rely on coordinate-specific ``combinatorial projections,'' our algorithm is rotationally invariant and works by projecting samples onto approximate centers obtained via a $k$-means computation on the best rank-$k$ approximation of the data matrix. This resolves a conjecture of McSherry on the existence of such geometric algorithms for discrete distributions. The same algorithm also applies to continuous distributions such as high-dimensional Gaussians, providing a unified approach across distribution types. We prove that the algorithm succeeds under a natural separation condition on the cluster centers.

Authors: Marin Bougeret, Guilherme C. M. Gomes, Ignasi Sau

Enumerative kernelization is a recent promising at the intersection of parameterized complexity and enumeration algorithms, with two proposed models. The first, known as enum-kernels and due to Creignou et al., was too permissive, leading to constant-sized kernels for every problem solvable with FPT-delay. To remedy this, Golovach et al. proposed the polynomial-delay enumeration kernelization model that, while addressing the shortcoming of the previous one, appears to be too strict, which we believe is a central reason for the slow development of the area. In this paper, we propose a new model for enumeration kernels, which we have called polynomial-delay (PD) kernels. It is more flexible than Golovach et al.'s kernels while still preserving their qualities; informally, it allows us to ignore ``bad'' solutions of the compressed instance when producing the solution set of the input instance, but still requires that the ``good'' solutions are lifted with polynomial-delay. After discussing the main properties of our model, we design a generic framework for vertex-subset problems to adapt decision kernels into PD kernels of the same size. We showcase our model's versatility and the framework's expressive power on the \textsc{Enum Vertex Cover} problem, where we want to list all vertex covers of size at most $k$ of a given graph. We generalize the kernelization dichotomy by Bougeret et al. about the existence of polynomial kernels for \textsc{Vertex Cover} parameterized by the vertex deletion distance to a minor-closed graph class, as well as by the solution size or feedback vertex number. The second one, in particular, is significantly simpler than the known kernel, requiring only a few lines for its lifting algorithm. Beyond our framework, we also show how to generalize to the enumeration setting the kernel of Bougeret et al. for the vertex-deletion distance to $c$-treedepth.

Authors: Yu Cong, Kangyi Tian

Motivated by the FPTAS for connectivity interdiction of Huang et al. (IPCO'24), we isolate the part of the argument that does not use cuts. The setting is a minimization problem over a feasible-set family $\mathcal F$ with a linear objective $w(S)=\sum_{e\in S}w(e)$. After dualizing the interdiction budget, deletion can be absorbed into truncated weights $w_λ(e)=\min\{w(e),λc(e)\}$. At an optimal Lagrange multiplier $λ^*$, the unknown optimal interdiction witness is a strict $2$-approximate minimizer of the reweighted problem. Thus an exact algorithm can be obtained whenever one can optimize $w_{λ^*}$ over $\mathcal F$, enumerate all its $2$-approximate minimizers, and solve the remaining knapsack problem.

Authors: Shabarish Chenakkod, Michał Dereziński, Xiaoyu Dong, Mark Rudelson

Perturbing a deterministic $n$-dimensional matrix with small Gaussian noise is a cornerstone of smoothed analysis of algorithms [Spielman and Teng, JACM 2004], as it reduces the condition number of the input to $O(n)$, and with it the complexity of many matrix algorithms. However, when deployed algorithmically, these perturbations are expensive due to the cost of generating and storing $n^2$ Gaussian random variables. We propose a perturbation that requires generating and storing $O(n)$ random numbers in $O(\log n)$ bits of precision, and reduces the condition number of any deterministic matrix to $O(n)$, matching Gaussian perturbations. Our result in particular implies a better complexity for the perturbed conjugate gradient algorithm, showing that we can solve an $n\times n$ linear system in linear space to within an arbitrarily small constant backward error using $O(n)$ matrix-vector products. In our construction, we introduce the concept of a pattern matrix, which is a dense deterministic matrix that maps all sparse vectors into dense vectors, and we combine it with a sparse perturbation whose entries are dependent and located in a non-uniform fashion. In order to analyze this construction, we develop new techniques for lower bounding the smallest singular value of a random matrix with dependent entries.

Authors: Takumi Kano, Yutaro Yamaguchi

We present a deterministic linear-time algorithm for finding an odd cycle through two specified vertices in an undirected graph. This is shown in a generalized form as follows: Let $Γ$ be any group in which every element is of order at most $2$. For a given $Γ$-labeled graph with two specified vertices (or edges), we can determine in linear time whether there exist two cycles with distinct labels that are through both of the two specified vertices (or edges), and find such cycles if yes.