Theory of Computing Report

Front-running is a pervasive and costly problem on blockchains. Users earn rewards by publishing functional transactions that keeps markets efficient, such as arbitrage. But an attacker can observe such a transaction before it is ordered and publish her own ahead of it, seizing the reward and eroding users’ incentive to issue these transactions at all. The problem is well known and has drawn sustained effort from both industry and academia,...

By Hongyin Chen, Xu Zheng, Jichen Li, Ittay Eyal

Of the many cursed segments of vertical video, few annoy me more than the cottage industry of lunatics ranting over screenshots of PubMed pages to claim authority for whatever therapy, training program, or peptide they are selling. These people are all full of shit. They promise to cure your pain, get you thin, and make you stronger. All through SCIENCE.

These influencers will tell you that the scientific is better than the not scientific, and might even go so far as to say that the remainder is pseudoscience or quackery. But we unfortunately live in a narrow-minded world where scientific too often means “proven efficacious in a systematic review of randomized controlled trials.” You’ll be hard-pressed to find anything in the realm of treating musculoskeletal limitations that fits the bill.

It’s hard to shoehorn these sorts of therapies into the starting requirements for randomized trials. We’d need to start with clean definitions of an intervention and an outcome. What would these be for the management of pain by physical therapy?

Let’s start with the intervention. If we are being dogmatic evidence-based practitioners, the intervention in any physical therapy trial is the invitation to have therapy. According to the intention-to-treat principle, the invitation is the only thing that can be randomized. We can’t look only at the people who comply with every instruction and make it to the end of the rigorous therapy regimen. The model patients who diligently comply might differ from those who don’t, and our statistical signal will be biased if we include only the former. The only way to avoid these selection biases is to count everyone who was randomized, regardless of what happens between randomization and the final assessment. Both committed patients and no-shows contribute to the measured average efficacy.1

But what does it even mean for patients to follow the protocol? Physical therapy is far more complex than taking a drug. There’s no simple unit of treatment applied. Each interaction with a physical therapist involves a conversation about how things have been going, a plan for moving forward, some sort of interactive intervention in the office, and a discussion about what to do once the patient goes home. Each step here introduces a new branch in a deep decision tree. And every PT I’ve interacted with has been different, even when performing similar range-of-motion tests or manual therapies. Moreover, the treatment of any session depends on the entire history of the treatment so far. On top of this, every physical therapist I’ve seen has assigned daily exercises to do between sessions. This is part of the treatment, too! There is no way to perfectly isolate and randomize a single component of these complex treatment protocols.

A multi-stage protocol is an exponentially large collection of interventions. I made this point on the blog a few weeks ago in the context of anticoagulant trials for heart disease: “If you want to compare the effect of three different timings and three different dosages of a single drug, you need nine arms in your trial. If you want to additionally see if a second drug is helpful, you need 18.” Physical therapy is arguably much more complex.2

What about the outcome? In drug trials, we might get grim, unambiguous, objective outcomes like mortality. In vaccine trials, we might get unambiguous outcomes, such as a PCR diagnosis. Unfortunately, in pain management, the outcome is necessarily subjective. You can measure changes in range of pain-free motion, but there is too much heterogeneity to definitively stake out what a good outcome would be. Instead, pain therapies are most commonly evaluated based on improvements on the Numeric Ranking Scale. Studies ask participants at admission how their pain is on a scale of 0 (no pain) to 10 (worst pain imaginable). They ask them again at the follow-up. Statistical protocol then dictates computing the mean of the differences in treatment and control and running a t-test. You can try to remove the heterogeneity in how people respond to these questions, but these adjustments are based on subjective clinician calls. No matter what you do, pain is hard to mathematize. Doing statistics on these “numbers” and coming away with strong conclusions is a fool’s errand.

Beyond the treatment and outcome, all sorts of investigator biases make randomized trials even messier. You can blind the patients and the clinicians who assess outcomes, but you can’t blind the people applying physical therapy. It’s impossible to say what effect this sort of bias has on the scientific record. Even when well-intentioned, a clinician who believes in PT can subtly give away the secret assignment to their patients during a session.

I’ve never read a single study in this space that’s been compelling, and I don’t know why we hope that a narrow view of therapy can help us out of it. This fuels the fire of debate with people using studies to attack each other’s practices. There are countless articles and videos castigating stretching, massage, or cupping as not backed by evidence. These are all denounced as pseudoscience by a medical establishment that prescribed OxyContin like candy for two decades. Boy do I have some bad news for people who think there is great evidence that opioids work for pain management.

If we want to understand best practices for “wellness,” we need a different language around it. Maybe this language will need to lean on biomechanical plausibility or biochemical pathways. That certainly wouldn’t hurt. But more importantly, the language will have to prioritize discussions of craft, practice, and the cultivation of expertise. Whatever the case, the narrow definition of evidence-based needs to be reimagined. Healthcare is far more than a collection of unambiguous interventions with unambiguous outcomes.

Subscribe now

By Ben Recht

Authors: Luyining Gan, Jie Han, Bin Wang

A $4$-uniform $2$-cycle in a $4$-uniform hypergraph of length $t$ is a cyclic ordering of $2t$ vertices $v_1v_2\cdots v_{2t}v_1$ such that $v_{2i+1}v_{2i+2}v_{2i+3}v_{2i+4}$ are edges for $0\le i\le t-1$ while the addition is modulo $2t$. For every $γ>0$ and large $n$, we characterize the $n$-vertex $4$-uniform hypergraphs such that every triple of vertices is contained in at least $(1/3+γ)n$ edges and admits a Hamilton $2$-cycle. Up to the error term $γn$, the assumption on the minimum codegree is best possible and verifies a conjecture of Garbe and Mycroft. As a consequence, this gives a polynomial-time algorithm that decides whether an $n$-vertex $4$-uniform hypergraph with minimum codegree $(1/3+γ)n$ contains a Hamilton $2$-cycle. This stands as a steep contrast to the graph case where such a hardness gap has size $o(n)$.

Authors: Pingshi Yu, Chengsong Tan, Nicolas Wu, Alastair Donaldson

Randomised testing is a widely-used approach to software validation, yet its theoretical foundations remain thin. In particular, the fundamental question of what it means for a set of inputs to be \emph{generable} has gone unanswered in both the literature and folklore. We present the first complexity-theoretic foundations for random generators in software testing. We model generators as Turing transducers that consume random bits and produce string-encoded outputs, and show that the theoretically generable languages coincide exactly with the recursively enumerable languages. This has direct implications for testing at the boundaries of decidability, such as compiler testing. For \emph{efficient} generation, we show that the polynomial-time generable languages lie within \textit{NP}, that certain \textit{NP}-complete languages admit efficient generators, and that -- under standard cryptographic assumptions -- there are languages in \textit{P} for which no efficient generator exists: the complexity of efficienct generation and of efficient decision are not the same. We show space-bounded complexity is the natural framework for generators producing \emph{correlated} samples, capturing methodologies such as coverage-guided fuzzing and symbolic execution. Beyond classification, we characterise efficient generability: a language has a polynomial-time generator iff it admits a \emph{certificate scheme} over a verifier -- so witness planting, the folklore technique behind generators to test SAT solvers, is in a sense the only route to efficient generation. On the design of property-based testing libraries, we prove no library can compositionally derive efficient generators from logical predicates involving conjunction or negation, under standard assumptions. However, restricted classes like \textit{NL} (equivalently, linear Datalog predicates) would admit such a compilation.

Authors: Christoph Hertrich, Moritz Stargalla

We study tropical circuits with scalar multiplication gates, that is, algebraic circuits whose gates implement $\max$, $+$, or multiplication with a positive constant. For such circuits, we prove exponential size lower bounds for computing maximum weight directed spanning trees and maximum weight bipartite perfect matchings. As a corollary, we obtain an exponential size separation between monotone and non-monotone maxout neural networks, which generalize the popularly used ReLU neural networks. One conclusion from this is that neural network models with enforced convexity constraints, such as input-convex neural networks (ICNNs), sometimes need to be exponentially larger than their unrestricted counterparts in order to express the same functions.

Authors: Léo Gayral, Mathieu Hoyrup

Links between physicals systems and computability properties have been an active field of investigation in recent years. Inspired by a previous work in the context of positive temperature Gibbs measures, we prove here that in the context of zero-temperature ergodic optimisation, for a computable potential and provided with several reasonable assumptions, the maximum ergodic average is a computable real number, and the set of maximising measures is a $Π_1$-computable compact set. Then, in the more specific context of symbolic dynamics, with finite-range interactions on subshifts of finite type, we provide an explicit algorithm to compute both the maximum ergodic average and the set of maximising measures in finite time, with a matching code repository.

Authors: Chaithanya Rayudu, Jun Takahashi

The Lee-Yang theorem and its quantum extensions state that, for a broad class of Hamiltonians on any graph, the partition function's zeros in the complex magnetic field plane lie only on the imaginary axis. For these Hamiltonians, we prove that under a uniform Z-field of any strength h, the ground state has a spectral gap of at least h/4, independent of the system size and of the coupling strengths. The proof uses the zero-freeness of the partition function as given by Asano and Suzuki-Fisher to show exponential decay of the imaginary-time correlations for any product of Z-operators. Our result gives a polynomial-time quantum algorithm for computing the ground state energy of any Lee-Yang Hamiltonian.

Authors: Vaibhav Krishan, Jayalal Sarma

We explore a torus polynomial approximation based approach towards a long-standing question: whether $AND$ can be computed by $CC^0$ circuits - the class of constant-depth polynomial size circuits containing $MOD_m$ gates for some $m$. Bhrushundi et al. (ITCS 2019) introduced torus polynomial approximations as an approach for proving lower bounds against $ACC^0$ - a class containing $CC^0$ with circuits comprising $AND$, $OR$ and $NOT$ gates. We show how lower bounds for torus polynomials approximating $AND$ can be used to make progress on this question. Using lower bounds on the degree of symmetric torus polynomials approximating $AND$ from Krishan and Vishwanathan (ITCS 2026), we prove size lower bounds for symmetric $CC^0$-circuits computing $AND$. More precisely, we prove that any depth $h$ symmetric $CC^0$ circuit requires $2^{\widetildeΩ(n^{1/O(h)})}$ size to compute $AND$. A key ingredient in our proof is an argument that we can construct symmetric torus polynomials to approximate symmetric $CC^0$ circuits. Our construction exhibits an explicit correspondence between the symmetry of the circuit and that of the polynomial. Using this, we also establish lower bounds for weaker notions of circuit symmetry. Lower bounds for symmetric $CC^0$ circuits were also independently established by Pago (ICALP 2026) using different techniques. In the asymmetric regime, we establish degree upper bounds for depth three circuits of the form $MOD_p \circ MOD_m \circ AND_{O(1)}$ where $m=pq$ is a semiprime. This circuit class is a special case of the constant degree hypothesis, introduced by Barrington, Straubing and Therien (Inf. and Comp., 1990), where $m$ could be an arbitrary composite number. We argue that improved lower bounds for asymmetric torus polynomials approximating $AND$ imply size lower bounds for semiprime $m$ and hence progress on the constant-degree hypothesis.

Authors: Kai Cieliebak, Ángel González-Prieto, Eva Miranda

We prove that, given any contact $3$-manifold and any computable function $f: \mathbb{N} \dashrightarrow \mathbb{N}$, there exists a defining contact form and a Poincaré section of its Reeb flow whose partially defined return map computes $f$.

Authors: Hanlin Ren, Ryan Williams

We prove a near-maximum ($2^n / n$) circuit lower bound for the complexity class $\mathsf{E}^{\mathrm{pr}\mathsf{MA}}/_1$, corresponding to exponential time with access to a promise-$\mathsf{MA}$ oracle and one bit of advice. Our proof incorporates the iterative win-win paradigm (Chen--Lu--Oliveira--Ren--Santhanam, FOCS'23), the reduction from the Range Avoidance problem to circuit lower bounds (Jeřábek, Ann. Pure Appl. Log. '04; Korten, FOCS'21), and the PCP theorem. Crucial to our proof is the analysis of the complexity class $\mathsf{P}^\mathsf{NP}[{\textsf{#rounds}}=r, {\textsf{length}}=s]$, which is $\mathsf{P}^\mathsf{NP}$ with $r(n)$ adaptive rounds of $\mathsf{NP}$ queries, where each $\mathsf{NP}$ query has witness length $s(n)$.

Authors: Christoph Buchheim, Lowig Duer, Eva Ley, Maximilian Merkert, Komal Muluk

We consider bilevel optimization problems in which leader and follower jointly construct a feasible solution for an underlying combinatorial optimization problem. Response problems ask whether the leader can encourage -- or, in the pessimistic setting, enforce -- a reaction of the follower that includes a set of mandatory items while excluding a set of forbidden items. Our investigation focuses on tractability results for various cases which emerge from different combinations of the total number of mandatory, forbidden, and neutral items. After providing some results for response problems that hold for any underlying combinatorial optimization problem, we examine response problems over the maximum-weight matching problem and the minimum-weight perfect matching problem as illustrative and surprisingly varied examples. Among other results, we show that the response problem is hard for even a single given mandatory or forbidden edge. On the other hand, it is fixed-parameter tractable with respect to the total number of non-mandatory edges. If, however, each follower's edge is either mandatory or forbidden, the response problem for the perfect matching problem is solvable in polynomial time while it remains NP-hard for the maximum-weight matching problem.

Authors: Ei Ando

We investigate the problem of computing the distribution function for the shortest and longest path lengths in a directed graph with random edge lengths. Specifically, when these lengths are uniformly distributed, the problem reduces to computing the volume of a polytope defined by the graph structure. We establish that the problem is $\#P$-hard, even under the restricted condition that the random edge lengths are identically and independently distributed (i.i.d.) according to any continuous probability distribution with certain natural conditions, the local uniformity. This hardness result applies broadly: while the uniform distribution provides an essential case for the reduction, other distributions -- such as exponential or normal -- are similarly hard because they contain uniform distributions in every arbitrarily small interval. Furthermore, we show that the problem is contained within $\mathrm{XP}$ with respect to the treewidth $k$ of the underlying undirected graph. For the specific case of i.i.d. uniform edge lengths, we present a novel dynamic programming algorithm that processes a tree decomposition by iteratively performing convolutions to propagate distribution functions. Our approach achieves a time complexity of $n^{O(k^2)}$ for any fixed treewidth $k$.

Authors: Amirmahdi Mirfakhar, Maria-Florina Balcan, Hedyeh Beyhaghi

We study the problem of efficient online proportional sampling from a high-dimensional domain under a $σ$-smoothed adversary, where the sampling distribution is induced by a dynamically evolving weight function defined over a sequence of piecewise-structured partitions. This setting captures a broad range of applications, including principal-agent games (e.g., pricing and contract design), and algorithm configuration and parameter tuning. The central challenge is maintaining an efficient data structure as the induced partition grows increasingly complex over time -- naively, the number of subregions can grow as $O(t^d)$ by round $t$ in $d$ dimensions. We design a data structure that supports efficient updates and proportional sampling while avoiding the cost of explicitly maintaining this exponential growth, where the discontinuities are structured from axis-parallel hyperplanes. Under a $σ$-smoothed adaptive adversary, we prove a tight $O(\sqrt{σT})$ bound on the depth of our data structure, and an $O(\log T)$ bound under a random-order adversary -- to our knowledge, the first such results for this class of problems. We apply this framework to online learning with piecewise-structured rewards, obtaining efficient no-regret algorithms under both full-information and bandit feedback, with provable sublinear regret guarantees.

Authors: Sariel Har-Peled, Elfarouk Harb, Qizheng He

Given a positive integer $k$, we study the problem of finding a convex polygon of minimum perimeter that encloses exactly $k$ points of $\mathbf{Z}^2$. We show that an optimal polygon is contained in a circular annulus of width $O(k^{1/6})$, has $Θ(k^{1/3})$ boundary grid points, and its longest edge has length $Θ(k^{1/4})$. Using these structural bounds, we present a deterministic algorithm that computes an optimal polygon in $O(k^{29/18+o(1)})$ time, improving over the previous $O(k^3)$-time algorithm.

Authors: Chaya Keller, Shakhar Smorodinsky

The VC-dimension is a fundamental measure of the complexity of a set system. In this paper, we introduce and study a colorful variant of VC-dimension that captures the behavior of set systems on colored ground sets. By studying this new notion, we obtain a variety of geometric results. First, we prove that separable abstract convexity spaces with Radon number $D$ admit a Tverberg theorem with Tverberg number $O(D^2 r \log r)$. This bound significantly improves the $O(Dr^2\log r)$ bound of Alon and Smorodinsky from SODA'26 and is the first quasi-linear bound in $r$, in which the dependence on $D$ is not super-exponential. Second, we prove the first colorful $k$-wise Tverberg theorem for separable abstract convexity spaces. Using this theorem, we obtain a colorful selection lemma with $O(D^3)$ colors, an uncolored selection lemma for subsets of size $O(D^3)$, a weak $\varepsilon$-net theorem with nets of size $O_D(\varepsilon^{-O(D^3)})$, and a $(p,q)$-theorem with exponent of $\mathrm{poly}(D)$. All these quantitative bounds are significantly better than the best previously known general bounds for abstract convexity spaces. Finally, we extend our method to obtain a colorful Tverberg theorem for unions of convex sets, generalizing the uncolored theorem of Alon and Smorodinsky (SODA'26).

Authors: Oscar Chacón-Rivera

We study maximum-sum red-blue matchings and matching equilibrium for finite planar point sets. For a red-blue perfect matching $M = \{(a_i,b_i) : 1 \le i \le n\}$, we define the gain of a directed red cycle as the change in total weight produced by cyclically shifting the corresponding blue partners. We prove that $M$ is maximum-sum if and only if every directed red cycle has nonpositive gain, and we derive a geometric sufficient condition for optimality from cyclic intersections of distance-difference regions. We then characterize balanced matchings, in which all red-blue perfect matchings have the same total weight. Equilibrium is shown to be equivalent to vanishing cycle gains, to an additive form of the distance matrix, and to a common level-set condition for distance-difference functions. In the squared Euclidean case this yields an orthogonality classification, while in the Euclidean case it yields a hyperbolic level-set description and a collinear-separation classification in the nondegenerate setting.

Authors: Theodore Fung, Csaba D. Tóth

For an edge-weighted graph $G=(V,E)$ and a stretch parameter $t\geq 1$, a $t$-spanner is a subgraph $H\subseteq G$ such that the shortest path distances in $G$ and $H$ satisfy $δ_H(u,v)\leq t\, δ_G(u,v)$ for all $u,v\in V$. In metric spanners, $V$ is a finite metric space, and $G$ is the complete graph with edge weights corresponding to the distances between the endpoints. When $G$ is the complete graph on $n$ points in the plane, $O(n)$-size $t$-spanners are possible for any $t>1$: For every $\varepsilon>0$, there is an $(1+\varepsilon)$-spanner with $O(n/\varepsilon)$ edges (i.e., the stretch can be arbitrarily close to 1). When $G=K(R,B)$ is the complete bipartite graph on $n$ bichromatic points in the plane, in general, no spanner construction can guarantee stretch $t<3$ with $o(n^2)$ edges. Bose et al.~(SICOMP 2009) constructed a $(3+\varepsilon)$-spanner with $O(n\log n)$ edges for any constant $\varepsilon>0$. Our main result is a new construction for a $(3+\varepsilon)$-spanner with $O(\sqrt{1/\varepsilon}\cdot n)$ edges. Eliminating the $O(\log n)$ factor resolves a problem left open for more than 17 years, and raises a new research problem about optimizing the dependence on $\varepsilon$. We also study spanners for $G=K(R,B)$ on $n$ bichromatic points on the real line: In this case, we show that the MST of $K(R,B)$ is a 7-spanner, and we construct a 3-spanner with at most $2n-3$ edges.

Authors: Reilly Browne, Prahlad Narasimhan Kasthurirangan

We consider covering and partitioning a simple polygon into pieces which either have unit geodesic radius or unit geodesic diameter, using the $\ell_2$-metric for distances. There is no known method for finding an exact solution to these problems, even when the input size is constant, and the problem is known to be NP-hard in the case of polygons with holes. With this in mind, we instead devote our attention to developing simple approximation algorithms that run in polynomial time. For the radius problem, we present the first known approximation algorithms for both covering and partitioning, achieving a factor of 9. For the diameter problem, we are only able to give a positive result for the partition version of the problem, where we improve upon a complicated 72-approximation from Abrahamsen and Rasmussen [SODA '25], achieving a simple 15-approximation.

Authors: Lotte Blank, Anne Drieme, Sariel Har-Peled, Marena Richter

We give linear-time, and thus optimal, $(1+\varepsilon)$-approximation algorithms for numerous variants of the Frechet distance between $c$-packed curves (where $c \in O(1)$), removing an additional log factor that was present in previous algorithms. The key to our new algorithms is a linear-size approximation of the elevation function, which uses a decomposition of the domain into rectangles, and a careful implicit dynamic programming on this decomposition. The algorithm extends to the strong, weak, discrete, and continuous Frechet distances with a running time of roughly $O(cn/\varepsilon)$. The $c$-packedness assumption is used only in the analysis, and the algorithm is simple and should work efficiently for other inputs.

Authors: Marcin Kozik, Stanislav Živný

For a relational structure A, the Minimum Cost Constraint Satisfaction Problem is the following problem denoted by MinCostCSP(A): Given an instance of CSP(A) with rational costs on variable-value pairs, find a solution to the instance minimizing the sum of the chosen costs. For the exact minimization, a classification of MinCostCSP(A) in terms of A was established by Takhanov [STACS'10]. We focus on constant-factor approximations of MinCostCSP(A). DeHaan, Huang, and Lee recently showed that if A fails to admit a conservative near-unanimity polymorphism then MinCostCSP(A) is not constant-factor approximable [APPROX'25]. We provide a first step towards a classification, by proving a dichotomy for structures A admitting a conservative majority (also known as 3-near-unanimity) polymorphism. Our dichotomy criterion is not in terms of an algebraic condition on A but we show that this is unavoidable. We include a simple argument proving that no such condition exists.

Authors: Jason Fong, Jeffrey Kam, Steven Wong

The subgraph reconfiguration problem asks whether one subgraph can be transformed into another via a sequence of local changes while maintaining a specified graph property. In this work, we focus on the setting where the subgraph is specified by its set of edges. Our contributions in this paper are twofold. First, motivated by the contrast that path reconfiguration is $\textsf{NP}$-hard while tree reconfiguration is solvable in linear time, we prove two generalizations: (1) for any fixed $k$ at least one, reconfiguring connected graphs with pathwidth at most $k$ is $\textsf{NP}$-hard, and (2) for any fixed $k$ at least two, reconfiguring graphs with pathwidth at most $k$ is also $\textsf{NP}$-hard. En route to proving (2), we show a general hardness result that applies to a range of minor-closed graph classes, which we use to show planar graph reconfiguration is also $\textsf{NP}$-hard. Second, given our negative results, we extend the problem to a resource-focused setting, asking how much additional buffer space is needed to turn a non-reconfigurable instance into a reconfigurable one. We show that $Ω(n)$ extra buffer space is needed for planar graphs and graphs with bounded pathwidth and treewidth, while $O(1)$ extra buffer space is sufficient for cactus graphs in a restricted setting.

Authors: Yu Gao

Rectilinear matching to the integer grid asks to assign each of $n$ points in $\mathbb R^2$ to a distinct point of $\mathbb Z^2$, minimizing total $\ell_1$ movement. The main difficulty is that the target set is infinite: one must first identify a finite set of relevant grid points without losing optimality. We prove a geometric compression theorem for this infinite-target problem. In $O(n\log^2 n)$ time, we construct a set $\mathcal{C}$ of asymptotically optimal size $O(n)$ such that, simultaneously for every $p\in[1,\infty]$, some optimal $\ell_p$ assignment uses only points of $\mathcal{C}$. The construction is independent of the subsequent optimization algorithm and of the coordinate spread. For the rectilinear case, we combine this candidate set with a linear-size sparse network representation of $\ell_1$ distances. In the word-RAM model with $O(1)$-word dyadic coordinates and $O(\log n)$ fractional bits, a nearly-linear time minimum-cost flow algorithm then gives a randomized exact algorithm with expected running time $\widetilde O(n)$. This improves the standard $\widetilde O(n^2)$ approach. Combined with existing finite geometric matching algorithms, the same candidate set also gives an $\widetilde O(n\sqrt n\log(1/\varepsilon))$-time $(1+\varepsilon)$ approximation for every fixed integer $p\ge1$.

Authors: Fran Sučić, Leo Vitasović, Nikola Petrušić

We present Need for Speed Sort (NFS Sort), a recursive distribution-based sorting algorithm designed for numeric arrays. The algorithm partitions elements into equal-width value intervals, recursively refines dense buckets, and propagates analytical interval bounds between recursive calls, avoiding repeated scans for local minima and maxima. NFS Sort combines a fragment-based, cache-conscious scatter procedure for large subarrays with a lower-overhead auxiliary-array approach for smaller inputs. Small buckets are deferred to a final insertion-sort cleanup, while a comparison-based fallback is activated when recursive partitioning repeatedly fails to reduce the problem size. This mechanism guarantees a worst-case running time of O(n log n) and auxiliary space usage of O(log n). Experimental evaluation on synthetic inputs and real-world datasets from the SOSD benchmark suite compares NFS Sort with Balanced Learned Sort, IPS4o, Boost Spreadsort, PDQSort, and std::sort. The results show that NFS Sort is competitive or better than established state-of-the-art sorting methods across dataset sizes and distributions, outperforming the learned baseline particularly on smaller inputs while retaining strong performance at larger scales. Overall, NFS Sort combines efficient recursive distribution, practical memory management, and robust worst-case guarantees for high-performance numeric sorting.

Authors: Thiago Oliveira, Mohit Singh, Sahil Singla

We study online welfare maximization with divisible resources. A sequence of $n$ players arrive one by one; upon arrival, each player draws a valuation function over $m$ divisible items from a known distribution, reveals this valuation, and must be allocated an irrevocable fractional bundle subject to unit supply constraints. While online welfare maximization has been extensively studied for indivisible items and combinatorial valuations, much less is known when the resources are divisible and players have multi-dimensional concave valuations. We give approximation algorithms for monotone concave valuations satisfying diminishing returns. Our main result is a $2/3$-approximation to the optimal online policy, also known as the philosopher benchmark. The algorithm is guided by a low-dimensional concave relaxation of the online benchmark and rounds it via a new single-item capped online contention resolution scheme. This Capped-OCRS problem allocates to each realized type no more than its prescribed fractional bundle while preserving a $2/3$-fraction of that bundle in expectation. Its analysis uses a submartingale potential for the remaining side, we show that computing the optimal online policy is #P-hard even for a single divisible item. We also obtain a tight prophet inequality against the offline hindsight optimum. We show that a fixed-price auction with one linear per-unit price for each original divisible item achieves a $1/2$-approximation to the offline/prophet benchmark. The prices are obtained by aggregating Aumann--Shapley supporting prices, a continuous analogue of supporting prices for submodular/XOS set functions, and yield simple item prices rather than copy-dependent prices arising from discretization. The factor $1/2$ for the prophet benchmark is information-theoretically tight even for one item with linear valuations.

Authors: Aljaž Krpan, Janez Povh

We study the interaction between reduction rules and upper-bound functions for the Maximum Clique Problem (MCP). We show how MCP upper-bound functions can strengthen classical core and truss reductions by replacing local size conditions with upper-bound tests. This leads to the \((k,ω^u)\)-core, the \((k,ω^u)\)-truss, and the more general \((k,d,ω^u)\)-truss, where the parameter \(d\) controls the trade-off between stronger reductions and additional computational cost. For each of these notions, we prove clique-preservation properties, correctness of the corresponding peeling algorithm, and running-time bounds. Based on these reductions, we introduce a general framework for improving upper-bound values for MCP. We give two concrete instantiations of the framework: one that uses only the combined truss and core reductions, and one that combines the truss and core reductions with repeated applications of structions. Computational experiments on 73 benchmark graphs show that the proposed reductions can substantially improve several standard upper-bound functions and that combining multiple reduction methods can be beneficial in practice. In particular, the combination of structions, truss and core reductions with a DSatur-based bound often reached SDP-level upper-bound values faster than direct SDP computation; on the tested graphs with edge density below \(0.7\), it did so in every case. Using the truss and core reduction with the Lovász theta upper-bound function, we also improve the previously best certified integer upper-bound values for three difficult DIMACS instances whose exact clique numbers are not known. In particular, we improve upper-bound values for graph \texttt{C500.9} from 83 to 73, for graph \texttt{C1000.9} from 122 to 115, and for graph \texttt{C2000.9} from 177 to 168.

Authors: Alexander E. Black, Lei Xue

In 1992, Billera and Sturmfels introduced coherent monotone paths on polytopes as part of their description of the fiber polytope construction, and later in 1994 showed with Kapranov that these coherent monotone paths capture the topology of the space of all monotone paths, paths from a minimum to a maximum, in the directed graph of a polytope with orientation induced by a linear function. Those results motivate the following analog of the polynomial Hirsch conjecture: Does there always exist a coherent monotone path of polynomial length on a polytope for any choice of orientation induced by a linear function? We show this is not the case by exhibiting a family of polytopes and corresponding linear functions for which every coherent monotone path is exponentially long. As applications, we strengthen longstanding results pertaining to lower bounds for the shadow simplex method, geometric transversals in discrete geometry, and parametric linear optimization.

Authors: Moses Charikar, Jon Kleinberg, Chirag Pabbaraju

We study how little extra information is needed to make adversarial language learning possible. In Gold's model of language identification in the limit, a learner is given an enumeration of the strings from an unknown language chosen from a countable language collection. The learner guesses the identity of the language over the course of the enumeration, and it succeeds if, eventually, all of its guesses are the correct language. Classical results of Gold and Angluin show that many natural collections cannot be learned in this way. Recent work on trace colorings, motivated by the success of thinking-trace strategies in language learning, overcomes this obstruction by annotating every symbol of every string with a color. We ask whether the learner really needs this whole sequence of colors, or whether one color at the end of each string (a terminal coloring) is enough for language identification. We show that just one terminal bit per string is enough for every countable collection of infinite languages. In fact, the colorings can be chosen collection-independently: there is a single assignment of a two-color terminal coloring to every infinite language such that the same preassigned colorings identify every countable subcollection. Thus, in this model, an entire color trace can be compressed to one bit attached to the end of each example. Our global construction uses transfinite recursion, and we prove that this kind of nonconstructivity is unavoidable for any bounded number of colors. As a notion of constructivity, we use the formalism of Borel maps (a regularity condition satisfied by natural explicit constructions); we show that no global terminal coloring with a finite number of colors defined by a Borel map can identify all countable subcollections. By contrast, known trace-coloring constructions are Borel when encoded as terminal colorings, but require infinitely many colors.

Authors: Sayan Bhattacharya, Ermiya Farokhnejad, Thatchaphol Saranurak, Haoze Wang

The minimum degree spanning tree problem is a classic NP-hard problem whose optimal approximation guarantee was established since the early 1990s: Fürer and Raghavachari [FR92] gave an $\tilde O(mn)$-time algorithm that computes a spanning tree with maximum degree $Δ^\star+1$, where $Δ^\star$ denotes the optimum value. Whether similarly strong guarantees can be achieved in near-linear time has remained open for over three decades. We give the first near-linear-time algorithm that computes a spanning tree with maximum degree $\lceil (1+ε)Δ^\star\rceil+1$ in $\tilde O(m/ε^2)$ time. Prior near-linear-time algorithms either achieved the weaker bound $\lceil (1+ε)Δ^\star\rceil + O(\log n/ε^2)$ [DHZ20] or required dense graphs with $m\ge n^{7/4}$ [CQT21,BFW26]. Using the same framework, our algorithm can also compute a spanning tree with maximum degree $Δ^\star+1$ in $\tilde O(mn^{2/3})$ time, improving upon the recent $\tilde O(mn^{3/4})$-time algorithm of [BFW26]. These two results strictly improve all previous construction algorithms for the minimum degree spanning tree problem.

Authors: Tamas Visegrady

Montgomery's trick accelerates simultaneous modular inversion of $N$ inputs by amortizing a single shared inversion, but auxiliary multiplications for complement products are typically scheduled in a linear, serial form. We construct a maximally parallelizable data-flow graph (DFG) that computes all $\overline{x}$ complement~products by scheduling auxiliary multiplications into idle multiplier slots during accumulation of the product of all inputs, and that of the shared inversion. This scheduling ensures the post-inversion phase adds exactly one multiplication layer of latency regardless of $N$, yielding a critical path latency of $\lceil \log_2 N \rceil$ multiply layers, one inversion, and one final parallel multiply layer.

Authors: Salil Vadhan, Jiyu Zhang

Inspired by recent advances in notions of spectral approximation of digraphs [Ahm+20], we study spectral algorithms for finding periodic structures in digraphs via the spectrum of a class of rotated Laplacian matrices. This class of Laplacian matrices was previously studied by Lange, Liu, Peyerimhoff, and Post [Lan+15]. We consider a notion of periodicity ratio that generalizes the bipartiteness ratio of Trevisan [Tre09], and show that it is closely related to the spectrum of rotated Laplacian matrices. In particular, if the digraph is strongly connected and represents a Markov chain, this periodicity ratio for a given $p \in \mathbb{N}$ is a quantitative measure of how close this Markov chain is to having periodicity $p$. We propose and analyze a periodicity-ratio variant of the spectral algorithm by Louis, Raghavendra, Tetali and Vempala [Lou+12]. We show that the algorithm runs in randomized polynomial time and can find many nearly periodic components (i.e, components with small periodicity ratio). This also implies a new higher-order Cheeger-type inequality for periodicity in the spirit of that in [Lou+12; LOT14]. As part of our analysis, we prove a new theorem that upper bounds the probability that the largest magnitudes of two sequences of coordinate-wise correlated complex Gaussian random variables occur at different indices, which may be of independent interest. Previously, an analogous result was known only for real Gaussian random variables.

Authors: Alexandr Andoni, Justin Dallant, László Kozma, Hantao Yu

We nearly settle a natural extremal question about set systems over $[n]$: the tradeoff between the {size} (number of sets) and the number of {full chains}. This question was initially raised by Johnson, Leader, and Russell [Combin.~Probab.~Comp., 2015] as a counterpart to Sperner-type results in combinatorics. Recently, a framework introduced by Ameli, Nederlof, and Wang, and independently by Dallant and Kozma [FOCS 2026] linked this question to the space- and time-complexity of Bellman-Held-Karp-style dynamic programming algorithms for permutation problems such as the traveling salesman (TSP). Precisely, they showed that a space-time product $γ^{n+o(n)}$ is feasible for the TSP, whenever a set system of (normalized) size $S$ and chain density $D$ exists, with $ γ= S^2/D$. In this paper we show an essentially {optimal} bound of $γ\approx 3.1819$ for this quantity, closing the gap between the previous best lower and upper bounds of $γ\geq 3.015$ and $ γ\leq 3.572$ respectively. This implies a TSP algorithm with space-time product $O(3.1819^n)$ for input size $n$, as well as a limit to further improvements in this broad framework. More generally, we can obtain close to optimal values $D$ for any feasible value $S$, effectively settling the question of the number of full chains at every size. The crucial step towards our results is casting the extremal combinatorics question as an {information~vs.~entropy} tradeoff involving two random variables. This reformulation {exactly} captures the optimal tradeoff for the combinatorial problem, leading to a framework in which primal-dual certificates can be derived, proving rigorous upper and lower bounds on $γ$. We also give a further application of our techniques, improving a bound of Duffus, Sands, and Winkler on the minimum size of fibres in the Boolean lattice.

Authors: Svenja M. Griesbach, Felix Hommelsheim, Max Klimm

We introduce a unified framework for classical search and routing problems, including pathwise search, expanding search, the minimum spanning tree problem, and the traveling salesperson problem. The framework is based on two parameters. The first is a discount factor $α\in [0,1]$: the first traversal of an edge incurs its full cost, whereas each subsequent traversal incurs only an $α$-fraction of this cost. For a path starting at a designated root vertex, the $α$-latency of a vertex is the discounted cost accumulated until the vertex is first visited. The second parameter is a norm parameter $p\geq 1$. The objective is to find a root-starting path that visits all vertices and minimizes the $p$-norm of the resulting vector of $α$-latencies. The model interpolates between several well-studied objectives. For $p=1$ and $α=1$, it recovers pathwise search; for $p=1$ and $α=0$, it recovers expanding search. As $p$ tends to infinity, the objective converges to a makespan-type criterion. At the endpoints $α=1$ and $α=0$, this limiting objective corresponds to TSP-type and MST-type behavior, respectively. For $p=1$, we give polynomial-time constant-factor approximation algorithms for all $α\in[0,1]$, matching the best known guarantees for expanding search at $α=0$ and pathwise search at $α=1$. For general $p\geq 1$, we obtain a randomized constant-factor approximation algorithm and a derandomized pseudo-polynomial-time algorithm with the same guarantee.

Authors: Antoine Deza, Yan Gerard, Yijun Ma, Sebastian Pokutta

We consider the following additive Latin transversal problem. Given a multiset $A=(a_1,\dots,a_k)$ of elements of $\mathbb Z_m$ and a set $B\subseteq\mathbb Z_m$ of cardinality $k$, the task is to order $B$ as $b_1,\dots,b_k$ so that the sums $a_i+b_i$ are pairwise distinct. When $k=m$, Hall proved that a solution exists if and only if $\sum_{i=1}^m a_i\equiv 0 \pmod m$; moreover, his theorem yields a polynomial-time construction. Alon proved that a solution always exists when $m$ is prime and $k

Authors: Tuukka Korhonen, Daniel Lokshtanov, Saket Saurabh

Recently, Bumpus, Downey, Eagling-Vose, Enright, Fellows, Kutner, Larios-Jones, Martin, Rosamond, and Yates defined Truly Linear FPT (TLFPT) to be the class of parameterized problems with algorithms running in time $O(n) + f(k)$, where $n$ is the input size and $k$ the parameter [arXiv:2606.02492]. They gave several algorithmic techniques for designing TLFPT algorithms, but left parameterization by treewidth open. In this paper, we give a general method for designing TLFPT algorithms parameterized by treewidth, solving three open problems posed by Bumpus et al. In particular, we give a TLFPT algorithm for Courcelle's theorem: We show that given an $n$-vertex $m$-edge graph $G$, an integer $k$, and a $\mathsf{CMSO}_2$-formula $\varphi$, we can in time $O(n+m) + f(k, \varphi)$ either conclude that the treewidth of $G$ is more than $k$, or check whether $G$ satisfies $\varphi$. As a part of our algorithm, we give an approximation algorithm for treewidth that runs in time $O(n+m)$ and returns a tree decomposition whose width is at most $2^{O(k)}$ times the optimum. Our result also implies a TLFPT algorithm for computing the value of treewidth exactly.

Authors: Yuki Kawashima, Naoki Kitamura, Taisuke Izumi

The local failover routing is a mechanism that routes a packet from a source to a destination only using pre-calculated routing tables, even when several edges fail. In this paper, we study local failover schemes that minimize the number of rewritable bits in the packet header on directed graphs with $k$-arc failures. There are many studies of failover routing on undirected graphs, and it has been investigated whether routing is possible depending on the number of bits in the packet header, the type of failure, the graph properties, etc. In contrast, there is not much research on directed graphs. Van et al.~first showed the upper and lower bounds of rewritable bits in the packet header on directed graphs. However, their results showed a large gap between the upper and lower bounds. The main contribution of this paper is to close the gap between the upper and lower bounds. Specifically, we show that our scheme can route packets with $k$ faulty arcs if the packet header has $\min(k \log ( \frac{e(2n+k-3)}{k}, 2n \log ( \frac{e(2n+k-3)}{2n})))$ rewritable bits, where $n$ is the number of nodes. Moreover, any local failover routing scheme needs $Ω(k\lceil\log\frac{n}{k}\rceil)$ rewritable bits when the number of faulty arcs is equal to or less than $\frac{3(n-1)}{8}$ and $\frac{n-1}{4}$ rewritable bits when the number of faulty arc is more than $\frac{3(n-1)}{8}$. This result means our scheme is nearly optimal when the number of faulty arcs is approximately less than the number of nodes.

Authors: Júlia Baligács, Jan Hązła, Lena Volk

In online graph exploration, introduced by Kalyanasundaram and Pruhs (1994), an agent must visit all vertices of an initially unknown weighted graph and return to its starting position, while the graph is revealed only locally at visited vertices. Although the problem has attracted considerable attention, previous work has focused exclusively on deterministic algorithms. Randomized strategies are often substantially harder to analyze because of a fundamental challenge inherent to exploration. In this work, we give the first positive result showing that randomization can improve competitive guarantees in online graph exploration. To this end, we focus on cycles, a simple graph class which nevertheless captures a key difficulty of online exploration. Our main contribution is \(\textsc{RandHeavyTest}\), a randomized algorithm for online exploration of cycles whose competitive ratio we prove to be at most 1.315. This establishes a strict separation from the deterministic setting, where the optimal competitive ratio is $\thickapprox 1.366$, and thus gives the first provable advantage of randomization in online graph exploration. A key step towards this result is a new, simplified optimal deterministic algorithm, \(\textsc{HeavyTest}\), whose formulation naturally suggests the randomized variant. We complement our upper bounds with lower bounds of 1.115 for arbitrary randomized algorithms and 1.207 for the natural class of so-called forward-greedy algorithms, which includes \(\textsc{RandHeavyTest}\).

Authors: Suprovat Ghoshal, Neng Huang, Euiwoong Lee, Konstantin Makarychev, Yury Makarychev

We describe an $\widetildeΩ(1/d^4)$-improvement over threshold rounding schemes for a broad class of Boolean MAX 2-CSP instances in which every variable appears in at most $d$ constraints. In the case of MAX 2-SAT, we improve the ratio further and obtain an $(β_\star + \widetildeΩ(1/d^2))$-factor approximation algorithm for bounded-degree MAX 2-SAT instances, where $β_\star$ is the UGC-optimal approximation ratio for MAX 2-SAT achieved by the LLZ algorithm. Our result generalizes an $(α_{GW} + \widetildeΩ(1/d^2))$-factor approximation algorithm for MAX CUT on graphs with degrees bounded by $d$, due to Hsieh and Kothari. Together with the state-of-the-art approximability results for MAX DI-CUT and MAX 2-AND, our result suggests that similar improvements exist for bounded-degree instances of these problems as well.

Authors: Shubhadip Mitra, Sona Elza Simon, C Oswald, Arnab Bhattacharya, Arindam Pal

Given a large graph, how to generate a compact summary graph that is configurable by the user and supports multiple graph queries with either no loss or with high accuracy? The ever growing size of graph datasets makes the above question on graph summarization very pertinent. Although, there are several approaches, there does not exist a configurable graph summarization method that offers high compression along with support for multiple graph queries on the summary graph with high accuracy, and allows the user to configure the summarization based on: (1) lossless or lossy summarization, (2) amount of tolerable neighborhood loss, (3) the type of loss it can tolerate, in terms of false positive edges (i.e., extra edges), false negative edges (i.e., missing edges), or neither, in both the (a) reconstructed graph and the (b) query answers. To overcome these limitations, we propose a novel graph summarization framework CGS (Configurable Graph Summarizer) that builds upon the idea of aggregating nodes with common neighborhoods. The CGS framework consists of three summarization variants, CGS-E, CGS-I and CGS-U. While CGS-E is a lossless scheme, CGS-I and CGS-U are lossy schemes that allow reconstruction of the input graph with no false positive edges and no false negative edges, respectively. To bound the graph reconstruction loss, we introduce a user-specified parameter neighborhood loss tolerance threshold, that limits the maximum loss allowed in the neighborhood of each node. This allows graph reconstruction and neighborhood query evaluation with either no loss or with bounded loss guarantees. Empirical evaluation on several synthetic and real-world graphs shows that CGS offers superior summarization than the state-of-the-art methods, and can answer graph queries with fairly high accuracy and efficiency.

Authors: Jan Dreier, Nikolas Mählmann, Rose McCarty, Michał Pilipczuk, Szymon Toruńczyk

Monadic dependence is a proposed structural dividing line for fixed-parameter tractability of first-order model checking on hereditary graph classes. A graph class is \emph{monadically dependent} if the class of all graphs cannot be interpreted in its vertex-colored members using a fixed first-order formula. We prove two structural consequences of monadic dependence. First, every monadically dependent class has \emph{almost linear neighborhood complexity}: for every graph $G$ in the class and every set $A\subseteq V(G)$, the family $\{N_G(v)\cap A : v\in V(G)\}$ has size $|A|^{1+o(1)}$. Second, every $n$-vertex graph in a monadically dependent class has radius-1 merge-width $n^{o(1)}$. Here, merge-width is the decomposition parameter of Dreier and Toruńczyk based on construction sequences; its radius-$r$ version measures local reachability among parts through already resolved pairs. This settles the radius-1 case of the conjectured connection between monadic dependence and almost bounded merge-width and provides the first decomposition-based structural description of monadically dependent graph classes. Our proof is algorithmic: we give an $\mathcal{O}(n^5)$-time algorithm that, given an $n$-vertex graph $G$ such that $|\{N_G(v)\cap A : v\in V(G)\}|\le O(|A|^d)$ for every $A\subseteq V(G)$, computes a construction sequence witnessing radius-1 merge-width $\mathcal{O}(n^{1-1/d}\log n)$.

Authors: Dinesh Kumar Baghel

We consider a variant of the bin packing problem with constraints on the number of copies of each item and their placement in the packing. The input $D_q := DD\ldots$ is defined as $q$ consecutive copies of the multiset $D$, with a fixed bin capacity $S$. Note that, for each item in $D$, there are $q$ copies in $D_q$. The goal is to pack all the items in $D_q$ into the minimum number of bins, such that each bin contains at most one copy of each item and the total size of all items in a bin does not exceed the bin capacity $S$. We call this problem $q$BP. First Fit Decreasing ($\mathsf{FFD}$) is a classical bin packing algorithm: it first orders the items in nonincreasing order, then packs the next item into the first bin where it fits. In the literature, $\mathsf{FFD}$ proofs rely on the assumption that the last bin in the $\mathsf{FFD}$ packing contains only a single item. This assumption does not naturally extend to the $q$BP problem. In this paper, we circumvent this difficulty by analyzing $\mathsf{FFDq(D_q)}$ on a carefully chosen subinstance ${D'}_q \subseteq D_q$ ($q$ consecutive copies of $D$, each copy sorted in non-increasing order) while preserving the same upper bound for the original input $D_q$. We show that the approximation ratio of $\mathsf{FFDq(D_q)}$ for some special cases is \begin{align*} \mathsf{FFDq(D_q)} \leq \frac{11}{9}\mathsf{OPT(D_q)} + 3q \end{align*} where $\mathsf{FFDq}$ and $\mathsf{OPT}$ denote the number of bins used by the $\mathsf{FFD}$ generalization and by an optimal algorithm, respectively.

Authors: Tao Jiang, Shaowei Cai

We revisit Scheder's analysis of the original PPSZ algorithm. Keeping his regular and irregular estimates unchanged, we express them in common structural coordinates and replace only their final recombination by an explicit linear-programming dual certificate. The old and new running-time bounds are \[ \begin{array}{c|cc} & \text{Unique-$3$-SAT} & \text{general $3$-SAT} \\ \hline \text{Scheder's analysis} & O^*(1.306972377^n) & O^*(1.307031594^n) \\ \text{this work} & O^*(1.306969598^n) & O^*(1.307031578^n). \end{array} \] In both rows, the general-case bound is obtained by applying the same existing Scheder--Steinberger unique-to-general lifting theorem to the corresponding Unique-$3$-SAT analysis. To the best of our knowledge, $O^*(1.307031578^n)$ is the best currently known worst-case randomized running-time bound for general $3$-SAT. Neither PPSZ nor the lifting theorem is modified. The numerical inequalities are certified by exact rational interval computation.

Authors: Yotam Kenneth-Mordoch, Robert Krauthgamer

In the (fully) dynamic edge connectivity problem, the goal is to maintain the edge connectivity $λ_G$ of an $n$-vertex graph $G$ that undergoes edge insertions and deletions. Our main result is a randomized algorithm for maintaining edge connectivity in dynamic simple graphs using worst-case update and query time $\tilde{O}(n^{12/13})$, for all values of $λ_G$. This is the first algorithm that has $o(n)$ update and query time, as all existing algorithms achieve this only when $λ_G$ is below $n^{1/11}$ or above $n^{1/2}$ (up to polylogarithmic factors). We then use the tools developed for this purpose to design two additional algorithms. The first one is a deterministic algorithm for the exact same task, that uses $n^{1+o(1)}$ worst-case update and query time or $\tilde{O}(n)$ amortized update and query time; this gives a polynomial improvement over existing deterministic algorithms. The second one is a deterministic algorithm for the same task but in dynamic unweighted multigraphs, that uses $\tilde{O}(n^{3/2})$ worst-case update and query time.

Authors: Ziad Ismaili Alaoui

The Token Jumping and Sliding Token problems are fundamental reconfiguration problems defined on the independent sets of an undirected graph. Given two independent sets $I$ and $J$, each of size $k$, these problems ask whether there exists a sequence of elementary operations transforming $I$ into $J$ such that every intermediate configuration is also an independent set of size $k$. In Sliding Token, an operation moves a token from a vertex $u \in I$ to an adjacent vertex $v \notin I$; in Token Jumping, the token may instead move to any vertex $v \notin I$. While both problems are PSPACE-complete on general graphs, polynomial-time algorithms have been developed for several graph classes, including trees, block graphs, cacti, bipartite permutation graphs, cographs, $P_4$-tidy graphs, and interval graphs. In this paper, we prove that both problems are solvable in polynomial time on threshold signed graphs, also known as Dilworth-2 graphs. A graph $G=(V,E)$ is a threshold signed graph if there exist a mapping $a:V\to\mathbb{R}$ and positive real constants $S$ and $T$ such that, for any distinct vertices $u,v\in V$, $\{u,v\}\in E$ if and only if $|a(u)+a(v)|\ge S$ or $|a(u)-a(v)|\ge T$. This graph class is a subclass of permutation graphs, for which the complexity of these problems remains open, and is incomparable with the class of bipartite permutation graphs studied by Fox-Epstein et al. (ISAAC, 2015). The algorithm is based on the inclusion-chain structure that characterises threshold signed graphs, a structural property that may be of independent interest.

Authors: Noam Licht, Ilan Newman, Yuri Rabinovich

We study online embeddings of metric spaces into Euclidean spaces of a constant dimension $d>1$, against an adaptive adversary. While the case of $d=1$ is well understood, for higher dimensions little is known. In particular, even for $d=2$ it remains unknown whether the worst-case distortion grows exponentially with the number of exposed points, as it does in the case for the line, or whether it is polynomial, as in the case for unbounded $d$. Our first result is about fixed {\em solid} graphs, i.e., $K_5$, whose edges are solid intervals, equipped with the shortest-path metric. We show that if the input points arrive from such a metric space, they can indeed be online-embedded into ${\mathbb R}^2$ with a polynomial distortion. This refutes the previously believed conjecture that the topological non-embeddability of $K_5$ into the plane could be exploited for establishing exponential lower bounds. The second results is about online embeddings of tree metrics of a certain type, including, e.g., ultrametrics and HST's. Somewhat surprisingly, we show that for metrics from this class the worst-case online embedding into ${\mathbb R}^d$ is not much worse that the offline embedding, both being $n^{Θ(1/d)}$, and this holds even when $d = Θ(\log n)$. This is in a stark contrast to the more common situation where the online-offline gap is typically huge, and even exponential. This result allows us to transfer results about probabilistic embeddings of metrics into HST's to low-dimensional Euclidean spaces, in an almost optimal possible manner.

Authors: Yichen Huang, Shaofeng H. -C. Jiang

We study online metric facility location with uniform opening costs in the random-order model (Meyerson FOCS'01). The best previous upper bound was a $3$-competitive randomized algorithm (Kaplan, Naori, Raz SODA'23), leaving a gap to the best known lower bound of $2$. In this work, we give two algorithms with improved competitive ratios: (i) a deterministic algorithm with a competitive ratio below $2.42$ and (ii) a randomized algorithm with a competitive ratio below $2.59$ and the additional property that it retains the asymptotically optimal $O(\log n/\log \log n)$ competitive ratio in the adversarial-order model. A key improvement is to take the arrival time of the request into consideration when making opening decisions: The arrival time carries geometric information about the local density around the request, which fundamentally helps the algorithm.

Authors: Ruizhe Zhang

We prove an optimal extrapolation theorem for $k$-sparse Fourier sums over arbitrary real frequencies, without any separation assumption, bounding how large such a sum can be just outside an interval on which its energy is observed. For every $g(t)=\sum_{j=1}^k v_j e^{iλ_jt}$ with $λ_j\in\mathbb R$ and every $x\ge1$, $$ |g(x)|\le k^{O(1)}\exp(O(k\mathop{\mathrm{arcosh}} x))\|g\|_{L^2[-1,1]} . $$ In the endpoint regime, this refines to the explicit bound $$ |g(1+δ)|\le O(k)\exp(O(k\sqrtδ))\|g\|_{L^2[-1,1]}, \qquad 0\leδ\le1 . $$ This improves on the $\exp(O(k^2\log k\cdotδ))$ growth estimate of Chen and Price (ICALP 2019), and the exponential scaling is optimal up to constants and polynomial factors in $k$. As an algorithmic consequence, we improve the cluster-center resolution of Chen--Price's clustered-frequency recovery algorithm by a factor of $k$, while preserving its sample complexity up to logarithmic factors. We also obtain exterior leverage-score and transfer bounds for sparse Fourier feature spaces, converting in-domain active-regression guarantees into essentially sharp prediction guarantees just outside the sampling interval.

Authors: Lin Chen, Tingwei Hu, Yuchen Mao, Guochuan Zhang

We study the additive structure of dense subset sum in multi-dimension, and use the structure to develop efficient algorithms for the dense subset sum problem. More precisely, given a set $A$ of $n$ vectors in the $d$-dimensional hyperrectangle $[N_1]\times [N_2]\times\cdots\times [N_d]$, we study the structure of $\mathcal{S}(A)$, which is the set of all subset sums of $A$. We focus on the dense regime of the problem where $n \gg \sqrtΦ$ and $Φ= N_1 \times \cdots \times N_d$. We show that for any constant $d\geq 1$, if $n \gg \sqrtΦ$, then $\mathcal{S}(A)$ contains a long generalized progression in multi-dimension. If we further have that no non-trivial lattice can contain the majority of $A$, then $\mathcal{S}(A)$ contains all the integer points in the zonotope $\{x_1\vec{a}_1 + \cdots + x_n\vec{a}_n: o(1)\leq x_j \leq 1-o(1), x_j \in \mathbb{R}\}$. Compared to the previous results for $d \geq 2$, our result significantly reduces the density threshold and enlarges the region inside which all the integer points belong to $\mathcal{S}(A)$. Also, it matches the bound for the 1-dimensional case. Using our combinatorics result, we also develop an $\tilde{O}(n)$-time algorithm for the dense subset sum problem in multi-dimension.

Authors: Haoran Wang

Min-wise hashing and its (k)-min-wise variant are standard tools in similarity estimation, sampling, sketching, and streaming. A (k)-min-wise family requires every prescribed (r)-subset of a fixed set, for (r\le k), to appear as the (r) smallest hash values with approximately the fully random probability, up to multiplicative error (δ). Previous analyses show that (O(\log(1/δ)+k\log\log(1/δ)))-wise independence suffices. Consequently, for (k=Θ(\log N)) and (δ=N^{-c}), the standard polynomial construction uses (O(k\log N\log\log N)) seed bits. Recent work of Chen, Huang, and Li achieves the optimal (O(k\log N)) seed length for (k=\log^{O(1)}N), but only with almost-polynomial error (2^{-O(\log N/\log\log N)}), leaving open whether polynomially small error is possible with the same seed length. We prove that the standard (s)-wise independent polynomial hash family is (k)-min-wise with multiplicative error (δ) for [ s=O(k+\log(1/δ)). ] Thus, when (k=Ω(\log(1/δ))), only (O(k))-wise independence is required. In particular, for (k=Θ(\log N)) and (δ=N^{-c}), this gives an explicit family with seed length (O(k\log N)), matching the support-size lower bound up to constant factors. The proof conditions on the prescribed bottom set and bounds the error only after averaging over the random threshold given by its largest hash value, rather than controlling every threshold separately.

Authors: Chunyang Wang, Yuichi Yoshida, Zihan Zhang

We study the mixing time of Wang-Swendsen-Kotecký (WSK) dynamics for uniformly sampling proper $q$-colorings. The WSK dynamics is widely used in statistical physics for sampling from the antiferromagnetic Potts model and can be considered a global counterpart of the flip dynamics, which currently yields the state-of-the-art bounds for sampling colorings in general graphs (Carlson and Vigoda, SODA 2025). However, despite its importance, the tools for analyzing such dynamics remain limited. We develop new tools that enable us to analyze the mixing time of the WSK dynamics through the lens of relative entropy contraction. We introduce new criteria for multi-spin distributions: approximate colorwise tensorization of entropy (ACTE) and approximate colorwise subadditivity of entropy (ACSE). These criteria provide a colorwise counterpart to standard vertex-wise entropy factorization principles, and expose a form of color symmetry beyond coordinate-wise analyses. We also develop new inductive approaches for establishing such criteria on specific types of graphs, which can be viewed as local-to-global arguments for proving high-dimensional functional inequalities in a graph-theoretic sense. As concrete applications, we establish an optimal $O_q(\log n)$ mixing time for the WSK dynamics on chordal and outerplanar graphs, down to the optimal number of colors. Because trees and line graphs of trees are chordal, the result covers both vertex and edge colorings of trees. Our results work in a regime that bypasses the irreducibility threshold for Glauber dynamics while also improving the best known mixing time bounds (Carlson, Chen, Feng and Vigoda, SODA 2025).

Authors: Aaron Bernstein, Anupam Gupta, Zhaozi Wang

We study the well-known load balancing problem in the distributed CONGEST model of computation. We consider the unrelated machines setting, where each job $j$ specifies a size $s_{ij}$ for every machine $i$. We want to find an assignment $\varphi: J \to M$ minimizing the maximum machine load, where the load of a machine $i$ is the total size of the jobs assigned to it. In the CONGEST model, the state-of-the-art is an algorithm that runs in polylog rounds and returns a $(1+\varepsilon)$-approximate fractional solution from Ahmadian, Liu, Peng, and Zadimoghaddam (2021). However, this algorithm, as well as all previous CONGEST algorithms only solve a special case of load balancing, where each job has the same size on each machine. Our main contribution is an algorithm for general sizes $s_{ij}$. The algorithm computes a $(1+\varepsilon)$-approximate fractional solution or a $(2+\varepsilon)$-approximate integral solution in polylog rounds. The problem structure changes significantly once we allow arbitrary edge-sizes, so our techniques are very different from those used in previous algorithms for distributed load balancing. One ingredient of our result is a black-box tool of independent interest: a $(1+\varepsilon)$-approximation algorithm to arbitrary mixed packing-covering linear programs in the CONGEST model in polylog rounds. such algorithms were known in the more powerful parallel model, but previous polylog-round algorithms in the distributed CONGEST model only solved pure packing or pure covering problems. We improve upon a recent $O(D\,\mathrm{polylog})$-round CONGEST algorithm for mixed packing-covering, where $D$ is the diameter of the communication graph.