Theory of Computing Report

We show that a (stronger) version of random resolution has the feasible disjunction property. This is the first instance of a proof system not known to have feasible interpolation, which nevertheless has the feasible disjunction property.

Authors: Martin Kassabov, J. M. Landsberg, Victor Souza, Philip Speegle

This paper addresses centroids, which are fundamental invariants of tensors. Our main results are as follows: (i) The construction of explicit tensors with very large centroids, whereas previously it had been conjectured that none such exist. (ii) An upper bound on the dimension of the centroid that is essentially attained by our examples. (iii) The development of a geometric technique to write down border rank decomposition of tensors using centroids and "extended centroids". (iv) The technique is applied to tensors of this paper to prove they are of minimal border rank. The technique is versatile and enables us to geometrically derive and improve upon previous ad hoc decompositions. (v) The construction of symmetric tensors with large centroids and proof that they are wild in the sense of Buczyńska-Buczyński. Our results also pave the way for new upper bounds on the exponent of matrix multiplication. The geometric technique also constructs new "better" tensors for Strassen's laser method from old, and we apply this to the tensors of Strassen and Schönhage to get better tensors in the sense that they give better upper bounds on the exponent than the original tensors.

Authors: Thomas Watson

We prove an exponential separation between zero-sided-error randomized and two-sided-error pseudodeterministic communication complexities of partial boolean functions. This qualitatively improves and simplifies the proof of the separation by Göös, Harms, Riazanov, Sofronova, Sokolov, and Yuan (STOC 2026), which had a two-sided-error randomized upper bound. Then, we generalize our technique to separate the communication complexity analogues of MA and NP^BPP.

Authors: Benedikt Kolbe, Tim Mayr

We present results on the approximate computation of stable invariants for filtrations of finite metric spaces in the context of persistent homology. We establish novel approximation algorithms in the setting of $n$-point metric spaces where the growth of the doubling dimension is in $o(\log n)$ and the diameter is bounded. In the $1$-parameter case, by revisiting known techniques (greedy permutations) in a new way, we derive the first linear-time algorithms for the problem of computing additive $\varepsilon$-approximations of any stable barcode. By deriving bounds on the convergence rate and the approximation quality of uniform samples, we extend the approach to selected multiparameter filtrations. We show that for normalized measure bifiltrations, including the multicover and subdivision-Rips bifiltration, any stable invariant can be probabilistically approximated in time constant in $n$. The constants in the running times of our algorithms depend on the doubling dimension, the diameter and the success probability. We further study the problem through the lens of fine-grained complexity and show that computing the rank of a matrix reduces to that of approximating the barcode of the Vietoris--Rips or Čech filtration. We present two variants of the reduction, one for sufficiently good additive approximations and the other for any constant factor multiplicative approximations.

Authors: Ondřej Draganov, Herbert Edelsbrunner, Sophie Rosenmeier, Morteza Saghafian

Motivated by the recent introduction of chromatic persistent homology, we generalize the Euclidean minimum spanning tree (EMST) for $n$ points in $\mathbb{R}^2$ to the lunar EMST for the case in which the points come in $s+1$ colors. Calling the intersection of $s+1$ disks of radius $r$ centered at points with pairwise different colors a \emph{lune}, the generalized EMST reflects the history of the union of lunes as $r$ goes from $0$ to $\infty$, and its \emph{cost} is twice the difference between the radii when the arcs and nodes of the tree are formed. If the points are chosen uniformly at random in $[0,1]^2$ and colored randomly, the expected cost converges to some constant (that depends on $s$) times $\sqrt{n}$, as $n$ goes to infinity. The main contribution of this paper is a proof that this constant exists, however similar to the case of the classic EMST, its precise value remains elusive.

Authors: Eunku Park

We study nearest and farthest Voronoi diagrams of lines in $\mathbb{R}^3$ under the Euclidean metric when all $n$ lines belong to one ruling of a smooth doubly ruled real quadric. For arbitrary line sites, the combinatorial complexity of the nearest Voronoi diagram is known only to lie between $Ω(n^2)$ and $O(n^{3+\varepsilon})$. Under general-position assumptions, we prove that both diagrams in the ruling class have at most $4n(n-3)$ vertices and $O(n^2)$ total combinatorial complexity. Conversely, for every $n \ge 4$, one ruling of a fixed non-rotational one-sheeted hyperboloid contains a general-position set of $n$ lines with at least $(n-2)(n-3)/2$ distinct regular nearest vertices, where regular means that exactly four lines support the vertex and their three defining bisectors meet transversely. Thus the worst-case complexity of the nearest Voronoi diagram in this class is $Θ(n^2)$, while the farthest diagram has $Θ(n^2)$ complexity for every general-position input, since it has exactly $n(n-1)$ three-dimensional cells. Under the Plücker embedding, the ruling is a conic, and the condition for a line to be tangent to a Euclidean sphere restricts to a binary quartic. At a regular vertex, the four supporting parameters exhaust its roots, and sign alternation forces two arcs of the parameter circle to be site-free. This leaves only $n(n-3)/2$ possible cyclic support types, while Bézout's theorem bounds the number of centers for each type by eight. The same reduction yields an exact $O(n^2)$-time algorithm that, after cyclically sorting the site parameters, enumerates all finite nearest and farthest vertices as constant-degree real univariate representations.

Authors: Joshua A. Grochow, Gülce Kardeş, Michael Levet

In this paper, we investigate the low-depth circuit complexity of Group Isomorphism in the multiplication (Cayley) table model. We prove the first circuit lower bounds for Group Isomorphism: namely, we show that every family of depth-$2$ Boolean circuits deciding Group Isomorphism requires quasipolynomial-size. We complement this with upper bounds of uniform depth-$2\frac{1}{2}$ circuits of quasipolynomial-size. A sequence of previous results from 1970-2025 progressively reduced the circuit depth from polynomial to $3\frac{1}{2}$; all of these results relied on the generator-enumerator strategy and, in fact, applied more generally to quasigroups. In contrast, our depth-$2\frac{1}{2}$ construction follows a fundamentally different strategy that exploits structure more specific to groups. We guess a composition series for each group, together with generators for its terms and the isomorphism types of its composition factors. We then inductively verify that the corresponding extensions at each level of the two composition series are compatible. A central part in this approach brings to bear the extensive work on the Short Presentation Conjecture, in tandem with the algorithmic theory of group extensions and cohomology.

Authors: Julian Teusch, Jörg Philipp Müller, Monika Sester

Operational requirements developed with the City of Braunschweig frame municipal micromobility planning under geofenced exclusions, mandatory retained sites, spacing rules, and area-level caps. Each policy edit requires a new feasible plan; full-set greedy takes tens of seconds per alternative at city scale. We present CLIPPER (Constraint-exact Low-latency Iterative Planning with Pooled Evaluation and Replay). It forms bounded candidate pools but recomputes exact current gains and checks every active constraint before selection. Coverage from each candidate alone sets the initial order. Offline full-set scans measure gains omitted by the pool; online, a conservative bound triggers expansion or audit. CLIPPER-F gives each proposal group the same number of candidate slots. Across Braunschweig, Munich, and Berlin, its mean coverage over complete chains stays within 0.245 percentage points of full-set greedy under the same policy, with 13.6--28.9 times lower mean rollout time. CLIPPER-A instead distributes one shared candidate budget across the groups. Under its coverage-prioritized policy, it uses 9--15% of full-set greedy's rollout time under the same policy, with mean gaps of 1.82 percentage points in Braunschweig, 0.12 in Munich, and 0.27 in Berlin. Together, CLIPPER enables rapid, replayable comparison of recorded city-scale planning states while enforcing every encoded model constraint.

Authors: Frederic Koehler, Youngtak Sohn

We establish a sharp phase transition for fitting random vectors by an ellipsoid. The random vectors have independent subgaussian coordinates with mean zero, variance one, and a common fourth moment, and the number of vectors is proportional to the square of the dimension. We identify an explicit satisfiability threshold such that, with high probability, a positive definite ellipsoid passes through every data point below the threshold, whereas no positive semidefinite fit exists above it. We also determine the optimal squared fitting error throughout the unsatisfiable regime. In particular, the threshold depends on the coordinate distributions only through their common fourth moment, revealing a fourth moment universality phenomenon. For standard Gaussian data the threshold is $1/4$, resolving the ellipsoid fitting conjecture.

Authors: Francesco Paolo Nerini, Francesco Bonchi, Arijit Khan, André Panisson

Correlation Clustering (CC) is a natural formulation of clustering in combinatorial optimization, which uses a graph representation of the input and does not require a pre-specified number of clusters. Given $n$ objects and a pairwise similarity function, the goal is to cluster the objects so that similar objects are put in the same cluster and dissimilar objects are put in different clusters. Despite its versatility, existing CC algorithms suffer from significant scalability issues and are inherently transductive: i.e., the algorithm must be executed from scratch for any new problem instance. In this work, we bridge this gap by leveraging Graph Neural Networks (GNNs) to solve Inductive Correlation Clustering, a novel generalization of the CC problem designed to handle unseen graph instances. By learning to exploit common structural patterns and node features during training, our framework generalizes to new graphs drawn from the same distribution with minimal computational overhead with respect to standard algorithms. We demonstrate the effectiveness and scalability of our approach through extensive experiments. Our framework not only excels in the inductive setting, e.g., lowering the inference time up to $5$ order of magnitude, while maintaining an approximation ratio within $~10\%$ of the best baseline solution, but also achieves competitive results on standard (transductive) CC benchmarks. Finally, we showcase a practical application of our framework as a learnable pooling mechanism for graph classification. Our results indicate that our method serves as an efficient pooling layer, enhancing the ability of GNNs to capture hierarchical structural information in networks.

Authors: Michael A. Bekos, Giordano Da Lozzo, Petr Hliněný, Michael Kaufmann

A track layout of a graph is a partition of its vertices into linearly ordered independent sets, called tracks, such that no two edges between the same pair of tracks cross. Given a graph, the goal in this context is to determine its track number, that is, the minimum number of tracks required for the graph to admit a track layout. In this work, we present upper bounds on the track number of graphs admitting a product structure. Our main contribution is an algorithm that computes a track layout with at most $(2h+1) \cdot r \cdot tn(H)$ tracks for every subgraph of the strong product $P^h \boxtimes K_r \boxtimes H$, where $P^h$ is the $h$-th power of a path $P$, $K_r$ is the complete graph on $r$ vertices, and $H$ is a graph with track number $tn(H)$. Combined with existing product-structure results from the literature, this algorithm yields upper bounds on the track number of several graph classes. For planar graphs, the obtained bound matches the current best-known upper bound of $225$. For $1$-planar and optimal $2$-planar graphs, our algorithm yields track layouts with at most $375$ tracks, while for genus-$k$, $k$-planar, $k$-framed, $k$-map, and $k$-string graphs it provides track layouts with a number of tracks that depends solely on $k$, thus establishing new upper bounds on the track number for these graph classes. The algorithm runs in linear time for planar graphs and, more generally, in $O(n + h \cdot r \cdot t + f_t(H))$ time whenever a corresponding product-structure decomposition of the input $n$-vertex graph is provided as part of the input, where $t=tn(H)$ and $f_t(H)$ is the time needed to compute a $t$-track layout of $H$. Furthermore, our algorithm only uses elementary linked-list data structures.

Authors: Luyao Fan, Jiayang Zou, Jiayang Gao, Jia Wang

We study the zero-error randomized query complexity of finding all minimal elements in an unknown $n$-element poset of width at most $w$. Previous work of Daskalakis, Karp, Mossel, Riesenfeld, and Verbin established a randomized upper bound with leading term $\frac{w+1}{2}n$, while the corresponding lower bound left a multiplicative gap in the leading constant that approaches a factor of 2 as $w$ grows. We prove the finite lower bound \( R^{\mathrm{LV}}_{n,w}\ge \frac{w+1}{2}n-\frac{w(w+3)}4 +w\left(1-\frac1w\right)^n +\frac{w(w-1)}4\left(1-\frac2w\right)^n. \) Consequently, for every fixed $w$, \( R^{\mathrm{LV}}_{n,w} = \left(\frac{w+1}{2}+o(1)\right)n. \) Thus the known randomized upper bound has the correct asymptotic leading constant for every fixed width. The argument is based on a pairwise accounting of incomparable queries under a random-chain hard distribution, using a component-flip involution and a unique ownership property for incomparable comparisons. Generative AI was used in the preparation of this manuscript.

Authors: Matic Požar

Recent work by Haeupler, Hladík, Rozhon, Tarjan, and Tětek on the instance optimality of shortest-path algorithms established several results concerning Dijkstra's algorithm and bidirectional Dijkstra's algorithm in weighted and unweighted graphs. Motivated by these results, we revisit the question of instance optimality for shortest $st$-path algorithms in the standard query model. We identify several issues in the analysis of the instance optimality of both unidirectional and bidirectional Dijkstra's algorithms and provide corresponding counterexamples. We then propose a minimal simple modification of the bidirectional Dijkstra algorithm and prove that the resulting variant is instance optimal in the weighted setting. Furthermore, we revisit the unweighted case, provide a simplified proof of the lower bound showing that no algorithm can achieve instance optimality up to a factor better than $O(Δ)$, where $Δ$ denotes the maximum degree of the graph, and discuss the implications of this result for approximation algorithms. Finally, we make progress on the open problem of instance optimality in simple graphs. We show that if the problem instance satisfies $n\ge m/16$, where $n$ is the number of nodes and $m$ is the number of edges queried by our algorithm, then it is optimal up to a constant factor. Additionally, we show instance optimality for a broad class of instances, in particular when the largest degree in the graph is at most the square root of the number of explored edges, our algorithm exhibits optimality up to a constant factor.

Authors: Omer Gurevich, Maor Matityahu, Tal Mor, Aryeh Lev Zabokritskiy

We revisit a degree-only arc Hamiltonian for fixed-fleet, homogeneous, uncapacitated vehicle routing. Because its local penalties define only a cycle cover, ground states may contain customer cycles disconnected from the depot. We construct a polynomial-size quadratic unconstrained binary optimization (QUBO) repair using capped single-commodity flow and prove that every ground-state routing is connected and cost-optimal under explicit penalty assumptions. For $N-1$ customers and $K$ nonempty routes, the unreduced encoding uses exactly $|E|(1+\lceil\log_2(N-K+1)\rceil)$ logical problem qubits. A reversible compute--phase--uncompute realization evaluates the flow penalties in $O(N^2\log N+N\log^2N)$ logical gates on a complete graph with $O(\log N)$ reusable workspace and no product register. On complete loopless graphs, a depot-delimited single-sequence position encoding uses fewer problem qubits and fewer written terms when the flow-word length grows. Conversely, the flow model achieves a smaller structured logical-gate upper bound under a common reversible accounting model. Exact audits of the Hamiltonian and circuit implementation, combined with a $1{,}200$-matrix classical benchmark, verify the formulation and quantify the connectivity gap. Finally, a 32,000-shot Amazon Braket task on IQM Emerald characterizes depth-one termwise Ising circuits on a diagnostic $N = 4,\, K = 1$ counterexample instance. In the degree-only circuit, $78.05\%$ of selected $p=1$ shots realize the invalid disconnected ground state; the reduced 14-qubit flow-augmented circuit yields no fully feasible sample. These device results characterize mapped Hamiltonians and compilation rather than an asymptotic routing solution advantage.

Authors: Xiaoyu Chen, Eric Vigoda, Xiongxin Yang

The permanent of an $n\times n$ $0/1$ matrix $A$ equals the number of perfect matchings in the bipartite graph with edges defined by $A$. Jerrum, Sinclair, and Vigoda (2004) presented an FPRAS for approximating the permanent of any nonnegative matrix using a novel simulated-annealing algorithm. The running time was improved by Bezáková, Štefankovič, Vazirani, and Vigoda (2008) to $O(n^7\log^4 n)$ for $0/1$ matrices, for any fixed approximation and success parameters. We present the first asymptotic improvement over this running time bound, obtaining an $O(n^6\log^5 n)$-time algorithm. As in the previous works, our algorithm extends to arbitrary nonnegative matrices. The analysis of Bezáková et al. yields an $O(n^4)$ relaxation time bound for the JSV Markov chain on perfect and near-perfect matchings with ideal hole weights, under which each hole pattern (the unmatched vertices, if any) is equally likely in the stationary distribution. We introduce a restricted Poincaré inequality for the partition into hole patterns and prove an $O(n^3)$ bound on the corresponding restricted relaxation time. Our proof uses a coupled multicommodity flow argument inspired by a recent transport-flow argument of Chen et al.~(2025) for the Jerrum-Sinclair chain on all matchings.

Authors: Zhao Song, Lichen Zhang

Randomized sketch-and-solve algorithms accelerate overconstrained $\ell_2$ regression by replacing the input with a smaller problem. Standard subspace embeddings guarantee that the cost of the regression is nearly preserved, but coordinate-wise accuracy of the solution is more delicate: we want the solution vector itself to be close to the optimal solution in $\ell_\infty$ norm. In particular, we want to find a vector $x'\in \mathbb{R}^d$ such that $\|x'-x^*\|_\infty\leq \fracε{\sqrt d}\cdot \|Ax^\star-b\|_2\cdot \|A^\dagger\|_{\rm op}$. Price, Song and Woodruff initiated the study of this problem and showed that the subsampled randomized Hadamard transform (SRHT) with $O(ε^{-2} d^{1+Θ(\sqrt{\log\log n/\log d})})$ rows achieves this guarantee. A subsequent work of Song, Ye, Yin and Zhang claimed to improve the row count to $O(ε^{-2}d\log^3 n)$. Unfortunately, their proof relies on an independence assumption that does not hold in general, and we exhibit an explicit instance on which it fails. To achieve a truly nearly-linear-in-$d$ row count, we introduce a new fast, dense randomized transform, which combines a randomized Hadamard flattening, a random permutation, and balanced, disjoint Gaussian pooling. Conditioned on the Hadamard-and-permutation stage, the sketched problem becomes an exact Gaussian regression in which the noise is independent of the entire sketched design; this conditional independence is exactly what the earlier argument was missing. Our sketch yields the $\ell_\infty$ guarantee with $m=O(ε^{-2}d\log d)$ rows, uses one Hadamard pass with a padded internal dimension $N=\widetilde{O}(n+ε^{-2}d^3)$, and is efficient to apply: the sketched pair $(SA, Sb)$ can be computed in $O(Nd\log N)=\widetilde{O}(nd+ε^{-2}d^4)$ time.

Authors: Aaron Li, Yifan Li, Drew DeHaas, Giulia Guidi

Updating a graph by inserting or replacing nodes while preserving semantics and reusing existing structure is a recurring computational problem. In population genetics, this problem arises in the genotype representation graph (GRG), a directed acyclic graph that losslessly encodes phased genetic variation across hundreds of thousands of samples by sharing subgraph structure for individual mutations. In a GRG, each mutation's carrier set is implicitly encoded as the set of leaf nodes reachable from the node it is assigned to. Updating a mutation is therefore a structural editing problem, and current approaches remap mutations individually. This paper introduces a batched mutation-remapping algorithm that replaces independent reuse-aware traversals with a single shared reverse-topological pass, identifying reuse candidates for an entire batch at once. The pass propagates compact bit-parallel per-mutation state and uses an adaptive sparse/dense carrier set representation spanning rare-to-common variant densities. Batching is the memory-scalable complement to split-based parallelism, which instead replicates graph and traversal state per worker. Our remapping is evaluated on a controlled update workload and on end-to-end allele polarization, a bulk carrier set update that is common in population genetic analysis. Our approach is up to 10.5$\times$ faster than independent remapping while preserving exact carrier-set semantics.

Authors: Somya Nigam, Johan Springael, Kenneth Sörensen

The problem of finding a fair consensus ranking is an active research topic in the domain of fair rank aggregation and has been well studied; however, existing studies predominantly consider both the input rankings and the output ranking to be permutations where elements are always strictly ordered. In practice, however, a ranking with ties is far more common. This study bridges this gap by presenting a post-processing approach to determine the closest fair consensus ranking when an unfair tie-aware consensus ranking is provided. It proposes an exact algorithm and a fast heuristic to achieve this.

Authors: Francisco J. Soulignac

The time-dependent traveling salesman problem with time windows (TDTSPTW) generalizes the well-known traveling salesman problem with time windows by accounting the effects of congestion on travel times. In this paper, we develop an exact framework for the TDTSPTW with a makespan objective that extends the range of instances solvable to optimality under loose time windows while remaining effective across all levels of time-window tightness. Our framework relies on a dynamic-programming labeling algorithm and combines column generation, ng-memory augmentation, and exact search, using completion bounds for state-space sparsification, variable fixing, and exact search pruning. Embedded within a branch-and-price method, the framework solves all instances with up to 45 customers in a benchmark comprising more than 10,000 instances, including all instances without time windows with up to 50 customers.

Authors: Shamisa Nematollahi, Daniel Vaz

We consider the buy-at-bulk facility location problem (BBFL), a problem combining the classic facility location problem with buy-at-bulk network design, which finds motivation in telecommunication networks. In it, we are given a graph with edge lengths, opening costs and demands for each vertex, and a monotone and subadditive capacity-cost function, and our task is to open facilities on a subset of the vertices and route the demand from each vertex to these facilities. The cost of a solution (which we want to minimize) is given by the opening costs of the chosen facilities, plus the cost on each edge, which is given by its length times the cost of providing enough capacity for the demands through the edge, given by the capacity-cost function. A common variant of the problem, the $k$-cable facility location problem (kCFL), considers the case where capacity is provided by buying copies of given cable types, each with a certain capacity and cost. We study BBFL on tree instances and show, for the unit-demand and splittable variants, that the problem admits a PTAS (a $(1+ε)$-approximation for any $ε> 0$). We also consider kCFL in the new setting of cable-unsplittable demands, where the demand of a vertex cannot be split among multiple cables. We show that the problem is NP-hard to approximate to a factor better than $3/2$ on stars, and then provide an algorithm for tree instances that outputs a solution with optimal cost, but which exceeds the capacity on each cable by a factor of $1+ε$. As a consequence, we show that the problem has a $2$-approximation algorithm on trees.

I more or less said what I was going to do in my tongue-in-cheek, cryptic post on Tuesday, but let me dive into the full details of how I’m planning on structuring this grad seminar. I’m going to log the course content here, which now lists a rough schedule for the class sessions. Taking inspiration from Matt Jones and Chris Wiggins, I’m going to do a weekly split between culture and engineering. Focusing on a particular application domain each week, we’ll spend one session discussing the purpose of forecasts in that domain and the other on the methods.

I arranged things into a thematic arc, starting with the weather—forecasting’s biggest success story—then moving to shakier ground in seismology and epidemiology, and ending with, well, millenarianism. As we move across timescales, our ability to predict nature dissipates: we can make accurate ten-day forecasts, but predicting large-scale climate disruptions is far more qualitative. We can predict immediate earthquake impacts at a distance once an earthquake has happened, but we can’t nail down precisely when a big one will happen. What we do with precise, short-term forecasts is completely different from what we do with imprecise long-term forecasts. Short-term forecasts dictate actions; long-term forecasts of discrete shocks inform risk management, preparedness, and rapid-response policies. I’m hoping that by the end of the semester I can better articulate what long-term forecasts of the end of the world do.

We’ll look at forecasts in governance and how they influence and shape policy. I’m particularly interested in discussing the rise of cost-benefit analysis in US governance. Cost-benefit analysis puts a specific number on something completely unknowable, but is now mandatory for any bill or law to pass. I want to trace how we became so reliant on a particular set of methods for guessing costs and benefits. I’m also interested in how economists became convinced you could forecast “the economy.” This required inventing something called “the economy” that could be forecast in the first place. How our system of government got so tied to a particular style of economic prediction will occupy several weeks of the class.

We’ll also get into why we want to predict “the public.” I want to examine how opinion polls went from a question of legibility to one of prediction. How did we get obsessed with using surveys to predict outcomes like elections? In parallel, we’ll look at the history of attempts to simulate the public. Simulation is nice because you don’t have to talk to people, right? We’ll look at the many misses over the history of human simulation in policy scenarios, and dig into the current obsessions with using LLMs to predict what people might do.

Finally, we’ll get into the weird culture of competitive forecasting. We’ll engage with ideas from superforecasting and prediction markets and ask why people think these are useful information-processing systems. We’ll talk about punditry and how it’s not always interested in minimizing a Brier Score. We have to talk about the relationship between forecasts and gambling. And we’ll try to piece together why putting odds on outcomes makes people feel better about the future.

For the methods, I did my topic matching so you could extract a logically ordered half-semester course on forecasting from those lectures alone. This is not a class on how to be a rational forecaster. I want to problematize those methods more than tell you how to implement them. You can ask your friend Claude if you need an honest, load-bearing implementation.

Our methods survey starts with a refresher on my idiosyncratic views of machine learning as optimization-driven algorithmic pattern recognition. This will lead to a lot of discussion of the optimization problems themselves and why people like them. We’ll cover scoring rules, calibration, maximum likelihood, and utility maximization. We will discuss the role of models and look at probabilistic recurrence models, dynamical system models, differential equations, and other simulation-based tools. We’ll spend time on uncertainty quantification and how people come up with error bars (part of being a good forecaster is plausible deniability). Then we’ll look at offline and online optimization methods that let you fill in predictions based on your cost functions and modeling assumptions. I’m interested in highlighting the metrical determinism. The cost functions and models more or less tie your hands algorithmically, and most of the cleverness goes into how you evaluate.

Hopefully this arc will feel coherent as we go. I’m not into predictions, so don’t get mad if the story changes as I go. I’ll blog through it, and then we can reflect on where we land at the end of the semester.

Enrolled students (and those dedicated to following along at home) have an important first assignment: pick something to forecast. I don’t care what it is. Throughout the course, the goal is to learn the practical techniques by making predictions. Every week I’ll ask you to try to apply the tools to your problem. Or at least find how other people have applied those same tools to your problem. At the end of the semester, we’ll present our full findings and see how accurate we can be.

Subscribe now

By Ben Recht

Authors: Martin Koutecký, Nikolaos Melissinos, Tung Anh Vu, Lluís Sabater

Computational social choice seeks algorithmic answers to questions about preference aggregation, safety of elections, robustness of outcomes, stability, etc. It overwhelmingly models societies as composed of discrete agents. We propose to study computational social choice problems in a society continuum} setting, where a society is modeled as a distribution of infinitely many infinitesimal agents of different types. An analogous approach has been very useful in physics (it is the basis of statistical mechanics), economics (mean field games), and other fields. As an initial case study, we focus on election attacks (bribery and control), which have been extensively studied in the discrete setting. We show that a broad class of standard election attacks becomes polynomial-time solvable in the society continuum. The class contains problems that are NP-hard discretely, among them Borda- and Bucklin-CCDV and unit-cost Borda-SWAP BRIBERY. Furthermore, we give polynomial-time algorithms for $k$-Approval-SWAP BRIBERY when $k$ is constant for general costs, and when $k$ varies and the cost function is additively separable. The latter result contrasts with the discrete problem, which we prove NP-complete for additively separable costs and every fixed $k\ge 2$. In contrast, we prove that Borda-SWAP BRIBERY and $k$-Approval-SWAP BRIBERY, both with general costs, remain computationally hard in the society continuum. To obtain these results, we use both continuous and discrete optimization techniques, such as the Configuration LP framework and dynamic programming. Of particular note is the technique underlying our hardness proofs, which shows how to ''reverse the flow of hardness'' between LP formulations and pricing problems.

Authors: Youlong Ding, Aayush Jain, Ilan Komargodski

We present a new generic transformation from weak PRFs computable in depth $d(n) = Ω(\log n)$ to strong PRFs computable in depth $O(d(n))$. This construction refines the classical tree-based paradigm of GGM by {tapering} the internal state so the per-level depth decreases geometrically. We complement the above with new depth-efficient weak PRF constructions based on various standard assumptions. As a corollary, we obtain new $\mathsf{NC}^1$-computable PRFs from various classical assumptions, resolving several long-standing open problems. Concretely, for the first time, we obtain $\mathsf{NC}^1$-computable PRFs: (1) from the \textbf{Learning With Errors (LWE)} assumption with a polynomial modulus-to-noise ratio, improving upon prior low-depth constructions that required Ring-LWE with super-polynomial ratios [Banerjee-Peikert-Rosen, EUROCRYPT 2012]; (2)from the standard \textbf{Learning Parity with Noise (LPN)} assumption, removing the need for structured LPN variants [Boyle et al., FOCS 2020], [Ding-Jain-Komargodski, STOC 2025]; (3) from the \textbf{Computational Diffie-Hellman (CDH)} assumption; prior works relied on the stronger Decisional Diffie-Hellman (DDH) or generalized Diffie-Hellman (GDH) assumptions [Naor-Reingold, FOCS '97, J. ACM '04].

Authors: Pedro M. M. de Castro

Let $p_0,p_1,\ldots,p_N$ be points of the unit ball of $\mathbb R^d$, processed in a prescribed order. We study the insertion cost $\sum_{i=1}^N\lVert p_i-x_{i-1}\rVert^α$, where each $x_{i-1}$ is computed from the previously observed points. The input-order path is sensitive to the input distribution but can repeatedly pay the diameter under adversarial input. The center star has controlled worst-case scale but ignores the observed sequence. We compress the past into one point through $x_0=p_0$ and $x_i=γx_{i-1}+(1-γ)p_i$, where $0\leqγ\leq1$. Thus $x_i$ is an exponentially weighted memory of the input, maintained with one $d$-dimensional point of working state. For independent uniform points, the stationary insertion length is nonincreasing in the usual stochastic order as $γ$ increases. If $d\geq2$ and $α>0$, every optimal constant parameter for $N$ insertions satisfies $1-γ_N^*=Θ(N^{-1/2})$. We determine its asymptotic constant and the resulting $\sqrt N$ correction, with explicit bounds in $d$ and $α$. For $α=1$, the leading expected tree length equals that of the center star and is strictly smaller than those of the endpoint constructions. For $α=2$, the minimizer is unique for $N\geq2$, with $1-γ_N^*=N^{-1/2}-\tfrac12N^{-1}+O(N^{-3/2})$. For arbitrary input sequences and fixed $0\leqγ<1$, the largest asymptotic mean cost is $(2/(1+γ))^α$ for $0<α\leq3$, strictly below the path value when $γ>0$. Among fixed nonnegative weighting rules whose contributing points have the same average distance in the input order from the most recent point, exponential weighting is within a factor smaller than $1.161^α$ of the best adversarial value in dimension at least two; this ratio tends to one as that average distance grows.

Authors: Édouard Bonnet, Julien Duron, Marcin Pilipczuk, Marek Sokołowski, Szymon Toruńczyk

The notion of linear neighborhood complexity is a very general structural assumption on a graph class, covering most classes of sparse graphs such as planar graphs, graphs excluding a fixed (topological) minor, or bounded expansion graphs, as well as many structured classes of dense graphs, such as graphs of bounded clique-width, twin-width, merge-width, or flip-width. In this work, we present $O(n^2)$-time optimal algorithms for $n$-vertex graphs coming from a class of linear neighborhood complexity for the following problems: $\bullet$ All-Pairs Shortest Paths, $\bullet$ the multiplication of the adjacency matrix $M$ of the input graph with any $n \times n$ matrix. More specifically, after a quadratic preprocessing, we can multiply $M$ with any $n$-vector in $O(n)$ time. This solves several questions raised in [Bonnet, Kim, Geniet, Moon; ICALP '26], and improves and generalizes results in several other recent papers [Bonnet, Giocanti, Ossona de Mendez, Thomassé; STACS '23], [Bannach, Marwitz, Tantau; STACS '24], [Anand, van den Brand, McCarty; NeurIPS '26], [Kozma, Opler '26], and [Cardinal, McCarty, Yuditsky '26]. We also extend our results to classes of bounded VC density. In classes of linear neighborhood complexity, we also give a triangle-detection algorithm in randomized linear time $O(n+m)$ in $n$-vertex $m$-edge graphs, a $K_4$-detection algorithm in randomized $O(n \log^5 n + m \log n)$ or deterministic $O(n^2)$ time, and a $K_5$-detection algorithm in randomized $O(n \log^9 n + m \log^5 n)$ time.

Authors: Gramoz Goranci, Rasmus Kyng, Maximilian Probst Gutenberg, Yibin Zhao, Gernot Zöcklein

We give a randomized data structure for undirected weighted graphs that are partially dynamic, i.e., that undergo either only edge insertions or only edge deletions. The data structure maintains $(1\pmε)$-approximations to the maxflow value and effective resistance between any queried pair of vertices, with total update time $\widetilde{O}_ε(n^2)$ and worst-case query time $\widetilde{O}_ε(1)$. Thus, for dense graphs where $m = Ω(n^2)$, our guarantees are near-optimal. Our algorithms succeed with high probability against an adaptive adversary. Our result follows from a simple stability principle for partially dynamic graphs. We show how to partition an online sequence of $m$ updates into $\widetilde{O}(n/ε)$ epochs such that every graph within an epoch is a $(1\pm O(ε))$-spectral approximation of the graph at the beginning of the epoch. The epochs are determined by the cumulative leverage score of the updated edges: small leverage-score mass implies small spectral change, while the total leverage-score mass over a monotone update sequence is $\widetilde{O}(n)$. Consequently, a spectral sparsifier needs to be recomputed only once per epoch. Applying known static all-pairs maxflow and effective-resistance oracles to these sparsifiers then yields the result.

Authors: Roberto Bruno, Ugo Vaccaro

Given a probability distribution $p = (p_1, \dots, p_n)$ and an integer $1\leq m \leq n$, a contiguous aggregation of $p$ is a probability distribution $q = (q_1, \dots, q_m)$ such that each $q_i$ is a sum of consecutive elements of $p$. Given $p$ and a positive number $R$, we consider the problem of computing a maximum entropy contiguous aggregation $q$ of $p$, under the constraint that its Shannon entropy $H(q)$ is at most $R$. We devise a dynamic programming algorithm that solves the problem exactly, and two time-efficient greedy algorithms that provide close-to-optimal solutions. We discuss a few scenarios where our problem arises.

Authors: Narek Bojikian, Alexander Firbas, Robert Ganian, Hung P. Hoang, Krisztina Szilagyi

We study the computation of minimum spanning trees subject to local degree constraints. Recent work (ICALP 2026) established that three natural formalizations of this problem share the exact same parameterized complexity under standard structural graph parameters, including treewidth, pathwidth and clique-width. This applies to the cases where every vertex has a single target degree (Specified Degree MST), or a degree upper bound (Bounded Degree MST), or is equipped with a set of admissible degrees (Set of Degrees MST). In this paper, we investigate these problems under more restrictive parameterizations and reveal that their complexity landscapes fundamentally diverge on bounded-treedepth graphs. Specifically, we prove that the former two problems are fixed-parameter tractable when parameterized by the treedepth of the input graph. In sharp contrast, we show that Set of Degrees MST remains W[1]-hard parameterized by treedepth, even when combined with the feedback vertex number (i.e., deletion distance to treewidth $1$). Finally, we show that this divergence seems to be specific to treedepth: we exclude an analogous W[1]-hardness result for Set of Degrees MST w.r.t. the vertex cover number and also rule out fixed-parameter algorithms for the former two problems w.r.t. deletion distance to constant pathwidth.

Authors: Xiaoyu Chen, Kuikui Liu

It is proved that, for every $δ\in (0,1)$, the Glauber dynamics for the uniform distribution on proper $q$-colorings is rapidly mixing when $q \geq (1+δ)Δ$ and the underlying graph has girth at least $5$ and maximum degree $Δ= Ω_δ(1)$. This result also extends to general multi-spin systems satisfying a $\textit{local spectral contraction}$ condition, including the anti-ferromagnetic Potts model with $q\geq (1+δ)(1-β)Δ$. These results are achieved by a new spectral local-to-global principle on graphs with girth at least five for general multi-spin systems, and a novel Fourier analysis for Glauber dynamics on a star. The main ideas behind all the proofs were developed through several rounds of interaction with GPT-5.6 Sol Ultra.

Authors: Tianhang Lu, Runtian Ren, Shengcai Liu

Classical paging couples every miss to an immediate replacement. We ask what remains of its algorithmic structure when a miss may wait. In our per-replacement maximum-delay model, loading a pending page costs one unit of movement plus the age of its oldest outstanding request and clears the whole page-specific episode. Equivalently, the instantaneous holding rate is the number of pending pages, rather than the number of pending requests. The classical competitive hierarchy survives this change. For cache size $k$, we give a deterministic $(5k+3)$-competitive threshold-LRU algorithm and a randomized $5H_k$-competitive algorithm against an oblivious adversary; classical lower-bound instances give matching $Ω(k)$ and $Ω(H_k)$ orders. The randomized algorithm uses cache-independent temporal windows to create an ordinary-paging sequence fixed before any random choices; a shadow paging algorithm is then projected onto nonproactive physical replacements. The offline picture is less classical. We give an exact $O(nk)$ dynamic program with one hole, an exact configuration dynamic program for a fixed number of holes, and a deterministic nonproactive polynomial-time $5$-approximation without fixing that number. Yet farthest-next-use victim selection can be suboptimal in the physical delayed problem already with three pages.

Authors: Zhao Song, Lichen Zhang

We analyze exact-metric, Metropolis-adjusted Dikin walks by keeping the proposal determinant and reverse quadratic form together. Their leading uncentered terms cancel in the complete logarithmic acceptance ratio, leaving centered fluctuations that can be controlled with second-order tools. For a polytope given by $n$ inequalities and a convex $L$-Lipschitz potential, this yields warm-start mixing in $\widetilde O((d^{2}+dL^{2}R^{2})\log(w/δ))$ steps for the regularized Lee--Sidford walk. For a spectrahedron with $n\times n$ blocks, the log-det walk mixes in $\widetilde O((ψ^\star nd+dL^{2}R^{2})\log(w/δ))$ steps, where $ψ^\star$ measures matrix leverage. The two analyses share an acceptance-to-mixing reduction. A proposal-comparison argument transfers the polytope bound to an appropriately padded $O(1/d)$-accurate metric computed from high-precision Lewis weights. For spectrahedra, given $\widehatψ\geψ^\star$, a direct-or-two-seed TensorSRHT construction gives an exact-arithmetic implementation with $ψ^\star$ replaced by $\widehatψ$ in the mixing bound.

Authors: László Kozma, Junqi Tan

The optimal discretization problem asks, given two disjoint sets of points $R$ and $B$ in the plane, for a minimal family of horizontal and vertical lines that separate the two sets, so that no cell delimited by the lines contains points from both sets. The problem arises as a pre-processing in supervised machine learning, and has received significant attention in parameterized algorithmics. Answering the question raised by Bonnet, Giannopoulos, and Lampis [IPEC 2017] and Froese [PhD thesis, 2018], it was shown by Kratsch, Masařík, Muzi, Pilipczuk, and Sorge [SODA 2021] that optimal discretization admits a fixed-parameter algorithm with running time $2^{\mathcal{O}(k^2 \log k)} \cdot n^{\mathcal{O}(1)}$, where $k$ is the solution size and $n = |R| + |B|$. In this paper we give an algorithm for optimal discretization that runs in time $\mathcal{O}(1.9602^n)$. We also study the related point separation problem that asks to separate all input points by axis-parallel lines. For this problem we obtain an algorithm with runtime $\mathcal{O}(1.8906^n)$. Our guarantees follow from structural observations about bichromatic and monochromatic point sets, and hold even if points are allowed to share coordinates. To our knowledge, these are the first improvements over the trivial $2^n$ bound for both problems.

Authors: Armen Kostanyan, Arevik Harmandayan

The problem of pattern matching, that is, finding all occurrences of a given pattern in a string, is one of the fundamental problems in computer science that has applications in many areas. In this paper, we consider fuzzy patterns, defined as sequences of fuzzy properties over the basic alphabet. We first consider fuzzy pattern matching for sequences of elements of the basic alphabet and then extend the problem to partially ordered sets of nodes labeled by elements of the basic alphabet. For sequences, we seek segments that match the pattern, whereas for partially ordered structures, we seek saturated chains of nodes that match the pattern. The key concept underlying the solutions to these problems is the notion of a trajectory, which generalizes the concept of the prefix function used in the Knuth--Morris--Pratt (KMP) algorithm. A trajectory is processed together with the corresponding data structure, allowing the proposed algorithms to be represented as transition systems whose states are trajectories for sequences and trajectories associated with nodes for partially ordered structures. The trajectory-based approach provides a unified framework for fuzzy pattern matching in various data structures.

I have just posted this report, which contains two previous reports, the counterexample to the dream xor lemma and the simple proof using majority, together with a new proof which appears to improve the parameters of all previous proofs of the xor lemma. Specifically, if a function has correlation epsilon with circuits of size S, the xor of two copies has correlation about epsilon square with circuits of size about S times epsilon square. By contrast, it seems to me that all previous proofs lost at least epsilon to the four in circuit size, and some also had a dependence on N. This loss arose from the need to estimate the final correlation, as is evident, for example, in Levin’s proof. The proof with the hard core set incurs this loss for similar reasons.

The new proof in the report does not do this estimate. Instead, it uses an object which I call BMA for bounded mean amplifier. It is a function that, given iid variables with a small mean returns a variable whose mean is amplified. Majority is a decent BMA but doesn’t quite get to the square of the correlation. A randomized variant of majority does get you that. The function is very similar to what’s used, for example, in Levin’s proof and, I’m sure, in many other places, but as far as I can tell, the analysis is different. I also find it simpler.

By Manu

There's a scene in Apollo 13 where Jim Lovell, played by Tom Hanks, asks Houston control to check his calculations, which they do using a slide rule. 

By Lance Fortnow

Authors: Aritra Das, Vincent Froese, Moritz Grillo, Debayan Gupta, Christoph Hertrich, Tharrshann Jayan Logarajah, Georg Loho, Mihir More, Moritz Stargalla

Lipschitz constants are a standard way to quantify the sensitivity of neural networks to small input perturbations, but computing them is difficult even for shallow ReLU networks. We study this problem for two-layer input-convex neural networks (ICNNs), a restricted architecture where nonnegative output weights enforce convexity. Computing the $L_p$-Lipschitz constant for these networks is equivalent to maximizing the dual norm over a zonotope. While $L_1$- and $L_\infty$-norm maximization on zonotopes admit fixed-parameter and polynomial-time algorithms, respectively, the parameterized complexity of the remaining $L_p$-norms was open. We prove that, for every fixed $p\in (1,\infty)\cap \mathbb{Q}$, maximizing the $L_p$-norm over a zonotope in $\mathbb{R}^d$ is W[1]-hard with respect to the dimension $d$. Moreover, our hardness results imply that brute-force enumeration algorithms are essentially optimal for this problem under the Exponential Time Hypothesis. By duality, the same hardness results hold for computing the $L_p$-Lipschitz constant of two-layer ReLU ICNNs. Our proof first establishes the result for the $L_2$-norm and then transfers the construction to arbitrary fixed $p\in (1,\infty)\cap\mathbb{Q}$ using a suitable Taylor approximation. These results resolve the corresponding questions regarding the parameterized complexity status for zonotope norm maximization and two-layer ICNN Lipschitz constants. Our paper resolves an open problem posted at COLT'25. There are several independent concurrent papers resolving the same problem. Our paper prioritizes a clear exposition of the underlying mathematics and conceptual intuitions behind the proof. Additionally, we explicitly describe our research process including the use of LLMs.

Authors: A. R. Balasubramanian, Dmitry Chistikov, Rupak Majumdar

Many problems in the verification of recursive programs can be reduced to pushdown model checking. In this problem, we are given as input a pushdown automaton (PDA) over a constant-sized stack alphabet, and a description of undesirable behaviors given by an intersection of NFAs, and the problem is to decide if there is a behavior of the PDA that belongs to the set of undesirable behaviors. It is well-known that there is an algorithm for this problem that runs in time $O(n^{2k} |Σ| + n^{3k})$, where $n$ is the maximum number of states of the PDA and the NFAs, $Σ$ is the common input alphabet, and $k-1$ is the number of NFAs. Despite the importance of this problem, no better algorithm is known for it. In this paper, we provide an explanation for this lack of progress using the lens of fine-grained complexity theory. We prove that if the $3k$-Clique hypothesis (resp. combinatorial $3k$-Clique hypothesis) is true, then for any $ε> 0$, there is no algorithm (resp. combinatorial algorithm) that solves this problem in time $O((n^{(ω-1)k} |Σ| + n^{ωk})^{1-ε})$ (resp. $O((n^{2k} |Σ| + n^{3k})^{1-ε})$) where $ω$ is the matrix multiplication exponent. Furthermore, using the combinatorial hypothesis, we also show that pushdown model checking over constant-sized input alphabets cannot be solved in time faster than $O(n^{3(k-1)-ε})$ for any $ε> 0$. Finally, we investigate the possibility of an $O(N^{3k-ε})$ time algorithm for this problem where $N$ is the total bit size of the input. We formulate a new hypothesis, the 2NPDA$(k)$ hypothesis, that helps explain the lack of $O(N^{3k-ε})$ time algorithms for this problem. To corroborate this hypothesis, we show a web of linear-time reductions between the 2NPDA$(k)$ hypothesis, pushdown model checking, and other problems in formal language and automata theory.

Authors: Benedek Nagy

The Post Correspondence Problem is as follows: having a set of dominoes, is there any (maybe repeating) sequence of them such that the words formed by the upper parts and the lower parts by the sequence of dominoes are identical. It is one of the most known problems that is algorithmically undecidable. In this paper, the reverse Post Correspondence Problem is defined, that is, where the two assembled words of the dominos are reversals of each other. Undecidability about this new, modified problem is proven. Further, based on this result, it is also proven that the emptiness problem for 5'->3' String Assembly Systems is undecidable too. 5'->3' String Assembly Systems belong to String Assembly Systems type formal language generating models. The 5'->3' denotes that, in these variants, the derivations of the generated words start from the two extremes. The notation and the new model are bio-motivated as any double stranded DNA has two opposite oriented 5'->3' strands.

Authors: Yota Maeda, Hiroshi Yano

We study the approximation of the number of solutions of Laurent polynomials over finite fields. For a Laurent polynomial \[f(x)=\sum_{j=1}^{s}a_jx^{u_j}\in \mathbb{F}_q[x_1^{\pm1},\ldots,x_n^{\pm1}], \] let $U$ be its augmented support matrix whose columns are $(1,u_j)$ with rank $ρ$ and $N(f) := \# \{x\in (\mathbb{F}_q^\times)^n \mid f(x)=0\}$ be its torus point count. Our first main result is a quantum algorithm that outputs $\widehat{N}(f)$ satisfying \[ |\widehat{N}(f) - N(f)| \le \varepsilon q^{n+s/2-ρ} \] with success probability $1-δ$. Provided that $ρ$ and $\|U\|_\infty$ are bounded, the algorithm runs in both classical bit and quantum gate complexity $\mathrm{poly}(n, s, \log q, 1/\varepsilon, \log(1/δ))$. It provides finer resolution than relative-error approximations in general settings. To the best of our knowledge, in the explicit finite-field input model considered here, no previous algorithm achieves this additive accuracy with running time polynomial in $\log q$. Van Dam (arXiv:quant-ph/0405081) conjectured the existence of such an algorithm under the assumption of an oracle reflecting the algebraic properties of the polynomial. In contrast, by exploiting a point-counting formula derived from character sums over finite fields, we develop an alternative approach that efficiently approximates the number of points without assuming the existence of such an oracle. As a second main result, we prove that the same approximation problem becomes $\#$P-hard under randomized polynomial-time Turing reductions when the support matrix $U$ varies freely as part of the input. Thus, taken together, our results clarify how the effectiveness of the quantum approach depends on the tradeoff between the accuracy scale and the support parameters of the input polynomial.

Authors: Hari Mohan Pandey

This paper proposes the Coronavirus Optimization Algorithm (COA), a SARS-CoV-2-inspired success-history adaptive evolutionary optimizer for box-constrained continuous global optimization. COA does not model disease transmission; instead, it maps selected coronavirus mechanisms to explicit search operators, including elite-guided attraction, trial-vector generation, adaptive parameter variation, stagnation recovery, and population-size scheduling. The algorithm combines opposition-based initialization, current-to-pbest mutation, binomial crossover, an external archive, success-history adaptation, population reduction, and partial restart. COA is evaluated on 29 CEC 2017 benchmark functions at 10, 30, and 50 dimensions against 15 competitive optimizers. Results show that COA achieves the best overall Friedman rank across all dimensions, with particularly strong performance on composition functions. The findings demonstrate that COA is a compact, transparent, and competitive adaptive evolutionary optimizer, while also highlighting limitations on some hybrid functions and the need for further high-dimensional validation.

Authors: Jiaqi Liu, Yansong Feng, Yanbin Pan

We prove that exact Euclidean decision-CVP is $\mathsf{NP}$-complete on coefficient lattices of nonzero principal ideals in the power-of-two cyclotomic rings $R_d=\mathbb{Z}[y]/(y^d+1)$. A deterministic reduction from X3C produces an integral target and squared threshold $Δ$ such that the closest squared distance is exactly $Δ$ in YES instances and at least $Δ+4$ in NO instances. The ideal elements within squared distance $Δ$ are in bijection with exact covers, which also gives $\mathsf{NP}$-hardness of exact search-CVP under polynomial-time Turing reductions. We further lift these instances to full-rank principal ideals of $\mathbb{Z}[X]/(X^D-1)$, where $D=2d$. The lift preserves principality, doubles the dimension, and scales corresponding squared distances by eight. Hence exact decision-CVP is $\mathsf{NP}$-complete and exact search-CVP is $\mathsf{NP}$-hard on principal cyclic ideal lattices. Both results admit uniformly computable fixed-family forms: for each X3C universe size, the principal cyclotomic and cyclic ideals can be fixed before the triple collection is known, with only the targets and thresholds depending on the collection. If exact decision-CVPP were polynomial-time solvable on either family, then $\mathsf{NP}\subseteq\mathsf{P}/\mathrm{poly}$; by Karp--Lipton, the polynomial hierarchy would collapse to $Σ_2^{\mathsf P}$. To our knowledge, the cyclic results resolve the exact decision versions of Micciancio's questions for cyclic lattices and fixed cyclic-lattice families.

Authors: Vincent Delecroix, Vincent Despré, Camille Lanuel, Hugo Parlier, Monique Teillaud

Hyperbolic surfaces are a fundamental object in mathematics and play an increasingly important role in computational geometry and topology. A key ingredient in the design of efficient algorithms on such surfaces is the availability of a geometric discretization of controlled complexity. In this paper, we present the first algorithm for constructing e-nets on hyperbolic surfaces starting from a fundamental polygon representation. Our approach is based on Delaunay refinement and relies on maintaining Delaunay triangulations through edge flips. The size of an e-net cannot be bounded solely as a function of the genus because of the presence of arbitrarily long collars around short geodesics. To overcome this difficulty, we introduce the notion of a pseudo e-net, which decomposes the surface into e-thin cylinders together with a Delaunay triangulation over an e-net of the remaining thick part. As applications, we obtain algorithms for computing the length spectrum of an e-thick hyperbolic surface and for computing the systole from a pseudo log(sqrt(2))-net. These results demonstrate that Delaunay-based discretizations provide a practical and versatile framework for algorithmic computations on hyperbolic surfaces.

Authors: Emerson G. Escolar, Yuta Shimada

In topological data analysis, in particular persistent homology analysis, extracting "optimal" representatives for homology classes is crucial for identifying geometric regions of interest. In prior work, optimality is defined in terms of minimizing length or volume. In this work, we restrict our attention to a single homology class in degree $1$ and introduce the total absolute curvature of cycles as the cost function. We show that this cost function, based on angles between edges of cycles, penalizes departures from planarity, convexity, and simple-ness of the cycle representative. We formulate the "angle-optimal homologous cycle problem", recast it as a binary quadratic optimization problem, and show the results of experiments on artificial toy data.

Authors: Jiaheng Wang

It is shown in this manuscript that a random graph $G$ drawn from the Erdős--Rényi model $\mathcal{G}(n,p)$ with \[ p=p(n)\leq 1/2, \qquad \lim_{n\to+\infty}(np-\log n-\log\log n)=+\infty, \] is a homomorphic core, i.e., every homomorphism from $G$ to itself is an automorphism. This implies tight ETH-based lower bounds of the subgraph isomorphism problem for almost all $k$-vertex patterns with polynomial average degree.

Authors: Rolando D. Somma, Ronald de Wolf

The guided Hamiltonian problem is the following: given access to the unitary $U=e^{i H}$ for some Hamiltonian $H$, and given access to a unitary that prepares a guiding state promised to have overlap at least $γ>0$ with the ground space of $H$, estimate the ground-state energy of $H$ within additive error $δ> 0$ and success probability at least $1-\varepsilon $, $\varepsilon>0$. How many applications of $U$ and its inverse $U^{-1}$ are necessary and sufficient? An upper bound $O(\log(1/\varepsilon)\log(1/γ)/γδ)$ was known, and was improved to $O(\log(1/\varepsilon)/γδ)$ very recently [JW26]. A matching lower bound was known whenever one of the three parameters $δ,γ,\varepsilon$ was held constant [MdW26]. In this paper we prove the joint lower bound $Ω(\log(1/\varepsilon)/γδ)$ with the tight $\varepsilon$-dependence provided the dimension of $H$ is at least $\log(1/\varepsilon)/γ^2$. Furthermore, we show that this same lower bound (with slightly larger dimension) holds for both the special case in which the ground state is guaranteed to be unique and $H$ has a gap of $δ$ between its first and second eigenvalue; and for ground-state preparation, where $δ$ denotes the spectral gap and $\varepsilon$ now is the approximation error. The lower bounds also apply when the Hamiltonian can be accessed via its block-encoding, and when fractional powers of $U$ are allowed, as in continuous-time Hamiltonian simulation. Lastly, improved upper bounds are known when $H$ is nonnegative and presented as a sum of squares; and our results imply the lower bound $Ω(\log(1/\varepsilon)/γ\sqrtδ)$ for this case.

Authors: Stacey Jeffery, Freek Witteveen

In the problem of ground-state energy estimation, one aims to estimate the smallest eigenvalue of a Hamiltonian, often given a guiding state, with some promised overlap $γ$ with the ground space. The main approach to this problem is to simulate its evolution, and estimate the smallest (or equivalently, largest) eigenphase of the resulting unitary $U$. We give a quantum algorithm that estimates the largest eigenphase of a unitary $U$ in this guided setting using a factor of $\log\frac{1}γ$ fewer queries to $U$ than the previous best approach. The result matches an existing lower bound, and answers an open question from Mande and de Wolf. The algorithm is based on transducers, which often allow composition of quantum algorithms without overhead from error reduction.

Authors: Ainesh Bakshi, Alex Conway, Hanna Komlós, William Kuszmaul, Alek Westover

Affine modular linear hashing is one of the simplest classical hash families. For a prime $p > u$, the hash function is obtained by choosing $s,t$ uniformly from $\mathbb{Z}_p$ and mapping each key $x \in \{0,\ldots,u-1\}$ to one of $n$ bins by $h(x) = [(sx+t) \bmod p] \bmod n$. Despite its simplicity, the maximum load of linear hashing remains poorly understood. For $n$ keys hashed into $n$ bins, the best known upper bound is $O((n \log n)^{1/3})$, whereas the best known lower bound is only $Ω(\log n / \log\log n)$. We prove a lower bound of $\exp(Ω(\log n / \log\log n))$ for universes of size $n^{1+o(1)}$. Surprisingly, there is a key set for which this load holds not just in expectation, but for every random seed. The proof is driven by two simple reductions: one transfers lower bounds from a real version of linear hashing to modular linear hashing, and the other transfers arithmetic Kakeya constructions to real hashing. We further show that, for sufficiently large $p$, the expected maximum loads in the modular and real settings are essentially the same, giving an alternative route to an $n^{1/3+o(1)}$ upper bound. Finally, we show that any uniform subpolynomial upper bound for either setting would imply a polynomial-length arithmetic Kakeya conjecture and hence the Kakeya conjecture for upper Minkowski dimension.

Authors: Gabriel Marques Domingues, Minh Hang Nguyen, Shay Solomon

We study the \emph{fully dynamic edge orientation problem}, focusing on \emph{worst-case} time bounds. An undirected graph undergoes edge insertions and deletions, and the goal is to maintain an orientation with small {\em maximum outdegree} (hereafter, outdegree) and small worst-case update time. The outdegree of any orientation is at least $α-1$, where $α$ is the graph's \emph{arboricity}, i.e., the minimum number of forests into which its edge set can be partitioned. When $α= O(1)$, it is long known that both the outdegree and the worst-case update time can be bounded by $O(\log n)$. Despite numerous follow-ups, no $o(\log^3 n)$ worst-case update time is known for maintaining constant outdegree, even for very basic graph families---with a notable exception, \emph{forests}. For forests, a \emph{simple folklore} algorithm maintains outdegree 2 via \emph{random walks}: When an insertion creates a vertex of outdegree 3, the algorithm repeatedly chooses a uniformly random outgoing edge until reaching a vertex of outdegree at most 1, and then flips the resulting directed path. As the underlying graph is cycle-free, the path length is easily shown to be $O(\log n)$ in expectation, and also with high probability for polynomially long update sequences. We prove that this simple random walk paradigm extends to \emph{outerplanar graphs}. Our algorithm maintains constant outdegree with $O(\log n)$ worst-case update time, where the time bound holds in expectation, and also with high probability for polynomially long update sequences. We give a \emph{tight analysis}: outdegree 4 is achievable with $O(\log n)$-length paths, while outdegree 3 incurs $\mathtt{poly}(n)$-length paths. We also extend the argument to $K_{2,t}$-minor-free graphs, for any $t \ge 2$, with the outdegree bound depending only on $t$ and with the same update time guarantees. The locality of [...]

Authors: Karthekeyan Chandrasekaran, Krishna Kalathur

We show that there exists a polynomial-time algorithm to find a stable matching in network hypergraphic preference systems. The key connection that drives the algorithm was discovered by chatting with ChatGPT-5.6 Sol Max. We verified it independently and present the details in our own words.

Authors: Júlia Baligács, Bartłomiej Bosek, Yann Disser, Andreas Emil Feldmann, Grzegorz Gutowski, Katarzyna Kępińska, Paweł Putra, Anna Zych-Pawlewicz

In this paper we study the fractional vertex cover problem on trees in two related models: online and incremental. In the online model, the vertices of the tree are known a priori and the edges arrive one at a time. The goal is to maintain a fractional vertex cover of the tree, i.e., an assignment of fractional weights from [0,1] to the vertices such that the weights of endpoints of every edge sum up to at least one. After each edge arrival, we need to modify the fractional vertex cover to cover the new edge as well. However, we can only increase the values assigned to vertices. The problem was studied before (in the vertex arrival model) by Wang and Wong, who motivated it as a generalization of the ski-rental problem, but also (more importantly) by its close connection to the dual online matching problem. They presented a 1.901-competitive algorithm for general graphs in the vertex arrival model. We present an $\frac{11}{6} \approx 1.83$-competitive algorithm for trees in the more general edge arrival model. In addition, we study the fractional vertex cover problem in an incremental model, where we again seek a fractional vertex cover after every update, but all the updates to the tree are known to the algorithm a priori. In this model, we give a 1.5-competitive algorithm and provide a matching lower bound.