Theory of Computing Report

Fully Funded Joint PhD – BITS Pilani × RMIT (Trustworthy AI, LLMs, RAG) 2 positions on:

Unlearning & AI behavior
RAG + Right to be Forgotten

CS/AI/ML/Data/Math/EE
₹42.8k–45.8k + AUD stipend
India + Melbourne
Deadline: 28 Mar 2026

Website: https://www.linkedin.com/feed/update/urn:li:activity:7436398877475483648/
Email: yash.sinha@pilani.bits-pilani.ac.in

By shacharlovett

I’ve been wanting to write a summary of the Cultural AI conference I attended at NYU last week, but I’ve been struggling to succinctly capture my thoughts. That’s indicative of the depth and complexity of how AI meets culture, and the different perspectives and disciplines might not lend themselves to a tidy summary.1 As I often do when trying to wrap my head around complex things, I will stop worrying and just blog through it.

The talk that serves as my hub in the complex network of cultural AI is Cosma Shalizi’s “Aware of All Internet Traditions: Large Language Models as Information Retrieval and Synthesis.” That language models simultaneously retrieve information and synthesize new content isn’t controversial. Nor is the fact that this synthesis is formulaic. The current synthesis is next-token prediction trained on all written information, whose output is warped by some selective post-training. By design, language models mechanistically reproduce the recurring regularities in their training data. That training data consists of all the text files on the internet and what is easily available in printed books. Hence, the regularities are the tropes, stereotypes, templates, conventions, and genres of language and code.

The formulaic generation of discourse looks like discourse in ways we could never have imagined. But with hindsight, we shouldn’t be surprised. Human culture is very formulaic! There are long-standing formulas for oral tradition, for generating small talk, or for generating scientific papers. As Cosma put it, in the single sentence that summarizes the entire Cultural AI conference:2

Not having to think is often a good thing! Tradition lets us externalize certain processes so we can focus on other tasks. Formalities strengthen cultural connections. Traditions in communication help us understand each other better and come to consensus faster.

Indeed, our vast externalized cultural intelligence is the jewel of human tradition. Cosma cites Jacques Barzun’s conception of the House of Intellect: intellect is the communal form of society’s intelligence. “[I]t is intelligence stored up and made into habits of discipline, signs and symbols of meaning, chains of reasoning and spurs to emotion — a shorthand and a wireless by which the mind can skip connectives, recognize ability, and communicate truth.” According to Barzun, intellect lets society share and externalize knowledge. It belongs to society, not any individual. It connects individual intelligences. It lives after any single intelligence dies.

GenAI is the mechanization of this intellect. It is the mechanization of all of our traditions.

With James Evans, Henry Farrell, and Alison Gopnik, Cosma has been preaching the gospel that AI is a cultural technology for several years. He’s gone through several iterations of what that means and what it implies, but mechanized tradition is the characterization that resonates most with me. Mechanized tradition of Barzun’s artificial intellect is a far better description of GenAI technology than “artificial intelligence.” This frame helps us get away from the silly C-suite sci-fi navel-gazing about the personalities inside the data centers. Claude is not a person. It is a mechanized intellect. A Lore Laundering Machine. The frame of mechanized tradition helps me build a social metascience of our LLM condition.

Let me give you a fun example.

In the same session as Cosma, Wouter Haverals gave a rhizomatic inspection of the tradition of literary style. What is style anyway? We love to ask LLMs to write in new styles. It’s funny to have it generate poetry. One of my most common queries is how to rewrite emails to sound less angry.

But humans are also great at mimicking style. It can be a fun, creative game to do the sort of rewriting we now task AI with. And our audience can all tell when something hits or misses the mark when we very ape a particular tradition.

Wouter introduced Raymond Queneau’s Exercices de Style, a book consisting of 99 rewritings of the same story in different styles. The main story is simple enough. Here’s Barbara Wright’s 1958 translation:

In the S bus, in the rush hour. A chap of about 26, felt hat with a cord instead of a ribbon, neck too long, as if someone’s been having a tug-of-war with it. People getting off. The chap in question gets annoyed with one of the men standing next to him. He accuses him of jostling him every time anyone goes past. A snivelling tone which is meant to be aggressive. When he sees a vacant seat he throws himself on to it.

Two hours later, I meet him in the Cour de Rome, in front of the gare Saint-Lazare. He’s with a friend who’s saying: You ought to get an extra button put on your overcoat.” He shows him where (at the lapels) and why.

Queneau rewrites this story in the past and the present. In reported speech. In the passive voice. In haiku.

Summer S long neck

plait hat toes abuse retreat

station button friend

Obviously, you can feed an LLM Queneau’s original story and prompt it to write in each of the prescribed styles. Can LLM capture the style? How could you know that LLM did a good job?

The only way to answer such questions is to lean on the tradition of vulgar positivism. In a delightfully recursive metanarrative,3 Wouter and his co-author Meredith Martin ran a survey experiment. On the platform Prolific, they asked “real people” a series of questions about Wright’s translations of Queneau’s original stories and AI-generated versions. They ran several variants. In one, mimicking the style of Kevin Roose’s mechanistically obnoxious New York Times quiz last week, they didn’t tell the participants how the two stories were generated and simply asked which better captured the style. In the second variant, they asked which captured the style better when the participants knew whether the story was Queneau’s or AI’s. In the third experiment, they asked for preferences with the true labels switched.

What happened next was entirely predictable. Without attribution of authorship, the “people” on Prolific slightly preferred the AI version, choosing the AI 55% of the time. There were 186 participants and 930 pairwise judgments, so statistical tradition would spew out a confidence interval somewhere between 3 and 7 percentage points wide, depending on the pedantry of Reviewer 2. Make of that what you will. On the other hand, with the correct labels, “people” only chose the AI 48% of the time. Most hilariously, when the labels were swapped, “people” chose what they thought was human 62% of the time.

To situate these numbers within our broader house of intellectual tradition, Haverals and Martin adopted a recently instituted social-scientific tradition: silicon sampling. They ran a survey experiment where the participants were LLMs. When prompted with the same survey, LLMs chose AI-writing 50% of the time without labels. But with the correct labels, the machines judged Queneau superior 70% of the time. And with the swapped labels, AI chose what was presented as Queneau 64% of the time. As the title of Wouter and Meredith’s paper says, “Everyone prefers human writers, even AI.”

There’s nothing surprising in these survey results, and that shouldn’t be surprising. Survey experiments are a woefully limited way to understand the social condition. They are completely mechanical. Of course, this sort of impoverished social science can be done by mechanical literary analysis. Silicon-sampled survey experiments enable us to mechanically generate stories from illusory correlations. These stories are interpreted traditionally as either informative or absurd, depending on the academic tradition in which you were raised. The recursion continues indefinitely. There are so many patterns and regularities in human behavior, and by simulating common text strings, we get text conforming to these regularities. To rephrase Nelson Goodman, regularities are where you find them, and in human tradition, you find them everywhere.

Subscribe now

By Ben Recht

Authors: Yuhan Ye, Saurabh Amin, Asuman Ozdaglar

We study how to construct compressed datasets that suffice to recover optimal decisions in linear programs with an unknown cost vector $c$ lying in a prior set $\mathcal{C}$. Recent work by Bennouna et al. provides an exact geometric characterization of sufficient decision datasets (SDDs) via an intrinsic decision-relevant dimension $d^\star$. However, their algorithm for constructing minimum-size SDDs requires solving mixed-integer programs. In this paper, we establish hardness results showing that computing $d^\star$ is NP-hard and deciding whether a dataset is globally sufficient is coNP-hard, thereby resolving a recent open problem posed by Bennouna et al. To address this worst-case intractability, we introduce pointwise sufficiency, a relaxation that requires sufficiency for an individual cost vector. Under nondegeneracy, we provide a polynomial-time cutting-plane algorithm for constructing pointwise-sufficient decision datasets. In a data-driven regime with i.i.d.\ costs, we further propose a cumulative algorithm that aggregates decision-relevant directions across samples, yielding a stable compression scheme of size at most $d^\star$. This leads to a distribution-free PAC guarantee: with high probability over the training sample, the pointwise sufficiency failure probability on a fresh draw is at most $\tilde{O}(d^\star/n)$, and this rate is tight up to logarithmic factors. Finally, we apply decision-sufficient representations to contextual linear optimization, obtaining compressed predictors with generalization bounds scaling as $\tilde{O}(\sqrt{d^\star/n})$ rather than $\tilde{O}(\sqrt{d/n})$, where $d$ is the ambient cost dimension.

Authors: Thomas Bläsius, Emil Dohse, Deborah Haun, Laura Merker

Hyperbolic uniform disk graphs (HUDGs) are intersection graphs of disks with some radius $r$ in the hyperbolic plane, where $r$ may be constant or depend on the number of vertices in a family of HUDGs. We show that HUDGs with constant clique number do not admit \emph{product structure}, i.e., that there is no constant $c$ such that every such graph is a subgraph of $H \boxtimes P$ for some graph $H$ of treewidth at most $c$. This justifies that HUDGs are described as not having a grid-like structure in the literature, and is in contrast to unit disk graphs in the Euclidean plane, whose grid-like structure is evident from the fact that they are subgraphs of the strong product of two paths and a clique of constant size [Dvořák et al., '21, MATRIX Annals]. By allowing $H$ to be any graph of constant treewidth instead of a path-like graph, we reject the possibility of a grid-like structure not merely by the maximum degree (which is unbounded for HUDGs) but due to their global structure. We complement this by showing that for every (sub-)constant $r$, HUDGs admit product structure, whereas the typical hyperbolic behavior is observed if $r$ grows with the number of vertices. Our proof involves a family of $n$-vertex HUDGs with radius $\log n$ that has bounded clique number but unbounded treewidth, and one for which the ratio of treewidth and clique number is $\log n / \log \log n$. Up to a $\log \log n$ factor, this negatively answers a question raised by Bläsius et al. [SoCG '25] asking whether balanced separators of HUDGs with radius $\log n$ can be covered by less than $\log n$ cliques. Our results also imply that the local and layered tree-independence number of HUDGs are both unbounded, answering an open question of Dallard et al. [arXiv '25].

Authors: Sunil Arya, David M. Mount

We prove polarity duality for covering problems in Hilbert geometry. Let $G$ and $K$ be convex bodies in $\mathbb{R}^d$ where $G \subset \operatorname{int}(K)$ and $\operatorname{int}(G)$ contains the origin. Let $N^H_K(G,α)$ and $S^H_K(G,α)$ denote, respectively, the minimum numbers of radius-$α$ Hilbert balls in the geometry induced by $K$ needed to cover $G$ and $\partial G$. Our main result is a Hilbert-geometric analogue of the König-Milman covering duality: there exists an absolute constant $c \geq 1$ such that for any $α\in (0,1]$, \[ c^{-d}\,N^H_{G^{\circ}}(K^{\circ},α) ~ \leq ~ N^H_K(G,α) ~ \leq ~ c^{d}\,N^H_{G^{\circ}}(K^{\circ},α), \] and likewise, \[ c^{-d}\,S^H_{G^{\circ}}(K^{\circ},α) ~ \leq ~ S^H_K(G,α) ~ \leq ~ c^{d}\,S^H_{G^{\circ}}(K^{\circ},α). \] We also recover the classical volumetric duality for translative coverings of centered convex bodies, and obtain a new boundary-covering duality in that setting. The Hilbert setting is subtler than the translative one because the metric is not translation invariant, and the local Finsler unit ball depends on the base point. The proof involves several ideas, including $α$-expansions, a stability lemma that controls the interaction between polarity and expansion, and, in the boundary case, a localized relative isoperimetric argument combined with Holmes--Thompson area estimates. In addition, we provide an alternative proof of Faifman's polarity bounds for Holmes--Thompson volume and area in the Funk and Hilbert geometries.

Authors: Haisheng Zhu, Taotao He, Mohit Tawarmalani

We present a novel relaxation framework for general mixed-integer nonlinear programming (MINLP) grounded in computational geometry. Our approach constructs polyhedral relaxations by convexifying finite sets of strategically chosen points, iteratively refining the approximation to converge toward the simultaneous convex hull of factorable function graphs. The framework is underpinned by three key contributions: (i) a new class of explicit inequalities for products of functions that strictly improve upon standard factorable and composite relaxation schemes; (ii) a proof establishing that the simultaneous convex hull of multilinear functions over axis-aligned regions is fully determined by their values at corner points, thereby generalizing existing results from hypercubes to arbitrary axis-aligned domains; and (iii) the integration of computational geometry tools, specifically voxelization and QuickHull, to efficiently approximate feasible regions and function graphs. We implement this framework and evaluate it on randomly generated polynomial optimization problems and a suite of 619 instances from \texttt{MINLPLib}. Numerical results demonstrate significant improvements over state-of-the-art benchmarks: on polynomial instances, our relaxation closes an additional 20--25\% of the optimality gap relative to standard methods on half the instances. Furthermore, compared against an enhanced factorable programming baseline and Gurobi's root-node bounds, our approach yields superior dual bounds on approximately 30\% of \texttt{MINLPLib} instances, with roughly 10\% of cases exhibiting a gap reduction exceeding 50\%.

Authors: Patrick Loiseau, Simon Mauras, Minrui Xu

We study auction design in the celebrated interdependence model introduced by Milgrom and Weber [1982], where a mechanism designer allocates a good, maximizing the value of the agent who receives it, while inducing truthfulness using payments. In the lesser-studied procurement auctions, one allocates a chore, minimizing the cost incurred by the agent selected to perform it. Most of the past literature in theoretical computer science considers designing truthful mechanisms with constant approximation for the value setting, with restricted domains and monotone valuation functions. In this work, we study the general computational problems of optimizing the approximation ratio of truthful mechanism, for both value and cost, in the deterministic and randomized settings. Unlike most previous works, we remove the domain restriction and the monotonicity assumption imposed on value functions. We provide theoretical explanations for why some previously considered special cases are tractable, reducing them to classical combinatorial problems, and providing efficient algorithms and characterizations. We complement our positive results with hardness results for the general case, providing query complexity lower bounds, and proving the NP-Hardness of the general case.

Authors: Sitan Chen, Jingqiu Ding, Mahbod Majid, Walter McKelvie

Bayesian methods lie at the heart of modern data science and provide a powerful scaffolding for estimation in data-constrained settings and principled quantification and propagation of uncertainty. Yet in many real-world use cases where these methods are deployed, there is a natural need to preserve the privacy of the individuals whose data is being scrutinized. While a number of works have attempted to approach the problem of differentially private Bayesian estimation through either reasoning about the inherent privacy of the posterior distribution or privatizing off-the-shelf Bayesian methods, these works generally do not come with rigorous utility guarantees beyond low-dimensional settings. In fact, even for the prototypical tasks of Gaussian mean estimation and linear regression, it was unknown how close one could get to the Bayes-optimal error with a private algorithm, even in the simplest case where the unknown parameter comes from a Gaussian prior. In this work, we give the first efficient algorithms for both of these problems that achieve mean-squared error $(1+o(1))\mathrm{OPT}$ and additionally show that both tasks exhibit an intriguing computational-statistical gap. For Bayesian mean estimation, we prove that the excess risk achieved by our method is optimal among all efficient algorithms within the low-degree framework, yet is provably worse than what is achievable by an exponential-time algorithm. For linear regression, we prove a qualitatively similar lower bound. Our algorithms draw upon the privacy-to-robustness framework of arXiv:2212.05015, but with the curious twist that to achieve private Bayes-optimal estimation, we need to design sum-of-squares-based robust estimators for inherently non-robust objects like the empirical mean and OLS estimator. Along the way we also add to the sum-of-squares toolkit a new kind of constraint based on short-flat decompositions.

Authors: Alexander Munteanu, Simon Omlor, Jeff M. Phillips

We establish new exponential in dimension lower bounds for the Maximum Halfspace Discrepancy problem, which models linear classification. Both are fundamental problems in computational geometry and machine learning in their exact and approximate forms. However, only $O(n^d)$ and respectively $\tilde O(1/\varepsilon^d)$ upper bounds are known and complemented by polynomial lower bounds that do not support the exponential in dimension dependence. We close this gap up to polylogarithmic terms by reduction from widely-believed hardness conjectures for Affine Degeneracy testing and $k$-Sum problems. Our reductions yield matching lower bounds of $\tildeΩ(n^d)$ and respectively $\tildeΩ(1/\varepsilon^d)$ based on Affine Degeneracy testing, and $\tildeΩ(n^{d/2})$ and respectively $\tildeΩ(1/\varepsilon^{d/2})$ conditioned on $k$-Sum. The first bound also holds unconditionally if the computational model is restricted to make sidedness queries, which corresponds to a widely spread setting implemented and optimized in many contemporary algorithms and computing paradigms.

Authors: Oswin Aichholzer, Joseph Dorfer, Sándor P. Fekete, Phillip Keldenich, Peter Kramer, Stefan Schirra

We give an overview of the 2026 Computational Geometry Challenge targeting the problem of finding a Central Triangulation under Parallel Flip Operations in triangulations of point sets. A flip is the parallel exchange of a set of edges in a triangulation with opposing diagonals of the convex quadrilaterals containing them. The challenge objective was, given a set of triangulations of a fixed point set, to determine a central triangulation with respect to parallel flip distances. More precisely, this asks for a triangulation that minimizes the sum of flip distances to all elements of the input

Authors: C. S. Elder, Guillaume Marçais, Carl Kingsford

We study Turnpike with uncertain measurements: reconstructing a one-dimensional point set from an unlabeled multiset of pairwise distances under bounded noise and rounding. We give a combinatorial characterization of realizability via a multi-matching that labels interval indices by distinct distance values while satisfying all triangle equalities. This yields an ILP based on the triangle equality whose constraint structure depends only on the two-partition set $\mathcal{P}_y=\{(r,s,t): y_r+y_s=y_t\}$ and a natural LP relaxation with $\{0,1\}$-coefficient constraints. Integral solutions certify realizability and output an explicit assignment matrix, enabling an assignment-first, regression-second pipeline for downstream coordinate estimation. Under bounded noise followed by rounding, we prove a deterministic separation condition under which $\mathcal{P}_y$ is recovered exactly, so the ILP/LP receives the same combinatorial input as in the noiseless case. Experiments illustrate integrality behavior and degradation outside the provable regime.

Authors: Rui Chai

We study online resource allocation among N interacting modules over T rounds. Unlike standard online optimization, costs are endogenous: they depend on the full allocation vector through an interaction matrix W encoding pairwise cooperation and competition. We analyze three paradigms: (I) uniform allocation (cost-ignorant), (II) gated allocation (cost-estimating), and (III) competitive allocation via multiplicative weights update with interaction feedback (cost-revealing). Our main results establish a strict separation under adversarial sequences with bounded variation: uniform incurs Omega(T) regret, gated achieves O(T^{2/3}), and competitive achieves O(sqrt(T log N)). The performance gap stems from competitive allocation's ability to exploit endogenous cost information revealed through interactions. We further show that W's topology governs a computation-regret tradeoff. Full interaction (|E|=O(N^2)) yields the tightest bound but highest per-step cost, while sparse topologies (|E|=O(N)) increase regret by at most O(sqrt(log N)) while reducing per-step cost from O(N^2) to O(N). Ring-structured topologies with both cooperative and competitive links - of which the five-element Wuxing topology is canonical - minimize the computation x regret product. These results provide the first formal regret-theoretic justification for decentralized competitive allocation in modular architectures and establish cost endogeneity as a fundamental challenge distinct from partial observability. Keywords: online learning, regret bounds, resource allocation, endogenous costs, interaction topology, multiplicative weights, modular systems, Wuxing topology

Authors: Danny Segev

The continuous-time joint replenishment problem has long served as a foundational inventory management model. Even though its unconstrained setting has seen recent algorithmic advances, the incorporation of resource constraints into this domain precludes the application of newly discovered synchronization techniques. Such constraints arise in a broad spectrum of practical environments where resource consumption is bounded as an aggregate rate over time. However, for nearly four decades, the prevailing approximation guarantee for resource-constrained joint replenishment has remained $\frac{ 1 }{ \ln 2 } \approx 1.4427$, achieved via classical power-of-$2$ policies. In this paper, we circumvent these structural policy restrictions by devising generalized rounding frameworks, demonstrating that a well-known convex relaxation is much tighter than previously established. In particular, we expand our analytical scope to encompass fractional base expansion factors, randomized shifting, and staggered interleaved grids. Through this multifaceted methodology, we present a sequence of gradually improving performance guarantees. First, by proposing a best-of-two framework that exploits structural asymmetries between deterministic power-of-$m^{1/k}$ policies, we surpass the classical barrier to obtain a $1.3776$-approximation. Second, by injecting a random shift into the logarithmic grid domain and formulating a factor-revealing linear program to optimize a dual-policy approach, we attain a $1.2512$-approximation. Finally, by superimposing a secondary offset grid to subdivide rounding intervals and suppress holding cost inflation, we utilize interleaved policies to arrive at our ultimate approximation ratio of $\frac{5}{6\ln 2} \approx 1.2023$, which is proven to be best-possible for the class of interleaved power-of-$m^{1/k}$ policies.

Authors: Jean-Guillaume Dumas, Clément Pernet, Alexandre Sedoglavic

We propose a more accurate variant of an algorithm for multiplying 4x4 matrices using 48 multiplications over any ring containing an inverse of 2. This algorithm has an error bound exponent of only log 4 $γ$$\infty$,2 $\approx$ 2.386. It also reaches a better accuracy w.r.t. max-norm in practice, when compared to previously known such fast algorithms. Furthermore, we propose a straight line program of this algorithm, giving a leading constant in its complexity bound of 387 32 n 2+log 4 3 + o n 2+log 4 3 operations over any ring containing an inverse of 2. Introduction: An algorithm to multiply two 4x4 complex-valued matrices requiring only 48 non-commutative multiplications was introduced in [16] 1 using a pipeline of large language models orchestrated by an evolutionary coding agent. A matrix multiplication algorithm with that many non-commutative multiplications is denoted by ___4x4x4:48___ in the sequel. An equivalent variant of the associated tensor decomposition defining this algorithm, but over the rationals (more precisely over any ring containing an inverse of 2), was then given in [8]. Most error analysis of sub-cubic time matrix multiplication algorithms [3, 4, 2, 1, 17] are given in the max-norm setting: bounding the largest output error as a function of the max-norm product of the vectors of input matrix coefficients. In this setting, Strassen's algorithm has shown the best accuracy bound, (proven minimal under some assumptions in [2]). In [6, 8], the authors relaxed this setting by shifting the focus to the 2-norm for input and/or output; that allowed them to propose a ___2x2x2:7___ variant with an improved accuracy bound. Experiments show that this variant performs best even when measuring the max-norm of the error bound. We present in this note a variant of the recent ___4x4x4:48___ algorithm over the rationals (again in the same orbit under De Groot isotropies [10]) that is more numerically accurate w.r.t. max-norm in practice. In particular, our new variant improves on the error bound exponent, from log 2 $γ$ $\infty$,2 $\approx$ 2.577 Consider the product of an M x K matrix A by a K x N matrix B. It is computed by a ___m, k, n___ algorithm represented by the matrices L, R, P applied recursively on ${\ell}$ recursive levels and the resulting m 0 x k 0 by k 0 x n 0 products are performed using an algorithm $β$. Here M = m 0 m ${\ell}$ , K = k 0 k ${\ell}$ and n = n 0 n ${\ell}$ . The accuracy bound below uses any (possibly different) p-norms and q-norms for its left-handside, ___$\bullet$___ p and right-hand side, ___$\bullet$___ q . The associated dual norms, are denoted by ___$\bullet$___ p $\star$ and ___$\bullet$___ q $\star$ respectively. Note that, these are vector norms, hence ___A___ p for matrix A in R mxn denotes ___Vect(A)___ p and is the p-norm of the mn dimensional vector of its coefficients, and not a matrix norm.

Authors: Eduar Castrillo Velilla

In this paper we study the single-deletion variant $Δ$-DRESS, part of the broader DRESS framework. We demonstrate empirically that $Δ$-DRESS, a single level of vertex deletion applied to the DRESS graph fingerprint, achieves unique fingerprints within each tested SRG parameter family across all 51,718 non-isomorphic strongly regular graphs (SRGs) considered, spanning 16 parameter families: the complete Spence collection (12 families, 43,703 graphs on up to 64 vertices) plus four additional SRG families with up to 4,466 graphs per family. Combined with 18 additional hard graph families (102 graphs including Miyazaki, Chang, Paley, Latin square, and Steiner constructions), $Δ$-DRESS achieves 100% within-family separation across 34 benchmark families covering 51,816 distinct graph instances, implicitly resolving over 576 million within-family non-isomorphic pairs. Moreover, the classical Rook $L_2(4)$ vs. Shrikhande pair, SRG(16,6,2,2), is known to be indistinguishable by the original 3-WL algorithm, yet $Δ$-DRESS separates it, proving that $Δ$-DRESS escapes the theoretical boundaries of 3-WL. The method runs in polynomial time $\mathcal{O}(n \cdot I \cdot m \cdot d_{\max})$ per graph; a streamed implementation of the combined fingerprint uses $\mathcal{O}(m + B + n)$ memory, where $B$ is the number of histogram bins, while the experiments reported here additionally retain the full deleted-subgraph multiset matrix for post-hoc analysis.

Authors: Kangyi Tian, Mingyu Xiao

The Kidney Exchange Problem is a prominent challenge in healthcare and economics, arising in the context of organ transplantation. It has been extensively studied in artificial intelligence and optimization. In a kidney exchange, a set of donor-recipient pairs and altruistic donors are considered, with the goal of identifying a sequence of exchange -- comprising cycles or chains starting from altruistic donors -- such that each donor provides a kidney to the compatible recipient in the next donor-recipient pair. Due to constraints in medical resources, some limits are often imposed on the lengths of these cycles and chains. These exchanges create a network of transplants aimed at maximizing the total number, $t$, of successful transplants. Recently, this problem was deterministically solved in $O^*(14.34^t)$ time (IJCAI 2024). In this paper, we introduce the representative set technique for the Kidney Exchange Problem, showing that the problem can be deterministically solved in $O^*(6.855^t)$ time.

Authors: Mingda Qiao

The distance from calibration, introduced by Błasiok, Gopalan, Hu, and Nakkiran (STOC 2023), has recently emerged as a central measure of miscalibration for probabilistic predictors. We study the fundamental problems of computing and estimating this quantity, given either an exact description of the data distribution or only sample access to it. We give an efficient algorithm that exactly computes the calibration distance when the distribution has a uniform marginal and noiseless labels, which improves the $O(1/\sqrt{|\mathcal{X}|})$ additive approximation of Qiao and Zheng (COLT 2024) for this special case. Perhaps surprisingly, the problem becomes $\mathsf{NP}$-hard when either of the two assumptions is removed. We extend our algorithm to a polynomial-time approximation scheme for the general case. For the estimation problem, we show that $Θ(1/ε^3)$ samples are sufficient and necessary for the empirical calibration distance to be upper bounded by the true distance plus $ε$. In contrast, a polynomial dependence on the domain size -- incurred by the learning-based baseline -- is unavoidable for two-sided estimation. Our positive results are based on simple sparsifications of both the distribution and the target predictor, which significantly reduce the search space for computation and lead to stronger concentration for the estimation problem. To prove the hardness results, we introduce new techniques for certifying lower bounds on the calibration distance -- a problem that is hard in general due to its $\textsf{co-NP}$-completeness.

Authors: Jeanne Clelland, Kristopher Tapp

We develop effective methods for constructing an ensemble of district plans via independent sampling from a reasonable probability distribution on the space of graph partitions. We compare the performance of our algorithms to that of standard Markov Chain based algorithms in the context of grid graphs and state congressional and legislative maps. For the case of perfect population balance between districts, we provide an explicit description of the distribution from which our method samples.

Authors: Martin Nägele, Christian Nöbel, Rico Zenklusen

The odd-red bipartite perfect matching problem asks to find a perfect matching containing an odd number of red edges in a given red-blue edge-colored bipartite graph. While this problem lies in $\mathsf{P}$, its polyhedral structure remains elusive, despite renewed attention to achieving better polyhedral understanding, nurtured by recent advances from two complementary angles. Apart from being a special case of bimodular integer programs, whose polyhedral structure is also badly understood, it is related to one of the most notorious open derandomization questions in theoretical computer science: whether there is a deterministic efficient algorithm for the exact bipartite perfect matching problem, which asks to find a perfect matching with exactly $k$ red edges. Recent progress towards deterministic algorithms for this problem crucially relies on a good polyhedral understanding. Motivated by this, Jia, Svensson, and Yuan show that the extension complexity of the exact bipartite perfect matching polytope is exponential in general. Interestingly, their result is true even for the easier odd-red bipartite perfect matching problem. For this problem, they introduce an exponential-size relaxation and leave open whether it is an exact description. Apart from showing that this description is not exact and even hard to separate over, we show, more importantly, that the red-odd bipartite perfect matching polytope exhibits complex facet structure: any exact description needs constraints with large and diverse coefficients. This rules out classical relaxations based on constraints with all coefficients in $\{0,\pm1\}$, such as the above-mentioned one, and suggests that significant deviations from prior approaches may be needed to obtain an exact description. More generally, we obtain that also polytopes corresponding to bimodular integer programs have complex facet structure.

Authors: Anish Hebbar, Rong Ge, Amit Kumar, Debmalya Panigrahi

The field of learning-augmented algorithms seeks to use ML techniques on past instances of a problem to inform an algorithm designed for a future instance. In this paper, we introduce a novel model for learning-augmented algorithms inspired by online learning. In this model, we are given a sequence of instances of a problem and the goal of the learning-augmented algorithm is to use prior instances to propose a solution to a future instance of the problem. The performance of the algorithm is measured by its average performance across all the instances, where the performance on a single instance is the ratio between the cost of the algorithm's solution and that of an optimal solution for that instance. We apply this framework to the classic $k$-median clustering problem, and give an efficient learning algorithm that can approximately match the average performance of the best fixed $k$-median solution in hindsight across all the instances. We also experimentally evaluate our algorithm and show that its empirical performance is close to optimal, and also that it automatically adapts the solution to a dynamically changing sequence.

The Department of Computer Science at the University of Warwick invite applications at the ranking of Assistant/Associate Professor. Preference will be given to outstanding candidates with an independent research agenda who will complement existing strengths in the Department of Computer Science. We are especially interested in strengthening the Division of Theory and Foundations and DIMAP.

Website: https://warwick.ac.uk/fac/cross_fac/dimap/focs_post_2026/
Email: igorcarb@gmail.com

By shacharlovett

Authors: Samuel Bismuth, Erel Segal-Halevi

We present an approximation notion for NP-hard optimization problems represented by binary functions. We prove that (assuming P != NP) the new notion is strictly stronger than FPTAS, but strictly weaker than having a polynomial-time algorithm.

Authors: Sergey S. Ketkov, Oleg A. Prokopyev

A standard approach to solving optimistic bilevel linear programs (BLPs) is to replace the lower-level problem with its Karush-Kuhn-Tucker (KKT) optimality conditions and reformulate the resulting complementarity constraints using auxiliary binary variables. This yields a single-level mixed-integer linear programming (MILP) model involving big-$M$ parameters. While sufficiently large and bilevel-correct big-$M$s can be computed in polynomial time, verifying a priori that given big-$M$s do not cut off any feasible or optimal lower-level solutions is known to be computationally difficult. In this paper, we establish two complementary hardness results. First, we show that, even with a single potentially incorrect big-$M$ parameter, it is $coNP$-complete to verify a posteriori whether the optimal solution of the resulting MILP model is bilevel optimal. In particular, this negative result persists for min-max problems without coupling constraints and applies to strong-duality-based reformulations of mixed-integer BLPs. Second, we show that verifying global big-$M$ correctness remains computationally difficult a posteriori, even when an optimal solution of the MILP model is available.

Authors: Weikun K. Zhang, Rohan Pandey, Bhaumik Mehta, Kaijie Jin, Naomi Morato, Archit Ganapule, Michael Ruofan Zeng, Jarod Alper

Motivated by auto-proof generation and Valiant's VP vs. VNP conjecture, we study the problem of discovering efficient arithmetic circuits to compute polynomials, using addition and multiplication gates. We formulate this problem as a single-player game, where an RL agent attempts to build the circuit within a fixed number of operations. We implement an AlphaZero-style training loop and compare two approaches: Proximal Policy Optimization with Monte Carlo Tree Search (PPO+MCTS) and Soft Actor-Critic (SAC). SAC achieves the highest success rates on two-variable targets, while PPO+MCTS scales to three variables and demonstrates steady improvement on harder instances. These results suggest that polynomial circuit synthesis is a compact, verifiable setting for studying self-improving search policies.

Authors: A. Ramos-Cisneros, M. Skopenkov, H. Pottmann

We study analogs of planar-quadrilateral meshes in Laguerre sphere geometry and the approximation of smooth surfaces by them. These new Laguerre meshes can be viewed as watertight surfaces formed by planar quadrilaterals (corresponding to the vertices of a mesh), strips of right circular cones (representing the edges), and spherical faces. In the smooth limit, we get an analog of conjugate nets in Laguerre geometry, which we call Laguerre conjugate nets with respect to an attached sphere congruence. We introduce the notion of Laguerre conjugate directions, provide a method for computing them, and apply them to approximate surfaces by L-meshes with prescribed radii of spherical faces.

Authors: Giordano Da Lozzo, Fabrizio Frati, Ignaz Rutter

In 1999, Heath, Pemmaraju, and Trenk [SIAM J. Comput. 28(4), 1999] extended the classic notion of book embeddings to digraphs, introducing the concept of upward book embeddings, in which the vertices must appear along the spine in a topological order and the edges are partitioned into pages, so that no two edges in the same page cross. For a partitioned digraph $G=(V,\bigcup^k_{i=1} E_i)$, that is, a digraph whose edge set is partitioned into $k$ subsets, an upward book embedding is required to assign edges to pages as prescribed by the given partition. In a companion paper, Heath and Pemmaraju [SIAM J. Comput 28(5), 1999] proved that the problem of testing the existence of an upward book embedding of a partitioned digraph is linear-time solvable for $k=1$ and recently Akitaya, Demaine, Hesterberg, and Liu [GD, 2017] have shown the problem NP-complete for $k\geq 3$. In this paper, we study upward book embeddings of partitioned digraphs and focus on the unsolved case $k=2$. Our first main result is a novel characterization of the upward embeddings that support an upward book embedding in two pages. We exploit this characterization in several ways, and obtain a rich picture of the complexity landscape of the problem. First, we show that the problem remains NP-complete when $k=2$, thus closing the complexity gap for the problem. Second, we show that, for an $n$-vertex partitioned digraph $G$ with a prescribed planar embedding, the existence of an upward book embedding of $G$ that respects the given planar embedding can be tested in $O(n \log^3 n)$ time. Finally, leveraging the SPQ(R)-tree decomposition of biconnected graphs into triconnected components, we present a cubic-time testing algorithm for biconnected directed partial $2$-trees.

Authors: Michał Szyfelbein

We consider the following generalization of the classic Binary Search Problem: a searcher is required to find a hidden target vertex $x$ in a graph $G$, by iteratively performing queries about vertices. A query to $v$ incurs a cost $c(v, x)$ and responds whether $v=x$ and if not, returns the connected component in $G-v$ containing $x$. The goal is to design a search strategy that minimizes the average-case search cost. Firstly, we consider the case when the cost of querying a vertex is independent of the target. We develop a $\br{4+ε}$-approximation FPTAS for trees running in $O(n^4/ε^2)$ time and an $O({\sqrt{\log n}})$-approximation for general graphs. Additionally, we give an FPTAS parametrized by the number of non-leaf vertices of the graph. On the hardness side we prove that the problem is NP-hard even when the input is a tree with bounded degree or bounded diameter. Secondly, we consider trees and assume $c(v, x)$ to be a monotone non-decreasing function with respect to $x$, i.e.\ if $u \in P_{v, x}$ then $c(u, x) \leq c(v, x)$. We give a $2$-approximation algorithm which can also be easily altered to work for the worst-case variant. This is the first constant factor approximation algorithm for both criterions. Previously known results only regard the worst-case search cost and include a parametrized PTAS as well as a $4$-approximation for paths. At last, we show that when the cost function is an arbitrary function of the queried vertex and the target, then the problem does not admit any constant factor approximation under the UGC, even when the input tree is a star.

Authors: Yiyi Cai

Experimental implementations of Hamiltonian dynamics are often affected by dissipative noise arising from interactions with the environment. This raises the question of whether one can detect the presence or absence of such dissipation using only access to the observed time evolution of the system. We consider the following decision problem: given black-box access to the time-evolution channels $e^{t\mathcal{L}}$ generated by an unknown time-independent Lindbladian $\mathcal{L}$, determine whether the dynamics are purely Hamiltonian or contain dissipation of magnitude at least $ε$ in normalized Frobenius norm. We give a randomized procedure that solves this task using total evolution time $\mathcal{O}(ε^{-1})$, which is information-theoretically optimal. This guarantee holds under the assumptions that the Lindblad generator has bounded strength and its dissipative part is of constant locality with bounded degree. Our work provides a practical method for detecting dissipative noise in experimentally implemented quantum dynamics.

Authors: Yota Otachi, Emi Toyoda

We prove that Balanced Biclique Reconfiguration on bipartite graphs is PSPACE-complete. This implies the PSPACE-completeness of the spanning variant of Subgraph Reconfiguration under the token jumping rule for the property "a graph is an $(i, j)$-complete bipartite graph," which was previously known only to be NP-hard [Hanaka et al. TCS 2020]. Using our result, we also show that Connected Components Reconfiguration with two connected components is PSPACE-complete under all previously studied rules, resolving an open problem of Nakahata [COCOON 2025] in the negative.

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

We simplify the proof of the optimality of the Shortest Lower-Bound First (SLF) algorithm, introduced by Gupta, Kaplan, Lindermayr, Schlöter, and Yingchareonthawornchai [FOCS'25], for minimizing the total flow time in the $\varepsilon$-clairvoyant setting.

Authors: Pietro Negri, Manuel Sica, Rocco Zaccagnino, Rosalba Zizza

The Lyndon array stores, at each position of a word, the length of the longest maximal Lyndon subword starting at that position, and plays an important role in combinatorics on words, for example in the construction of fundamental data structures such as the suffix array. In this paper, we introduce the Inverse Lyndon Array, the analogous structure for inverse Lyndon words, namely words that are lexicographically greater than all their proper suffixes. Unlike standard Lyndon words, inverse Lyndon words may have non-trivial borders, which introduces a genuine theoretical difficulty. We show that the inverse Lyndon array can be characterized in terms of the next greater suffix array together with a border-correction term, and prove that this correction coincides with a longest common extension (LCE) value. Building on this characterization, we adapt the nearest-suffix framework underlying Ellert's linear-time construction of the Lyndon array to the inverse setting, obtaining an O(n)-time algorithm for general ordered alphabets. Finally, we discuss implications for suffix comparison and report experiments on random, structured, and real datasets showing that the inverse construction exhibits the same practical linear-time behavior as the standard one.

Authors: Siyue Liu, Olha Silina

Let $\vec{G}=(V,E^+\cup E^-)$ be a bidirected graph whose underlying undirected graph $G=(V,E)$ is $2$-edge-connected. A strongly connected orientation (SCO) is defined as a subset of arcs that contains exactly one of $e^+,e^-$ for every $e\in E$ and induces a strongly connected subgraph of $\vec{G}$. Given a family $\mathcal{F}$ of proper subsets of $V$, we call an SCO tight if there is exactly one arc entering $U$ for every $U\in \mathcal{F}$. We give a polynomial-time algorithm to construct a set $\mathcal{B}$ consisting of tight SCO's which forms an integral basis for the linear hull of tight SCO's. This means that $\mathcal{B}$ is a linearly independent subset of tight SCO's, and every integer vector in the linear hull of tight SCO's can be written as an integral combination of $\mathcal{B}$. This extends the main result of Abdi, Conuéjols, Liu and Silina (IPCO 2025), who gave a non-constructive proof of the existence of such a basis in an equivalent setting. While their proof uses polyhedral theory, our proof is purely combinatorial and yields a polynomial-time algorithm. As an application of our algorithm, we show that parity-constrained tight strongly connected orientation can be solved in deterministic polynomial time. Along the way, we discover appealing connections to the theory of perfect matching lattices.

Authors: Chien-Chung Huang, Naonori Kakimura, Yusuke Kobayashi, Tatsuya Terao

This paper studies randomized polynomial kernelization for the weighted $d$-matroid intersection problem. While the problem is known to have a kernel of size $O(d^{(k - 1)d})$ where $k$ is the solution size, the existence of a polynomial kernel is not known, except for the cases when either all the given matroids are partition matroids~(i.e., the $d$-dimensional matching problem) or all the given matroids are linearly representable. The main contribution of this paper is to develop a new kernelization technique for handling general matroids. We first show that the weighted $d$-matroid intersection problem admits a polynomial kernel when one matroid is arbitrary and the other $d-1$ matroids are partition matroids. Interestingly, the obtained kernel has size $\tilde{O}(k^d)$, which matches the optimal bound~(up to logarithmic factors) for the $d$-dimensional matching problem. This approach can be adapted to the case when $d-1$ matroids in the input belong to a more general class of matroids, including graphic, cographic, and transversal matroids. We also show that the problem has a kernel of pseudo-polynomial size when given $d-1$ matroids are laminar. Our technique finds a kernel such that any feasible solution of a given instance can reach a better solution in the kernel, which is sufficiently versatile to allow us to design parameterized streaming algorithms and faster EPTASs.

Authors: Elizaveta Popova, Elad Tzalik

We present a simple greedy procedure to compute an $(α,β)$-spanner for a graph $G$. We then show that this procedure is useful for building fault-tolerant spanners, as well as spanners for weighted graphs. Our first main result is an algorithm that, given a multigraph $G$, outputs an $f$ edge fault-tolerant $(k,k-1)$-spanner $H$ of size $O(fn^{1+\frac1k})$ which is tight. To our knowledge, this is the first tight result concerning the price of fault tolerance in spanners which are not multiplicative, in any model of faults. Our second main result is a new construction of a spanner for weighted graphs. We show that any weighted graph $G$ has a subgraph $H$ with $O(n^{1+\frac{1}{k}})$ edges such that any path $P$ of hop-length $\ell$ in $G$ has a replacement path $P'$ in $H$ of weighted length $\leq w(P)+(2k-2)w^{(1/2)}(P)$ where $w(P)$ is the total edge weight of $P$, and $w^{(1/2)}$ denotes the sum of the largest $\lceil \frac{\ell}{2} \rceil$ edge weights along $P$. Moreover, we show such approximation is optimal for shortest paths of hop-length $2$. To our knowledge, this is the first construction of a spanner for weighted graphs that strictly improves upon the stretch of multiplicative $(2k-1)$-spanners for all non-adjacent vertex pairs, while maintaining the same size bound. Our technique is based on using clustering and ball-growing, which are methods commonly used in designing spanner algorithms, to analyze simple greedy algorithms. This allows us to combine the flexibility of clustering approaches with the unique properties of the greedy algorithm to get improved bounds. In particular, our methods give a very short proof that the parallel greedy spanner adds $O(kn^{1+\frac{1}{k}})$ edges, improving upon known bounds.

Authors: Elad Tzalik

We study $(α,β)$-spanners for weighted graphs. We propose a simple greedy completion procedure which starts from a sparse initial graph, and repeatedly fixes pairs of vertices with a bad stretch, generalizing Kunedsen's additive completion [SWAT '14]. As an application, we construct $(k,k-1)$-spanners for weighted graphs of size $\tilde{O}(n^{1+1/k})$, which were previously unknown.

I’m on a spring break vacation-plus-lecture-tour with Dana and the kids in Mexico City this week, and wasn’t planning to blog, but I see that I need to make an exception. Charles Bennett and Gilles Brassard have won the Turing Award, for their seminal contributions to quantum computing and information including the BB84 quantum key distribution scheme. This is the first-ever Turing Award specifically for quantum stuff (though previous Turing Award winners, including Andy Yao, Leslie Valiant, and Avi Wigderson, have had quantum among their interests).

As a practical proposal, BB84 is already technologically feasible but has struggled to find an economic niche, in a world where conventional public-key encryption already solves much the same problem using only the standard Internet—and where, even after scalable quantum computers become able to break many of our current encryption schemes, post-quantum encryption (again running on the standard Internet) stands ready to replace those schemes. Nevertheless, as an idea, BB84 has already been transformative, playing a central role in the birth of quantum information science itself. Beyond BB84, Bennett and Brassard have made dozens of other major contributions to quantum information science, with a personal favorite of mine being the 1994 BBBV (Bennett Bernstein Brassard Vazirani) paper, which first established the limitations of quantum computers at solving unstructured search problems (and indeed, proved the optimality of Grover’s algorithm even before Grover’s algorithm had been discovered to exist).

While I take my kids to see Aztec artifacts, you can learn much more from Ben Brubaker’s Quanta article, to which I contributed without even knowing that it would be about Bennett and Brassard winning the Turing Award (info that was strictly embargoed before today). It’s an honor to have known Charlie and Gilles as well as I have for decades, and to have been able to celebrate one of their previous honors, the Wolf Prize, with them in Jerusalem. Huge congrats to two of the founders of our field!

By Scott

Gilles Brassard and Charlie Bennett

Charlie Bennett and Gilles Brassard will receive the 2025 ACM Turing Award for their work on the foundations of quantum information science, the first Turing award for quantum. Read all about it in The New York Times, Science and Quanta.

Bennett and Brassard famously met in the water off a beach during the 1979 FOCS conference in Puerto Rico. That led to years of collaboration, most notably for their quantum secure key distribution protocol. The basic idea is pretty simple and does not require quantum entanglement. Alice sends a series of random bits, either straightforward or rotated 45 degrees. Bob measures each of these bits in randomly chosen bases. They discard the bits where they used different bases and use some of the remaining bits to check for eavesdropping, which would collapse the state, and others to set the key.

Bennett and Brassard and four other authors showed how to teleport a quantum bit using entanglement and two classical bits. Bennett with Stephen Wiesner gave the dual superdense coding protocol of sending two classical bits using a single quantum bit. 

Bennett and Brassard, with Ethan Bernstein and Umesh Vazirani, showed that in black-box setting, quantum computers would require \(\Omega(\sqrt{n})\) queries to search \(n\) entries, matching Grover's algorithm. For some reason, the popular press rarely covers these results that limit the power of quantum computing. 

I've had the pleasure of knowing both Bennett and Brassard since the 1980s, both just full of enthusiasm and wonderful ideas. 

Let me end by saying I don't see this as a Turing award for quantum computing. Once (if?) we get large scale machines, we'll certainly see Turing awards, if not Nobel Prizes, for Peter Shor, Umesh Vazirani and others.

By Lance Fortnow

The National University of Singapore invites applications for the position of Research Fellow (postdoc) in the Department of Computer Science, School of Computing (SoC). Possible subjects include quantum space complexity, quantum property testing, and quantum communication complexity. Feel free to send any questions to John Kallaugher at the e-mail below.

Website: https://careers.nus.edu.sg/job/Research-Fellow-%28Quantum-Computing-Theory%29%2C-School-of-Computing/32155-en_GB/
Email: john.kallaugher@nus.edu.sg

By shacharlovett

Authors: Sahil Samar, Marc Vinyals, Vijay Ganesh

We prove that there exists a deterministic configuration of Conflict Driven Clause Learning (CDCL) SAT solvers using a variant of the VSIDS branching heuristic that solves instances of the Ordering Principle (OP) CNF formulas in time polynomial in n, where n is the number of variables in such formulas. Since tree-like resolution is known to have an exponential lower bound for proof size for OP formulas, it follows that CDCL under this configuration has an exponential separation with any solver that is polynomially equivalent to tree-like resolution and therefore any configuration of DPLL SAT solvers.

Authors: Steven Kordonowy, Bibhas Adhikari, Hannes Leipold

We develop a perfectly distributable quantum-classical streaming algorithm that processes signed edges to efficiently estimate the counts of triangles of diverse signed configurations in the single pass edge stream. Our approach introduces a quantum sketch register for processing the signed edge stream, together with measurement operators for query-pair calls in the quantum estimator, while a complementary classical estimator accounts for triangles not captured by the quantum procedure. This hybrid design yields a polynomial space advantage over purely classical approaches, extending known results from unsigned edge stream data to the signed setting. We quantify the lack of balance on random signed graph instances, showcasing how the classical and hybrid algorithms estimate balance in practice.

Authors: Zach Hunter, Matthew Kwan, Lisa Sauermann

Fix a finite field $\mathbb F_q$ and let $A\in \mathbb F_q^{n\times n}$ be a uniformly random $n\times n$ matrix over $\mathbb F_q$. The asymptotic distribution of the determinant $\det(A)$ is well-understood, but the asymptotic distribution of the permanent $\operatorname{per}(A)$ is still something of a mystery. In this paper we make a first step in this direction, proving that $\operatorname{per}(A)$ is significantly more uniform than $\det(A)$.

Authors: Sarita de Berg, Joachim Gudmundsson, Peter Kramer, Christian Rieck, Sampson Wong

We investigate multiple fundamental variants of the classic coordinated motion planning (CMP) problem for unit square robots in the plane under the $L_1$ metric. In coordinated motion planning, we are given two arrangements of $k$ robots and are tasked with finding a movement schedule that minimizes a certain objective function. The two most prominent objective functions are the sum of distances traveled (Min-Sum) and the latest time of arrival (Min-Makespan). Both objectives have previously been studied extensively. We introduce a new objective function for CMP in the plane. The proposed Min-Exposure objective function defines a set of polygonal regions in the plane that provide cover and asks for a schedule with minimal elapsed time during which at least one robot is partially or fully outside of these regions. We give an $\mathcal{O}(n^4\log n)$ time algorithm that computes exposure-minimal schedules for $k=2$ robots, and an XP algorithm for arbitrary $k$. As a result of independent interest, we leverage new insights to prove that both the Min-Makespan and Min-Sum objectives are fixed-parameter tractable (FPT) parameterized by the number of robots. Our parameterized complexity results generalize known FPT results for rectangular grid graphs [Eiben, Ganian, and Kanj, SoCG'23].

Authors: Marcel Nöhre, Dominik Dürrschnabel, Bernhard Ganter, Gerd Stumme

The visualization of concept lattices is a central problem in the field of Formal Concept Analysis. Force-directed algorithms, as popular in graph drawing, are a promising approach, treating lattice diagrams as physical models, optimizing node positions based on forces derived from the lattice structure. We build on the work of Zschalig, who, however, limited himself to attribute-additive diagrams. We use a more general additivity, in which both the attributes and the objects contribute to the positions of the concept nodes. We replace the planarity enhancer used by Zschalig to obtain a starting diagram for force-directed optimization with the DimDraw algorithm, which generates structured order diagrams on its own. The combination results in DimFlux, an algorithm that leverages the advantages of DimDraw but generates additive diagrams in which readability is increased by maximizing the conflict distance between nodes and non-incident edges.

Authors: Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas

We study mean estimation for a Gaussian distribution with identity covariance in $\mathbb{R}^d$ under a missing data scheme termed realizable $ε$-contamination model. In this model an adversary can choose a function $r(x)$ between 0 and $ε$ and each sample $x$ goes missing with probability $r(x)$. Recent work Ma et al., 2024 proposed this model as an intermediate-strength setting between Missing Completely At Random (MCAR) -- where missingness is independent of the data -- and Missing Not At Random (MNAR) -- where missingness may depend arbitrarily on the sample values and can lead to non-identifiability issues. That work established information-theoretic upper and lower bounds for mean estimation in the realizable contamination model. Their proposed estimators incur runtime exponential in the dimension, leaving open the possibility of computationally efficient algorithms in high dimensions. In this work, we establish an information-computation gap in the Statistical Query model (and, as a corollary, for Low-Degree Polynomials and PTF tests), showing that algorithms must either use substantially more samples than information-theoretically necessary or incur exponential runtime. We complement our SQ lower bound with an algorithm whose sample-time tradeoff nearly matches our lower bound. Together, these results qualitatively characterize the complexity of Gaussian mean estimation under $ε$-realizable contamination.

Authors: Younes Ben Mazziane, Vinay Kumar B. R., Othmane Marfoq

\texttt{Elastic-Sketch} is a hash-based data structure for counting item's appearances in a data stream, and it has been empirically shown to achieve a better memory-accuracy trade-off compared to classical methods. This algorithm combines a \textit{heavy block}, which aims to maintain exact counts for a small set of dynamically \textit{elected} items, with a light block that implements \texttt{Count-Min} \texttt{Sketch} (\texttt{CM}) for summarizing the remaining traffic. The heavy block dynamics are governed by a hash function~$β$ that hashes items into~$m_1$ buckets, and an \textit{eviction threshold}~$λ$, which controls how easily an elected item can be replaced. We show that the performance of \texttt{Elastic-Sketch} strongly depends on the stream characteristics and the choice of~$λ$. Since optimal parameter choices depend on unknown stream properties, we analyze \texttt{Elastic-Sketch} under a \textit{stationary random stream} model -- a common assumption that captures the statistical regularities observed in real workloads. Formally, as the stream length goes to infinity, we derive closed-form expressions for the limiting distribution of the counters and the resulting expected counting error. These expressions are efficiently computable, enabling practical grid-based tuning of the heavy and \texttt{CM} blocks memory split (via $m_1$) and the eviction threshold~$λ$. We further characterize the structure of the optimal eviction threshold, substantially reducing the search space and showing how this threshold depends on the arrival distribution. Extensive numerical simulations validate our asymptotic results on finite streams from the Zipf distribution.

Authors: Kabir Aladin Verchand, Ankit Pensia, Saminul Haque, Rohith Kuditipudi

We consider computationally-efficient estimation of population parameters when observations are subject to missing data. In particular, we consider estimation under the realizable contamination model of missing data in which an $ε$ fraction of the observations are subject to an arbitrary (and unknown) missing not at random (MNAR) mechanism. When the true data is Gaussian, we provide evidence towards statistical-computational gaps in several problems. For mean estimation in $\ell_2$ norm, we show that in order to obtain error at most $ρ$, for any constant contamination $ε\in (0, 1)$, (roughly) $n \gtrsim d e^{1/ρ^2}$ samples are necessary and that there is a computationally-inefficient algorithm which achieves this error. On the other hand, we show that any computationally-efficient method within certain popular families of algorithms requires a much larger sample complexity of (roughly) $n \gtrsim d^{1/ρ^2}$ and that there exists a polynomial time algorithm based on sum-of-squares which (nearly) achieves this lower bound. For covariance estimation in relative operator norm, we show that a parallel development holds. Finally, we turn to linear regression with missing observations and show that such a gap does not persist. Indeed, in this setting we show that minimizing a simple, strongly convex empirical risk nearly achieves the information-theoretic lower bound in polynomial time.

Authors: Thomas Bläsius, Annemarie Schaub, Marcus Wilhelm

We present an algorithm that computes the diameter of random geometric graphs (RGGs) with expected average degree $Θ(n^δ)$ for constant $δ\in(0,1)$ in $\tilde{O}(n^{\frac{3}{2}(1+δ)} +n^{2 - \frac{5}{3}δ})$ time, asymptotically almost surely. This brings the running time down to $\tilde{O}(n^{\frac{33}{19}})\approx \tilde{O}(n^{1.737})$ for average degree $Θ(n^{3/19})$. To the best of our knowledge, this constitutes the first such bound for RGGs and for a substantial range of average degrees, it is notably smaller than the recent bound of $O^*(n^{2-1/18}) \approx O^*(n^{1.944})$ by Chan et al. (FOCS 2025) for the more general class of all unit disk graphs. Our algorithm also works on RGGs with the flat torus as ground space, with a running time in $\tilde{O}(n^{\frac{3}{2}(1+δ)} + n^{2 - \frac{1}{3}δ})$. While our bounds on random geometric graphs are interesting in their own right, they are only an application of our main contribution: A general framework of deterministic graph properties that enable efficient diameter computation. Our properties are based on the existence of balanced separators that are well-behaved regarding the metric space defined by the graph and can be seen as a distillation of the combinatorial features a graph gets from having an underlying geometry. As a by-product of verifying that RGGs fit into our framework, we also derive running time bounds for iFUB, a diameter algorithm by Crescenzi et al. (TCS 2013) that is highly efficient on real-world graphs. We show that a.a.s.\ iFUB achieves a speedup in $\tildeΩ(n^{δ/3})$ over the naive $O(nm)$ algorithm, but runs in $Ω(nm)$ time on torus RGGs. This constitutes the first theoretical analysis in a geometric setting and confirms prior empirical evidence, thus suggesting geometry as a reasonable model for certain real-world inputs.

Authors: Massimo Equi, Md Rabiul Islam Khan, Veli Mäkinen

A degenerate string is a sequence of sets of characters. A generalized degenerate (GD) string extends this notion to the sequence of sets of strings, where strings of the same set are of equal length. Finding an exact match for a pattern string inside a GD string can be done in $O(mn+N)$ time (Ascone et al., WABI 2024), where $m$ is the pattern length, $n$ is the number of strings and $N$ the total length of strings constituting the GD string. We modify this algorithm to work under a quantum model of computation, achieving running time $\tilde{O}(\sqrt{mnN})$.

Authors: Parikshit Gopalan, Konstantinos Stavropoulos, Kunal Talwar, Pranay Tankala

Recent work has highlighted the centrality of smooth calibration [Kakade and Foster, 2008] as a robust measure of calibration error. We generalize, unify, and extend previous results on smooth calibration, both as a robust calibration measure, and as a step towards omniprediction, which enables predictions with low regret for downstream decision makers seeking to optimize some proper loss unknown to the predictor. We present a new omniprediction guarantee for smoothly calibrated predictors, for the class of all bounded proper losses. We smooth the predictor by adding some noise to it, and compete against smoothed versions of any benchmark predictor on the space, where we add some noise to the predictor and then post-process it arbitrarily. The omniprediction error is bounded by the smooth calibration error of the predictor and the earth mover's distance from the benchmark. We exhibit instances showing that this dependence cannot, in general, be improved. We show how this unifies and extends prior results [Foster and Vohra, 1998; Hartline, Wu, and Yang, 2025] on omniprediction from smooth calibration. We present a crisp new characterization of smooth calibration in terms of the earth mover's distance to the closest perfectly calibrated joint distribution of predictions and labels. This also yields a simpler proof of the relation to the lower distance to calibration from [Blasiok, Gopalan, Hu, and Nakkiran, 2023]. We use this to show that the upper distance to calibration cannot be estimated within a quadratic factor with sample complexity independent of the support size of the predictions. This is in contrast to the distance to calibration, where the corresponding problem was known to be information-theoretically impossible: no finite number of samples suffice [Blasiok, Gopalan, Hu, and Nakkiran, 2023].

Authors: Vladimir Kolmogorov, Jack Spalding-Jamieson

We present a family of fast pseudo-approximation algorithms for the minimum balanced vertex separator problem in a graph. Given a graph $G=(V,E)$ with $n$ vertices and $m$ edges, and a (constant) balance parameter $c\in(0,1/2)$, where $G$ has some (unknown) $c$-balanced vertex separator of size ${\rm OPT}_c$, we give a (Monte-Carlo randomized) algorithm running in $O(n^{O(\varepsilon)}m^{1+o(1)})$ time that produces a $Θ(1)$-balanced vertex separator of size $O({\rm OPT}_c\cdot\sqrt{(\log n)/\varepsilon})$ for any value $\varepsilon\in[Θ(1/\log(n)),Θ(1)]$. In particular, for any function $f(n)=ω(1)$ (including $f(n)=\log\log n$, for instance), we can produce a vertex separator of size $O({\rm OPT}_c\cdot\sqrt{\log n}\cdot f(n))$ in time $O(m^{1+o(1)})$. Moreover, for an arbitrarily small constant $\varepsilon=Θ(1)$, our algorithm also achieves the best-known approximation ratio for this problem in $O(m^{1+Θ(\varepsilon)})$ time. The algorithms are based on a semidefinite programming (SDP) relaxation of the problem, which we solve using the Matrix Multiplicative Weight Update (MMWU) framework of Arora and Kale. Our oracle for MMWU uses $O(n^{O(\varepsilon)}\text{polylog}(n))$ almost-linear time maximum-flow computations, and would be sped up if the time complexity of maximum-flow improves.