Theory of Computing Report

Saturday afternoon, July 25, was quite magical for me: all three beautiful talks were closely related to my interests and to my own work. Here is a brief personal description of the lectures, with links to the slides and papers, followed by a more detailed account of each talk.

Jinyoung Park gave a beautiful talk entitled “Thresholds,” concerning an array of conjectures about the location of thresholds for monotone properties and some of their applications. She concentrated on three conjectures: the Kahn–Kalai conjecture, also known as the expectation-threshold conjecture; the second Kahn–Kalai conjecture; and Talagrand’s discrete convexity conjecture. Here are the links to the proceedings paper and the slides.

Tom Braden and Nicholas Proudfoot gave a beautiful talk entitled “Intersection Cohomology Without Spaces,” devoted to a major theme in algebraic combinatorics: geometric structures can survive, and remain powerful, even in settings where the geometry itself does not exist. They discussed three examples: Kazhdan–Lusztig polynomials for Coxeter groups, toric -polynomials for polytopes, and Kazhdan–Lusztig–Stanley polynomials for matroids. Here are the links to the proceedings paper and to the slides.

Raghu Meka gave a beautiful talk entitled “Structure vs Randomness Redux.” The talk focused mainly on the new bounds of Meka and Zander Kelley for the density of sets of integers containing no three-term arithmetic progression. In my view, this is among the most important mathematical results of the past few years. The method relies on a new version of the “structure versus randomness” paradigm, and it has led to important progress in both additive combinatorics and theoretical computer science. Here are the links to the proceedings paper and the slides.

Breaking news

On another matter: OpenAI reported today on the solution of ten major mathematical problems.

Some personal comments

1. I wrote about the Kahn–Kalai conjecture in several earlier posts. (In my lectures and posts, I was often imprecise about the distinction between the first and second conjectures.) Although both Jeff and I were skeptical about the conjecture, in our paper we proposed a program for proving it based on strong inverse forms of discrete isoperimetric inequalities. The central inverse conjecture, Conjecture 6(a) in our paper, is still open, although some stronger versions (6(b) and 6(c)) turned out to be false. Another part of the program, Conjecture 7, was also refuted. This was the subject of our first AI+Polymath project, in which the counterexample was found with the help of AI; see this post.
2. Of the three topics discussed by Tom and Nicholas, the one I have studied most closely is the second: toric -vectors of polytopes. Beyond the major achievement of extending the theory from rational polytopes to arbitrary polytopes, an important remaining challenge is to extend it further to strongly regular CW-spheres—that is, regular CW-spheres in which the intersection of any two cells is itself a cell. Karim Adiprasito’s solution of the -conjecture for triangulated spheres—see this post and this one—may offer hope in this direction. Another important problem is to understand the combinatorial consequences of the results arising from algebraic geometry, whether “with spaces” or “without spaces.” See also this post.
3. I have followed progress on Roth’s theorem and Szemerédi’s theorem for many years, including here on the blog. (I reported on the Kelley-Meka breakthrough in this 2023 post, and see, for example, also  this 2020 post; this 2010 post; this 2009 post; , and this 2016 post.) From time to time, I even tried to work on these problems myself.
4. I have many fond memories connected with the mathematics of these three lectures, with the speakers, and with many of the other mathematicians involved.

Let me move now to a more detailed description of the three talks.

With Jinyoung Park and Hari Bercovici

Jinyoung Park: Thresholds

Jinyoung Park’s lecture, simply titled “Thresholds,” was organized around the question: What drives thresholds? Let be a finite set and let be the random subset obtained by choosing every element independently with probability . For an increasing family , its threshold is defined by . A basic lower bound comes from the first-moment method. We call -small if it can be covered by simple witnesses whose total expected contribution satisfies , and we let be the largest such . Park discussed three fundamental questions concerning the relation between this simple expectation bound and the actual threshold.

The first question was the Kahn–Kalai conjecture, which asserted that the first-moment bound always determines the threshold up to a logarithmic factor. In its strengthened form, proved by Park and Huy Tuan Pham,

where is the size of the largest minimal member of . Earlier, Keith Frankston, Jeff Kahn, Bhargav Narayanan, and Park had proved Talagrand’s fractional version, replacing ordinary covers by fractional covers. The dual language of spread measures turned out to be particularly powerful: once one constructs a probability distribution on the desired combinatorial structures for which no fixed set of elements occurs too often, the threshold theorem can be applied. This circle of ideas gives remarkably short routes to the correct threshold orders for perfect hypergraph matchings, Hamiltonian cycles, bounded-degree spanning trees, and several other difficult problems. The logarithmic factor cannot in general be removed, as illustrated by coupon-collector phenomena.

The second Kahn–Kalai conjecture is more concrete and remains open. Given a graph , let be the smallest for which the expected number of copies in of every subgraph is at least . Clearly , and the conjecture asserts that

where is the number of vertices of . This is stronger than the general theorem because it asks us to use only the obvious subgraph witnesses, rather than arbitrary and possibly nonsymmetric covers. Recent work of Quentin Dubroff, Jeff Kahn, and Park proves the bound with an additional factor , and proves the conjectured bound itself in the sparse regime . Thus the remaining question is whether the complicated abstract witnesses defining can always be replaced, at constant cost, by the natural subgraphs of .

Park’s third theme was Talagrand’s discrete convexity conjecture. For a decreasing family , let

and let .

The conjecture says that there are universal constants and such that, whenever has sufficiently large -measure, the exceptional family is -small. In words, boundedly many unions of members of a large decreasing family should cover almost the entire discrete cube, apart from an exceptional set whose smallness has an explicit first-moment explanation. The Park–Pham theorem gives a related statement with but with a necessary logarithmic loss in ; Talagrand’s conjecture predicts that allowing a bounded number of unions eliminates this loss. Talagrand described this as his “lifetime favorite problem,” and it remains open.

Tom Braden, Nicholas Proudfoot, with Pierre Deligne and George Lusztig

Tom Braden and Nicholas Proudfoot: Intersection Cohomology Without Spaces.

The second lecture, by Tom Braden and Nicholas Proudfoot, was entitled “Intersection Cohomology Without Spaces.” Ordinary cohomology behaves beautifully for smooth projective varieties, satisfying Poincaré duality, the hard Lefschetz theorem, and the Hodge–Riemann relations. For singular varieties, ordinary cohomology may lose these properties, but intersection cohomology restores them. Besides the global groups one has local intersection cohomology groups  , which measure the singularity of near . Their graded dimensions often assemble into polynomials of central importance in combinatorics and representation theory.

Braden and Proudfoot presented three parallel examples. For Coxeter groups one obtains the Kazhdan–Lusztig polynomials; for convex polytopes one obtains Stanley’s -polynomials; and for matroids one obtains the Kazhdan–Lusztig polynomials of matroids. All three belong to Stanley’s general theory of Kazhdan–Lusztig–Stanley, or KLS, polynomials associated with a ranked poset and a suitable collection of polynomials called a -kernel. The KLS-polynomials are defined recursively, together with the crucial degree condition

From their recursive definitions it is far from evident that their coefficients should be nonnegative. Geometry explains this by identifying them with Poincaré polynomials

of appropriate local intersection cohomology groups.

The relevant geometric spaces exist only in special cases. For Weyl groups they are Schubert varieties in flag varieties; for rational polytopes they are toric varieties; and for realizable matroids they are arrangement Schubert varieties. But the combinatorial polynomials make sense for arbitrary Coxeter groups, nonrational polytopes, and nonrealizable matroids, where no corresponding algebraic variety exists. The remarkable development described in the lecture is that one can nevertheless construct the intersection cohomology groups themselves: by Soergel bimodules or moment-graph sheaves for Coxeter groups, by intersection cohomology sheaves on fans for polytopes, and by intersection cohomology modules for matroids. Thus the title “intersection cohomology without spaces” is quite literal: the algebraic and combinatorial shadows of the geometric theory continue to exist even after the underlying geometric space has disappeared.

The common framework uses sheaves of graded modules on finite posets. The strata of a variety are replaced by the elements of the poset, and the intersection cohomology sheaf is constructed inductively: after the data have been defined above an element , the stalk at is obtained as a minimal free module mapping onto the already known boundary data. This elementary-looking construction is only the beginning. The deep part is proving that the resulting graded vector spaces have the required dimensions, and this demands combinatorial analogues of hard Lefschetz and the Hodge–Riemann relations. These theories give much more than coefficientwise nonnegativity. For example, intersection cohomology of matroids was a central ingredient in the proof of the Dowling–Wilson top-heavy conjecture: if is the lattice of flats of a rank- matroid, then

The lecture offered a striking illustration of a major theme in modern combinatorics: geometric structures can survive, and remain powerful, even in settings where the geometry itself does not exist.

Remark (for the experts): The IH of a matroid that Tom and Nicholas outlined in the final slides (especially 23 and 24) is not the one that appears in the paper “Singular Hodge theory for combinatorial geometries”. They are currently finishing the papers with the new construction, to be posted soon.

Raghu Meka Raghu Meka: Structure vs Randomness Redux.

Raghu Meka’s lecture was entitled “Structure vs Randomness Redux.” The classical structure-versus-randomness paradigm says that a complicated mathematical object can either be decomposed into structured pieces or shown to behave like a random object. Meka described a new and remarkably successful version of this paradigm, developed in works with Amir Abboud, Nick Fischer, Zander Kelley, and Shachar Lovett. Its central principle is

Roughly speaking, an object is spread if its density does not increase substantially when we restrict it to any large natural substructure—an affine subspace or a Bohr set for additive problems, and a rectangle for matrices. A spread object need not itself look random. The surprising assertion is that after combining two spread objects, by convolution or matrix multiplication, the result becomes close to uniform.

The first application was the classical problem of three-term arithmetic progressions. How large can a set be if it contains no distinct satisfying

Behrend’s celebrated construction gives progression-free sets of density . After a long sequence of results beginning with Roth’s theorem, the best upper bounds remained only polylogarithmic in . Kelley and Meka made a striking jump to the stretched-exponential bound

for some absolute constant . The proof first passes to finite vector spaces. There, either has increased density on a low-codimensional affine subspace, or is spread. In the latter case its normalized convolution satisfies, schematically,

and this mixing forces many solutions to . Thus one obtains a particularly clean density-increment argument: either we already have many progressions, or we move to a smaller ambient space where the set is denser.

A key ingredient in this theory is a new decoupling inequality. The quantities one wants to estimate often involve products such as

in which the factors are dependent because they share variables. Decoupling replaces such an expression by related expressions involving more independent copies of the variables, where analytic estimates are much easier to apply. Two further ideas are essential. Spectral positivity converts unexpectedly small values into comparable upward deviations, which can drive a density increment; and sifting uses dependent sampling to locate the substructure on which this increased density occurs. These tools make the slogan “spreadness implies mixing” applicable far beyond ordinary additive convolution.

The final application concerned finding triangles and Boolean matrix multiplication. For a tripartite graph with adjacency functions , , and , the normalized number of triangles is

Abboud, Fischer, Kelley, Lovett, and Meka proved a new spread regularity lemma: every graph can be decomposed algorithmically into a controlled number of pieces, each of which is either sparse or spread. Sparse pieces can be handled directly, while on spread pieces the product of the relevant adjacency matrices mixes, making triangle detection easy. This leads to a combinatorial algorithm for Boolean matrix multiplication, and hence for triangle detection, with running time

a super-polylogarithmic improvement over the earlier combinatorial algorithms. The broader message of Meka’s lecture was that this new version of structure versus randomness provides a common explanation for breakthroughs in additive combinatorics, communication complexity, and fast algorithms.

 

By Gil Kalai

We study pseudorandom bit generators for Boolean linear sums modulo a fixed integer $M$. A distribution $X\in\{0,1\}^n$ $\varepsilon$-fools these tests if, for every $a\in\mathbb{Z}_M^n$, the distribution of \[ \sum_{i=1}^n a_iX_i \pmod M \] is $\varepsilon$-close in statistical distance to the corresponding distribution under independent uniform bits. Lovett, Reingold, Trevisan, and Vadhan constructed generators with optimal seed length for every fixed prime-power modulus. We extend this result to every fixed modulus of the form \[ M=2^{t}\cdot p^{k}, \] where $t,k\ge 0$ and $p$ an odd prime. Specifically, we give an explicit generator with seed length \[ O_M\!\left(\log n+\log\frac{1}{\varepsilon}\right), \] which is optimal up to the constant depending on $M$. Our main contribution is a modulus-doubling reduction that transforms any generator fooling Boolean linear sums modulo $m$ into one fooling such sums modulo $2m$, while preserving the optimal asymptotic seed length.

• ACM considers allowing LLMs to read its digital library (\(\mathbb{M}\)) and requests feedback on this choice.

• Daedalus’ labyrinth (\(\mathbb{M}\)), a puzzle game dual to loopy/slitherlink.

• Voronoi go (\(\mathbb{M}\)), a variant of go where you can play anywhere on the board (not just intersections).

• Human mathematicians are being outcounterexampled (\(\mathbb{M}\)). Kevin Buzzard of the Xena Lean formalization project on recent counterexamples to the unit distance problem and Jacobian conjecture.

• 3-boundary surfaces for 3-component links (\(\mathbb{M}\)) with crochet, 3d-printed, and vector graphics illustrations.

• Innovations in Graph Theory added to DOAJ (\(\mathbb{M}\)).

• zbMATH digitizes 50 years of its old reviews (\(\mathbb{M}\)).

• Three new Wikipedia articles about mathematics books (\(\mathbb{M}\)), posted by Samuel Adrian Antz: Characteristic Classes (1974) by John Milnor and Jim Stasheff, Instantons and Four-Manifolds (1984) by Dan Freed and Karen Uhlenbeck, and The Geometry of Four-Manifolds (1990) by Simon Donaldson and Peter Kronheimer.

• AI in scientific publishing: Slower, worse, and more expensive (\(\mathbb{M}\), via). H. Holden Thorp notes that the rapid increase in AI-generated research is increasing rather than decreasing the need for human effort, in checking the research, and likens the resulting effects on human workers to those in the industrial revolution’s shift from craftspeople to factory workers.

• The existence of designs (\(\mathbb{M}\)), posted to arXiv in 2014 by Peeter Keevash, has finally been accepted for publication in the Annals of Mathematics, 12.5 years later.

• Three recent algorithms preprints on arXiv make some strong and interesting claims (\(\mathbb{M}\)):

  • “Bellman–Ford in almost-linear time”, by Hair, Li, Li, and Zhang, arXiv:2607.19346, computes single-source shortest paths in a directed graph with real weights, allowed to be negative but with no negative cycles, in time \(O(m^{1+o(1)})\), building on recent subquadratic breakthroughs by overlapping authors.

  • “Splay trees are almost dynamically optimal”, by Chmel, Haeupler, Hladík, Koucký, Roeyskoe, Rozhoň, Sladký, and Tarjan, arXiv:2607.18498, proves a competitive ratio of \(O(\log\log n(\log\log\log n)^3)\), the first nontrivial competitiveness for splay trees. Tango trees have a slightly better proven bound but unlike splay trees cannot be \(O(1)\)-competitive.

  • “Shortest paths with linear edge weights”, by Chillara, Gajjar, and Raja, arXiv:2607.21055, considers shortest -paths in a directed graph whose weights vary linearly as a function of one or more parameters. Different parameter settings give different paths, but how many? The answer was known to be \(n^{\Theta(\log n)}\) for a single parameter, with weaker bounds for more. The new preprint proves a bound of the same form for any fixed number of parameters.

  You might have thought that such old and well-established topics in algorithms research as shortest paths and balanced binary search trees would be very stable, but instead things are still changing rapidly.

• Wikimedia refuses to recognize a union for its employees (\(\mathbb{M}\)) after a supermajority of workers signed union cards requesting it.

• A long thread about variants of Kőnig’s infinity lemma in relation to computability theory.

• On using computational hardness to resolve a mathematical conjecture (\(\mathbb{M}\)). Noam Zeilberger points to “A system of interaction and structure III: The complexity of BV and pomset logic” (Lê Thành Dũng Nguyên and Lutz Straßburger, doi:10.46298/lmcs-19(4:25)2023) where an incompatibility of complexity classes for provability in two conjecturally-equal logics led to a counterexample to their equality.

• I don’t know why it took me so long to realize it (\(\mathbb{M}\)), but my phone’s HP 16C programmer’s calculator app turns out to be surprisingly useful for mixing hex-coded html/svg colors.

By David Eppstein

Authors: Péter Madarasi

The Kemeny rule aggregates rankings by minimizing their total Kendall-tau distance from an aggregate order. We prove that Kemeny Score is NP-complete for exactly three unweighted rankings, even when every candidate pair is split $2$-to-$1$. On the same profiles, the winner, unique-winner, and possible- and necessary-precedence problems are $Θ_2^p$-complete, while recognizing a Kemeny-optimal or uniquely Kemeny-optimal aggregate is coNP-complete. The hard instances induce tournaments of majority dimension exactly $3$. The reduction also determines the exact maximum-cut value from the optimal Kemeny score and recovers a maximum cut from any Kemeny-optimal aggregate. For every fixed $q\geq3$ and $\lceil q/2\rceil\leq s\leq q$, minimum pairwise support $s$ yields a sharp dichotomy: the score problem is NP-complete, the winner and precedence problems are $Θ_2^p$-complete, and the recognition problems are coNP-complete when $3s\leq2q$; for $3s>2q$, the majority tournament is transitive and its unique topological order is the unique Kemeny-optimal aggregate. Exact support $s$ suffices in the hard case when $s>q/2$, and supports in ${s,s+1}$ suffice when $s=q/2$. These results give complete fixed-profile-size classifications and transfer to Slater orders, permutation medians, and maximum-likelihood central rankings in the Mallows model. Finally, a six-copy construction proves NP-completeness of both Kemeny Score and Kendall--Tau Center for three pairwise-equidistant rankings that still split every pair $2$-to-$1$. For $N$ output candidates, their common distance is $\frac23\binom N2$, the largest possible for an equidistant triple. The construction gives affine formulas for both optimal values, characterizes all Kemeny-optimal output orders, and shows that the output has a unique Kemeny-optimal order and a unique center exactly when the input has a unique Kemeny-optimal order.

Authors: Pasin Manurangsi

We study the complexity of computing the Threshold dimension of a hypothesis class and its variant, the Extended threshold dimension. For the latter, we prove that it is both NP-hard and co-NP-hard, which (partially) answers an open question of Dmitriev et al. (SODA 2026). Furthermore, by relating the problem to a variant of Maximum Balanced Biclique, we prove strong hardness of approximation for both dimensions, including in the parameterized setting. As an intermediate result, we also prove hardness (of approximation) results for computing the ladder index and the semi-ladder index (Fabianski et al., STACS 2019), which have recently been used in the design of fixed-parameter tractable algorithms.

Authors: Tianhang Lu, Runtian Ren, Shengcai Liu, Ke Tang

This paper studies learning-augmented and randomized online aggregation with delays on a line metric. We consider advice given as online suggested service lengths, and evaluate the algorithms in terms of robustness and consistency. For each $λ\in (0,1]$, we first propose a deterministic learning-augmented \textsc{Balance} algorithm that is $(4/λ+1/λ^2)$-robust and $(4+λ)$-consistent. We also propose a randomized algorithm for the problem in the classical adversarial model, which is $(e+1)$-competitive against an oblivious adversary, improving over the deterministic $5$-competitive \textsc{Balance} benchmark~\cite{bienkowski2013chain}. Notably, this competitive ratio is even lower than the lower bound of $4$ for deterministic online algorithms. Moreover, we establish a lower bound of $e$ on the competitive ratio of randomized online algorithms, improving the previous lower bound of $e/(e-1)$. Besides, we combine the two ideas and obtain a randomized learning-augmented algorithm that is $(e/λ+1/λ^2)$-robust and $(e+λ)$-consistent. Finally, we conduct numerical experiments to complement our theoretical analysis and evaluate the empirical performance of our algorithms.

Authors: Mahendra Kumar R, Renjith P, Aadhavan S, Sadagopan N

A connected graph G is said to be a bisplit graph if the vertex set of G can be partitioned into a stable set and a complete bipartite graph. We establish the following dichotomy with chordality being the parameter; for chordal bisplit graphs, Hamiltonian cycle (HCYCLE) and Hamiltonian path (HPATH) problems are polynomial-time solvable, and for chordal bipartite bisplit graphs, HCYCLE (HPATH) is NP-complete. We further strengthen the result of [1] and show that HCYCLE (HPATH) is polynomial-time solvable on P5-free chordal bipartite graphs (bipartite chain graphs) and NP-complete on P10-free chordal bipartite graphs. By using our polynomial results on HCYCLE (HPATH) as a framework, we solve many variants and generalizations of HCYCLE (HPATH), which are also reported in this paper.

Authors: Jesús Gacías Franco

By examining the relationship between the support function of convex geometry and the Euler Characteristic Transform (ECT) of topological data analysis, we develop new tools and suggest variations on some common ECT pipelines. Specifically, we put forward new definitions of ECT-induced pseudodistances, which have the advantage of being invariant under common euclidean isometries and require no cutoff parameter to compare shapes with distinct Euler characteristic. These definitions rely on a generalization of the convex geometric concept of the Steiner point, which we define in general as a distinguished point given by the ECT. We also show how convex geometry provides a path to recover interesting geometric information of a flat shape from its ECT, namely, its perimeter, for which we give an explicit formula. By building on these concepts and leveraging persistent homology, we define Steiner barcodes as an isometry invariant feature of shapes, as well as homological variants of the support function and Steiner point. Finally, we put these constructions to the test in shape classification tasks, providing lightweight features for aligned and misaligned datasets.

Authors: Markus Wallinger, Oscar Navarro, Stephen G. Kobourov

Trees arise in many applications and computing nice tree layouts is a classical problem in information visualization. In many practical settings, vertices need to be represented as rectangles with a given width and height rather than as points. When an order over the children of each vertex is given, polynomial-time algorithms are known that produce drawings adhering to various drawing conventions. However, in many applications, the order of children carries no semantic meaning, and choosing it well can significantly reduce the drawing's width. In this paper, we study the problem \textsc{Min-Width Tree Drawing with Reordering} (\textsc{MWD}): given a rooted tree whose vertices have prescribed widths, find a sibling order at each internal vertex that minimizes the width of the resulting layered drawing. We show that the problem is \textsf{NP}-complete, even on binary trees with unit-width vertices. We present a mixed integer linear program that solves \textsc{MWD} exactly on moderately sized instances, and a heuristic that is fast and delivers good results in practice. We evaluate both approaches against a baseline on synthetic and real-world datasets, where reordering reduces drawing width by a median of $\approx20\%$ and by up to $\approx55\%$ on individual instances. The heuristic computes its layouts in under a second and, when the MILP proves optimality, it stays within $25\%$ of the optimal width in three-quarters of all instances.

Authors: Tongyang Li, Fengning Ou, Xinzhao Wang, Penghui Yao, Pei Yuan, Shengyu Zhang

Many quantum algorithms require coherent access to classical data, often modeled by quantum read-only memory (QROM). We initiate the study of the $T$ count of sparse QROM, in which only $s$ of the $2^n$ addresses store nonzero data. We prove asymptotically optimal $T$-count bounds $Θ(\sqrt{sm} + \sqrt{sn})$ with square-root dependence on the support size $s$ and message length $m$. Our upper bounds use a multilevel hashing scheme, while our lower bounds reduce sparse QROM to state preparation and use counting arguments for adaptive Clifford+$T$ circuits. The lower bounds thus hold even when mid-circuit measurements and classically controlled operations are allowed. As applications, we obtain matching $T$-count bounds $Θ(\sqrt{sn} + \sqrt{s\log(1/\varepsilon)} + \log(1/\varepsilon))$ for $s$-sparse state preparation and $Θ( \sqrt{2^n sn} + \sqrt{2^n s\log(s/\varepsilon_{\mathrm{BE}})} + \log(s/\varepsilon_{\mathrm{BE}}))$ for block encoding of $s$-sparse matrices, where $\varepsilon$ and $\varepsilon_{\mathrm{BE}}$ are the precision of state preparation and block encoding, respectively.

Authors: Robert Ganian, Manolis Vasilakis, Simon Wietheger

Instance selection is a vital technique for mitigating the computational bottlenecks of nearest-neighbor classification in large-scale supervised clustering. A classical theoretical formulation of this objective is the Minimum Consistent Subset (MCS) problem. While recent research has explored its complexity on unweighted graphs to uncover structural boundaries of tractability, arbitrary metric spaces are much more accurately modeled by (edge-)weighted graphs. In this paper, we develop a comprehensive fine-grained complexity map of MCS on both unweighted and weighted graphs. As our main result, we introduce a $3^{c \cdot(\mathrm{tw}+1)}\cdot n^{\mathrm{tw}+\mathcal{O}(1)}$ algorithm for $n$-vertex $c$-colored MCS instances on weighted graphs of treewidth $\mathrm{tw}$, substantially improving upon the previous state-of-the-art algorithm for unweighted MCS on trees both in terms of generality and running time. We complement this positive result with a series of lower bounds that rule out asymptotic improvements to the running time for both weighted and unweighted graphs under the Exponential Time Hypothesis (ETH). Moreover, we improve the recent slightly superexponential vertex-cover based algorithm for unweighted MCS (AAAI 2026) to a single-exponential one, and rule out further improvements to subexponential running times under the ETH. Together, our results strictly delineate the algorithmic boundaries of consistent subset selection across diverse metric structures.

Authors: Shuichi Hirahara, Naoto Ohsaka

In the Maxmin $q$-CSP Reconfiguration problem, given a satisfiable $q$-CSP instance and a pair of its satisfying assignments, we are asked to transform one assignment into the other by repeatedly changing the value assigned to a single variable. The objective is to find such a transformation that maximizes the minimum fraction of satisfied constraints along the transformation. In this paper, we prove that for any $q \geq 2$ and $\varepsilon > 0$, Maxmin $q$-CSP Reconfiguration is $\mathsf{PSPACE}$-hard to approximate within a factor of $\frac{1}{2^{q-1}}+\varepsilon$. To complement this hardness result, we prove that a $\bigl(\frac{1}{2^{q-1}}-\varepsilon\bigr)$-factor approximation for Maxmin $q$-CSP Reconfiguration is in $\mathsf{NP}$ in the perfect completeness case. These results establish the optimal $\mathsf{PSPACE}$-hardness of approximating Maxmin $q$-CSP Reconfiguration for every $q \geq 2$ under $\mathsf{NP} \neq \mathsf{PSPACE}$.

Authors: Khaled Elbassioni, Rishikesh Gajjala, Saurabh Ray

Many geometric stabbing problems admit natural covering LPs in which each constraint is a union of consecutive traces on ordered candidate sets. We prove a transfer theorem showing that every fixed finite, bounded-arity integrality-gap instance of this form yields a matching hardness ratio under the Unique Games Conjecture. Using the strict-CSP framework of Kumar, Manokaran, Tulsiani, and Vishnoi [SODA 2011], we construct the required connected local distributions by randomized rounding and a full-support perturbation. Given a fractional vector $x$ on a block, the rounding selects candidate $i$ with marginal probability $x_i$ and hits each consecutive trace $T$ with probability $\min\{1,x(T)\}$. We obtain three tight UGC thresholds. First, for every fixed $d\ge 2$, stabbing arbitrary-size axis-parallel $d$-cubes with coordinate hyperplanes has threshold $d$. For $d=2$, the hardness holds for arbitrary-size squares and establishes threshold $2$ for rectangle and square stabbing, matching the $2$-approximation of Gaur, Ibaraki, and Krishnamurti [ESA 2000]. Second, stabbing horizontal segments with horizontal and vertical lines has threshold $e/(e-1)$, matching the $e/(e-1)$-approximation of Kovaleva and Spieksma [ESA 2004]. Third, separated $d$-interval transversal has threshold $d$ for every fixed $d\ge 2$, closing under UGC the gap left by the $d$-approximation of Ben-David, Grant, Ma, and Sharpe [CCCG 2012].

Authors: Jincheng Guan, Shuai Shao, Ke Shi

The weighted Eulerian orientation counting problem ($\#\mathrm{EO}$) plays a key role in the complexity classification program for Holant problems. A recent result established an $\mathrm{FP}^{\mathrm{NP}}$ versus $\#\mathrm{P}$-hard dichotomy for $\#\mathrm{EO}$ problems. The tractable side of this dichotomy can be characterized by functions admitting quasi-polymorphisms of the ternary XOR operation, leaving open whether these cases on the $\mathrm{FP}^{\mathrm{NP}}$ side are in fact in FP. In this paper, we settle this question by giving a polynomial-time algorithm for all cases on the $\mathrm{FP}^{\mathrm{NP}}$ side. Consequently, we obtain a complete FP versus $\#\mathrm{P}$ dichotomy for counting weighted Eulerian orientations, and further for complex-valued Holant problems with an odd-arity signature. Our algorithm is based on a linear programming relaxation, but we use it in a nonstandard way. Instead of proving that the relaxation is integral and solving the problem directly from an optimal LP solution, we use the relaxation as a structural tool to lift the quasi-polymorphism condition to an ordinary polymorphism condition. This reveals an affine local structure of the constraint functions, which leads to tractability.

Authors: Zhili Chen, Zhan Yu

We study the problem of learning an unknown Markovian open-system generator from access to its physical time evolution. This generator, called a Lindbladian, contains Hamiltonian and dissipative coefficients indexed by an exponentially large family of possible Pauli terms. We propose an efficient algorithm that learns arbitrary Lindbladians from time evolution under minimal assumptions. For a Lindbladian of dynamical strength at most $Λ$, the algorithm estimates every coefficient to error $ε$ using $\widetilde O(Λ^2/ε^2)$ experiments and $\widetilde O(Λ/ε^2)$ total evolution time, together with polynomial classical running time. The algorithm consists of two nonadaptive, ancilla-free, and control-free stages: 1. The support-learning stage outputs a candidate support of size $\mathrm{poly}(Λ/η)$ that contains every Hamiltonian and dissipative coordinate of magnitude at least $η$, using $\widetilde O(Λ^2/η^2)$ experiments with preparations of product Pauli eigenstates and single-qubit Pauli measurements. 2.The coefficient-learning stage estimates all coefficients in any candidate support of size $M$ to error $ε$, using $\widetilde O(Λ^2\log M/ε^{2})$ experiments with preparations of random stabilizer states and measurements in random Clifford bases. Composing the two stages identifies and estimates every coefficient of an arbitrary Lindbladian in polynomial time. The experiment-count and total-evolution-time scalings match the lower bounds up to logarithmic factors, so the algorithm is nearly optimal for learning arbitrary Lindbladians.

Authors: Alexandra Lassota, Krzysztof Sornat

We study the computational complexity of winner determination problems in approval-based committee elections under Thiele voting rules. These form a class of rules parameterized by a fixed weight vector that specifies how a voter's satisfaction depends on the number of approved candidates elected. We first analyze the structure of optimal solutions based on the sets of voters who approve each candidate---that is, how voters' approval ballots induce dependencies between candidates---revealing constraints on a winning committee under any fixed Thiele voting rule. Using this, we design FPT algorithms for Proportional Approval Voting (PAV) and other Thiele rules on a natural restricted domain known as the Voter Interval (VI) domain---that is, after a suitable ordering of voters, each candidate is approved by a consecutive interval of voters. In particular, we show that every Thiele rule on VI is FPT with respect to a parameter for which the problem is NP-hard on general instances, even when the parameter takes constant values. Our results advance the understanding of the computational complexity of PAV on Voter Interval instances, which remains one of the central open questions in this area. We further resolve two open questions from the literature on PAV (and other Thiele voting rules) by providing a polynomial-time algorithm for instances where each candidate is approved by at most two voters, and an FPT algorithm parameterized by the total score of a winning committee.

Authors: Sotiris Kanellopoulos

In perpetual scheduling theory, the Pinwheel Covering problem asks, given $n$ frequencies $f_i$, whether there exists an infinite schedule such that every $f_i$ consecutive entries contain at most one occurrence of $i\in [n]$. This models $n$ agents taking turns at executing a job, with a recovery period before working again. Pinwheel Covering is, in a sense, the dual of Pinwheel Packing (also known as Pinwheel Scheduling), which similarly asks for at least one occurrence of $i$ in every $f_i$ consecutive entries. The complexity of both problems is a major open question: both are known to be in PSPACE, but PSPACE-hardness remains unknown. Recently, a finite version of Pinwheel Packing requiring only $k$ occurrences of $i\in [n]$ was introduced by [Kanellopoulos et al., SODA 2026] and proven to be strongly NP-complete. In this work we introduce $k$-Visits Covering, the analogous finite version of Pinwheel Covering, establishing strong NP-completeness even for $k=2$. As a corollary, we obtain that a generalization of Pinwheel Covering with varying frequencies is strongly NP-hard. To the best of our knowledge, this is the first strong NP-hardness result in the covering setting. We complement these results with a linear-time algorithm for $2$-Visits Covering with two distinct frequencies and a randomized polynomial-time algorithm when the number of distinct frequencies is constant. Lastly, we study the density thresholds of $k$-Visits Covering and prove that no non-trivial density bounds exist, contrasting the finite packing version.

Authors: Jan-Henrik Haunert, Joshua Marc Könen, Heiko Röglin, Tarek Stuck

A problem that occurs in different applications in geographical information science is to generate compact regions from areas on a map. This is important, e.g., in the context of electoral districting to avoid gerrymandering. A common measure for the compactness of a region is the Polsby-Popper score, which measures how close a given region is to a circle based on its area and perimeter. We assume that a polygonal subdivision of the plane is given and study the problem of selecting a subset of the polygonal faces that maximizes the Polsby-Popper score, given by $\frac{4πA}{P^2}$, where $A$ is the area of the selected shape and $P$ is its perimeter. We consider the more general task of maximizing $\frac{A}{P^α}$ for an arbitrary $α>1$, which we call the $α$-circularity problem. We perform the first rigorous study of its complexity and show that it is weakly NP-hard if $α\in (1,2]$. Furthermore, for $α>1$ we present a pseudopolynomial time algorithm for this problem.

Authors: Sebastian Angrick, Ben Bals, Paweł Gawrychowski, Solon P. Pissis, Yuki Yonemoto

We consider directed graphs in which the nodes are labeled with strings. A walk in such a graph naturally corresponds to the concatenation of the visited nodes' labels. These graphs are widely used in bioinformatics to compactly describe large collections of highly similar genomes. Given such a graph $G=(V,E)$ and a pattern of length $m$, we seek a walk whose corresponding string has an occurrence of the pattern. We call this the SMLG problem. Amir et al. [J. Algorithms, 2000] showed that SMLG can be solved in $\mathcal{O}(m|E| + N)$ time, where $N$ is the total length of all node labels. Equi et al. [ACM Trans. Algorithms, 2023] showed that this is essentially optimal (under SETH). The existing lower bound assumes that the sought walk is of length $Θ(|V|)$. Thus, we might be able to bypass this lower bound by restricting the walk length to $b-1$, which naturally reduces to having as input a directed graph whose set of nodes is partitioned into $b$ blocks. Then, we seek a walk in this graph that starts in the first block and ends in the last block. We call this the $b$-SMBG problem. We provide a more fine-grained classification that essentially settles the complexity of $b$-SMBG parameterized by $b$: (1) We give a near-linear-time algorithm for $b=3$. (2) We show that there is no combinatorial algorithm improving over the state-of-the-art $\mathcal{O}(m|E| + N)$ bound for any $b\ge 4$. (3) We also present a fast matrix multiplication-based algorithm yielding an improvement for $b \in \mathcal{O}(1)$, which is conditionally optimal. (4) Finally, we show that under SETH, for any $b \in ω(\log |V|)$, no algorithm can improve over the state of the art.

Authors: Gabriel Carmona, Paolo Ferragina, Giovanni Manzini, Francesco Tosoni

In this paper, we study static, computation-friendly, lossless compression formats for graphs, focusing on memory locality and operational efficiency of $k^2$-trees. We observe that their traditional level-wise layouts suffer from poor cache performance due to weak locality, especially in operations such as matrix-vector and matrix-matrix operations. To address this limitation, we propose four depth-first representations of $k^2$-trees: a plain depth-first layout (EDF-1), a balanced-parenthesis representation (BP), and their compressed variants (CEDF and CBP). We further introduce a linear-time compression method based on suffix and LCP arrays to identify and compress identical subtrees. We experimentally evaluate the execution time, the disk space, and the peak-memory usage of our approaches against classical level-wise $k^2$-trees and DFUDS-based representations across two real and one synthetic dataset (i.e., Web Graphs, Wikidata, and random adjacency matrices) over the above linear-algebra operations. Results show that our depth-first layouts are competitive and often superior than known approaches: CEDF achieves the best compression in most settings, EDF-1 and CEDF reduce the peak memory usage consistently, and performance varies by workload, with different layouts excelling in different operations and data regimes. Overall, this work demonstrates that depth-first layouts of $k^2$-trees provide a practical and efficient alternative to traditional layouts, improving both compression and computational performance in matrix operations.

Authors: David García-Soriano, Antoine Schohn

We give an $(1.3865+\varepsilon)$-approximation for correlation clustering in complete graphs, improving the previous best factor of $1.485+\varepsilon$ of Cao et al.\ (STOC'24). Our two key contributions are independent: an efficient approximate separation oracle for the cluster-LP dual and a new rounding scheme. The dual separation task is the CCMinRatio problem: for signed vertex weights $q$, minimize $cost(S)/q(S)$ over sets with $q(S)>0$; here $cost(S)$ measures the correlation clustering disagreements attributed to $S$ in any clustering in which $S$ is a cluster. We give a randomized $(1+\varepsilon)$-approximation in time $2^{poly(1/\varepsilon)}(n+\langle q\rangle)^{O(1)}$. Via the ellipsoid method, this yields a $(1+\varepsilon)$-approximation of the fractional cluster-LP optimum, along with exactly feasible primal and dual solutions certifying its value and a per-instance certificate. The algorithm works directly on the original instance, without a global preclustering: a new localization technique restricts the search to a small universe while preserving a violation, after which weak regularity handles the resulting dense quadratic minimization. Our rounding scheme retains the cluster-based procedure of Cao et al.\ but uses a continuous conditional pivot rule whose analysis rests on a single variance inequality with explicit weights and an exact computer-assisted verification of the resulting polynomial inequalities. This also places the integrality gap of the cluster LP in the narrow range [4/3,1.3865].

Authors: Jayant Chandwani, Pranav M R, Anand Jat, Anshu Ostwal, Diptendu Chatterjee, Anand Narasimhamurthy

The Multi-Depot Capacitated Vehicle Routing Problem (MDCVRP) asks for minimum-cost delivery tours from several capacitated depots to a set of customers. Like most vehicle-routing variants it is NP-hard, so practical solvers must trade solution quality against speed. We revisit this trade-off through the lens of graph matching. Adapting a matching-based construction first developed for the Traveling Tournament Problem, we present two algorithms, Cluster-First and Match-First, that reduce routing to a sequence of minimum-weight matchings. This is more than a heuristic. We prove that for tours of up to two targets the matching formulation solves the MDCVRP exactly in polynomial time for any number of depots, and that both algorithms are constant-factor approximations, with a tight factor of two, in the structured regimes. This matching optimum coincides with the exact combinatorial-auction optimum, so the auction serves as a strong quality baseline. On instances of 1000 customers and 20 depots our methods match or slightly beat that baseline in tour length while running two to three orders of magnitude faster, in tens of milliseconds against tens of seconds, a scale at which exact and auction-based solvers become impractical. Because Cluster-First routes each depot independently, the approach also re-routes cheaply when new customers arrive.

Authors: Zhao Song

We prove an improved restricted isometry bound for Gaussian partial circulant matrices with arbitrary prescribed sampling sets. There is a universal constant $C>0$ such that the following holds. Let $1\leq K\leq m\leq N$ be positive integers, let $Ω\subset\mathbb Z_N$ be any fixed set with $|Ω|=m$, and let $g\sim\mathcal N(0,I_N)$. For every $δ,η\in(0,1)$, the normalized partial circulant matrix generated by $g$ has the RIP of order $K$ with constant at most $δ$, with probability at least $1-η$ over the draw of $g$, provided \[ m\geq Cδ^{-2}K \max\{\log^2(eK)\log(2N)\log(em),\log(2/η)\}. \] The proof refines the Maurey entropy step in the chaos-process argument by combining a noncommutative Khintchine inequality with a Schatten moment estimate controlled by $m$, replacing one factor $\log(2N)$ in the Krahmer--Mendelson--Rauhut bound by $\log(em)$.

The Princeton DeCenter invites applications for Postdoctoral Fellows (and more senior researchers) beginning February 2027. Fellows will join an interdisciplinary community advancing research on blockchain, decentralized technologies, and their applications across computer science, economics, law, political science, philosophy, and related fields at Princeton University.

Website: https://apply.interfolio.com/185365
Email: decenter@princeton.edu

By shacharlovett

There is a lot of anxiety about ai wiping off mathematics, including theoretical computer science. It’s funny that we wanted ai to cut *their* jobs, and instead it’s *our* jobs that are cut (maybe). My expectation of what is going to happen is rather flat, and I am open to various scenarios. Still I wanted to make some points.

First, at the moment of this writing, I am not so worried about ai killing the field. There are so many problems in math, and the literature is so unmanageably vast and technical, that I am not particularly shocked that using massive resources one can solve *some* problems. It is very different if the resources can solve *the* problems. For example I, and I am sure many others, have tried to use ai to solve problems in computational complexity and so far didn’t get much. I do find ai to be a very useful assistant, but so are many other things. It may be that the next level of solving target problems (as opposed to finding targets) may prove the most difficult to reach.

I want to suggest an option for the community to put ourselves in a position of strength, in case one really fears the impact of ai. I think ai can easily enough be “frozen” and made much less useful for future research. The way to do this is simple: We could stop feeding it. It was humiliating enough to post papers online only to be asked later by the publisher to pay for “gold open access.” But now that there is this new way to exploit, plagiarize, and monetize our creations on a massive scale, it may be too much. Suppose starting immediately all new math is communicated in ways that ai can’t easily scrape. There are many ways to do this; we could still put papers online, but allow only much more limited access, compatible with human beings but not ai scraping. It coud be similar to what is done for example at the Internet archive, where you can read a book but not easily download it. I am not going to go more in details. While ai would remain very useful for things on the table until that moment, I think it would quickly become much less useful for new lines of research, series of papers building on each other, etc. This would put the community in a position of strength as keeper of knowledge. After a while, things could be reassessed.

We should not forget that the models can do math only because back then we chose to be nice and so taught them how to do it for free.

By Manu

Tenure-track position in theoretical computer science. Two course per semester teaching load, competitive salary. UNF’s School of Computing offers BS, MS, and PhD degrees in Computing. Candidates must have earned Ph.D. by start date of August 2, 2027.

Website: https://unf.wd5.myworkdayjobs.com/unfjobs/job/Jacksonville-FL/Professor—Computing–Open-Rank-_JR103390
Email: indika.kahanda@unf.edu

By shacharlovett

Authors: Igor S. Sergeev

It is shown that the $\mathsf{OR}$-rank (covering rank) of the $2^n \times 2^n$ unique disjointness matrix is $n^{O(1)}(3/2)^n$, hence the known lower bound $1.5^n$ turns out to be essentially tight. By the way, an upper bound $1.89^n$ is obtained for the $\mathsf{SUM}$-rank (partition rank) of this matrix.

Authors: Ramin Javadi, Hossein Shokouhi

Given a graph $G=(V,E)$, a (proper) $k$-coloring for $G$ is a vertex coloring with $k$ colors such that every two adjacent vertices receive different colors. Suppose that the vertex set $V$ is partitioned into some groups, a proper coloring is called fair if for every color class, the difference between the number of vertices in any two groups does not exceed a given threshold. In this paper, we investigate the parameterized complexity of the fair coloring problem with respect to the structural parameters of the input graph. In particular, we prove that the problem is W[1]-hard with respect to the number of groups for forests and also graphs of modular-width two, even when the number of colors is equal to two. On the positive side, we prove that when the number of colors is equal to two, then the problem is FPT with respect to neighborhood diversity of the input graph. Moreover, in general, the problem is FPT with respect to neighborhood diversity and the number of groups. As a by-product, we prove that unary vector bin packing problem is W[1]-hard with respect to the dimension.

Authors: Fangqi Dong, Alex Lombardi, Fermi Ma

The unitary synthesis problem (Aaronson-Kuperberg, CCC 2007) asks whether every $n$-qubit unitary $U$ is computable by efficient quantum circuits relative to some classical oracle $f = f_U$ depending on $U$. Recently, Lombardi-Ma-Wright (STOC 2024) proved that Haar-random unitaries cannot be efficiently synthesized by algorithms that make 1 query (or poly$(n)$ parallel queries) to an arbitrary classical oracle. In this work, we prove several results about the hardness (and easiness!) of variants of unitary synthesis. Our results include: (1) 1-query vs. 2-query unitary synthesis: we prove 1-query lower bounds for synthesizing random permutation unitaries $P\lvert x\rangle = \lvert π(x)\rangle$, as well as random alternating-basis phase unitaries $F_2 \cdot H^{\otimes n} \cdot F_1$. This gives 1-query lower bounds for "explicit" families of unitaries that have efficient (even 2-query) synthesis algorithms. (2) Upper bound for complex phase unitaries: we also consider complex phase unitaries $\lvert x\rangle\mapsto α_x \lvert x\rangle$, which have a clean 2-query synthesis algorithm with no obvious 1-query algorithm. In this case, we prove an upper bound: there are 1-query algorithms (relative to binary phase oracles) that constant-approximate these unitaries in diamond distance. In order to prove our lower bounds, we introduce and analyze two new cryptographic games: the oracle state search game and the oracle Choi state game. Compared to prior work, our framework is mathematically simple, more flexible in what it can prove, and more accurately captures the hardness of synthesizing unitaries that are not "fully random". Finally, we also use the search game to prove a new hardness-of-approximation result for quantum programs (synthesizing unitaries relative to quantum advice) for phase unitaries, giving a sharper separation between 1-query unitary synthesis and quantum programs.

Authors: Theodoros Yianni, Nyan Raess, Farid Shahandeh

Generalized contextuality is a canonical distinguishing property of nonclassical generalized probabilistic theories, in particular quantum mechanics. Methods for certification and characterization of generalized contextuality of a given generalized probabilistic theory are well developed for prepare-measure and single-stage prepare-transform-measure scenarios. In a recent work [arXiv:2512.10000], a bottom-up, statistics-first linear-algebraic framework for contextuality in prepare-measure scenarios was introduced. We extend this approach to operational scenarios with sequential transformations with an arbitrary number of stages. We give a full decision procedure for contextuality of such scenarios within operational theories and analyze its computational complexity. In particular, our decision procedure has a complexity linearly exponential in the minimum generalized probabilistic theory (GPT) dimension, and polynomial in the number of procedures. We demonstrate our framework and approach through multiple examples, including Spekkens' toy theory and the 8-state single-qubit stabilizer theory. In particular, we construct an operational theory in which contextuality manifests itself only in the sequential structure of the transformations. Our findings thus shed new light on the significant role of compositional structures in the phenomenon of generalized contextuality.

Authors: Matan Gilboa

In a hedonic game, agents need to be partitioned into coalitions, and have a preference order over partitions. A partition is called strongly popular if it beats any other partition in a majority vote among the agents. We focus on the fundamental class of additively separable hedonic games (ASHGs), where agents have additive valuations that induce their preferences. We prove that determining the existence of strongly popular partitions in ASHGs is complete for PCW, a recently introduced complexity class which lies in between $P^{NP}$ and $S_2^P$ (Gilboa et al., 2025). This settles an open problem by Brandt and Bullinger (2022) and Bullinger and Gilboa (2025).

Authors: Tomoyo Kikuchi, Takashi Kanai

Convex Collision-Free Regions (CCFR) is a collision handling method that explicitly represents local convex feasible regions to enforce non-penetration. Each feasible region is constructed from surrounding mesh primitive configurations, including edge-edge and vertex-face interactions. The resulting convex region represents admissible non-penetrating vertex displacements at the current configuration. Existing collision handling methods for deformable body simulation have largely relied on implicit representations of feasibility, resulting in either compromised robustness for secondary collisions and codimensional contacts or tight coupling with specific nonlinear optimization schemes. Our formulation constructs feasible regions independently for each vertex, defined prior to penetration, inherently accounts not only for primary collisions but also for secondary collisions and codimensional contacts, enabling highly scalable and parallelizable collision handling. These feasible regions encode geometric non-penetration constraints independently of physical contact response models. CCFR does not rely on nonlinear optimization and is compatible with simulation frameworks such as Extended Position-Based Dynamics (XPBD) that do not explicitly maintain interior feasibility during iterative updates. The effectiveness of CCFR is demonstrated across cloth, hair, wire, particle systems, and codimensional contact scenarios, showing versatile and efficient collision handling.

Authors: Chris Kapulkin, Kyle Koyanagi

We show stability of persistent path homology of path complexes. As a consequence, we deduce the stability of persistent path homology of hypergraphs and of sequence hypergraphs, and recover the known stability result for digraphs, originally due to Chowdhury and Mémoli.

Authors: Angelos Pelecanos, Jack Spilecki, Ewin Tang, John Wright

We give an algorithm which, given $n = O(d^2 \cdot (\log\log(d)/\log(d))^2)$ copies of $ρ$, estimates the eigenvalues of $ρ$ to constant error in total variation distance. Thus, we can learn the eigenvalues of a quantum state with fewer copies than the $Θ(d^2)$ needed to run full state tomography. This is the first improvement to spectrum estimation over the influential Keyl-Werner algorithm, which uses $n = Θ(d^2)$ copies, thereby resolving a question raised by Keyl and Werner in 2001 and refuting a 2016 conjecture of Wright. Our main technical tool is a new tomography guarantee, where the error of tomography in a particular direction $|w\rangle$ scales with $\langle w | ρ|w\rangle$ for all directions simultaneously. From this stronger "relative-error" bound, we recover better algorithms for principal component analysis in Bures distance and tomography in $χ^2$-divergence as corollaries.

Authors: Xiaobin Ren, Hans L. Bodlaender

A graph is outer k-planar if it admits a straight-line drawing in which all vertices lie on a circle and every edge is crossed by at most k other edges. We study the parameterized complexity of a broad collection of graph problems on outer k-planar graphs, with k as the parameter. Many graph problems are known to be XALP-hard when parameterized by treewidth or outerplanarity, and XNLP-hard when parameterized by pathwidth. We show that only a few such problems, including Binary CSP and Scattered Set, remain intractable on outer k-planar graphs, whereas a large class of the others become fixed-parameter tractable in this setting, assuming that an outer k-planar drawing of the input graph is given. These include List Coloring, Capacitated Dominating Set, Capacitated Vertex Cover, Target Outdegree Orientation, and Target Set Selection, among others. In addition to the algorithmic and complexity results, we establish several structural results. We show that outer k-planar graphs have mim-width at most k+2, that graphs of cut-width at most k are outer 2k-planar, and that graphs of feedback edge set number at most k are outer 6k-planar. We also show that many graph parameters are incomparable with outer k-planarity, thereby clarifying its position within the graph parameter hierarchy.

Authors: Cassandra Marcussen, Edward Pyne, Ronitt Rubinfeld, Asaf Shapira, Shlomo Tauber

Graph $k$-coloring is one of the classic NP-complete problems. Previous work has studied its average time complexity, defined to be the average runtime of computing a $k$-coloring over the set of all $k$-colorable graphs on $n$ vertices. A highly influential result of Dyer-Frieze from 1989 gave an algorithm with $O(n^2)$ average runtime for constant $k$. This quadratic runtime appeared natural (and possibly even optimal) since almost all $k$-colorable graphs have $Θ(n^2)$ edges, so one needs at least this time in order to read the (entire) input. However, this was later improved by Kučera in 1995 to average runtime $O(n^2/k)$ for every $k \leq n^{c}$ where $c \in (0, 1)$. Nevertheless, in the most interesting case of $k = O(1)$, the best-known bound remained quadratic in $n$. The true average complexity of the $k$-coloring problem has remained elusive for the last three decades. We break the longstanding quadratic barrier. Our main result in this paper shows that the exact average-case complexity of this fundamental problem is $Θ(nk)$ for every $k \leq n^{c'}$ and some $c' \in (0, 1)$. For $k = O(1)$, this reveals the average sublinear nature of $k$-colorability: the average-case complexity is linear in $n$, and thus sublinear in the size of the input. We further show that our $Θ(nk)$ average runtime is optimal, since a simple bound proves that every algorithm that correctly $k$-colors all $k$-colorable graphs requires $Ω(n k)$ average runtime. Our proofs draw on ideas from sublinear and local algorithms and also yield a local computation algorithm (LCA) for $k$-coloring with average-case probe complexity $\text{poly}(k)$. A key new ingredient in our algorithm is a method for certifying the unique colorability of random subgraphs, using tools from the theory of graph regularity.

Authors: Venkatesan Guruswami, Xuandi Ren, Shaoxuan Tang

The Unique-Machine Precedence Scheduling (UMPS) problem, introduced by [DKRSTZ22], seeks a makespan-minimizing schedule of precedence-constrained jobs when each job has a unique eligible machine. On the one hand, UMPS generalizes job shop scheduling by allowing the precedence graph to be an arbitrary DAG rather than a disjoint union of chains. On the other hand, UMPS admits approximation-preserving reductions to scheduling problems with communication delays, including the job-job delay model [DKRSTZ22] and the job-machine delay model [RSY23]. Despite its central role, the approximability of UMPS has remained poorly understood: even for unit-length jobs, known scheduling techniques do not seem to yield a non-trivial approximation, and the existence of a polylogarithmic approximation was left open by [DKRSTZ22]. On the hardness side, the previous best lower bound for unit-length jobs was only the 5/4 inherited from job shop scheduling [WHHHLSS97]. We prove that unit-length UMPS is NP-hard to approximate within any constant factor. We further show that, assuming NP is not in quasi-polynomial time, unit-length UMPS admits no polynomial-time $(\log n)^γ$-approximation for some constant $γ>0$. Via the known reductions from UMPS, these lower bounds also transfer to the corresponding unit-length communication-delay scheduling models. Our proof proceeds via a reduction from a hypergraph coloring promise problem. In the yes case, the input hypergraph admits a balanced coloring, while in the no case, the hypergraph has no large independent set. Instantiating this reduction with the hardness of [GL18] gives arbitrary constant-factor inapproximability, while combining the $4$-colorable $4$-uniform hypergraph coloring hardness of [GHHSV17] with a certain composition operation for hypergraphs yields the polylogarithmic factor inapproximability.

Authors: Huck Bennett, Matthew Fox, Bryant Morrell

Two linear error-correcting codes $\cal{C}_1, \cal{C}_2 \subseteq \mathbb{F}_q^n$ are called linearly equivalent if there is a linear isometry mapping $\cal{C}_1$ to $\cal{C}_2$. In this work, we generalize the notion of linear equivalence and study the minimum distortion $\cal{D}(\cal{C}_1, \cal{C}_2)$ of a linear mapping between codes $\cal{C}_1, \cal{C}_2 \subseteq \mathbb{F}_q^n$, which quantifies how similar $\cal{C}_1$ and $\cal{C}_2$ are. We introduce and study the Code Distortion Problem (CDP), which asks to find a minimum distortion mapping between two input codes $\cal{C}_1$ and $\cal{C}_2$. CDP generalizes the Linear Code Equivalence Problem (LCE), which is essentially the special case of CDP where $\cal{D}(\cal{C}_1, C_2) = 1$ and which is well-studied because of its role in cryptography. We prove that (decisional) CDP is $\mathsf{NP}$-hard to approximate to within any constant factor, and that it is in $Σ_2^P$. We also give a single-exponential-time $k^2$-approximation algorithm for CDP, where $k$ is the dimension of the input codes. Furthermore, we give a single-exponential-time $\big(\frac{2k + 1}{3})^2$-approximation algorithm for a natural special case of CDP, and we show that our analysis is tight in this case. We use techniques from analogous work on the Lattice Distortion Problem (LDP) by Bennett, Dadush, and Stephens-Davidowitz (ESA, 2016). We also introduce or study a number of additional concepts that might be of independent interest. These include an adaptation of the celebrated reduction of Goldreich, Micciancio, Safra, and Seifert (IPL, 1999) from the Shortest Vector Problem (SVP) to the Closest Vector Problem (CVP) on lattices to the analogous problems on codes; successive minima bases for codes; and the matrix $0 \to 0$ "norm" on subspaces.

Authors: Kuldeep S. Meel, N. V. Vinodchandran, Sourav Chakraborty

We study estimating the size of the union of sets $S_1,\dots,S_M$, where each $S_i\subseteqΩ$ is presented implicitly and arrives in a stream. We introduce Delphic sets, a class of streaming problems in which membership, sampling, and counting queries to each set are efficient, and show that this notion captures three well-known problems: Klee's measure problem (discrete version), test coverage estimation in combinatorial testing, and model counting of DNF formulas. Our primary contribution is a simple and efficient sampling-based algorithm that outputs an $(\varepsilon,δ)$-approximation of the cardinality of the union of Delphic sets in the streaming setting. It has space complexity $O(R\log|Ω|)$ and update time $O(R\log R\cdot\log(M/δ)\cdot\log|Ω|)$, where $R=O(\log(M/δ)\cdot\varepsilon^{-2})$. For the streaming Klee's measure problem, this gives the first algorithm whose update time depends linearly on the dimension $d$ for $d>1$, settling an open problem of Tirthapura and Woodruff (PODS 2012), and it directly yields efficient streaming algorithms for coverage estimation and DNF model counting. We further show that the space for coverage estimation can be made near-optimal at the cost of an update procedure in $\mathrm{P}^{\mathrm{NP}}$, revealing a time-space trade-off. A key strength of our approach is the simplicity of both the algorithm and its analysis, which makes it amenable to practical implementation. In this revised version, the algorithm and its correctness analysis have additionally been formalized and machine-checked in Lean 4. (Shortened for Arxiv)

Authors: Kevin Pratt

We show that for all $k$, there exists $\varepsilon_k > 0$ such that graph $k$-coloring can be solved by a randomized algorithm with one-sided error in time $O((2-\varepsilon_k)^n)$. Prior to this work and independent concurrent work of Zamir [arXiv, 2026], exponential improvements over the $2^n \cdot \mathrm{poly}(n)$-time algorithm of Björklund, Husfeldt, and Koivisto [SIAM Journal on Computing, 2009] were only known for $k \le 6$.

Authors: Xue Chen, Shengtang Huang, Xin Li

Min-wise hashing and its $k$-min-wise extension are fundamental tools in sampling, sketching, and similarity estimation. A standard approach to constructing such families is bounded independence. For ordinary min-wise hashing, the required degree of independence is fully understood: $Θ(\log 1/δ)$-wise independence is both sufficient and necessary. For $k$-min-wise hashing, however, the best previous result only showed that $O(k\log\log1/δ+\log1/δ)$-wise independence suffices, with no matching lower bound. We give a tight characterization of the amount of bounded independence required for $k$-min-wise hashing, proving that $Θ(k+\log1/δ)$-wise independence is both sufficient and necessary. This improves the previous upper bound and provides a matching lower bound. Consequently, the standard construction of bounded-independent hash families has seed length $O\big((k+\log1/δ)\log(N/δ)\big)$. In particular, for any polynomially small error $δ$ and any $k=Ω(\log N)$, it achieves the optimal seed length $O(k\log N)$. We also study random affine hash functions over $\mathbb{F}_2$ and show that, despite being pairwise independent, they may incur multiplicative error $Ω(\log n)$ even for ordinary min-wise hashing.

Authors: Or Stern, Or Zamir

In a seminal result of Yuster and Zwick, they showed that for any fixed $k$, the even cycle $C_{2k}$ can be detected in an $n$-vertex graph in time $O(n^2)$. For $4$-cycles, a folklore algorithm extends to listing: for any $t$, we can list $t$ different $4$-cycles, if such exist, in $O(n^2+t)$ time. Recently, Jin, Vassilevska-Williams, and Zhou obtained similar bounds for listing $6$-cycles. In this work, we generalize the above to cycles of sizes $8, 10, 12, 14,$ and $16$; we show that for all $k\leq 8$, we can list $t$ distinct $2k$-cycles in $\tilde{O}(n^2+t)$ time. In fact, our algorithm gives enumeration with pre-processing time $\tilde{O}(n^2)$ and delay $\tilde{O}(1)$. Additionally, for any fixed $k$, we present an optimal enumeration (and hence also listing) algorithm for all cycles of size at most $2k$. More generally, for any fixed $k$ and any $3\le i\le \frac{4k}{3}$, we present an algorithm with preprocessing time $\tilde{O}(n^2)$ and delay $\tilde{O}(1)$ that enumerates all cycles of sizes in the range $[i,2k]$.

Authors: Frederik Glitzner

Many fundamental problems in multi-agent systems involve the arrangement of agents, who have preferences over each other, on a target graph. These problems include, for example, Stable Matching, Seat Arrangement, and Coalition Formation. However, guaranteeing game-theoretically desirable properties such as exchange-stability or envy-freeness is difficult, as such solutions may not exist, and even if they do, they are often intractable to find, even in highly constrained settings such as path or cycle target graphs. In this paper, we challenge the classical setup and investigate what can be achieved when the structure of the target graph is a designable object for the central planner, rather than a fixed part of the input. We study this in the context of a natural pairwise stability criterion, which is similar to having spare seats. In particular, we introduce a highly flexible framework to efficiently design approximately optimal target graphs and associated pairwise-stable agent arrangements. Our model assumes that agents have (weak or strict) ordinal preferences over other agents. We show that classical results from stable matching theory can be extended and adapted to this much more general setting and can serve as a useful tool for navigating the trade-off between stability and computational efficiency. Our results highlight strict boundaries between tractability and intractability, and between local and global optimality. We also uncover intriguing connections to classical computational problems such as subgraph isomorphism, disjoint path partitioning, and bin-packing.

Authors: Konrad Anand, Alistair Benford, Heng Guo

We present a linear time approximation algorithm of the total variation distance between two product distributions. The main algorithm was found using ChatGPT 5.6 Sol Ultra.

Authors: Jiale Chen, Torsten Hoefler, Dan Alistarh

Adaptive rounding methods such as GPTQ, or equivalently Babai's nearest plane algorithm, round a real matrix to integers under a quadratic metric. They process the entries in a fixed order, one at a time, propagating each rounding error to the entries not yet processed through a triangular feedback matrix. We study the two-sided version of this task, in which fixed nonsingular basis matrices act on both the left and the right of the residual; the familiar one-sided case is the special case of an identity right basis. Vectorizing the matrix turns the two-sided objective into a quadratic metric whose Gram matrix is a Kronecker product, so the one-dimensional algorithm applies verbatim, but takes quartic time in the matrix dimension. We present GPTQ-2D, which produces the identical rounded matrix in cubic time. It rounds the entries anti-diagonal by anti-diagonal; entries on the same anti-diagonal are independent and are rounded in parallel.

Authors: Alex Zihan Xu, Stephen Jing Chick

We present the first in-place comparison-based sorting algorithm that sorts an array of $n$ elements using $n\lg n + O(n)$ comparisons with exponentially high probability and always $O(n)$ moves. This matches the information-theoretic lower bound up to an additive linear term despite making only linear moves and working in-place. For the worst-case, we present an algorithm that makes $n\lg n + O(n\lg^{(t)}n)$ comparisons and $O(tn)$ data moves, where $t$ is an integer parameter satisfying $2 \leq t \leq \lg^{*}n - 1$ and $\lg^{(t)}n$ denotes the $t$-time iterated logarithm, improving over the previous upper bound of $n\lg n + O(n\lg\lg n)$ comparisons and $O(n)$ moves when using constant $t>2$. We thus achieve the ultimate goal of minimal move in-place sorting via randomization whilst narrowing the gap to this goal in the worst-case. This advance primarily relies on a novel ordered set structure that supports searches in an optimal $\lg n + O(1)$ comparisons for $n$ elements.

Authors: Eros De Simone, Giuseppe Bifulco, Lorenza Di Mauro, Antonio Policicchio, Raoul Heese

We propose a sparse computational-basis encoding of voxelized molecular geometries that converts molecular reconstruction from full-state tomography into support recovery by computational-basis sampling. To realize the encoding scheme, the molecular space is discretized into a 3D grid, and each atom's position and chemical species is mapped to a single computational basis state. This discretization introduces spatial quantization at the voxel-resolution scale. The molecule is then encoded as an equal superposition over this sparse set of occupied states, where we assume that a suitable state preparation method exists. In contrast to full state tomography, which requires on the order of $\mathcal{O}(3^n \times 10^{2\text{--}3})$ measurement shots, where $n$ is the number of qubits, our proposed encoding scheme reduces to a coupon-collector sampling problem in the computational basis. Complete recovery of an $A$-atom molecule requires $\mathcal{O}(A\log A)$ shots on noise-free hardware. On noisy hardware, the required number of shots increases. We demonstrate the method on the 156-qubit IBM Kingston device using 8-qubit circuits to reconstruct the discretized geometry of a 10-atom ethylamine molecule with high mean reconstruction recall using only $\mathcal{O}(10^2)$ shots despite substantial hardware noise. These results demonstrate that our proposed encoding scheme is a practical, readout-efficient representation for molecular geometries on near-term devices.

Authors: Ben Bals, Matei Tinca, Yasamin Nazari

In the cut-query model, we have access to a (directed) graph via an oracle and we can query the size of the (directed) cut of a given subset of the vertices. One of the most elementary tasks in this model is to decide if there is a path two fixed vertices $s$ and $t$. While many results are known for undirected graphs, much less in understood for directed graphs in the cut query model. Even for the basic task of $s$-$t$ reachability, the best known randomized algorithm, is to reconstruct the entire graph with a technique by Grebinski and Kucherov using $O(n^2 / \log n)$ queries [Grebinski and Kucherov, 2000]. We restrict our attention to directed acyclic graphs (DAGs) and obtain a deterministic single-source reachability algorithm using $O(n \sqrt{n \log n})$ queries. The result is based on a topological sort algorithm, and can also be adapted to compute single-source shortest paths in DAGs.

Authors: Rahul Vaze

Adaptive conformal inference (ACI) of Gibbs and Cand{è}s and its variants are the standard approach to online conformal prediction under distribution shift, but they suffer from three fundamental limitations. First, their guarantees control only the \emph{signed} long-run coverage error: persistent miscoverage in one direction can be masked by compensating errors later, so a method can satisfy the theoretical guarantee while being badly wrong for extended periods. Second, existing guarantees say nothing about prediction-set size, so validity can be achieved trivially at the cost of unduly wide prediction sets. Third, the efficiency guarantees that do exist compare against a \emph{fixed} predictor chosen in hindsight, a benchmark that becomes increasingly less meaningful once the data-generating distribution shifts, since the very notion of an optimal threshold then changes over time. We consider a unified online learning framework that simultaneously controls absolute, non-cancelling coverage violation and prediction-set efficiency against a dynamically evolving benchmark for three important models. In the fully adversarial setting, exploiting the fact that the standard ACI update is exactly projected online gradient descent on the pinball loss, we derive simultaneous coverage and efficiency guarantees for arbitrary monotone Lipschitz efficiency objectives, with no distributional or {\it convexity} assumptions. In the stochastic setting with full-score feedback, we propose a sliding-window quantile tracker and establish a matching minimax lower bound showing our algorithm is rate-optimal. In the covariate-dependent stochastic setting, we develop a partitioned ACI algorithm that tracks a function-valued oracle threshold, and derive simultaneous coverage and efficiency guarantees.

Authors: Georgii Kashintsev

Practitioner summary. Do not copy Java's threshold of eight alone: when bins grow long, hybrid-batch (convert after load) still walks lists during insert, while hybrid-incremental (convert as soon as a bin hits k) matches always-tree. Prefer hybrid-incremental or always-tree for overloaded bins; reserve hybrid-batch for pure bulk load then query when chains stay short after resize. Hybrid-incremental approximates Java conversion timing, not a HashMap port. Lead metrics below are strcmp counts and heap - more stable than long-list wall-clock. When individual hash buckets grow long, linked-list separate chaining incurs linear per-bucket cost. We show that when conversion runs (hybrid-batch finalize vs. hybrid-incremental) dwarfs the choice of threshold k for C implementers. Using one C separate-chaining API, we compare policies under uniform-hash FNV (including a fixed-m probe at alpha ~ 122), forced-bucket chaining stress, and a moderate-load same-API scale run (alpha = 16). Under stress, list lookup averages ~31,250 comparisons vs ~15 once treeified; mid-load probes need ~37M comparisons under hybrid-batch vs ~46k under hybrid-incremental; final post-load comparisons converge (~15). Tree buckets use about 1.7x more heap than lists. Stress wall-clock for long lists is illustrative and run-noisy; we therefore headline comparisons and memory. Replaying real trigram posting-list lengths through the same policies yields the same ranking. At alpha ~ 122 without resize, some tree wins are really deferred rehash - resize first when m is simply too small.