Theory of Computing Report

Authors: Adam Kurpisz, Lucas Slot, Mikhail Zaytsev

We analyze the sum-of-squares rank of unweighted instances of the Minimum Knapsack (MK) problem, i.e., minimization of $\sum_{i=1}^n x_i$ for 0/1 variables under the constraint $\sum_{i=1}^n x_i \geq q$, with $q \in \mathbb{R}$. Such instances have long served as a testbed for understanding the limitations of lift-and-project methods in Boolean optimization. For example, both the Lovász-Schrijver and Sherali-Adams hierarchies require (maximal) rank $n$ to solve them, already when $q=1/2$ is constant. The SOS hierarchy requires only \emph{sublinear} rank $O(\sqrt{n})$ to solve unweighted MK when $q=1/2$. On the other hand, when $q$ is allowed to vary with~$n$, the SOS rank of the problem may become linear. Interestingly, this is known to happen both when $q$ is large, and when $q$ is very small ($0

Authors: Kevin Buchin, Mark Joachim Krallmann, Frank Staals

Let $S$ be a set of $n$ points in $\mathbb{R}^2$. Our goal is to preprocess $S$ to efficiently compute the smallest enclosing disk of the points in $S$ that lie inside an axis-aligned query rectangle. Previous data structures for this problem achieve a query time of $O(\log^6 n)$ with $O(n \log^2 n)$ preprocessing time and space by lifting the points to 3D, dualizing them into polyhedra, and searching through their intersections. We present a significantly simpler approach, solely based on 2D geometric structures, specifically 2D farthest-point Voronoi diagrams. Our approach achieves a deterministic query time of $O(\log^4 n)$ and, via randomization, an expected query time of $O(\log^{5/2} n \log\log n)$ with the same preprocessing bounds.

Authors: Patrizio Angelini, Sabine Cornelsen, Giordano Da Lozzo, Fabrizio Frati, Philipp Kindermann, Ignaz Rutter, Johannes Zink

We consider upward-planar layered drawings of directed graphs, i.e., crossing-free drawings in which each edge is drawn as a y-monotone curve going upward from its tail to its head, and the y-coordinates of the vertices are integers. The span of an edge in such a drawing is the absolute difference between the y-coordinates of its endpoints, and the span of the drawing is the maximum span of any edge. The span of an upward-planar graph is the minimum span over all its upward-planar drawings. We study the problem of determining the span of upward-planar graphs and provide both combinatorial and algorithmic results. On the combinatorial side, we present upper and lower bounds for the span of directed trees. On the algorithmic side, we show that the problem of determining the span of an upward-planar graph is NP-complete already for directed trees and for biconnected single-source graphs. Moreover, we give efficient algorithms for several graph families with a bounded number of sources, including st-planar graphs and graphs where the planar or upward-planar embedding is prescribed. Furthermore, we show that the problem is fixed-parameter tractable with respect to the vertex cover number and the treedepth plus the span.

Authors: Julia Chuzhoy, Sanjeev Khanna, Junkai Song

In the fully dynamic maximal matching problem, the goal is to maintain a maximal matching in a graph undergoing an online sequence of edge insertions and deletions. The problem has been studied extensively in the oblivious-adversary setting, where randomized algorithms with polylogarithmic worst-case and constant amortized update time have been known for some time. A major challenge in this area has been designing an algorithm with non-trivial update time against an adaptive adversary. In a recent breakthrough, Bernstein, Bhattacharya, Kiss, and Saranurak (STOC 2025; hereafter, BBKS25) obtained the first algorithms with sublinear update time for this setting: namely, a randomized algorithm with $\tilde{O}(n^{3/4})$ amortized update time, and a deterministic algorithm with $\tilde{O}(n^{8/9})$ amortized update time. Our main result is a deterministic algorithm for fully dynamic maximal matching with amortized update time $n^{1/2+o(1)}$. A powerful tool in dynamic matching is the use of matching sparsifiers: sparse subgraphs that preserve enough information to recover matchings with desired properties. Sparsifiers, such as the EDCS data structure, have been successfully used for approximate maximum matching. For maximal matching, however, this paradigm is not as natural, since maximality must hold with respect to the entire graph. Nevertheless, BBKS25 showed that EDCS can be repurposed as a verification-and-repair mechanism for fully dynamic maximal matching against adaptive adversaries. We introduce a new deterministic framework, referred to as the subgraph system, which, in contrast to EDCS, is purpose-built for verification and maintenance of maximality. It is also designed to allow efficient recursive refinements leading to stronger and stronger parameters, that yield our deterministic algorithm with $n^{1/2+o(1)}$ amortized update time.

Authors: Babak Ghanbari, Robert Šámal

We present a near-linear-time algorithm that, given a bridgeless cubic graph, finds a perfect matching intersecting every 3-edge-cut in exactly one edge. This improves over a cubic algorithm of Boyd et al. for the same problem, and over our previous algorithm, which worked only for 3-edge-connected graphs. The main ingredient is a cactus representation of the 2-edge-cuts, together with an efficient update procedure under 2-cut reductions.

Authors: Zichun Ye, Runqi Wang, Xuchuang Wang, Xutong Liu, Shuai Li, Mohammad Hajiesmaili

Machine unlearning aims to unlearn data points from a learned model, offering a principled way to process data-deletion requests and mitigate privacy risks without full retraining. Prior work has mainly studied unsupervised / supervised machine unlearning, leaving unlearning for sequential decision-making systems far less understood. We initiate the first study of a foundational sequential decision-making problem: offline stochastic multi-armed bandits (MAB). We formalize the privacy constraint for offline MAB and measure utility by the post-unlearning decision quality. We conduct a systematic study of both single- and multi-source unlearning scenarios under two data-generation models, the fixed-sample model and the distribution model. For these settings, our algorithmic design is built on two canonical base algorithms: Gaussian mechanism and rollback, and we propose adaptive algorithms that switch between them according to the data regime and privacy constraint. We further introduce a mixing procedure that elucidates the rationale behind these baselines. We provide performance guarantees across the above settings and establish lower bounds under both dataset models. Experiments validate the predicted tradeoffs and demonstrate the effectiveness of the proposed methods.

Authors: Moshe Lewenstein, Ely Porat

We study the "set parameterized matching" problem, a generalization of the classical parameterized matching problem introduced by Baker. In set parameterized matching, both the pattern and text are sequences where each position contains a set of characters rather than a single character. Two set-strings parameterized match if there exists a bijection between their alphabets that maps one to the other set-wise. Boussidan introduced this problem for the case of equal-length set-strings. We present a randomized algorithm running in $O(N + M)$ time with high probability, where $N$ is the text size and $M$ is the pattern size. Our approach employs a novel three-layer hashing scheme based on Karp-Rabin fingerprinting that addresses the challenges of (1) the size blowup in representations of the problem, (2) set-to-set matching, and (3) the dynamic nature of encodings of text substrings during pattern scanning.

Authors: Shuchi Chawla, Kristin Sheridan

We consider the problem of finding the value of a maximum flow over time in a network with uniform edge lengths where the edge capacities change at specific time instants. To solve this problem, we show how to construct a condensed version of a Time Expanded Network (cTEN) whose standard max flow value is the same as the max flow over time on the original network. In particular, for a graph with $n$ nodes, $m$ edges, and $μ$ {\em critical times} where some edge capacity changes, we obtain a cTEN with $O(n^2μ)$ nodes and $O(μmn)$ edges. This implies that the problem can be solved in $O(μ^2n^3m)$ time using the combinatorial max flow algorithm of Orlin [Orl13], or in $O(μ^{(1+o(1))}(nm)^{1+o(1)}\log (UT))$ time using the algorithm of Chen et al. [CKL+22], where $U$ is the maximum capacity of any edge and $T$ is the time horizon. We focus on graphs that experience many time changes across the period of interest, as in such graphs the $μ$ term dominates the runtime.

Authors: Jeffery Li, Jayson Lynch, Liva Olina, Cecilia Chen, Andrew Lucas, Neil Thompson

In nearly every discipline, scientific computations are limited by the cost and speed of computation. For example, the best-known exact algorithms for the canonical Traveling Salesman Problem would take centuries to run on an instance of size 1 million. A natural response to such limits is to try to find new algorithms or to parallelize existing ones, but many algorithms are already at their theoretically-optimal level and parallelization is often impossible or prohibitively expensive. Starting in the 1960's, computer scientists pursued another solution: allowing solutions to have a small amount of error (i.e. approximating them). In this paper, we survey 118 of the most important algorithm problems in computer science, quantifying the gains and tradeoffs from approximation that have been discovered over the history of the field. Overall, only $\approx$20\% of problems have benefited from approximation. However, those with good approximate algorithms can be dramatically faster to compute with little cost to accuracy. For example, a quarter of computationally intractable problems (e.g. those that take exponential time to compute) have polynomial time approximate algorithms. Approximation also increases the number of algorithms that can run in linear time by 23\%, opening up new computational opportunities for those working in the big data regime. This work also sheds light on what should be expected from progress in AI, where approximation is at the heart of how deep learning works.

Authors: Kiarash Banihashem, MohammadTaghi Hajiaghayi, Mahdi JafariRaviz, Danny Mittal

The standard oracle model for matroid algorithms assumes that each independence query can be answered in constant time, regardless of the size of the queried set. While this abstraction has underpinned much of the theoretical progress in matroid optimization, it masks the true computational effort required by these algorithms. In particular, for natural and widely studied classes such as graphic matroids, even a single independence query can require work linear in the size of the set, making the constant-time assumption implausible. We address this gap by introducing a size-sensitive cost model where the cost of a query $Q$ scales with $|Q|$. Nearly linear-time oracle implementations exist for broad families of matroids, and this refined abstraction therefore captures the true cost of query evaluation while allowing for a more faithful comparison between general matroids and their natural special cases. Within this framework we study three fundamental algorithmic tasks: finding a basis of a matroid, approximating its rank, and approximating its partition size. We establish tight results, proving nearly matching upper and lower bounds that show the optimal query cost is (up to logarithmic factors) quadratic in the size of the matroid. On the algorithmic side, our upper bounds are realized by explicit procedures that construct the desired solution. On the complexity side, our lower bounds are unconditional and already hold even for weaker distinguishing formulations of the problems. Finally, for matroids with maximum circuit size at most $c$, we show that the quadratic barrier can be broken, providing an algorithm that calculates the maximum-weight basis with expected query cost $\mathcal{O}(n^{2-1/c} \log n)$.

Authors: Arend-Jan Quist, Marc Farreras Bartra, Alexis de Colnet, John van de Wetering, Alfons Laarman

Tensor networks and circuits are widely used data structures to represent pseudo-Boolean functions. These two formalisms have been studied primarily in separate communities, and this paper aims to establish equivalences between them. We show that some classes of tensor networks that are appealing in practice correspond to classes of circuits with specific properties that have been studied in knowledge compilation as \emph{tractable circuits}. In particular, we prove that matrix product states (tensor trains) coincide with nondeterministic edge-valued decision diagrams and that tree tensor networks exactly correspond to structured-decomposable circuits. These correspondences enable direct transfer of structural and algorithmic results; for example, canonicity and tractability guarantees known for circuits yield analogous guarantees for the associated tensor networks, and vice versa.

In secret-key private information retrieval (SK-PIR), the client in an offline phase processes the database using a short secret key. In the online phase the client could then use the secret key to make queries to the server, without revealing the entries accessed, and using only sublinear communication $o(N)$ in the database size $N$. While (non-SK) PIR requires public-key cryptography, recent work provides evidence that SK-PIR may not. In particular, Chen, Ishai, Mour, and Rosen (STOC 26) construct SK-PIR with communication $N^{\varepsilon}$, for any $\varepsilon$, from high-noise LPN, which is not known to imply public-key cryptography. We construct SK-PIR with online communication $\tilde{O}(\sqrt{N)}$, under the minimal assumption of one-way functions. More generally we can achieve client-to-server communication $\tilde{O}(N_c)$ and server-to-client communication $\tilde{O}(N_s)$ as long as $N_c \cdot N_s \geq N$. Our construction is simple and is based on garbled circuits satisfying an uncorrelated input encoding property. We show that this property is satisfied by point and permute schemes from the literature.

Michael Rabin passed away on April 14,2026. I blogged about him here. 

My post listed results of his that proved upper and lower bounds on problems. My point was that he proved upper and lower bounds for MANY different levels- from decidable to regular. And I am sure I left out some of his results. 

Here are some things I did not mention.

1) Rabin and Scott shared the Turing Award in 1976.  My not mentioning it raises the following question:

If I want to say someone has an impressive set of results which is a better way:

listing the awards they've won, or

listing  their results. 

I leave this to the reader. 

2) I had Rabin for two graduate courses at Harvard: Algorithms and Complexity Theory. He was a great teacher and gave insights into the results, some of which he had either proven or worked on.

3) I recalled thanking him in my PhD Thesis. So I dusted it off to see what I had said: 

The many courses I have taken at Harvard and MIT have helped me create this thesis. I am especially indebted to Michael Rabin, Mike Sipser, and Michael Stob for their excellent courses in algorithms, complexity theory, and recursion theory. Their pedagogy has been an inspiring example of what good teaching can and should be.

What is the probability that all three great teachers were named Michael? I do not know, however, I suspect Michael Rabin could have told me. 

By gasarch

The Question

I recently restarted working on this CS theory blog. One reason that I took a bit to get it going again is really stupid. Really silly. And perhaps I should not talk about it. It does not make me look smart. But here it goes anyway.

My email system stopped working recently. I got connected to the help desk. I told the help desk person H that I was not getting lots of messages.This was something that H could not figure out. Why were some messages being lost and others were not. H sent some test message to me and they never seemed to get there. H had set what I could see as what they could also see. What was making messages get lost? That led H to get me a ticket for a better expert at the help desk and said: “please wait a while and then use the ticket to get better help”. I thanked H and started to wait.

The Solution

While waiting my dear wife—Kathryn Farley asked me how the help desk was going. She knew I had finally had talked to the help desk. She was just interested in hearing if I had finally fixed things—were messages now getting there?

Kathryn has a PhD in performance studies from Northwestern in performance studies. She is now achieving her goal of being a professional actress in TV, film, and live theater. Here is an image of Kathryn from “The Gilded Age” which she began filming in January.

I explained the email problem to her. She solved it immediately.

Kathryn noticed that the email program was ordering the messages not in date order as I usually did. Rather it was ordering them in alphabet order on the sender’s name. So a message from asmith@some-where would be way before xfred@some-else. This made it look like certain messages were never received at all. We reset the order to date based and all the missing messages now appeared. Pretty cool.

Kathryn made me proud. Her insight was brilliant. It solved a problem that the help expert H could not do. I certainly could not do it. But she could see right away what would fix it.

Perhaps I Should Explain The P=NP Question To Her?

Does this mean that sometimes we all have a bad view of a problem? Can we need some cool insight to see how a problem can be solved? Perhaps I wondered. So many of us think that P is not equal to NP and could we all be missing some easy solution. Not clear to me.

By rjlipton

In this work, we continue the line of research on the complexity of distributions (Viola, Journal of Computing 2012), and study samplers defined by low degree polynomials. An $n$-tuple $\mathcal{P} = (P_1,\dots, P_n)$ of functions $P_i \colon \mathbb{F}_2^m \to \mathbb{F}_2$ defines a distribution over $\{0,1\}^n$ in the natural way: draw $X$ uniformly at random from $\mathbb{F}_2^m$ and output $(P_1(X),\dots, P_n(X)) \in \{0,1\}^n$. We show that when $\mathcal{P}$ is defined by polynomials of degree $d$, the total variation distance of $\mathcal{P}$ from the product distribution $\mathrm{Ber}(1/3)^{\otimes n}$ is $1-o_n(1)$, where $o_n(1)$ is a vanishing function of $n$ for any constant degree $d$. For small values of $d$, we show the following concrete bounds. (i) For $d=1$ we have $\|\mathcal{P}-\mathrm{Ber}(1/3)^{\otimes n}\|_{TV} \geq 1-\exp(-\Omega(n))$. (ii) For $d=2$ we have $\|\mathcal{P}-\mathrm{Ber}(1/3)^{\otimes n}\|_{TV} \geq 1-\exp(-\Omega(\log(n)/\log\log(n)))$. (iii) For $d=3$ we have $\|\mathcal{P}-\mathrm{Ber}(1/3)^{\otimes n}\|_{TV} \geq 1-\exp(-\Omega(\sqrt{\log\log(n)}))$. Our results extend the recent lower bound results for sampling distributions, which have mostly focused on local samplers, small depth decision trees, and small depth circuits. As part of our proof, we establish the following result, that may be of independent interest: for any degree-$d$ polynomial $P\colon\mathbb{F}_2^m \to \mathbb{F}_2$ it holds that $\Pr_X[P(X) = 1]$ is bounded away from $1/3$ by some absolute constant $\delta = \delta_d>0$. Although the statement may seem obvious, we are not aware of an elementary proof of this. The proof techniques rely on the structural results for low degree polynomials, saying that any biased polynomial of degree $d$ can be written as a function of a small number of polynomials of degree $d-1$.

The partial derivative method is a central tool in algebraic complexity, underlying lower bounds for multilinear formulas, bounded depth circuits, and algebraic branching programs. A key feature of this measure is its subadditivity and submultiplicativity, which are usually used to upper bound the measure. However, proving lower bounds requires bounding the measure of explicit polynomials from below, and in some cases, a sharp estimate is required. For example, a frequently used fact is that the dimension of the space spanned by order $k$ partial derivatives of a product of $n$ linearly independent linear functions is ${n\choose k}$. Beyond the linear case, however, not much is known about the behavior of the (general) partial derivative measure under multiplication. In particular, it has been conjectured that for algebraically independent polynomials $g_1,\dots,g_r \in \mathbb{C}[\mathbf{x}]$, the partial derivative complexity of the product $\prod_{i=1}^{r}{g_i(\mathbf{x})}$ grows exponentially with $r$ (see Question 42 in (Chaugule et al., 2023)), but prior to this work such bounds were only known when the $g_i$'s are linear polynomials, or satisfy additional restrictions. In this paper, we show a lower bound of $\exp(\Omega(r^{1/6}))$ for the measure of a product of $r$ linearly independent quadratic polynomials. This is the first result to show such a lower bound on the partial derivative measure of a product of nonlinear polynomials, without any further restrictions. Interestingly, we only assume linear independence, which is weaker than algebraic independence. Our proof relies on algebraic-geometric and combinatorial techniques, combining the Jacobian approach of (Chaugule et al., 2023) together with the theory of wide algebras introduced in (Ananyan and Hochster, 2018; Oliveira and Sengupta, 2022; Garg et al., 2023). To our knowledge, this is the first use of wide-algebra techniques for proving lower bounds on partial derivative complexity, and one of the first applications of these techniques outside the context of Sylvester-Gallai type problems.

Authors: Mingyang Liu, Gabriele Farina, Asuman Ozdaglar

Most familiar equilibrium concepts, such as Nash and correlated equilibrium, guarantee only that no single player can improve their utility by deviating unilaterally. They offer no guarantees against profitable coordinated deviations by coalitions. Although the literature proposes solution concepts that provide stability against multilateral deviations (\emph{e.g.}, strong Nash and coalition-proof equilibrium), these generally fail to exist. In this paper, we study an alternative solution concept that minimizes coalitional deviation incentives, rather than requiring them to vanish, and is therefore guaranteed to exist. Specifically, we focus on minimizing the average gain of a deviating coalition, and extend the framework to weighted-average and maximum-within-coalition gains. In contrast, the minimum-gain analogue is shown to be computationally intractable. For the average-gain and maximum-gain objectives, we prove a lower bound on the complexity of computing such an equilibrium and present an algorithm that matches this bound. Finally, we use our framework to solve the \emph{Exploitability Welfare Frontier} (EWF), the maximum attainable social welfare subject to a given exploitability (the maximum gain over all unilateral deviations).

Authors: Susanna F. de Rezende, David Engström, Yassine Ghannane, Kilian Risse

We prove superpolynomial length lower bounds for the semantic tree-like Frege refutation system with bounded line size. Concretely, for any function $n^{2-\varepsilon} \leq s(n) \leq 2^{n^{1-\varepsilon}}$ we exhibit an explicit family $\mathcal{A}$ of $n$-variate CNF formulas $A$, each of size $|A| \le s(n)^{1+\varepsilon}$, such that if $A$ is chosen uniformly from $\mathcal{A}$, then asymptotically almost surely any tree-like Frege refutation of $A$ in line-size $s(n)$ is of length super-polynomial in $|A|$. Our lower bounds apply also to tree-like degree-$d$ threshold systems, for $d \approx \log\bigl(s(n)\bigr)$, that is, for $d$ up to $n^{1-\varepsilon}$. More generally, our lower bounds apply to the semantic version of these systems and to any semantic tree-like proof system where the number of distinct lines is bounded by $\exp\bigl(s(n)\bigr)$.

Authors: Sanyam Agarwal, Markus Bläser, Mridul Gupta

Barvinok introduced the symmetrized determinant ($\sdet$) as a \emph{non-commutative} analogue of the determinant. Intuitively, given a square matrix over an associative algebra, we can obtain the symmetrized determinant by averaging over all possible multiplication orders in the Leibniz formula for the determinant. He used the symmetrized determinant to design algorithms estimating the permanent of a matrix. To this end, he showed that there is a $O(n^{r+3})$ algorithm computing $\sdet$, where $r$ is the dimension of the algebra, and is therefore polynomial-time computable for fixed $r$. In this work, we study the algebraic properties and complexity of $\sdet$. While most of the properties of the ordinary determinant don't generalize to $\sdet$ defined on non-commutative algebras, we show that the principal minor expansion of the $\sdet$ is analogous to the ordinary determinant. Second, we prove that there exists a polynomial-sized algebra such that computing the symmetrized determinant is $\sharpP$-hard. Third, we show that the associated polynomial family is $\VNP$-complete over a suitable polynomial-dimensional algebra in the non-commutative setting. Further, when seen as a family of polynomials over the matrix algebra, it is also $\VNP$-complete in the commutative setting. This places the symmetrized determinant among the natural complete families arising from algebraic computation.

Authors: Yupan Liu, Pei Wu

Stoquasticity, originating in sign-problem-free physical systems, gives rise to $\sf StoqMA$, introduced by Bravyi, Bessen, and Terhal (2006), a quantum-inspired intermediate class between $\sf MA$ and $\sf AM$. Unentanglement similarly gives rise to ${\sf QMA}(2)$, introduced by Kobayashi, Matsumoto, and Yamakami (CJTCS 2009), which generalizes $\sf QMA$ to two unentangled proofs and still has only the trivial $\sf NEXP$ upper bound. In this work, we initiate a systematic study of the power of unentanglement without destructive interference via ${\sf StoqMA}(2)$, the class of unentangled stoquastic Merlin-Arthur proof systems. Although $\sf StoqMA$ is semi-quantum and may collapse to $\sf MA$, ${\sf StoqMA}(2)$ turns out to be surprisingly powerful. We establish the following results: - ${\sf NP} \subseteq {\sf StoqMA}(2)$ with $\widetilde{O}(\sqrt{n})$-qubit proofs and completeness error $2^{-{\rm polylog}(n)}$. Conversely, ${\sf StoqMA}(2) \subseteq {\sf EXP}$ via the Sum-of-Squares algorithm of Barak, Kelner, and Steurer (STOC 2014); with our lower bound, our refined analysis yields the optimality of this algorithm under ETH. - ${\sf StoqMA}(2)_1 \subseteq {\sf PSPACE}$, and the containment holds with completeness error $2^{-2^{{\rm poly}(n)}}$. - ${\sf PreciseStoqMA}(2)$, a variant of ${\sf StoqMA}(2)$ with exponentially small promise gap, cannot achieve perfect completeness unless ${\sf EXP}={\sf NEXP}$. In contrast, ${\sf PreciseStoqMA}$ achieves perfect completeness, since ${\sf PSPACE} \subseteq {\sf PreciseStoqMA}_1$. - When the completeness error is negligible, ${\sf StoqMA}(k) = {\sf StoqMA}(2)$ for $k\geq 2$. Our lower bounds are obtained by stoquastizing the short-proof ${\sf QMA}(2)$ protocols via distribution testing techniques. Our upper bounds for the nearly perfect completeness case are proved via our new rectangular closure testing framework.

Authors: Hunter Monroe

We study when a sound arithmetic theory $\mathcal S{\supseteq}S^1_2$ with polynomial-time decidable axioms efficiently proves the bounded consistency statements $Con_{\mathcal S{+}φ}(n)$ for a true sentence $φ$. Equivalently, we ask when $\mathcal S$, viewed as a proof system, simulates $\mathcal S{+}φ$. The paper's two unconditional contributions constrain possible characterizations. First, for finitely axiomatized sequential $\mathcal S$, if $EA{\vdash}Con_{\mathcal S}{\rightarrow}Con_{\mathcal S{+}φ}$, then $\mathcal S$ interprets $\mathcal S{+}φ$, implying ${\mathcal S}{\vdash^{n^{O(1)}}}Con_{\mathcal S}(p(n)){\rightarrow}Con_{\mathcal S{+}φ}(n)$ for some polynomial $p$, and hence ${\mathcal S}{\vdash^{n^{O(1)}}}Con_{\mathcal S{+}φ}(n)$. Second, if $\mathcal S$ fails to simulate $\mathcal S{+}φ$ for some true $φ$, then for all sufficiently large $k$ it also fails for $φ_{BB}(k)$ asserting the exact value of the $k$-state Busy Beaver function. Informally, any argument showing that $\mathcal S$ fails to simulate some $\mathcal S{+}φ$ also yields unprovable $φ_{BB}(k)$ witnessing the same obstruction. These results suggest that relative consistency strength is a serious candidate for governing when simulation is possible, while leaving open whether it is the correct criterion. The paper's central conjectural proposal is that the above sufficient condition is also necessary: if $EA{\not\vdash}Con_{\mathcal S}{\rightarrow}Con_{\mathcal S{+}φ}$, then for every constant $c{>}0$, ${\mathcal S}{\not\vdash^{n^c}}Con_{\mathcal S{+}φ}(n)$. Under this proposal, hardness follows in canonical cases where $φ$ is $Con_{\mathcal S}$ or a Kolmogorov-randomness axiom. The latter yields further conjectural consequences and extensions.

Authors: Siu On Chan, Tommaso d'Orsi, Jeff Xu

Under what condition is a random constraint satisfaction problem hard to refute by the sum-of-squares (SoS) algorithm? A sufficient condition is t-wise uniformity, that is, each constraint has a t-wise uniform distribution of satisfying assignments, as shown by the lower bounds of Kothari, Mori, O'Donnell, and Witmer (STOC 2017). This condition is also necessary for random CSPs given by a predicate and uniformly random literals, due to the constant-degree SoS refutation of Allen, O'Donnell, and Witmer (FOCS 2015). For higher degree, Raghavendra, Rao, and Schramm (STOC 2017) gave a refutation for Boolean random CSPs with uniformly random literals, matching the lower bounds optimally in terms of the three-way tradeoff between constraint density, SoS degree, and strength of refutation. Two long-standing open problems are to find a more general sufficient condition for SoS lower bounds, and to refute similar random CSPs not involving literals. We show that for a general random k-CSP, the necessary and sufficient hardness condition is not t-wise uniformity, but t-wise independence. We generalize the optimal three-way tradeoff to any random k-CSP, without assuming a Boolean domain or uniformly random literals. Our analysis involves new Kikuchi matrices for odd order and for asymmetric tensors. It also uses the global correlation rounding technique of Barak, Raghavendra, and Steurer (FOCS 2011). To avoid the running-time penalty of this technique, we also give a spectral refutation algorithm.

Authors: Argyrios Deligkas, John Fearnley, Alexandros Hollender, Themistoklis Melissourgos

We study the problem of computing a competitive equilibrium with approximately optimal bundles in Fisher markets with separable piecewise-linear concave (SPLC) utility functions, meaning that every buyer receives a $(1-δ)$-optimal bundle, instead of a perfectly optimal one. We establish the first intractability result for the problem by showing that it is PPAD-hard for some constant $δ> 0$, assuming the PCP-for-PPAD conjecture. This hardness result holds even if all buyers have identical budgets (competitive equilibrium with equal incomes), linear capped utilities, and even if we also allow $\varepsilon$-approximate clearing instead of perfect clearing, for any constant $\varepsilon < 1/9$. Importantly, we show that the PCP-for-PPAD conjecture is in fact required to show hardness for constant $δ$: showing PPAD-hardness for finding such approximate market equilibria in a broad class of markets encompassing those generated by our hardness result would prove the conjecture. This is the first natural problem where the conjecture is provably required to establish hardness for it.

Authors: Yinqi Sun

We present a rank-$23$ algorithm for general $3\times3$ matrix multiplication that uses $56$ additions/subtractions and $23$ multiplications, for a total of $79$ scalar operations in the standard bilinear straight-line model. This improves the recent sequence of $60$-, $59$-, and $58$-addition rank-$23$ schemes. The algorithm works over arbitrary associative, possibly noncommutative, coefficient rings. Its tensor coefficients are ternary, meaning that every coefficient lies in $\{-1,0,1\}$. Correctness is certified by the $729$ Brent equations over $\mathbb{Z}$, and the verifier also expands the straight-line program and performs additional finite-field and noncommutative implementation tests.

Authors: Ahammed Ullah, Alex Pothen

We propose new graph representations that exploit dense local structure to improve time and space simultaneously. Given an undirected graph $G$, we define a dual clique cover (DCC) representation of $G$ to be the pair $(C, L)$, where $C$ is a collection of cliques that covers the edges of $G$ and $L$ is the incidence dual of $C$. We identify classes of polynomial-time constructible DCC representations that are compact and call them succinct DCC representations. We then develop representation-aware algorithms for several fundamental graph problems. We show that graph primitives such as connected components, breadth-first search forests, depth-first search forests, and maximal matchings can be computed in time proportional to the size of a DCC representation rather than the number of edges. Combined with our succinct DCC representations, these results give a class of algorithms that either match or improve the time and space bounds of their counterparts on standard graph representations. Furthermore, we design several algorithms for constructing succinct DCC representations and establish provable guarantees on their efficiency. We evaluate several graph algorithms on DCC representations against adjacency-list-based implementations on a large collection of real-world and synthetic graphs. All evaluated applications show substantial execution memory savings and total-time speedups; for example, the connected components algorithm achieves about $9\times$ execution memory savings on average, with a maximum of $35\times$, and about $6.5\times$ total-time speedups on average, with a maximum of $35\times$. We also evaluate several DCC construction algorithms and find that the succinctness property plays a key role in making DCC representations effective for algorithmic applications.

Authors: Tijn de Vos, Leo Wennmann, Malte Baumecker, Yannic Maus, Florian Schager

In this paper, we consider the Santa Claus problem in the CONGEST model. This NP-hard problem can be modeled as a bipartite graph of children and gifts where an edge indicates that a child desires a gift. Notably, each gift can have a different value. The goal is to assign the gifts to the children such that the least happy child is as happy as possible. Even though this is a well-studied problem in the sequential setting, we obtain the first results the distributed setting. In particular, we show that the complexity of computing an $\mathcal{O}(\log n/\log \log n)$-approximation is $\hat Θ(\sqrt n+D)$ rounds, where our $\widetildeΩ(\sqrt n+D)$-round lower bound is even stronger and holds for any approximation.

Authors: Davide Bilò, Shiri Chechik, Keerti Choudhary, Sarel Cohen, Martin Schirneck

An important tool in the design of fault-tolerant graph data structures are $(L,f)$-replacement path coverings (RPCs). An RPC is a family $\mathcal{G}$ of subgraphs of a given graph $G$ such that, for every set $F$ of at most $f$ edges, there is a subfamily $\mathcal{G}_F \,{\subseteq}\, \mathcal{G}$ with the following properties. (1) No subgraph in $\mathcal{G}_F$ contains an edge of $F$. (2) For each pair of vertices $s,t$ that have a shortest path in $G-F$ with at most $L$ edges, one such path also exists in some subgraph in $\mathcal{G}_F$. The covering value of the RPC is the total number $|\mathcal{G}|$ of subgraphs. The query time is the time needed to compute the subfamily $\mathcal{G}_F$ given the set $F$. Weimann and Yuster [TALG'13] devised a randomized RPC with covering value $\widetilde{O}(fL^f)$ and query time $\widetilde{O}(f^2 L^f)$. This was derandomized by Karthik and Parter [TALG'24], who also reduced the query time to $\widetilde{O}(f^2 L)$. Their approach uses some heavy algebraic machinery involving error-correcting codes and an increased covering value of $O((cfL \log n)^{f+1})$ for some constant $c > 1$. We instead devise a much simpler derandomization via conditional expectations that lowers the covering value back to $\widetilde{O}(fL^{f+o(1)})$ and decreases the query time to $\widetilde{O}(f^{5/2}L^{o(1)})$, assuming $f = o(\log L)$. We also investigate the optimal covering value of any $(L,f)$-replacement path covering (deterministic or randomized) for different parameter ranges. We provide a new randomized construction as well as improving a known lower bound, also by Karthik and Parter. For example, for $f = o(\log L)$, we give an RPC with $\widetilde{O}( (L/f)^f L^{o(1)})$ subgraphs and show that this is tight up to the $L^{o(1)}$ term.

Authors: Myeongjin Shin, Junseo Lee, Changhun Oh

Characterizing quantum systems by learning their underlying Hamiltonians is a central task in quantum information science. While recent algorithmic advances have achieved near-optimal efficiency in this task, they critically rely on accessing arbitrarily short-time dynamics. This reliance poses severe experimental challenges due to finite control bandwidth and transient pulse errors. In this work, we demonstrate that Heisenberg-limited Hamiltonian learning can be achieved without short-time control. We introduce a framework in which every query to the unknown dynamics has duration at least a prescribed minimum time $T$, and show that this restriction does not preclude Heisenberg-limited scaling. The key ingredient is a method for emulating the continuous quantum control required by iterative learning algorithms using only such lower-bounded evolution times. This reduces the learning task to sparse pure-state tomography. Notably, for logarithmically sparse Hamiltonians, our algorithm achieves the information-theoretically optimal $1/\varepsilon$ scaling in total evolution time for any arbitrary constant minimum evolution time $T$. For many-body (polynomially sparse) systems, we uncover a rigorous quantitative tradeoff, showing that the minimum required evolution time can be significantly relaxed from the standard limit at a polynomial cost in total evolution time. Our results affirmatively resolve a prominent open problem in the field and reveal that high-bandwidth, ultra-short pulses are not fundamentally necessary for optimal quantum learning.

Authors: Hanno von Bergen, Larissa Fastenau, Enna Gerhard, Nicola Lorenz, Stephanie Maaz, Amer E. Mouawad, Roman Rabinovich, Nicole Schirrmacher, Daniel Schmand, Sebastian Siebertz, Mai Trinh

We study solution discovery, where the goal is to obtain a feasible solution to a problem from an initial configuration by a bounded sequence of local moves. In many applications, however, the graph that defines which vertex sets are feasible is not the same as the graph that governs how tokens, agents, or resources may move. Existing models such as token sliding and token jumping typically do not distinguish the problem graph and the movement graph. Motivated by this mismatch, we introduce a directed weighted two-graph model that cleanly separates feasibility from movement. A problem graph specifies the desired combinatorial objects, while a movement graph specifies admissible relocations and their costs. This yields a flexible framework that captures asymmetry, heterogeneous movement constraints, and weighted transitions, while subsuming classical discovery models as special cases. We investigate this model through \textsc{Path Discovery} and \textsc{Shortest Path Discovery}, where the task is to realize a vertex set containing an $s$-$t$-path or a shortest $s$-$t$-path in the problem graph. These problems are particularly natural in applications, since directed and weighted shortest paths are among the most fundamental algorithmic primitives. At the same time, previous work has already shown that discovery can be computationally hard even when the underlying optimization problem is easy. Our results show that this phenomenon persists, and becomes especially rich, in the two-graph setting. We obtain a detailed complexity picture, identifying tractable cases as well as strong hardness results.

Authors: Javier Blanco-Romero, Florina Almenares Mendoza

Lattice reduction smooths the Gram-Schmidt profile, and we use majorization to describe the local swap mechanism behind that smoothing. In this language, each non-degenerate Lovász swap acts as a T-transform on the log-norm profile. As a consequence, every strictly Schur-convex measure of profile spread decreases at such a swap. Two structural consequences follow. First, the worst-case GSA envelope admits a variational interpretation. It is the unique minimum-variance profile compatible with the Lovász gap geometry, so its slope is determined by the LLL parameter alone. Second, the realized swap trajectory satisfies an exact telescoping identity for variance dissipation. The same viewpoint also helps organize deep-insertion heuristics. It suggests a thermal family of Schur-convex scoring rules, motivates adaptive selection within that family, and leads to two concrete selectors: Thermal-Adaptive, which reduces operation counts relative to SS-GG on flat profiles in our benchmarks while recovering SS-GG on $q$-ary inputs, and Geodesic Deep-LLL, which reduces equivalent-swap counts on structured lattices in our benchmarks at higher wall-clock cost.

Authors: Michelle Döring, Niklas Mohrin, George Skretas

We introduce the TemporallyEdgeDisjointScheduleCompletion (TEDSC) problem in which we need to cover a set of temporal edge demands $D$ by routing $k$ temporal walks through a directed static graph while remaining temporally edge disjoint. This problem combines the temporal aspects of train routing and passenger demands with the static nature of real-world rail networks. We present a polynomial time algorithm for TEDSC. Motivated by real world constraints, we next investigate two restricted variants of TEDSC in which each walk can only travel for some bounded distance or time $h$. We show that both are tractable when parameterized by $k + h$, but hard for $h$ and $k + |D|$. If we fix the underlying network, the two problems exhibit distinct complexities: The distance variant remains $W[1]$-hard parameterized by $k$ even on a path of three vertices whereas the time variant admits an FPT algorithm on any fixed star. Finally, we show how to approximate the number of required walks up to a factor of $(2-h^{-1})$.

Authors: Leo van Iersel, Mark Jones, Jannik Schestag, Celine Scornavacca, Mathias Weller

We investigate parameterized algorithms for computing the average-tree phylogenetic diversity (APD) in rooted phylogenetic networks, studying the problem under different structural parameters that capture the deviation of a network from a tree. Our primary parameter is the scanwidth, a measure of the tree-likeness of a given directed acyclic graph. We show that a subset of taxa with maximum APD can be found in polynomial time in phylogenetic networks of scanwidth at most 2, but becomes NP-hard in networks of scanwidth 3. Further, we design an algorithm that computes the APD of a given set of taxa in O(2^sw n) time, where sw denotes the scanwidth and n the number of taxa in the input network. Finally, we give a linear-time algorithm for computing the APD of a given set of taxa if the network induced by these taxa is reticulation-visible. We generalize this algorithm to still run in polynomial time if each biconnected component of the induced network has only constantly many invisible reticulations.

Authors: Hirotaka Yoneda, Masataka Yoneda

We study the problem of online coloring for graphs with large odd girth. The best previously known algorithm uses $O(n^{1/2})$ colors, which was discovered by Kierstead in 1998. This algorithm works when the odd girth is 7 or more. In this paper, we provide the following: for every $\varepsilon > 0$, there exists a constant $g' \in \{3, 5, 7, \dots\}$ such that graphs with odd girth at least $g'$ can be deterministically colored online using $O(n^{\varepsilon})$ colors.

Authors: Yuichi Yoshida

For a connected weighted hypergraph, we give a randomized almost-linear-time solver for the Poisson problem for the cut-based hypergraph Laplacian in the natural input size $P=\sum_{e\in E}|e|$, the sum of hyperedge sizes. For every fixed constant $C>0$, our randomized algorithm runs in $P^{1+o(1)}$ time and, with high probability over its internal randomness, returns a primal point and a dual certificate, with additive optimality gap at most $\exp(-\log^C P)$. A key step is to rewrite the Fenchel dual as a convex-flow problem on an auxiliary $O(P)$-arc graph, yielding a near-optimal dual flow. The main difficulty is primal recovery, because this flow does not by itself determine a primal potential. Our main new ingredient is a recovery theorem showing that, for primal recovery, the detailed routing of the dual flow inside each hyperedge gadget can be discarded: one nonnegative scalar per hyperedge is enough. After the necessary finite-precision rounding, these scalars define a linear-cost min-cost-flow instance on the auxiliary graph, and solving it exactly recovers a primal potential. Finally, a ground-vertex reduction from regularized objectives to the Poisson solver gives randomized almost-linear-time resolvent/proximal primitives for the same cut-based hypergraph Laplacian.

Authors: Dominik Köppl, Gregory Kucherov

The size of the \textit{smallest suffixient set} of positions of a string recently emerged as a new measure of string \textit{repetitiveness} -- a measure reflecting how much of repetitive content the string contains. We study how to maintain the smallest suffixient set online in near-real-time, that is with small (in our case, polyloglog) worst-case time on processing each letter. Two frameworks are considered: when the text is given letter-by-letter in either a right-to-left or left-to-right direction. Our central algorithmic tool is Weiner's suffix tree algorithm and associated algorithmic primitives for its efficient implementation.

Authors: Loukas Georgiadis, Evangelos Kipouridis, Evangelos Kosinas, Charis Papadopoulos, Nikos Parotsidis

Computing edge-connected components in directed and undirected graphs is a fundamental and well-studied problem in graph algorithms. In a very recent breakthrough, Korhonen [STOC 2025] showed that for any fixed $k$, the $k$-edge connected components of an undirected graph can be computed in linear time. In contrast, the directed case remains significantly more challenging: linear-time algorithms are only known for $k \le 3$, and for any fixed $k > 3$, the best known bound for sparse or moderately dense graphs is still the $O(mn)$-time algorithm of Nagamochi and Watanabe (1993). In this paper, we break the $O(mn)$ barrier for all $k = o(n^{1/4}/\sqrt{\log{n}})$. We present a randomized algorithm that computes the $(k+2)$-edge-connected components of a $k$-edge-connected directed graph in $O(k^2 m \sqrt{n} \log n)$ time, for any~$k$. This constitutes the first improvement over the classic Nagamochi--Watanabe bound for any constant $k > 3$. Our approach introduces new structural insights into directed edge-cuts and combines these with both new and existing techniques. A central contribution of our work is a substantial simplification and generalization of the framework introduced in~\cite{GKPP:3ECC}, which achieved an $\widetilde{O}(m\sqrt{m})$ bound for computing the $3$-edge-connected components of a digraph. In addition, we develop a variant of our algorithm that achieves the same $O(m \sqrt{n} \log n)$ running time for computing the $4$-edge-connected components of a \emph{general} directed graph.

Authors: Shisheng Li

Buchbinder and Feldman recently gave a deterministic $(1-1/e-\varepsilon)$-approximation for maximizing a non-negative monotone submodular function subject to a matroid constraint, with query complexity $\widetilde{O}_\varepsilon(nr)$. Their algorithm uses an integer parameter $\ell$, which Buchbinder and Feldman fix to $\ell = 1 + \lceil 1/\varepsilon \rceil$ via a loose bound on $(1+1/\ell)^{-\ell}$. We point out two purely elementary refinements. First, the classical Pólya--Szegő inequality $(1+1/\ell)^{-\ell} \le e^{-1}(1+1/(2\ell))$ replaces the loose step in their proof and permits $\ell = \lceil 1/(2e\varepsilon) \rceil$, shrinking the hidden constant in $\widetilde{O}_\varepsilon(nr)$ by a factor $\approx 2^{0.816/\varepsilon}$. Second, an alternating-series tail bound for $\log(1+t)$ yields the asymptotically sharp inequality $(1+1/\ell)^{-\ell} \le e^{-1}\exp(1/(2\ell) - 1/(3\ell^2) + 1/(4\ell^3))$, matching the true expansion of $(1+1/\ell)^{-\ell}$ through order $\ell^{-3}$ and translating into $\ell_\star = 1/(2e\varepsilon) - 5/12 + O(\varepsilon)$. The asymptotic class $\widetilde{O}_\varepsilon(nr)$ of the query complexity is unchanged in either case; only the implicit constant in $\varepsilon$ is improved. All inequalities in this note are formalized and machine-checked in Lean 4 against Mathlib.

Authors: Thomas Bellitto, Jules Bouton Popper, Justine Cauvi, Bruno Escoffier, Raphaëlle Maistre-Matus

Connectivity of temporal graphs has been widely studied both as graph theory and as gossip theory. In particular, it is well known that in order to connect every vertex to every other, a temporal graph needs to have at least $2n-4$ edges where $n$ is the number of vertices. This paper investigates the optimal number of edges required to satisfy partial connectivity requirements. We introduce the problem of Connectivity Request Satisfaction where we are given a directed graph that we call the request graph, where an arc from $u$ to $v$ means that we need to be able to go from $u$ to $v$. Our goal is to build a temporal graph on the same vertex set with as few temporal edges as possible that would satisfy all the requests. When the graph we build is directed, we prove that the number of temporal arcs required is $n-\mathrm{cc}+\mathrm{dfvs}$ where $\mathrm{cc}$ is the number of connected component of the request graph and $\mathrm{dfvs}$ is the size of its smallest directed feedback vertex set. It follows that the problem is NP-complete but inherits fixed parameter tractability properties of Directed Feedback Vertex Set. When the graph we build is undirected, we establish a characterization of strongly connected request graphs that admit a solution with $n-1$ edges: it is possible if and only if any set of pairwise non-vertex-disjoint closed walks all share a common vertex. We prove that this criteria can be tested in polynomial time.

Authors: Yael Kirkpatrick, Liam Roditty, Richard Qi, Virginia Vassilevska Williams

Computing the diameter of a graph is a problem of great interest both in general algorithms research and specifically within fine-grained complexity, where it is a cornerstone hard problem. Recent work has achieved a full conditional lower bound tradeoff curve for both directed and undirected graphs. However, the best known upper bounds do not match the lower bounds. In particular, the best known approximation scheme for undirected graph diameter has not been improved. Moreover, this scheme is randomized and no similar deterministic scheme is known. Another fundamental field of research in shortest paths computation is the construction of approximate distance oracles. Thorup and Zwick [JACM'05] provided the first such distance oracle with constant query time and (conditionally) optimal space, and in the years since many advances have led to a vast toolbox of techniques and data structures. These two areas of research seem natural to combine since they both concern approximating shortest paths. However, the known diameter approximation algorithms only use a small subset of the techniques used in distance oracles research. In this work we show that in fact approximate diameter and distance oracles are intricately connected. We first demonstrate a strong connection between the current best known diameter approximation scheme of Cairo, Grossi and Rizzi ("CGR") and the $(2k-1)$-approximate distance oracle of Thorup and Zwick. This allows us to derandomize the CGR algorithm and obtain the first deterministic diameter approximation tradeoff. We further derandomize other central techniques in the field of distance oracles and use them to achieve new deterministic diameter approximation algorithms. Finally, we show how these new techniques can be used to derandomize many current best known results in various fields of shortest paths approximations.

Authors: Pasin Manurangsi

We study the Maximum Balanced Biclique (MBB) problem: Given a bipartite graph $G$ with $n$ vertices on each side, find a balanced biclique in $G$ with maximum size. We give a polynomial-time $\left(\frac{n}{\widetildeΩ\left((\log n)^3\right)}\right)$-approximation algorithm for the problem, which improves upon an $\left(\frac{n}{Ω\left((\log n)^2\right)}\right)$-approximation by Chalermsook et al. (2020) and answers their open question. Furthermore, our approximation ratio matches that of the maximum clique problem by Feige (2004) up to an $O(\log \log n)$ factor.

Authors: Christian Coester, Yichen Huang

Metric embeddings into structured spaces, particularly hierarchically well-separated trees (HSTs), are a fundamental tool in the design of online algorithms. In the classical online embedding setting, points arrive sequentially and must be embedded irrevocably upon arrival, resulting in strong distortion lower bounds of $Ω(\min(n, \log n\log Δ))$, where $n$ is the number of points and $Δ$ their aspect ratio. We propose a novel relaxation, \emph{online monotone metric embeddings}, which allows distances between embedded points in the target space to decrease monotonically over time. Such relaxed embeddings remain compatible with many online algorithms. Moreover, this relaxation breaks existing lower bound barriers, enabling embeddings into HSTs with distortion $O(\log^2 n)$. We also study a dynamic variant, where points may both arrive and depart, seeking distortion guarantees in terms of the maximum number $l$ of simultaneously present points. For traditional embeddings, such bounds are impossible, and this limitation persists even for deterministic monotone embeddings. Surprisingly, probabilistic monotone embeddings allow for $O(l \log l)$ distortion, which is nearly optimal given an $Ω(l)$ lower bound.

Hi all! An announcement on behalf of the STOC/TheoryFest organizers:

ACM SIGACT is pleased to provide funds to support student attendance at STOC 2026. These travel awards are for students who are short on funds and are intended to help cover their registration, travel, and accommodation expenses. An advisor may support the applications of at most two students for a travel award. This support is funded by the US National Science Foundation and is only available for students attending US universities. The deadline to apply is May 13, 2026. More information here: https://acm-stoc.org/stoc2026/travel-support.html.

By mkwoot

Breaking the log-squared barrier in pseudorandom generator constructions for read-once branching programs, namely, achieving seed length $o(\log^2 n)$ for length-$n$ programs, has remained a longstanding open problem since Nisan's seminal construction. We show that breaking this barrier, even achieving seed length $O(\log^{3/2} n)$ (for, say, constant width), would follow from simultaneously improving the dependence of PRGs on two seemingly secondary parameters: the error $\varepsilon$ and the program's arity $|\Sigma|$. Such improved dependence is already achieved by certain weighted PRGs (WPRGs). This reduces the problem of breaking the log-squared barrier to deweightization: closing the gap between PRG and WPRG constructions. While the importance of the error parameter has been recognized over the past decade, the role of the arity $|\Sigma|$ has largely been overlooked. By inspection, several existing WPRG constructions achieve optimal dependence on $\Sigma$, though the state-of-the-art constructions do not. As our second result, we construct WPRGs that attain optimal dependence on $\Sigma$ while matching the best known bounds in all other parameters.

• Retraction Watch reports on the mass resignation of the editorial board of Elsevier’s Journal of Approximation Theory (\(\mathbb{M}\)). This follows in close succession from the mass resignation from Taylor & Francis’s Communications in Algebra.

• On Max Bill’s gelbes feld (\(\mathbb{M}\)), Barry Cipra, Notices of the AMS. Analysis of this artwork reveals that it depicts a magic square, with dice-like dot patterns encoding its digits, and with equal numbers of dots in each row or column of dots. You can do this with every magic square, but the diagonals are more problematic.

• One week ahead of its announced deadline for major institutions to make all online content meet WCAG 2.1 A/AA accessibility standards, the US government kicked the can down the road instead, extending the deadline to April 26, 2027 (\(\mathbb{M}\)). Although I was more or less on top of getting my 1600 pages of old university-hosted html content accessible, I also have a couple hundred old pdf files (for instance of papers and talk slides) that are difficult to convert, and are fortunately grandfathered by the requirements. Nevertheless I would like to make them as accessible as possible, eventually. I have found that it is often possible, if tedious, to convert old pdf files to tagged and alt-textified pdf within Acrobat.

  However, I hit a roadblock with some old pdf files, consisting purely of vector graphic artworks with no text. The accessibility checkers all suspect that these are secretly “image-only pdfs”, scans of text that need OCR to make them accessible to non-sighted readers. They are not scans. They are not written in any language. They are purely vector graphics. It does not work to add tags labeling them as figures, to add alt text to the figure tags, nor to set the document language to “None”: the accessibility checkers are still convinced that there must be secret hidden text somewhere in all that line art and complain that I haven’t told them what that supposed text says. Does anyone know how to tag or otherwise annote these files with the information that they contain no text in a way that will make the accessibility checkers shut up about them?

• The Centrality Fallacy and ACM (\(\mathbb{M}\)). Moshe Vardi in CACM protests ACM’s claims that they are making their Digital Library open-access while at the same time paywalling all of its metadata features. His post links to a petition to reopen the metadata.

• Peter Brass, Former NSF Theory Director, on the NSF budget (\(\mathbb{M}\)).

• Does anyone know what was the significance of the stella octangula to André Breton (\(\mathbb{M}\))? In case anyone near Paris wants a mathematically-themed excursion, one of these shapes ornaments Breton’s tomb in Batignolles.

• There’s no “age verification”, there is only “identity verification that includes age”, and the system doing that verification is not just a privacy-invasive user tracking system but a remotely controlled off switch for anyone of any age.

• A knot invariant that can be computed in polynomial time, separates more knots than many other invariants, likely gives a genus bound, and produces fun “QR code” images representing each knot (\(\mathbb{M}\), via Quanta). A recent arXiv preprint by Dror Bar-Natan and Roland van der Veen.

• On coloring Penrose rhomb tilings. A recursive substitution system can simultaneously generate a Penrose tiling and color its tiles with four colors. But a graph degeneracy argument and the De Bruijn–Erdős theorem on coloring infinite graphs together imply that every rhombus tiling, and in particular the Penrose tiling, has a 3-coloring. Can it be generated by a substitution system?

• Trump fires entire 24-member National Science Board (\(\mathbb{M}\), via). This board oversees the National Science Foundation’s funding of US science and advises the government on science policy, and the move is “widely seen as [Trump’s] latest move to erase NSF’s independence”. The National Science Foundation has also been lacking a director for the past year. Trump has proposed to cut the budget of the NSF by another 55% for the coming year (at the same time as saddling it with expensive white elephant projects).

• Book of New Patterns by Hokusai, 1824 (\(\mathbb{M}\), alt. link, via). The via-linked discussion led me to the story of the 1986 rediscovery of the wood blocks for printing this book in the Boston Museum of Fine Arts. The blocks were then brought back to Japan and new prints made from them.

• The number of ISO A(n) sheets that fit orthogonally into an A(0) sheet (\(\mathbb{M}\)) might be the least satisfying sequence in the whole OEIS. It should just be powers of two, but no: rounding sets in.

• Arizona State University professors disturbed to find their lectures chopped up and turned into AI slop (\(\mathbb{M}\)), by a new platform introduced by Arizona State using content scraped from its courses’ Canvas sites, without warning the faculty or offering any opt-out.

• The product of two zero-dimensional schemes can be infinite-dimensional. The example involves \(\mathbb{R}\otimes_{\mathbb{Q}}\mathbb{R}\), the same space in which Dehn invariants of polyhedra live.

By David Eppstein

We study two conjectures posed in the analysis of Boolean functions $f : \{-1, 1\}^n ? \{?1, 1\}$, in both of which, the Majority function plays a central role: the "Majority is Least Stable" (Benjamini et al., 1999) and the "Non-Interactive Correlation Distillation for Erasures" (Yang, 2004; O'Donnell and Wright, 2012). While both conjectures have been refuted in their originally stated form, we obtain a nearly tight characterization of the noise parameter regime in which each of the conjectures hold, for all $n \ge 5$. Whereas, for $n = 3$, both conjectures hold in all noise parameter regimes. We state refined versions of both conjectures that we believe captures the spirit of the original conjectures.

We study when a sound arithmetic theory $\mathcal S{\supseteq}S^1_2$ with polynomial-time decidable axioms efficiently proves the bounded consistency statements $Con_{\mathcal S{+}\phi}(n)$ for a true sentence $\phi$. Equivalently, we ask when $\mathcal S$, viewed as a proof system, simulates $\mathcal S{+}\phi$. The paper's two unconditional contributions constrain possible characterizations. First, for finitely axiomatized sequential $\mathcal S$, if $EA{\vdash}Con_{\mathcal S}{\rightarrow}Con_{\mathcal S{+}\phi}$, then $\mathcal S$ interprets $\mathcal S{+}\phi$, implying $\mathcal S{\vdash^{n^{O(1)}}}Con_{\mathcal S}(p(n)){\rightarrow}Con_{\mathcal S{+}\phi}(n)$ for some polynomial $p$, and hence $\mathcal S{\vdash^{n^{O(1)}}}Con_{\mathcal S{+}\phi}(n)$. Second, if $\mathcal S$ fails to simulate $\mathcal S{+}\phi$ for some true $\phi$, then for all sufficiently large $k$ it also fails for $\phi_{BB}(k)$ asserting the exact value of the $k$-state Busy Beaver function. Informally, any argument showing that $\mathcal S$ fails to simulate some $\mathcal S{+}\phi$ also yields unprovable $\phi_{BB}(k)$ witnessing the same obstruction. These results suggest that relative consistency strength is a serious candidate for governing when simulation is possible, while leaving open whether it is the correct criterion. The paper's central conjectural proposal is that the above sufficient condition is also necessary: if $EA{\not\vdash}Con_{\mathcal S}{\rightarrow}Con_{\mathcal S{+}\phi}$, then for every constant $c{>}0$, $\mathcal S\not{\vdash^{n^c}}Con_{\mathcal S{+}\phi}(n)$. Under this proposal, hardness follows in canonical cases where $\phi$ is $Con_{\mathcal S}$ or a Kolmogorov-randomness axiom. The latter yields further conjectural consequences and extensions.

Authors: David Miloschewsky, Supartha Podder, Dorian Rudolph

We study the power of quantum witnesses under perfect completeness. We construct a classical oracle relative to which a language lies in $\mathsf{QMA}_1$ but not in $\mathsf{QCMA}$ when the $\mathsf{QCMA}$ verifier is only allowed polynomially many adaptive rounds and exponentially many parallel queries per round. Additionally, we derandomize the permutation-oracle separation of Fefferman and Kimmel, obtaining an in-place oracle separation between $\mathsf{QMA}_1$ and $\mathsf{QCMA}$. Furthermore, we focus on $\mathsf{QCMA}$ and $\mathsf{QMA}$ with an exponentially small gap, where we show a separation assuming the gap is fixed, but not when it may be arbitrarily small. Finally, we derive consequences for approximate ground-state preparation from sparse Hamiltonian oracle access, including a bounded-adaptivity frustration-free variant.

Authors: Farzan Byramji, Daniel M. Kane, Jackson Morris, Anthony Ostuni

We provide a unified method for constructing explicit distributions which are difficult for restricted models of computation to generate. Our constructions are based on a new notion of robust extractors, which are extractors that remain sound even when a small number of points violate the min-entropy constraint. Using such objects, we show that for a broad range of sampling models (e.g., low-depth circuits, small-space sources, etc.), every output of the model has distance $1 - o(1)$ from our target distribution, qualitatively recovering essentially all previously known hardness results. Our work extends that of Viola (SICOMP '14), who developed an earlier unified framework based on traditional extractors to rule out sampling with very small error. As a further application of our technique, we leverage a recent extractor construction of Chattopadhyay, Goodman, and Gurumukhani (ITCS '24) to present the first explicit distribution with distance $1 - o(1)$ from the output of any low-degree $\mathbb{F}_2$-polynomial source. We also describe a potential avenue toward proving a similar hardness result for $\mathsf{AC^0}[\oplus]$ circuits.

Authors: Apurva Mudgal

We prove the Jordan curve theorem by generalizing the sweepline algorithm for trapezoidal decomposition of a polygon. Our proof uses Zorn's lemma (or, equivalently the axiom of choice). Though several proofs have been given for the Jordan curve theorem by various authors, ours is the {\bf first algorithmic proof} of Jordan curve theorem using computational geometry. Further, with some preparation, the proof can be taught as part of an undergraduate discrete mathematics course, where till now the proof of this theorem was considered inaccessible.

Authors: Lucas Meijer, Till Miltzow, Johanna Ockenfels, Miloš Stojaković

In the (Nesting) Bird Box Problem we are given a polygonal domain P and a number k and we want to know if there is a set B of k points inside P such that no two points in B can see each other. The underlying idea is that each point represents a birdhouse and many birds only use a birdhouse if there is no other occupied birdhouse in its vicinity. We say two points a,b see each other if the open segment ab intersects neither the exterior of P nor any vertex of P. We show that the Nesting Bird Box problem is ER-complete. The complexity class ER can be defined by the set of problems that are polynomial time equivalent to finding a solution to the equation $p(x) = 0$, with $x\in R^n$ and $p\in $Z[X_1,...,X_n]$. The proof builds on the techniques developed in the original ER-completeness proof of the Art Gallery problem. However our proof is significantly shorter for two reasons. First, we can use recently developed tools that were not available at the time. Second, we consider polygonal domains with holes instead of simple polygons.