Theory of Computing Report

One of the most popular posts in this blog’s history was Common Knowledge and Aumann’s Agreement Theorem, based on a lecture that I gave to high-school students 11 years ago. One of the impacts of that post, I’m proud to say, is that (according to Steven Pinker) it helped to inspire Steve’s excellent recent popular book, which you should read, entitled What Everyone Knows That Everyone Knows…: Common Knowledge and the Mysteries of Money, Power, and Everyday Life.

Two weeks ago, I was privileged to attend a workshop in Paris on “50 Years of Agreeing to Disagree,” where (among other things) I got to meet the 96-year-old Economics Nobel Laureate Robert Aumann for the first time.

I got to catch up there with Steven Pinker as well, who gave a phenomenal talk on the psychology of common knowledge. My own talk was entitled The Complexity of Agreement, with New Directions and Applications (link goes to my PowerPoint slides).

Aran Nayebi has graciously posted on YouTube some partial video from the meeting, including his talk, brief snippets from my talk, and Aumann’s own remarks:

Meanwhile, here were the Aumannian insights that I remembered to write down:

AUDIENCE QUESTION: What questions did people ask you after you published your famous agreement theorem in 1976?

AUMANN: I don’t remember what happened yesterday, let alone 1976.

Also:

ME: I thought you might enjoy knowing that I just came here from a meeting of rationalists…

AUMANN: A meeting of who?

ME: Rationalists, they call themselves, at a beautiful venue called Lighthaven in Berkeley, and that they named the main building there “Aumann Hall” in your honor.

AUMANN: OK, so I’ve made it then.

One reccent result announced at the workshop, for those who care, is that the proof of Aumann’s Theorem has now been formalized in Lean, by Scott Kominers at Harvard and a group from the startup company Axiom Math.

Thanks so much to Christina Katt-Pawlowitsch, Ziv Hellman, and others for organizing the workshop and for including me in it.

Happy to field questions in the comments, although if someone wants to call me an idiot like usual, we’ll just need to agree to disagree!

By Scott

We introduce a new family of propositional proof systems, denoted $\langle EF, R \rangle$, for an arbitrary TFNP search problem $R$. Informally, a refutation of a CNF formula $F$ in $\langle EF, R \rangle$ is given by a polynomial-time mapping reduction from the false-clause search problem ${\mathrm{Search}}_F$ to $R$, combined with an Extended Frege proof that the reduction is correct. These new systems are naturally motivated in two ways: 1. They are the propositional translations of witnessing theorems in bounded arithmetic, by which proofs of $\forall \Sigma^b_1$ formulas $\phi$ in a theory $T$ imply algorithms solving the search problem for $\phi$ in a TFNP subclass corresponding to $T$ [Bus86, KP90, BK94, KST07, BB09]. 2. They form a white-box analogue of the recent characterizations of proof systems using decision tree reductions to black-box TFNP problems [GHJ+22b, BIK+94, DR23, LPR24, FGJ+26, FIM25]. We consider the proof system $\langle EF, Iter \rangle$, where $Iter$ is the complete problem for the classical TFNP subclass PLS. We prove that $\langle EF, Iter \rangle$ is polynomially equivalent to the quantified boolean sequent calculus $G_1$, and also to the implicit Resolution proof system $[EF, Resolution]$ introduced by Krajícek [Kra04]. Hence $G_1$ and $[EF, Resolution]$ are polynomially equivalent, which is the first natural characterization of an implicit proof system by a classical propositional proof system beyond the work of Wang [Wan13]. We further observe our characterization can be extended to capture $G_i$ via the game induction principles of [ST07]. We also calibrate the strength of $\langle EF, R \rangle$ for general TFNP relations $R$. We observe that if Extended Frege can prove that a search problem $R$ is in FP, then $\langle EF, R \rangle$ is polynomially equivalent to $EF$. This contrasts to our above result, which shows that Extended-Frege provable reductions to $Iter$, a problem widely believed not to be in FP, yields a proof system ($G_1$) that is believed to be stronger than Extended Frege. Finally, and somewhat paradoxically, we show that for any proof system $P$ which is sufficiently strong, there is a polynomial-time computable search problem $R_P \in $ FP such that $\langle EF, R_P \rangle$ is polynomially equivalent to $P$. Letting $P = [EF, Resolution]$ and combining our two results shows that $\langle EF, Iter \rangle$ is polynomially equivalent to $\langle EF, R_{[EF, Resolution]} \rangle$. Hence, despite the widely-believed conjecture that $Iter \not \in $ FP, the problems which $EF$-provably reduce to $Iter$ are exactly the problems which $EF$-provably reduce to a fixed polynomial-time computable set.

This post is a map of the lower-bound posts on Decentralized Thoughts. The Start Here page already lists many of these results by topic, and the lowerbound tag lists the posts themselves. Here we turn that list into a chapter: first the main fault-threshold barriers, then communication, round complexity, latency, validity, privacy, and liveness. In distributed computing, an upper bound is often a condition and a protocol for the honest...

By Ittai Abraham

We design a deterministic algorithm that, given blackbox access to the product $f=\prod_{i=1}^{\ell}{h_i}$ of $\ell$ irreducible $s$-sparse $n$-variate polynomials of bounded individual degree $d$, over fields of characteristic zero, and more generally over fields of sufficiently large positive characteristic, recovers the $h_i$'s and their multiplicities in time $\mathrm{poly}(n,(s\ell d)^d)$. For any constant $d>2$, this is the first \emph{polynomial-time} algorithm for this problem, resolving for the bounded-individual-degree regime an open question of Dutta, Sinhababu, and Thierauf (Random 2026). The previous best deterministic algorithm, due to the authors, runs in $\mathrm{poly}(n,d^d,s^{d\log \ell},\ell^d)$ time, which is quasi-polynomial in $\ell$. The improvement is enabled by a new sparse rational interpolation theorem in the bounded-individual-degree setting, based on reconstructing the denominator from its logarithmic derivatives. Given blackbox access to rational functions $a_1/b,\ldots,a_N/b$ where the $a_j$'s and $b$ are $s$-sparse of individual degree at most $d$ with $\gcd(a_1,\ldots,a_N,b)=1$, we recover the $a_j$'s and $b$ in time $\mathrm{poly}(n,d!,s^d,N)$. In contrast to the rational interpolation theorem of Chuyoon-Shpilka (2026), our algorithm reconstructs the denominator directly and does not require a precomputed list of its irreducible factors.

The Hamiltonian Cycle polynomial, denoted as $HC_n$, is defined to be the sum of the weighted Hamiltonian Cycles in an $n$-vertex complete digraph, with vertices labeled $1$ to $n$ and edges weighted by formal variables $x_{i,j}$. The Permanent and $HC$, defined as the family $\{HC_n | \ n \geq 1\}$, were studied by Valiant (STOC 1979), with the former shown to be VNP-complete over all fields of characteristic other than $2$, and the latter to be VNP-complete over every field. Since its introduction, $HC$ has been studied from the perspective of circuit lower bounds by Jerrum-Snir (JACM 1982), determinantal complexity by Huttenhain-Ikenmeyer (LAA 2016), and its connection with the Permanent and the Determinant polynomials by Goulden-Jackson (EJC 1981) and Grochow (ToC 2017). It has been the most prominent choice for generalising results to all fields, such as in Malod (CCC 2007) and Grochow-Mulmuley-Qiao (ICALP 2016), owing to its VNP-completeness over every field. Hrubes (ToCT, 2016) showed the VNP-completeness of many graph-based polynomial families over every field by using $HC$. In Kayal (STOC 2012), a randomised polynomial time algorithm was given for the following problem: Given an $n^2$-variate degree-$n$ polynomial $f(\mathbf{x}) \in \mathbb{F}[\mathbf{x}]$ as a black box, decide if there exists $A \in \mathrm{GL}_{n^2}(\mathbb{F})$ such that $f(\mathbf{x}) = Perm_n(A\mathbf{x})$. Here, the Permanent polynomial $Perm_n$ computes the permanent of the $n \times n$ symbolic matrix $(x_{i,j})$. This problem is known as testing equivalence to the Permanent, or alternatively, ET for Permanent. In this work, we study ET for $HC$. While both families are VNP-complete, the efficient ET algorithm for Permanent does not imply the same for $HC$. Besides, there are crucial differences between the two polynomials that make studying the complexity of ET for $HC$ interesting: The underlying decision problem corresponding to the Permanent is in P (detecting perfect matchings in a bipartite graph), but that for $HC$ (detecting Hamiltonian cycles in a digraph) is NP-complete. The Permanent polynomial is known to be characterised by its symmetries as shown by Mulmuley-Sohoni (SIAM J. Computing, 2001). This property yields an efficient algorithm for the circuit-testing problem for the Permanent, a special case of ET for the Permanent, in which we check whether a given circuit computes the Permanent. In contrast, we show $HC_n$ is not characterised by its symmetries. In this work, we give a randomised polynomial time ET algorithm for $HC$ with mild constraints on the underlying field. The algorithm is obtained by studying and completely characterising the Lie algebra and the symmetries of $HC_n$. We show that, like the Permanent polynomial, the symmetries of $HC_n$ are generated by permutation and scaling matrices over large enough fields. However, we also show that, unlike the Permanent polynomial, $HC_n$ is not characterised by its symmetries. Nevertheless, like the Permanent polynomial, $HC_n$ is downward self-reducible, as shown in Zhang-Bai (TCS 2011), which implies $HC_n$ is characterised by circuit identities and that we can efficiently test whether a given circuit $\mathrm{C}$ computes $HC_n$. We also get a Flip theorem for $HC_n$ as a result of its circuit identities.

We introduce an approach to distinguishing isomorphism types of graphs based on vector spaces of polynomials that are set-wise invariant under permutations (“separating modules,” which are representations of the symmetric group), inspired by the Geometric Complexity Theory approach to separating complexity classes (Mulmuley & Sohoni, SIAM J. Comput., 2001). We characterize the power of this method for distinguishing non-isomorphic graphs under several different complexity measures: - We show that separating modules of "support-degree" $k$ (each monomial touches at most $k$ vertices) are equivalent to the counts of $O(k)$-vertex subgraphs. This is strictly weaker than $O(k)$-dimensional Weisfeiler--Leman (Fürer, ICALP '01). - We show that separating modules of symmetric circuit size $n^{\Theta(k)}$ are equivalent to $\Theta(k)$-WL. This generalizes and strengthens a result of Dawar & Wilsenach (CSL '18; ICALP '20; ACM Trans. Comput. Log., 2022; Theory Comput., 2025): they proved one direction of this equivalence for invariant polynomials; we generalize to separating modules and prove both directions. - When considering only the multiplicities of separating modules (as was proposed in GCT by Mulmuley & Sohoni, ibid., rather than the polynomials themselves), we show that two graphs are separated by multiplicities if and only if their automorphism groups have different cycle indices. The latter result is notable in the analogy with GCT, as it is the only result we are aware of in which the multiplicity approach to separating isomorphism types of objects has been given an "intrinsic" characterization in terms of the objects themselves. We use this to show that for graphs, multiplicity obstructions are stronger than occurrence obstructions. We also connect invariant polynomials to the Graph Reconstruction Conjectures and Forman's “invariants of finite type” (Adv. Math., 2004).

I’ve been hesitating in writing up a blog post about my latest preprint, “Minimum-weight Steiner triangulation of convex polygons requires interior Steiner points” (with my student Zahra Hadizadeh, arXiv:2606.25302, to appear at CCCG) because, despite being a completely concrete two-dimensional construction, its exponential scale makes it difficult to visualize. In the paper we included an illustration using logarithmic coordinates but I didn’t find that entirely satisfactory so I’m trying again in a different way here.

The new paper is about a problem from a much older paper of mine, “Approximating the minimum weight Steiner triangulation” (SODA 1992 and Discrete Comput. Geom. 1994), on “Steiner triangulation”, adding points to a geometric input to reduce the total edge length of a triangulation of the input. The added points are called Steiner points. The old paper proved that one could get within a constant factor of the minimum possible total edge length, for various kinds of inputs including point sets and convex polygons, using a method based on quadtrees. For convex polygons, you do sometimes need to add Steiner points; for instance the trapezoid below is optimally triangulated with one Steiner point (blue) on its long parallel side.

However, in my earlier work I could only find examples of convex polygons whose optimal Steiner points were on the polygon boundary. When that is the case, the “weak dual” of the triangulation (the graph of triangles and their adjacencies with other triangles) forms a tree. This tree structure should make finding the best triangulation with this structure easier, amenable to dynamic programming algorithms, although there are some difficulties with numerics and nonlinear functions that would need to be overcome. In the older paper, I conjectured that interior Steiner points would never be needed and therefore that we could find optimal Steiner triangulations of convex polygons in polynomial time. The result of the new paper is that the conjecture is false: we construct a polygon whose optimal triangulation requires interior Steiner points.

To understand our counterexample, I think it might be helpful to start with a counter-counterexample, showing why it’s not easy to construct counterexamples. More precisely, it’s not possible to have an optimal interior Steiner point with at most six neighbors and a convex neighborhood. If you had a triangulation like that, you could find a better triangulation with fewer Steiner points by contracting the low-degree Steiner point into its closest neighbor.

In the example above, the Steiner point is \(S\) and the closest of its six neighbors is \(A\). Contracting \(AS\) turns the blue shaded triangulation around \(S\) into the red shaded triangulation, replacing the six edges \(SA\), \(SB\), \(SC\), \(SD\), \(SE\), and \(SF\) by the three edges \(AC\), \(AD\), and \(AE\). Each added edge can be shown to be shorter than a pair of removed edges by using the triangle inequality and the assumption that \(A\) is the nearest neighbor to \(S\):

\[AC\le AS+SC\le BS+SC,\] \[AD\le AS+SD,\] \[AE\le AS+SE\le FS+SE.\]

Combining these inequalities gives

\[AC+AD+AE\le (BS+SC)+(AS+SD)+(FS+SE)\]

so the contracted non-Steiner triangulation is shorter than the Steiner triangulation.

This argument breaks down when a Steiner point has seven or more neighbors, because then there aren’t enough removed edges to pair them up and use the triangle inequality. We found our counterexample to the conjecture by looking for neighborhoods for which, instead, contracting the Steiner point to its nearest neighbor produces a worse triangulation. The resulting convex polygon has an approximate kite shape, with exponentially-spaced sequences of vertices along the short sides of the kite (which are rounded slightly to make the result convex). It has 28 vertices, most of which cluster together near the point where the two short sides of the kite meet:

The next image is a close-up of this cluster, scaled by a factor of approximately 40, with the Steiner point (blue) and its incident edges also shown.

Most of the edges incident to the Steiner point extend rightward, so contracting the Steiner point into its nearest neighbor to the left would lengthen these edges. The same contraction would eliminate the three edges connecting the Steiner point to its three nearest neighbors, but those eliminated edges are very short relative to the number of lengthened edges. A numerical calculation shows that, in fact, the Steiner triangulation is better than the triangulation obtained by connecting all vertices to the nearest neighbor of the Steiner point. More strongly, because of the exponential spacing of the points, that turns out to be the optimal non-Steiner triangulation. So for this polygon, there is a Steiner triangulation with an interior point that is better than any non-Steiner triangulation.

That’s not quite enough to disprove the conjecture. The harder part of the paper, extending to multiple pages of appendices, is proving that there is no good Steiner triangulation using only boundary Steiner points. Therefore, the Steiner triangulation with this one interior Steiner point is better than any Steiner triangulation using only boundary Steiner points. It’s (numerically) the optimal triangulation with a single symmetrically placed Steiner point. We didn’t prove that it’s the optimal Steiner triangulation, because (however implausible it might be) there might be some other way of placing interior Steiner points that is even better. But it’s enough to disprove the conjecture, and prove that some convex polygons require interior Steiner points in their minimum-weight Steiner triangulations.

(Discuss on Mastodon)

By David Eppstein

Authors: Fabio F. G. Buono

Impagliazzo's five worlds classify computational assumptions along a single axis, the existence of cryptographic primitives. All five worlds implicitly assume that every party, including the adversary, observes the full input, that the observer is always $O_{top}$. This assumption is so natural that it is never stated. This work makes it explicit and relaxes it by introducing a second, orthogonal axis, the observational axis, defined by the observer hierarchy introduced in previous work. Relaxing the assumption reveals structural phenomena, such as the collapse $P^{O_{prof}} = NP^{O_{prof}} \subset P$, that the five-world framework cannot express. We prove that this collapse holds unconditionally in all five worlds, showing that observational blindness and computational hardness are independent. We define the Observer World $W_O$, classify all world-observer pairs, identify the labeled cells (a)--(d), and introduce a parametric family $W_O^{\varepsilon}$ modelling partial violations of observational invariants. The framework also interfaces with physical information limits, including thermodynamic, quantum, and cosmological bounds.

Authors: Pablo Concha-Vega, Antonin Loubière, Kévin Perrot

Determining whether predicting two-dimensional sandpiles lies in $\mathbf{NC}$ or is $\mathbf{P}$-complete has been open for decades. Moore and Nilsson proved $\mathbf{P}$-completeness for the three dimensional case by encoding Boolean circuits into sandpiles, but this method fails in two dimension due to the impossibility of crossing gates. In this work, we study the existence of crossing gates on non-uniform and weighted grids. We establish an equivalence between uniform weighted crossing gates and a class of simple non-uniform crossing gates, which we call primal. We also exhibit a crossing gate that inherently requires more than one crossing, rather than a single crossing as in standard constructions. Finally, we show that the equivalence between uniform weighted and primal crossings breaks down in more general settings.

Authors: Tomoyuki Yamakami

In the past literature, families of two-way finite automata and pushdown automata having limited state complexity (i.e., the total number of inner states) and stack-state complexity (i.e., the total number of inner states multiplied by the total number of strings "pushable" to a stack), have been studied in direct connection to (mainstream) space-bounded complexity classes equipped with Karp-Lipton style advice of limited size when all inputs given to the automata have bounded length. Here, we acknowledge two major factors -- size and ceiling -- of such families, which have a significant impact on the complexity of finite and pushdown automata families, where the "size" refers to (stack-)state complexity and the "ceiling" refers to an input's length bound. In this line of study, we further explore those effects caused by different sizes and ceilings.

Authors: Agrim Dewan

The Hamiltonian Cycle polynomial, denoted as $HC_n$, is defined to be the sum of the weighted Hamiltonian Cycles in an $n$-vertex complete digraph, with vertices labeled $1$ to $n$ and edges weighted by formal variables $x_{i,j}$. Valiant (STOC 1979) studied the Permanent and $HC$, defined as the family $\{HC_n | \ n \geq 1\}$, and showed both families are VNP-complete, the former over any field of characteristic other than $2$, and the latter over any field. Since its introduction, $HC$ has been studied from the perspective of lower bounds by Jerrum-Snir (JACM 1982), determinantal complexity by Huttenhain-Ikenmeyer (LAA 2016), and its relation to the Permanent by Goulden-Jackson (EJC 1981) and Grochow (ToC 2017). Its VNP-completeness over any field has been used in Malod (CCC 2007), Grochow-Mulmuley-Qiao (ICALP 2016) and Hrubes (ToCT, 2016). The Equivalence Testing problem for a polynomial $f(\mathbf{x})$ (ET for $f$) is as follows: Given $g(\mathbf{x}) \in \mathbb{F}[\mathbf{x}]$ as a black box, decide if there exists $A \in \mathrm{GL}_{|\mathbf{x}|}(\mathbb{F})$ such that $g = f(A\mathbf{x})$. Kayal (STOC 2012) gave a randomised polynomial time ET algorithm for the Permanent. In this work, we give a randomised polynomial time ET algorithm for $HC$ with mild constraints on the field. We show that, like the Permanent polynomial, the symmetries of $HC_n$ are generated by permutation and scaling matrices over large enough fields. We also show that $HC_n$ is not characterised by its symmetries, unlike the Permanent polynomial, Mulmuley-Sohoni (SIAM J. Computing, 2001). Nevertheless, like the Permanent polynomial, $HC_n$ is downward self-reducible, Zhang-Bai (TCS 2011), implying $HC_n$ is characterised by circuit identities and an efficient algorithm to test if a given circuit $\mathrm{C}$ computes $HC_n$. We also get a Flip theorem for $HC_n$ as a result of its circuit identities.

Authors: Kuize Zhang

In this paper, we formulate a scenario that an agent can never be sure that another agent can uniquely determine the state of a finite-state automaton based on its observations to the automaton at the current and any past time as the property of order-2 bygone-state opacity. Based on our concurrent composition and the classical observer, we derive a tool to verify this property in doubly exponential time. The interest of this result lies in that we extend inference of finite automata from a single agent to two ordered agents.

Authors: Somnath Bhattacharjee, Rishabh Kothary, Shanthanu S. Rai, Shubhangi Saraf

We study factoring algorithms for general sparse polynomials and sparse polynomials of bounded individual degree and prove the following results. 1. We give a deterministic polynomial-time algorithm which takes as input an $n$-variate $s$-sparse polynomial $f$ of bounded individual degree $d$ and outputs a list of circuits which contains all factors of $f$, although there might be additional spurious circuits in the list. The algorithm runs in time $\operatorname{poly}(n, s^d)$. Additionally, every circuit in the list has constant depth. Our algorithm works over all fields of characteristic 0 or sufficiently large characteristic. Our result generalizes a recent result of Chuyoon and Shpilka that gives a $\operatorname{poly}(n, s^d)$-time algorithm for recovering all sparse factors of $f$ (without spurious factors). As a corollary, we can also recover all factors of $f$ in time $\operatorname{poly}(n, s^{d^2 \log n})$, and recover the algorithmic result of Bhargava, Saraf and Volkovich and its improvement by Chuyoon and Shpilka. Both the above consequences follow from known interpolation and divisibility testing techniques. 2. We give a deterministic quasipolynomial-time algorithm which takes as input a general $n$-variate $s$-sparse polynomial $f$ of (unbounded) individual degree $D$ and outputs a list of polynomials which contains all factors of $f$ that have bounded individual degree $d$. The algorithm runs in time $\operatorname{poly}(D^{d \log s}, s^{d^2 \log n})$ and works over arbitrary fields. The list may again contain spurious elements. Our result strengthens results of Dutta, Sinhababu and Thierauf and Kumar, Ramanathan and Saptharishi which give algorithms to recover all factors of $f$ of bounded total degree. A consequence of our algorithm is a new upper bound on the total number of bounded individual degree factors of a sparse polynomial.

Authors: Ioannis Nasios

This paper presents solarsystem, a validated lightweight and dependency-free Python package for planetary positions and solar-lunar event calculations. The package provides heliocentric and geocentric positions for the major planets, selected dwarf planets, the Centaur Chiron, and the Moon, together with sunrise, sunset, moonrise, moonset, and lunar illumination calculations. Additional functionality includes coordinate transformations between commonly used astronomical reference systems. The implemented algorithms employ analytical models that avoid reliance on external ephemeris datasets, resulting in a portable and computationally efficient solution suitable for a broad range of astronomical applications. An optional precession correction model is included, enabling calculations either in a precession-corrected reference frame or in a fixed epoch framework, depending on user requirements. The numerical performance of solarsystem was evaluated against the JPL DE440 planetary ephemerides using the Skyfield framework as a reference. Validation experiments spanning multiple bodies and extended temporal intervals demonstrate good agreement with the reference ephemerides, with mean planetary longitude and latitude deviations of approximately 0.44 and 0.16 arcminutes, respectively. Additional validation of solar and lunar event calculations yielded timing differences of only a few minutes relative to the reference solutions, while lunar illumination estimates differed by approximately 0.2%. The package can be installed directly through PyPI while the source code, documentation, validation notebooks and example workflows are publicly available through the project repository in https://github.com/IoannisNasios/solarsystem.

Authors: Jayanta Pari, Pratibha Bhandari, Soumyendu Raha

Community detection is a key task in network analysis, providing insight into the structural organization of complex systems. Effective resistance, a graph-theoretic metric derived from electrical network theory, has emerged as a powerful tool for evaluating connectivity and influence within networks. This paper proposes an effective resistance-based community detection algorithm that calculates the similarity between nodes using effective resistance values and produces a weighted graph. The sparse graph used in the algorithm is generated after computing the minimum spanning tree (MST) of the weighted graph and adopting a threshold sparsification strategy on non-MST edges. A maximum modularity approach is adopted using the Clauset-Newman-Moore algorithm on the resultant sparse graph. This algorithm is evaluated for both synthetic and real-world networks, demonstrating its effectiveness compared to popular existing methods. The result shows that the effective resistance-based approach accurately captures the structures of the community while maintaining computational efficiency.

Authors: Michael T. M. Emmerich

Selecting a fixed number of representative points from a finite Pareto-front approximation is a fundamental post-processing task in multiobjective optimization. This paper studies this problem for the integral R2 indicator in three objectives, where the indicator is defined as the integral of the lower envelope of weighted Tchebycheff scalarizations over the two-dimensional weight simplex. We provide two complementary algorithmic results. On the positive side, we show that the integral R2 improvement with respect to any fixed baseline is a monotone submodular set function. For the usual ideal-point based R2 indicator, with the ideal point fixed, this yields a direct gap-reduction guarantee: greedy selection closes at least a $(1-1/e)$-fraction of the maximum possible R2 gap between a fixed dominated anchor value and the best cardinality-$k$ value. We also give a tested greedy implementation that evaluates exact integral R2 values by subdivision, with worst-case running time $O(n^6)$. On the negative side, we prove that exact fixed-cardinality subset selection is NP-hard already in three objectives. The hardness proof uses a perspective transformation that maps Tchebycheff-shadow improvements to a weighted anchored-box union problem with density $(x_1+x_2+x_3)^{-4}$, and then adapts the three-dimensional anchored-box construction of Bringmann, Cabello, and Emmerich. Together, these results separate the tractable two-objective case from the three-objective case while identifying a principled approximation route based on submodular optimization.

Authors: Luoning Zhang, Xu Zhuang, Tianhao Wang, Nathan Kaplan

We study certain extremal problems in combinatorial geometry that ask about configurations of points in an $n \times n$ grid that satisfy strict, global geometric constraints. Classical exact solvers suffer from combinatorial explosion for these types of problems, and standard reinforcement learning and transformer-based models struggle with the sparse reward "validity cliff" and quadratic token-consumption limits. To overcome these bottlenecks, we propose a Geometry-Aware Monte Carlo Tree Search (MCTS) framework. Our approach strictly enforces geometric constraints through incremental updates to the feasible action space. For constraints about collections of collinear points, like those that occur in the classic No-Three-in-Line problem (Max-N3IL), this mechanism reduces the constraint checking complexity from $O(n^3)$ to $O(n^2)$. To improve search efficiency, we exploit geometric symmetries in two ways: canonical pruning during node expansion to reduce the branching factor, and symmetric batch transitions to accelerate the discovery of promising configurations. We perform extensive experiments and establish new best-known computational results on five out of six of the problems that we considered. Notably, for Max-N3IL we find configurations of size roughly $1.8 n$ for grids of size $82 \le n \le 119$. For the Smallest Complete Set problem, we find configurations of size roughly $0.95 n$, providing new upper bounds within the tested grids. This work establishes Geometry-Aware MCTS as a highly adaptable framework for discovering novel configurations in combinatorial geometry.

Authors: Weining Zhu

As a type of spatial tessellation model and an important spatial structure of computational geometry, Voronoi diagrams (VDs) are widely used in many fields. Due to differences in generation spaces, types of spatial entities, distance metrics, and relationships between entities and Voronoi regions, Voronoi diagrams vary into many types, such as the ordinary VD, VD on spheres, VD for linear entities, weighted VD, and ordered higher-order VD. These VDs also have their own generation algorithms. In this study, we propose a new cell-merge (CM) Voronoi generation algorithm based on the spatial chromatic model. The advantage of the CM algorithm is that it can quickly generate diverse VDs by retrieving and merging cells from a unified database, without requiring the development of specific algorithms for each VD. The CM Voronoi algorithm can be particularly applied in cases where a variety of Voronoi diagrams are frequently required for computation and analysis, such as in location-based spatial analysis. Furthermore, the proposed CM method can also generate some new types of spatial tessellations, such as competition intensity and couple-cell diagrams which are different from classical VDs.

Authors: Joshua A. Grochow, Jacob Urisman

We introduce an approach to distinguishing isomorphism types of graphs based on vector spaces of polynomials that are set-wise invariant under permutations ("separating modules," which are representations of the symmetric group), inspired by the Geometric Complexity Theory approach to separating complexity classes (Mulmuley & Sohoni, SIAM J. Comput., 2001). We characterize the power of this method for distinguishing non-isomorphic graphs under several different complexity measures: - We show that separating modules of "support-degree" $k$ (each monomial touches at most $k$ vertices) are equivalent to the counts of $O(k)$-vertex subgraphs. This is strictly weaker than $O(k)$-dimensional Weisfeiler--Leman (Fürer, ICALP '01). - We show that separating modules of symmetric circuit size $n^{Θ(k)}$ are equivalent to $Θ(k)$-WL. This generalizes and strengthens a result of Dawar & Wilsenach (CSL '18; ICALP '20; ACM Trans. Comput. Log., 2022; Theory Comput., 2025): they proved one direction of this equivalence for invariant polynomials; we generalize to separating modules and prove both directions. - When considering only the multiplicities of separating modules (as was proposed in GCT by Mulmuley & Sohoni, ibid., rather than the polynomials themselves), we show that two graphs are separated by multiplicities if and only if their automorphism groups have different cycle indices. The latter result is notable in the analogy with GCT, as it is the only result we are aware of in which the multiplicity approach to separating isomorphism types of objects has been given an "intrinsic" characterization in terms of the objects themselves. We use this to show that for graphs, multiplicity obstructions are stronger than occurrence obstructions. We also connect invariant polynomials to the Graph Reconstruction Conjectures and Forman's "invariants of finite type" (Adv. Math., 2004).

Authors: Akitoshi Kawamura

In the pinwheel scheduling problem, each task $i$ is associated with a positive integer $a_i$ called its period, and we want to (perpetually) schedule one task per day so that each task $i$ is performed at least once every $a_i$ days. An obvious necessary condition for schedulability is that the density, defined as the sum of execution rates $1/a_i$, does not exceed $1$. We prove that all instances with density not exceeding $5/6$ are schedulable, as was conjectured by Chan and Chin in 1993. Like some of the known partial progress towards the conjecture, our proof involves computer search for schedules for a large but finite set of instances. A key idea in our reduction to these finite cases is to generalize the problem to fractional (non-integer) periods in an appropriate way. As byproducts of our ideas, we obtain a simple proof that every instance with two distinct periods and density at most $1$ is schedulable, as well as a fast algorithm for the bamboo garden trimming problem with approximation ratio $4/3$.

Authors: Helin Wang, Chenyi Zhang, Xiwen Tao, Yexin Zhang, Tongyang Li

We study the problem of finding stationary points of non-convex functions when access to the objective is provided only through a comparison oracle that, given two points, outputs which has the larger function value. For a twice differentiable $f\colon\mathbb R^n\to\mathbb R$ with Lipschitz gradient and Hessian, we develop an algorithm that visits an $ε$-stationary point using $\widetilde O(n^2/ε^{1.5})$ queries. Our approach uses a subroutine that estimates the normalized Hessian to accuracy $δ$ using $\widetilde O(n^2\log(1/δ))$ queries. We further study this problem with a quantum comparison oracle model where queries can be made in superpositions, and develop the first quantum algorithm that finds an $ε$-stationary point, which takes $\widetilde O(n/ε^{1.5})$ queries.

Authors: Kan Shota, Kazuya Haraguchi

In network vulnerability analysis, it is crucial to evaluate the robustness of $k$-cores against vertex removals. A $k$-core is often fragile since removing a few vertices can trigger a large reduction in the core size, a phenomenon known as core collapse. In this paper, we study the problem of enumerating all minimal removable sets (MinRSs) of a given $k$-core, where a MinRS is a minimal nonempty set of vertices whose removal results in a smaller $k$-core graph. We consider this problem within a general mathematical framework based on monotone systems. We show that, for a monotone system that is given with an underlying graph $G=(V,E)$, all MinRSs of a solution can be enumerated in $O((n+m)nτ_ω)$ time, where $n=|V|$, $m=|E|$ and $τ_ω$ denotes the computation time of evaluating the monotone function of the system. Furthermore, if the system satisfies the newly defined in-dominating seed property, the complexity drops to $O((n+m) \log n \cdot τ_ω)$ time. We prove that standard $k$-cores in undirected graphs satisfy this property, enabling MinRS enumeration in $O((n+m)\log n)$ time, a significant improvement over the baseline. We also extend our framework to enumerate all solutions in a given monotone system. This yields an $O((n+m)\log n)$-delay algorithm for all $k$-core subgraphs, outperforming an algorithm given by [Boley et al., Theoretical Computer Science, 2010]. Our framework is applicable to various $k$-core extensions, including weighted $k$-cores, multi-layer $\boldsymbol{k}$-cores, and $(k,\ell)$-cores.

Authors: Barna Saha, Yinzhan Xu, Christopher Ye

Given a graph, computing distances and reachabilities from a small set of vertices to the whole graph is an important primitive both in theory and in practice. In undirected unweighted graphs, while computing single-source shortest path (SSSP) requires $O(n^2)$ time in dense graphs, all-pairs shortest paths (APSP) can be computed in $\hat{O}(n^ω) = O(n^{2.372})$ time [Seidel '95] providing significant savings over running $n$ SSSP instances separately. However, if one needs to compute multiple-source shortest paths (MSSP) from a set of $n^σ$ vertices, the previously best known running time was $\hat{O}(\min\{n^ω, n^{2 + σ}\})$: either compute APSP or run SSSP from each source. On the other hand, MSSP is only as hard as computing Boolean matrix product (BMM) between an $n^σ\times n$ matrix and $n \times n$ matrix, leaving a significant gap. Our first main result is an almost optimal algorithm for MSSP on undirected unweighted graphs running in $\hat{O}(n^{ω(σ, 1, 1)})$ time, which gives a smooth interpolation between the SSSP and APSP algorithms. The main technical tool behind our result is a novel graph decomposition, which may be of independent interest. Next, we study the multiple-source reachability problem, where we need to determine whether a given set of $n^σ$ vertices can reach each of the vertices in a given directed graph. Multiple-source reachability can also be solved in $\hat{O}(\min\{n^ω, n^{2 + σ}\})$ time, with the same lower bound from rectangular BMM. We give an optimal algorithm that runs in $\hat{O}(n^{ω(σ, 1, 1)})$ time, again matching the running time for BMM. Our algorithm for multiple-source reachability can be generalized to MSSP on DAGs. As an application, we provide an $O(n^{2.084})$ time algorithm for computing an $\widetilde{O}(n)$-size shortcut set that reduces diameter to $O(n^{1/3})$.

Authors: Beaudou Laurent, Foucaud Florent, Lorieau Lucas, Tale Prafullkumar

In DIRECTED GEODETIC SET, we are given a (directed) graph and seek a small solution set $S \subseteq V(G)$ such that every vertex lies on a shortest directed path between two vertices in $S$. It is known that the problem is W[2]-hard when parameterized by the solution size $k$, even on directed acyclic graphs (DAGs). Our first result is a kernel of size $2^{O(vcn)}$ for DIRECTED GEODETIC SET on general digraphs, where $vcn$ denotes the vertex cover number of the underlying (undirected) graph. This implies an algorithm running in time $2^{O(vcn^2)} \cdot n^{O(1)}$. Furthermore, we prove that, assuming the ETH, the problem does not admit an algorithm running in time $2^{o(vcn^2)} \cdot n^{O(1)}$. Next, we show that on general digraphs, DIRECTED GEODETIC SET admits a natural kernel of size $(kΔ)^{O(rdiam)}$, where $Δ$ is the maximum degree and $rdiam$ denotes the reachability diameter of the digraph (a natural analogue of diameter of undirected graphs). This yields an algorithm running in time $(kΔ)^{O(rdiam \cdot k)}\cdot n^{O(1)}$. We further prove that, assuming the ETH, the problem does not admit an algorithm running in time $(kΔ)^{o(rdiam \cdot k)} \cdot n^{O(1)}$. Finally, we justify the necessity of combining parameters by establishing the following hardness results for DIRECTED GEODETIC SET: - It is W[2]-hard parameterized by $k$, even on digraphs of maximum degree 3. - It is para-NP-hard parameterized by maximum degree and reachability diameter. One can infer that the problem remains W[2]-hard when parameterized by k, even on graphs of reachability diameter 3 from Araújo and Arraes [DAM 2022]. All our conditional lower bounds and hardness results hold even when the input digraph is restricted to be a DAG.

Authors: Haitong Liu, Deepak Narayanan Sridharan, David Steurer, Manuel Wiedmer

We study the fundamental problem of learning a high-dimensional Gaussian truncated to an unknown halfspace. Lee, Mehrotra and Zampetakis (FOCS'24) recently obtained the first polynomial time algorithm for this problem, but their resulting sample and time complexity bounds are not optimal. Under non-trivial truncation, for any target accuracy $\varepsilon > 0$ and dimension $d$ we give an efficient algorithm that uses $n = \tilde{O}(d^2/\varepsilon^2)$ samples and learns the underlying Gaussian to error $\varepsilon$ in total variation distance. Our algorithm is also fast: its runtime is dominated by the cost of computing the empirical covariance matrix. Both our sample and time complexity are optimal in terms of $d$ and $\varepsilon$ even without truncation: in this regard, we can learn a Gaussian under halfspace truncation for free. The key ingredient behind our result is a novel reinterpretation of the low-degree moments of the truncated Gaussian in terms of a relative truncation parameter. This relative truncation parameter uniquely determines the parameters of the untruncated Gaussian and enables direct parameter recovery. This reinterpretation allows us to circumvent the time intensive projected stochastic gradient descent procedure that is widely used in learning under truncation.

We study factoring algorithms for general sparse polynomials and sparse polynomials of bounded individual degree and prove the following results. 1. We give a deterministic polynomial-time algorithm which takes as input an $n$-variate $s$-sparse polynomial $f$ of bounded individual degree $d$ and outputs a list of circuits which contains all factors of $f$, although there might be additional spurious circuits in the list. The algorithm runs in time ${poly}(n, s^d)$. Additionally, we can ensure that every circuit in the list has constant depth. Our algorithm works over all fields of characteristic 0 or sufficiently large characteristic. Our result generalizes a recent result of Chuyoon and Shpilka that gives a ${poly}(n, s^d)$-time algorithm for recovering all sparse factors of $f$ (without spurious factors). As a corollary, we can also recover all factors of $f$ (without spurious factors) in time ${poly}(n, s^{d^2 \log n})$, and recover the algorithmic result of Bhargava, Saraf and Volkovich and its improvement by Chuyoon and Shpilka. Both the above consequences follow from known interpolation and divisibility testing techniques. 2. We give a deterministic quasipolynomial-time algorithm which takes as input a general $n$-variate $s$-sparse polynomial $f$ of (unbounded) individual degree $D$ and outputs a list of polynomials which contains all factors of $f$ that have bounded individual degree $d$. The algorithm runs in time ${poly}(D^{d \log s}, s^{d^2 \log n})$ and works over arbitrary fields. The list may again contain spurious elements. Our result strengthens results of Dutta, Sinhababu and Thierauf and Kumar, Ramanathan and Saptharishi which give algorithms to recover all factors of $f$ of bounded total degree. A consequence of our algorithm is a new upper bound on the total number of bounded individual degree factors of a sparse polynomial.

When you start thinking deeply about a mathematics problem you may enter the "zone", a period of intense focus where you think solely about the problem and potential solutions, and more importantly block out all other thoughts and even lose track of time. Mathematicians don't own the zone, actors, musicians, athletes and many others have their own version of the zone. But for math, when working on an open problem, you have no idea how difficult a solution may be, or if a solution exists at all. Most of the time you will fail (if not you need to try harder problems). Failure is not wasted time. You may find a counterexample, a partial solution and always you will come out with a better understanding of the problem. Then days, months or years later, some new proof idea comes from a paper, a talk or just the back of your head, and back in the zone you go. And when you do succeed you get a feeling not unlike scoring a goal in a soccer game. You should see my proof dance.

With AI generated and assisted proofs, we may think of outsourcing the zone to ChatGPT and Claude. We may prove more and stronger theorems, but you'll understand the results just a little bit less and mathematics will become a little less fun. 

By Lance Fortnow

Authors: Nikita Gaevoy

Resolution with symmetries is a natural extension of the Resolution proof system that allows to use symmetries of the formula to simplify the proof. Symmetries can be global (applied to the whole input formula), local (applied to a subformula), or dynamic (applied to newly derived clauses as well). The framework of Resolution with (global) symmetries was introduced by Krishnamurthy (1985) and further extended by Arai and Urquhart (2000) to local symmetries. Later, Szeider (2005) generalized this approach to homomorphisms and introduced the notion of Resolution with dynamic symmetries. While proving superpolynomial proof-size lower bounds for Resolution with dynamic symmetries remains an open problem already for two decades, the power of proof systems with global and local symmetries is well studied: exponential lower bounds have been proven for these proof systems, as well as exponential separations between all of them. However, these systems are too general to reflect practical applications since it is computationally too hard to find and efficiently exploit arbitrary symmetries. In this work, we introduce the notion of small symmetries: symmetries that can operate on a limited number of variables at the same time. Resolution with small symmetries gives hopes both for practical applications and for theoretical study of dynamic symmetries. We show that proof systems with both local and global small symmetries form strict hierarchies w.r.t. the size of symmetries. We prove exponential separations between proof systems with symmetries of different sizes and types. It turns out that even lower levels of these hierarchies are exponentially separated from Resolution and stronger proof systems, such as constant-depth Frege. As a byproduct of our constructions, we obtain an exponential separation between the classical systems SRCI and SRII that was not known before.

Authors: Marcel K. Goh, Hamed Hatami

We construct a point-line incidence problem over the reals whose randomized communication complexity is constant, but whose deterministic communication complexity is linear even when the players have access to an equality oracle. This is the strongest possible separation between these two measures, and it improves on an earlier $O(1)$-versus-$Ω(\sqrt{n})$ separation of Göös, Harms, and Riazanov. Because point-line incidence problems have constant sign rank, our construction also bears on a question of Harms and Zamaraev, who asked whether constant sign rank together with constant randomized communication complexity forces constant equality-oracle complexity. This was already refuted by Göös, Harms, Imbach, and Sokolov with a logarithmic lower bound; our example improves the separation to linear, which is optimal. The proof draws on a construction in the recent disproof of the sum-product conjecture over the reals by Bloom, Sawin, Schildkraut, and Zhelezov, using totally real number fields of large degree and small discriminant.

Authors: Peter Bürgisser

We study the logical relation of the P-NP separation conjecture in the Blum-Shub-Smale-model over the complex numbers with the P-NP separation conjecture in Valiant's algebraic model. This amounts to comparing Hilbert's Nullstellensatz Problem, that is, deciding feasibility of a given system of polynomial equations over the complex numbers, with the problem of evaluating the permanent of a given complex matrix. We compare the respective uniform models of computations and prove that $P_C\ne NP_C$ in the Blum-Shub-Smale-model over $C$ implies the separation $VP^0(u)\ne VNP^0(u)$ of the uniform versions of Valiant's constant-free complexity classes over $C$. For the nonuniform models we show the analogous implication: the separation $P^0_C(nu)\ne NP^0_C(nu)$ of the nonuniform, constant-free Blum-Shub-Smale classes over $C$ implies the separation $VP^0\ne VNP^0$ of Valiant's constant-free complexity classes over $C$. In the reverse direction, we conjecture that $VNP_C\not\subseteq\overline{VP}_C$ implies that $P_C(nu)\ne NP_C(nu)$.

Authors: Nikolas Gärtner, Victor Magron, Frank Vallentin

In this paper, we analyze the bit complexity of deciding whether a given polynomial can be represented as a sum of squares of polynomials. We show that the weak membership problem for the sum-of-squares cone lies in $\mathrm{P}$. Furthermore, we give a polynomial-time algorithm which computes, for a given polynomial and positive parameter $ε$, an $ε$-relaxed closest sum-of-squares polynomial.

Authors: Qisheng Wang

We consider the problem of estimating the fidelity of an unknown quantum state to a known reference state to within additive error $\varepsilon$. We show that the sample complexity is $O(r^2/\varepsilon^2)$ with optimal $\varepsilon$-dependence when the reference state is of rank $r$, improving the previous best $O(r^2\log^2(1/\varepsilon)/\varepsilon^4)$ due to Utsumi, Nakata, Wang, and Takagi (QIP 2026). We also provide a lower bound of $Ω(r/\varepsilon^2)$, improving the previous best $Ω(r/\varepsilon+1/\varepsilon^2)$, with implications to quantum query complexity. Moreover, we further consider the case where the unknown state is of rank at most $r$ while the reference state can be arbitrary, for which the sample complexity is shown to be $O(r^2/\varepsilon^4)$. As an application, we present an approach to tolerant quantum state certification, generalizing the exact certification studied in Bădescu, O'Donnell, and Wright (STOC 2019).

Authors: Barna Saha, Yinzhan Xu, Christopher Ye

Several fundamental problems in computational geometry admit algorithms with running time $f(d) \cdot n^{2-Θ(1/d)}$ for $n$ points in $d$ dimensions, making them among the most prominent examples of barely subquadratic computation. Notable members of this class include Furthest Pair, Bichromatic Closest Pair, (Bichromatic) Maximum Innter Product, and Hopcroft's Problem. Chen [Theory Comput. 2020] proved that, assuming the Strong Exponential Time Hypothesis (SETH), these problems require $n^{2-o(1)}$ time when the dimension satisfies $d=2^{Θ(\log^* n)}$. We extend this lower bound to all efficiently constructible dimensions $d=ω(1)$. Thus, assuming SETH, the dependence of the best known algorithms on the dimension is essentially unavoidable. The proof utilizes techniques in OpenAI's recent disproof of the Erdos unit distance conjecture. The proof was initially discovered by ChatGPT 5.5 Pro. The authors have validated and substantially edited the proof to improve the presentation.

Authors: Raphaël Tinarrage

We analyze the decrease of simplex diameters under iterated refinement of spherical Delaunay complexes. Unlike in ordinary subdivision, the refined Delaunay complex need not be a subdivision of the previous one, so mesh contraction is not automatic. We derive explicit contraction bounds for several families of Steiner points, including Delaunay analogues of barycentric and edgewise subdivision. The proof reduces the problem to sharp covering estimates for Euclidean simplices. These estimates are obtained through a strengthening of Maurey's empirical method via pivotal sampling and a dimension-dependent version of the approximate Carathéodory theorem. Theoretical results and numerical experiments show that Delaunay refinements achieve stronger contraction than their subdivision counterparts.

Authors: David Eppstein, Zahra Hadizadeh

We construct a convex polygon for which the minimum-weight Steiner triangulation requires an interior Steiner point. This provides a counterexample to a 1994 conjecture of Eppstein that minimum-weight Steiner triangulation of convex polygons needs only Steiner points on the boundary of the polygon.

Authors: Satoshi Kanno, Yoshi-aki Shimada

Topological information is widely used in data analysis, network design, and machine learning, and topological constraints naturally arise when optimizing or generating objects with prescribed homological structure. However, directly controlling Betti numbers and persistent homology is difficult because they are discrete and combinatorial. We propose a differentiable framework for topology-constrained optimization based on Hodge-spectral relaxations of homological constraints and low-pass spectral filters. From soft graphs and soft clique complexes, we construct Hodge-Laplacian-type spectral relaxations that unify graph clique complexes and Vietoris--Rips filtrations of point clouds. In the hard limit, the penalty-regularized ambient operator recovers the ordinary Hodge Laplacian on the active subcomplex, while in the soft regime it serves as a differentiable low-frequency spectral surrogate. Homological information is represented by zero and near-zero modes, and differentiable topological objectives are defined using heat filters, resolvent filters, and polynomial Laplacian moments. For point clouds, we show that the proposed Hodge spectral-filter losses yield more spatially distributed gradients, smoother scale-normalized behavior under persistence-pairing changes, and geometry-aware update directions than persistent-homology-based losses. For graph clique complexes, Laplacian moments control normalized first-Betti-type quantities and can be combined with ordinary graph-feature objectives. We also discuss connections to trace-based normalized Betti-number estimation, polynomial spectral methods, and possible quantum trace estimation.

Authors: Anna Brötzner, Omrit Filtser, Bengt J. Nilsson, Christian Rieck, Christiane Schmidt

Motivated by applications for robust guarding, we consider a variant of the multiple-watchmen problem that ensures that every point within a polygon $P$ is seen from more than one direction: we search for two routes $W_1,W_2$, such that every point $p\in P$ is contained in a segment $\overline{w_1w_2}\subseteq P$ such that $w_1\in W_1$ and $w_2\in W_2$. We call such routes segment watchman routes. We show that finding the two routes that are optimal with respect to the min-max criterion is weakly NP-hard even in simple polygons, and that finding the routes that are optimal with respect to the min-sum criterion is NP-hard in polygons with holes. Moreover, we present sufficient conditions for routes to be segment watchman routes, and provide a polynomial-time $2$-approximation under both the min-max criterion and the min-sum criterion, both in simple polygons. Finally, we show how to generalize our results for $k$ watchmen.

Authors: Yuanhao Wang, Wei Wang

Let $n$ and $p$ denote the numbers of vertices and labels, respectively, in an undirected edge-labeled graph. Previous work showed that, under the Exponential Time Hypothesis (ETH), there is no deterministic algorithm with running time \[ (np)^{o\left(\frac{\log n}{(\log\log n)^2}\right)}. \] In this paper, we give a deterministic reduction that strengthens this conditional running-time lower bound to \[ (np)^{o\left(\frac{\log n}{\log\log n}\right)}. \]

Authors: Thekla Hamm, Bart M. P. Jansen, Faezeh Motiei

We study generalizations of the Steiner Tree problem motivated by the design of power networks. While Steiner Tree asks for a single minimum-cost tree connecting given terminal vertices, a power network typically consists of multiple trees, each connecting a subset of the terminals, to avoid electrical overloads. The cost of installing depends on both the cable lengths and the cost of digging underground trenches for putting the cables where the digging costs can be shared. These leads to variants of Steiner Tree where the goal is to compute a minimum-cost set of Steiner trees with a common root, that together connect all terminals while balancing the power demand of the terminals in each tree. Two important variants arise depending on whether the network is intended for low-voltage or high-voltage power. In the low-voltage case, power loss imposes a bound on the maximum depth of each tree, while no such restriction applies in the high-voltage case. We study the parameterized complexity of several power network design problems, parameterized by the number of terminals. While Steiner Tree is fixed-parameter tractable under this parameterization, most of our variants are W[1]-hard. For low-voltage networks, we present an XP-algorithm for planar inputs based on structural bounds on the treewidth of solution subgraphs. We also give a reduction from Grid Tiling showing tightness under ETH. The XP-algorithm extends to the high-voltage setting and general graphs, albeit at a cost in the running time. For high-voltage networks, we show the problem remains W[1]-hard even on planar graphs. Finally, we explore a variant of the cost model for sharing digging costs in which both problems become fixed-parameter tractable.

Authors: Yu Chen, Zihan Tan

We study the following distance realization problem: given a metric $D$ on a set $T$ of terminals, does there exist an (edge-weighted) outerplanar graph $G$, such that $T\subseteq V(G)$, and for every pair $t,t'\in T$, $\textsf{dist}_G(t,t')=D(t,t')$? We first prove that there is no ``local characterization'', forming a contrast with trees and Okamura-Seymour instances. Our main result is an efficient algorithm for this problem whose running time is polynomial in $|T|$. Both our proof and our algorithm utilize a recent new approach of analyzing graph structures, by viewing graphs as paths and their intersections, which we believe is of independent interest.

Authors: Nicolas Flammarion, Chirag Pabbaraju, Hristo Papazov, Miltiadis Stouras, Ola Svensson

We initiate a resource-aware theory of \textit{language generation in the limit} under the minimal constraint of space efficiency. In our framework, a learner observes an adversarial positive stream from a target language $K$ and must eventually output a hallucination-free hypothesis language $L \subseteq K$ while omitting at most $Δ$ strings of $K$. We focus on $\mathcal{C}_{s,k}$, the collection of languages recognized by DFAs with at most $s$ states over an alphabet of size $k$, as the natural hypothesis class for memory-bounded learners. In the exponential-space regime, we prove that a learner can exactly identify the target $K$. Under a stricter memory budget, we characterize the strongest possible generation guarantees. In particular, we present a streaming algorithm using $\mathrm{poly}(s,k)$ space that converges to a hypothesis with generation gap $Δ= O(k^{2s-2})$. Moreover, the learned hypothesis captures every string in $K$ of length at least $2s-1$. We complement this result with a near-matching lower bound through a reduction from a standard communication complexity problem. Specifically, achieving generation gap $Δ\le k^{(1-\varepsilon)s}$ requires $k^{Ω(\varepsilon s)}$ memory. Together, these results reveal a sharp transition between polynomial-space generation and exponential-space exact identification.

Authors: Shimon Kogan, Merav Parter

The multi-source reachability problem asks to compute the reachable sets from a given subset of source vertices. For $n$-vertex digraphs $G=(V,E)$ and a subset of sources $S \subseteq V$ with $|S|=n^σ$ for some $σ\in [0,1]$, we present a near-optimal deterministic algorithm that solves this problem in $\tilde{O}(n^{ω(σ)})$ time, where $ω(σ)$ is the rectangular matrix multiplication exponent for multiplying an $n^σ\times n$ matrix by an $n \times n$ matrix. For dense graphs, this yields reachability from up to $n^{0.32}$ sources in near-linear time, breaking the super-quadratic time barrier and improving over the state-of-the-art $n^{1+2/3ω(σ)}$-time randomized algorithm of Elkin and Trehan [arXiv:2401.05628, 2024].

Authors: Felix Buld, Andreas S. Schulz

We study scheduling with testing on a single machine and on identical parallel machines to minimize the total \emph{weighted} completion time in the adversarial model. In this setting, each job is equipped with a weight, an upper bound on its processing time, and a testing time. An algorithm can either execute a job for an amount of time equal to the upper bound or test it first to reveal a potentially lower processing time used to schedule the job later. We establish the first constant-competitive algorithms for this problem with job-dependent weights that reflect each job's relative importance. For single-machine scheduling, we present a deterministic algorithm with a competitive ratio of 2.3166 and show that a randomized variant has a competitive ratio of 2.1523. These guarantees match the best-known upper bounds in the unweighted setting. Combining these algorithms with list scheduling yields competitive ratios of 2.7763 and 2.5110 for identical-parallel-machine scheduling, improving the previously best-known bounds even in the unweighted case.

Authors: Jakob Raupach, Tom-Lukas Breitkopf, Anton Herrmann, André Nichterlein

We explore the parameterized complexity of Bounded Density Vertex Deletion (BDVD): given a graph $G$, an integer budget $k$, and a target density $τ_ρ$, the task is to determine whether the density (i.e. number of edges divided by number of vertices) of the densest subgraph of $G$ can be reduced to at most $τ_ρ$ by deleting at most $k$ vertices. Our primary focus is on structural graph parameters related to treewidth, as the parameterized complexity of BDVD with respect to treewidth was left as open question by Bazgan et al. [JCSS, 2025]. We resolve this question by showing W[1]-hardness with respect to various parameters, including treedepth and feedback vertex number. These results imply W[1]-hardness with respect to treewidth. We obtain positive results for parameters larger than treedepth and feedback vertex number, namely we show BDVD is in FPT parameterized by the max leaf number or vertex integrity. Under the assumption that the target density $τ_ρ$ is a fixed constant the parameterized complexity landscape of BDVD changes drastically, allowing a fixed-parameter tractable algorithm even for parameters smaller than treewidth, namely cliquewidth. Altogether, our results provide a refined complexity landscape for Bounded Density Vertex Deletion, sharply distinguishing between tractable and intractable parameter regimes under structural parameterizations.

We study depth-$5$ algebraic circuits over small finite fields with restricted fan-in of the top product gates. We show that there exists an explicit degree-$d$ polynomial $P(\mathbf{x})$ such that any $\Sigma \Pi^{[\mathrm{poly(d)}]} \Sigma \Pi \Sigma$ circuit, computing $P(\mathbf{x})$, over a small finite field, requires size $2^{\Omega(\sqrt{d})}$. Our work builds upon and strengthens the work of [Kumar-Saptharishi'19], who showed $2^{\Omega(\sqrt{d})}$ lower bounds against $\Sigma \Pi^{[\mathcal{O}(\sqrt{d})]} \Sigma \Pi \Sigma$ circuits over small finite fields. It is known that proving $2^{\omega(d^{1/3} \log n)}$ lower bound for $\Sigma \Pi^{[a]} \Sigma \Pi$ circuits with $a = 2^{\mathcal{O}(d^{1/3} \log d)}$, over fields of characteristic $0$, implies VP $\neq$ VNP. In pursuit of this, we also prove superpolynomial lower bounds over small finite fields for $\Sigma \Pi^{[a]} \Sigma \Pi$ circuits where $a = 2^{\mathcal{O}(d^{\lambda} \log d)}$, for any constant $\lambda < 1/3$. We use evaluations of the shifted partial derivatives to prove our lower bounds. We follow the same outline as [Kumar-Saptharishi'19], but with a more delicate analysis of the complexity measure. We use a family of the Nisan-Wigderson polynomials as a hard polynomial. We show that over small finite fields, setting the parameters of our measure and the hard polynomial with care, the method of shifted partial derivatives can yield lower bounds well beyond the homogeneity restriction on depth-$4$ circuits. We also show an exponential gap between depth-$3$ and homogeneous depth-$4$ circuits over small finite fields. Previously, only a superpolynomial gap was known using [Chillara-Mukhopadhyay'17] and depth reduction of polynomials in VP until homogeneous depth-$4$. We use the complexity measure of [Grigoriev-Karpinski'98], and we use the Product of the Inner Product polynomial to show the separation.

Authors: Dean Doron, Tal Leonov, Jonathan Mosheiff, Henrique Navas, Nicolas Resch, João Ribeiro

We prove that random linear codes have nearly optimal discrepancy properties in a broad range of regimes. Our main results are two general theorems: one controlling all translates of a fixed test, and another controlling large families of Fourier-pseudorandom tests. Two motivating applications follow. First, random linear codes match unstructured random codes for list-decoding from errors above capacity. If $C\subseteq\mathbb F_q^n$ is a random linear code of rate $1-\frac1n\log_q |B_ρ|+ε$, where $B_ρ$ is a radius-$ρ$ Hamming ball, then with high probability $$ |C\cap B|=(1\pm o(1))\frac{|C||B|}{q^n} $$ simultaneously for all radius-$ρ$ Hamming balls $B\subseteq\mathbb F_q^n$. This extends the classical result that such codes have covering radius at most $ρn$ whp (Blinovsky, 1987). Second, over prime fields, random linear codes match unstructured random codes for zero-error list-recovery above capacity. For prime $q>2$ and $2\le \ell\le q-1$, a random linear code of rate $1-\log_q\ell+ε$ satisfies, with high probability, $$ |C\cap S|=(1\pm o(1))\frac{|C|\ell^n}{q^n} $$ simultaneously for all rectangles $S=S_1\times\cdots\times S_n$ with $|S_i|=\ell$. As a consequence, there are abundant $n$-party linear ramp secret sharing schemes over $\mathbb F_q$ with privacy threshold about $n/(2\log q)$ and reconstruction threshold about $5n/(2\log q)$, resilient to balanced local leakage; prior existence results required thresholds above $n/2$ even in this case. The translate result, hence the list-decoding application, holds over arbitrary finite fields, even growing with $n$. The list-recovery and leakage applications hold over prime fields under moderate growth, e.g. $q\le n^{1/5-o(1)}$. The proofs use a refined second-moment analysis tracking intersection sizes as random generators are added to $C$.

Authors: Rosemary U. Adejoh, Andreas Jakoby, Sneha Mohanty, Christian Schindelhauer

We establish that the two-dimensional ray tracing problem with thin lenses and plane mirrors is Turing-complete, thereby resolving an open question posed by Reif et al. in 1994 as to whether three-dimensional space is necessary for computational universality in optical systems. To this end, we consider the standard approximation of reflection and refraction, namely the ABCD model for paraxial optics, which describes ray propagation through lenses (refraction) via a 2 x 2 matrix, combined with the geometric reflection model for plane mirrors. In the absence of mirrors, two-dimensional ray tracing using any combination of lenses in this ABCD matrix model can be described by a single 2 x 2 matrix-vector product, where the matrix has real entries and determinant 1. Conversely, we show that any such matrix with determinant 1 can be represented as a composition of exactly three appropriately spaced thin lenses. When mirrors are combined with lenses, the ray tracing problem can be described by a flowchart using only two variables, which establishes Turing computability for rational-valued inputs, spaces and matrix entries. Building on this observation, we present a construction of ray tracing that simulates a reversible Turing machine. We begin with a restricted version of the reversible flowchart problem, in which only two variables and certain linear functions are permitted. We prove that this restricted variant is Turing-complete. We then show that such a flowchart admits a geometric realization using lenses and mirrors in our model, thereby establishing the main result: Turing-completeness of the two-dimensional ray tracing problem with ABCD-model lenses and mirrors.

Authors: Jie Wang

Wang~\cite{Wang2026} introduced the Stochastic-Oracle Turing Machine (SOTM) framework and defined token complexity as the minimum expected cost of interacting with a stochastic oracle needed to attain a specified solution quality for a task. This paper develops an analogous notion for certifying the reliability of a stochastic oracle on a given domain. Certification token complexity is the minimum expected token cost required, with controlled error probability, to distinguish oracles that meet a target reliability level from those that fall below a lower reliability threshold. We construct an SPRT-based certification SOTM that queries the oracle, computes binary correctness scores, and stops when the accumulated log-likelihood evidence crosses a decision threshold. The SOTM halts almost surely, satisfies the desired two-sided error guarantee over the reliability regions to be certified, and yields an explicit upper bound on certification token complexity in terms of the reliability thresholds, the error bound, and the expected per-turn token cost. We then establish a matching information-theoretic lower bound: even with adaptive queries, every error-bounded certification SOTM must incur the same leading-order expected token cost as the SPRT-based construction as the prescribed error bound tends to zero. Together, these bounds characterize the leading-order certification token complexity in the small-error regime.

Authors: Louis Desruisseaux, Simon Ducharme, Gurleen Padda, Dave Touchette

For many information processing tasks, de Finetti-style theorems can often simplify the analysis in worst-case input scenarios for which the task exhibits some permutation-invariance symmetry, as they can allow for a reduction from an analysis on worst-case inputs to that of i.i.d. inputs. If further information is available on the inputs, it might be advantageous to reflect this information in the de Finetti reduction. In our work, we focus on a form of such constraint, based on the type of the input. This allows us to obtain a conceptually simple proof of a new de Finetti reduction for classical probability distributions, derived from elementary properties from the method of types. We apply our constrained de Finetti reduction to the compression of quantum interactive communication protocols with classical inputs, and prove that the prior-free quantum information cost equals the worst-case input amortized quantum communication cost.

Authors: Fabien Feschet, Jacques-Olivier Lachaud

Full convexity is an interesting alternative to classical digital convexity since it guarantees connectedness and even simple connectedness in digital spaces Z d , for any dimension d. This paper aims at giving a better understanding of the monotonicity properties of fully convex digital sets, since earlier works showed that the question was difficult for thin fully convex sets. To decipher the hierarchy of fully convex sets ordered by inclusion, we study how we can peel a fully convex set progressively while keeping its full convexity. We provide a characterization of peelable points and fast algorithms to identify them. Furthermore we show that fully convex set can be peeled one point at a time till reduced to the empty set, similarly to digitally convex sets in the classical sense. The peeling of a fully convex set can be seen as an analog to homotopic thinning processes, but with an additional geometric property.