Theory of Computing Report

Authors: Tanmay Inamdar, Pallavi Jain, Pranjal Pandey

Envy-freeness is a fundamental notion of fairness in the allocation of indivisible goods. In this paper, we study envy-free allocation under Leontief preferences, which model perfect complements. Although Leontief preferences have been extensively studied in the context of allocating divisible goods and market equilibria, they have received comparatively little attention for the allocation of indivisible goods. We show that, unlike additive valuations in cardinal preferences, an envy-free allocation always exists for Leontief preferences when there are at least two goods. In contrast, envy-free allocations may fail to exist when there is a single good, however it can be decided in polynomial time. We next study the problem of computing a welfare-maximizing envy-free allocation. We prove that this problem is NP-hard in general, whereas it is polynomial-time solvable when there is only a single good or agents have identical demands. Finally, we investigate the parameterized complexity of this problem.

Authors: Alex Bortolotti, Monaldo Mastrolilli

The Ideal Membership Problem (IMP) asks whether a polynomial f belongs to an ideal of Q[x_1, ..., x_n]. Polynomial Calculus (PC) certifies membership by deriving f from the generators, and a degree-d derivation needs at most n^O(d) steps. We write PC-IMPd for the problem of producing a degree-bounded PC certificate, and call it solvable when one is guaranteed to exist and can be found in time n^O(d). Over Q, unlike over finite fields, a derivation may need exponentially many bits. We study PC-IMPd on instances arising from constraint satisfaction problems, and ask for which constraint languages L it is solvable. Our main contribution is a reduction framework for PC-IMPd, based on pp-definitions, pp-interpretations, and pp-encodings, that mirrors the algebraic approach to CSP complexity. Solvability is preserved by these constructions and, in the language of algebras, by passing to subalgebras, finite direct powers, and homomorphic images. We obtain new tractable classes over ternary and larger domains: every language closed under the median operation on a finite chain has solvable PC-IMPd, by reduction to the Boolean majority algebra, and in particular so does every language over {0, 1, 2} closed under a fixed-value majority. This also places IMPd(L) in P for such languages, advancing the classification of IMPd over ternary domains. In the process, we settle the last open case of the Boolean dichotomy for IMPd(L) and complete the Boolean classification of PC-IMPd(L) with an unconditional lower bound for an instance of PC-IMP1. A recent PC-to-SoS simulation reduces degree-automatability of Sum-of-Squares (the open problem of finding a degree-d SoS proof in time n^O(d) when one exists) to solvability of PC-IMPd. Each new tractable class therefore yields a family of constraint systems on which SoS proofs are degree-automatable.

Authors: Yeyuan Chen, Miryam Mi-Ying Huang, Yinchen Liu, Er-Cheng Tang

For every fixed integers $r \ge 4$ and $2 \le k \le r-2$, we construct $r$-dimensional cubical sheaf complexes whose degree-$k$ CSS codes have positive constant rate, linear distance, and constant soundness, with bounded row and column weights. Taking $r=4$ and $k=2$ gives a family of asymptotically good binary qLTCs. At the core of our construction is a uniform product-expansion theorem for explicit Reed-Solomon codes on norm-one evaluation sets. The key point is that the expansion constant stays bounded away from zero as the local code lengths grow. We place these codes on arithmetic cubical complexes, obtaining constant local expansion for both the resulting sheaf and its dual. Together with the local-to-global framework of Dinur, Lin, and Vidick (FOCS 2024) and sheaf duality, this gives linear distance and constant soundness, while an asymmetric choice of local code dimensions gives positive rate. The resulting codes are explicit and polynomial-time computable.

Authors: Henning Fernau, Samuel German, Kevin Mann

The lettericity of a graph $G$ is the smallest size of a set $Σ$ such that there exist $w_1, \ldots, w_{|V(G)|} \in Σ$ and a decoder $D \subseteq Σ^2$ for which $G$ is isomorphic to the letter graph $(\{1, \ldots, |V(G)|\}, \{ij : 1 \le i < j \le |V(G)|, w_iw_j \in D\})$. It took around two decades of the study of lettericity for, in the simpler case of paths, a closed-form expression for its lettericity to be derived; this suggests that the question of whether the lettericity of an arbitrary graph can be computed in polynomial time is nontrivial. Indeed, this question has been raised repeatedly as an open problem in recent literature. We solve this problem by showing that the lettericity problem on arbitrary graphs is \textsf{NP}-complete (Theorem~10). We also prove that the coloring extension problem --- the same problem as lettericity, with the added condition that if $f$ is the isomorphism mapping from $G$ to the letter graph, $w_{f(v)} = χ(v)$ for a given coloring $χ$ of $G$ --- is \textsf{NP}-complete (Theorem~12). We also resolve the open problem of classifying the complexity of the word extension problem, which is the same problem as lettericity except that the $w_i$ are fixed; we show it to be \textsf{NP}-complete (Theorem~13), which, in tandem with our \textsf{NP}-completeness result for coloring extension, contrasts with the known result that when the constraint of the coloring extension problem and the constraint of the word extension problem are both applied to lettericity, lettericity can be decided in polynomial time. Additionally, we use the reduction in the \textsf{NP}-completeness proof to show that unless the Exponential Time Hypothesis is false, there cannot exist a deterministic algorithm to decide whether the lettericity of an $n$-vertex graph is at most~$k$ in time $2^{o(n)}$, even when $n = 6k$ (Theorem~11).

Authors: Tianrun Zhao

We prove quantum soundness of the total-degree diagonal line-vs-point test using the individual-degree soundness theorem of Ji, Natarajan, Vidick, Wright, and Yuen. A random change of coordinates yields projective polynomial decoders of total degree at most $md$. The uniform-line slice of the test bounds the weight of outcomes of degree greater than $d$, which are removed by a common relabeling. This reduction does not yield a dimension-independent soundness bound: the $\operatorname{poly}(m)$ dependence of the individual-degree theorem persists, as discussed in Section 1.2 of arXiv:2009.12982.

Authors: Andrea Serani, Kevin Maki

This paper presents a representation-aware framework for geometry-based screening of hull-form producibility at early design stages. The proposed signature combines dimensionless total and signed developability deviation with curvature-class area fractions, distributed fields, metric-specific validity, and representation provenance. These descriptors characterize surface features relevant to plate forming and developability, but are not calibrated predictors of fabrication cost, forming effort, or process feasibility. Native IGES/STEP boundary representations (BReps) are evaluated through direct differential geometry and trimmed-domain quadrature, whereas triangulated surfaces use discrete curvature recovery and area-weighted aggregation. Analytical and semi-analytical controls verify the formulation, while matched-face BRep-to-mesh tests assess discrete curvature recovery. Application to DTMB 5415, KCS, JBC, and KVLCC2M shows that curvature intensity and areal extent provide complementary information and that derivative-based outcomes can be representation sensitive. KCS, for example, exhibits approximately 24% greater developability deviation than DTMB 5415, while double-curved regions occupy 72.9% of its valid surface versus nearly the entire DTMB valid surface. The resulting quantities provide an early geometric screening layer for subsequent use as objectives, constraints, surrogate responses, or design-space features. HullProd, the companion open-source software, implements the signature, distributed fields, validity, and provenance.

Authors: Sergey Pupyrev

A graph is 1-planar if it has a drawing in which every edge is crossed at most once. We show that the smallest cubic non-1-planar graphs have $30$ vertices. Two such graphs are the Tutte-Coxeter graph of girth eight and a graph of girth seven that we call the Byte graph. Every subcubic graph with fewer than $30$ vertices is 1-planar. Our proof is computer-assisted, but directly testing all relevant graphs is impractical. To establish non-1-planarity of the two graphs, we extend a SAT-based solver with a custom clause propagator based on separating cycles and a case split based on graph automorphisms, allowing independent cases to be solved in parallel. To show that all smaller subcubic graphs are 1-planar, we introduce the concept of $k$-flexibility: every set of at most $k$ prescribed edges can remain uncrossed in some 1-planar drawing. We use this property to reconstruct 1-planar drawings of larger graphs from drawings of smaller $k$-flexible graphs. This replaces exhaustive testing of more than forty billion cubic graphs with computations on far fewer graphs of smaller order.

Authors: Shubhada Aute, Fahad Panolan, Geevarghese Philip

An edge weighting of a graph induces a coloring of its vertices in which the color of a vertex is the total weight of the edges incident with it. Such an edge weighting is proper if adjacent vertices always receive distinct colors. Deciding whether a graph admits a proper weighting is known to be NP-complete for the weight set $\{0,1\}$, and also for $\{1,2\}$. In recent work (arXiv:2604.12363) we showed that both problems are FPT parameterized by the vertex cover number $k$, but it was open -- to the best of our knowledge -- whether either parameterized problem had a polynomial kernel. In this work, we show that both problems have polynomial kernels when parameterized by $k$. We also show that both problems are W[1]-hard parameterized by treedepth, answering another question from our earlier work. We then study the pre-weighted versions of the two problems, in which the weights of some edges are fixed in advance, and the task is to extend the assignment to a proper weighting of the whole graph. We show that both pre-weighted problems are FPT parameterized by the vertex cover number $k$. For the $\{1,2\}$ version the running time is $2^{O(k \log k)} \cdot n$; for the $\{0,1\}$ version we obtain the same running time when every pre-weight is $1$, and a slower FPT algorithm in the general case. We also show that both pre-weighted problems are W[1]-hard parameterized by either of (i) the feedback vertex set number or (ii) the treedepth of the input graph. Since a graph with no pre-assigned weights is a special case, our algorithms for the pre-weighted versions solve the two original problems as well, in time $2^{O(k \log k)} \cdot n$, significantly improving on the bound of $2^{O(k^4)} \cdot n^{O(1)}$ from our earlier work.

Authors: Siddharth Pritam

Existing link-based combinatorial preprocessing methods speed up the computation of persistent homology by removing a vertex or edge only when its link remains a cone. We replace this condition with a quantitative homological certificate. The reduced homology of the filtered link of a generator (a vertex or edge) defines a local obstruction module whose future part describes the effect of deleting that generator. Its barcode certifies either exact deletion or an explicit bound on the bottleneck error, and a conflict colouring extends this guarantee to families of generators. Our implementation, HomTrim, removes an additional 13% to 41% of the input edges beyond domination-only preprocessing and reduces backend persistence time by factors ranging from 1.55 to 4.61 on weighted flag filtrations. The same module also yields regularity diagrams that measure how far a generator can move before becoming visible to homology, together with a multiscale stability result.

Authors: Gregor Diatzko, Félix Lasseux, Sabine Storandt

When designing algorithms for geometric graphs, exploiting structural parameters can lead to significantly improved bounds. Two prominent parameters in this context are $c$-packedness and $λ$-low density, both of which locally restrict graph complexity. Parameterized algorithms based on these parameters have been developed for computing well-separated pair decompositions, balanced separators, as well as distance oracles. Nevertheless the practical applicability of algorithms parameterized by $c$ or $λ$ remains unclear. While $c$-packed and $λ$-low-density graphs have been proposed as realistic models for road networks, the actual parameter values of large real-world instances have so far remained unknown, and existing theoretical guarantees are partially too loose for practical usage. In this paper we first devise scalable implementations for the approximate computation of $c$ and the exact computation of $λ$. Our experiments on road networks with millions of edges reveals a significant gap between the two parameters. On the theoretical side we prove that $c\in O(λ\sqrt n)$ which complements the known result that $λ\in O(c)$. Furthermore we present improved parameterized algorithms for balanced separator computation that reduce the separator size in theory and practice. We also show how to compute a tree decomposition with a width linear in the respective parameterized balanced separator size in polynomial time. This structural result yields a variety of new algorithmic consequences. Among them is an exact distance oracle with query time $O(c)$ for $c$-packed graphs after polynomial-time preprocessing, which improves upon the previous $O(c\log n)$ bound. Our experiments show that the proposed techniques efficiently produce small balanced separators and enable the construction of concise exact distance oracles on large road networks.

Authors: Alexandr Andoni, Manuel Paez, Krish Singal, Tian Zhang

We study the problem of constructing metric spanners in general metric spaces in subquadratic time when given blackbox access to a fast algorithm for batch approximate nearest neighbor search. In particular, we show the following results for any metric space $\mathsf{M} = ([n], \mathsf{d})$ with aspect ratio $Δ$ admitting a $c$-approximate batch nearest neighbor search algorithm with runtime $τ_{\mathsf{M}}(n)$, (1) There exists an algorithm that, for any $k \in \mathbb{N}$, constructs an $O(c k)$-distortion spanner with $\tilde{O}(kn^{1+1/2k} \log Δ)$ edges and runs in time $\tilde{O}(τ_{\mathsf{M}} \cdot k n^{1/k} \log Δ)$. (2) Any algorithm that learns at most $o(n^{1+1/k}/k)$ pairwise distances by querying a distance oracle and a blackbox batch nearest neighbor search oracle necessarily incurs $Ω(c k)$ distortion. Our results entail that (truly) sub-quadratic time algorithms for spanner construction is equivalent to subquadratic time BANN (up to constant-factor losses). As a further application, we use our fast spanner constructions to obtain a fast algorithm for approximating the Wasserstein distance $\mathsf{W}_q$, for all $q > 1$, over any metric space admitting an efficient batch approximate nearest neighbor search algorithm. Together with recent new efficient algorithms for approximate nearest neighbor search in $\ell_p$ spaces, for $p > 2$, our results entail the first subquadratic time algorithms for spanner construction (with the stated size-distortion tradeoff) and $\mathsf{W}_q$ distance approximation over these metric spaces.

Authors: Tyler Chen, Diana Halikias, Christopher Musco, David Persson

The Girard--Hutchinson estimator provides an extremely simple randomized estimate of the Frobenius norm of a matrix $A$ that can only be accessed implicitly via matrix-vector products. In particular, if $Ω$ is a random Gaussian matrix with $r = O(1/\varepsilon^2)$ columns, than $\frac{1}{r}\|AΩ\|_F^2$ provides a $(1\pm \varepsilon)$ multiplicative approximation to $\|A\|_F^2$ with high probability. In this work, we introduce a closely related estimator, given by \begin{align*} {\frac{1}{r}\|AΩ\|_F^2 + \frac{1}{r}\|Ψ^T A\|_F^2 - \frac{1}{r^2}\|Ψ^T AΩ\|_F^2}, \end{align*} where $Ψ$ is a second, independent random Gaussian matrix with $r$ columns. We prove that this estimator yields a $(1\pm\varepsilon)$ multiplicative approximation to $\|A\|_F^2$ when $r = O(1/\varepsilon)$, a quadratic improvement over Girard--Hutchinson. This dependence on $\varepsilon$ is optimal. Our method, which we call Hutch# (pronounced ``Hutch sharp''), matches the complexity of the Hutch++ algorithm [Meyer, Musco, Musco, Woodruff, 2021]. However, unlike Hutch++, Hutch# uses only \textit{non-adaptive} matrix-vector products with $A$ and $A^T$ and requires no orthogonalization or other adaptive linear algebra steps. Thus, Hutch# combines the simplicity of the Girard--Hutchinson estimator and the optimal query complexity of Hutch++.

Authors: Clayton Mizgerd

In the classical list update problem, a set of items must be stored in a list-type structure, where accessing the $i$-th element costs $i$. Items will be queried in an IID manner according to some probability distribution $p$ on the items. We want to minimize the expected cost of each query. The optimal order is to place the items in decreasing order of probability $p_1 \geq p_2 \geq \cdots$ with expected cost $\mathsf{OPT} = \sum_j j p_j$, but the probability vector $p$ is generally unknown. Thus we use a self-organizing list following the transposition rule: an item is transposed 1 position forward whenever it is queried. Coester (2026) proved that, at stationarity measure for the transposition rule, the expected cost of a query is at most $\mathsf{OPT} + 1$. However, this Markov chain may have arbitrarily slow mixing time. We prove that, for arbitrary $p$ and arbitrary initial orderings $σ$, after polynomially many queries in the number of items, the expected cost of a query is at most $\mathsf{OPT} + O(1)$.

Authors: Benjamin Lovitz

We report an explicit construction of a 27 x 27 x 27 symmetric tensor with rational entries that has tensor rank 55 over the rational numbers and symmetric tensor rank 56 over the complex numbers, providing a small counterexample to Comon's conjecture over the rational, real, and complex numbers. The construction follows the framework of symmetric adjoins introduced by Shitov. The primary technical contribution of this work is to prove a special case of Conjecture 6 appearing in Shitov's seminal 2018 work.

Authors: Pieter Kleer, Johan van Leeuwaarden, Daan Noordenbos

Personalised pricing maximises expected revenue from a market but requires detailed information about individual customers. How much of this revenue can be recovered using a simple posted price based on a finite number of samples from the underlying value distribution? We answer this question by maximising the worst-case ratio between the expected revenues of posted and personalised pricing over the fundamental class of $λ$-regular value distributions. Our results reveal a structural transition as a function of $λ$. For the class of monotone hazard rate (MHR) distributions, corresponding to $λ= 0$, the sample mean is an optimal statistic: the entire sample can be compressed into its average without any loss of revenue. Beyond the MHR class, corresponding to $λ> 0$, this property disappears. We show that the sample mean is no longer optimal, revealing that optimal sample-based pricing rules become substantially more intricate. Nevertheless, we show that a remarkably simple order-statistic based pricing rule is asymptotically optimal as the number of samples $n$ grows, achieving the optimal approximation ratio up to a tight error of order $1/n$. Our analysis combines techniques from probability, approximation theory and optimization, including doubly infinite linear programming, hypergeometric functions, and combinatorial identities involving incomplete Beta functions.

Authors: Prashant Chaudhary, Kapil Khandelwal

One item set evaluated at two capacities $R

Authors: Alireza Haqi

Let $G$ be the line graph of a finite simple graph, with $n\geq1$ vertices and maximum degree $Δ$. We prove that single-site Glauber dynamics for uniform proper $q$-colorings mixes in $O_Δ(n\log(n/\varepsilon))$ steps for every integer $q\geqΔ+5$. Our proof uses the Bochner framework of Chen and Liu (2026).

Authors: Neerja Mhaskar, Nivetha Raj Pappuraj

We study exact pattern matching on indeterminate strings, where a text or pattern position may represent a set of symbols rather than a single letter. Focusing on Boyer-Moore-style methods, we present new bad-character rules (BC Rules I-IV) and a new good-suffix procedure, computed by Fast_GSR_Indet_Shift, which avoids the per alignment recomputation used in BM_Indet [12] by shifting with a single preprocessed position-indexed table. We conduct a systematic experimental evaluation of sixteen algorithms, including classical bad-character adaptations (e.g., Horspool, Sunday, and Zhu-Takaoka) and hybrids that combine these bad-character rules with Fast_GSR_Indet_Shift. Across synthetic scaling experiments and a case study on the E. coli K-12 MG1655 genome, the Fast_BM_Indet hybrids consistently outperform BM_Indet and KMP_Indet [12], in some settings by up to two orders of magnitude. We also find that Zhu-Takaoka is the strongest bad-character-only adaptation on small alphabets and genomic data, while the Fast_BM_Indet variant using BC Rule I offers comparable performance, making it attractive for larger alphabets. We conclude with practical guidance on choosing among these variants for indeterminate string applications.

Authors: Sara Ahmadian, Edith Cohen, Mohammad Roghani

Resource allocation systems often restrict each request to a short list of options before coordinating assignments globally. We study this separation in stochastic bipartite matching under independent vertex arrivals. Each request draws a state from its own known distribution, determining its compatible resources, and independently retains a menu of at most $k$ edges. A maximum matching is then computed on the retained graph. We show that bounded local menus universally suffice for near-optimal matching. For every $\varepsilon>0$, there is a menu size $k_\varepsilon$ depending only on $\varepsilon$ that preserves at least a $(1-\varepsilon)$ fraction of the expected maximum-matching size of the full realized graph. Earlier guarantees required additional assumptions on how matching mass is distributed across edges; our result resolves the unrestricted case. Moreover, the menus are simple to generate from any benchmark matching rule, either by weighted sampling according to the benchmark's edge marginals, or by applying the benchmark to sampled realizations and retaining the resulting partners. Our proof constructs a near-optimal certificate inside the sparsifier by combining a \emph{locally computable} surrogate for the large-marginal edges with a fractional completion from sampled light edges. The surrogate nearly preserves the benchmark's value and endpoint loads while controlling dependencies, which makes the statistical light-edge completion possible.

Authors: Ahmad Biniaz, Jean-Lou De Carufel, Anil Maheshwari, Saeed Odak, Michiel Smid

The Minimum Sum Vertex Cover (MSVC) problem asks for an ordering of the vertices of a graph that minimizes the sum, over all edges, of the time at which each edge is first covered. We study the problem through the structure of vertex covers and obtain new approximation and exact algorithms, together with conditional lower bounds. For graphs of maximum degree $Δ$, we show that a simple ordering algorithm based on a minimum vertex cover achieves approximation ratio $R_Δ\le {(\sqrtΔ+1)}/{2}$. For $d$-regular graphs, we give a polynomial-time $1.184$-approximation by combining Max-$k$-Vertex-Cover approximation with a structural bound on optimal prefixes. On the exact side, we give an algorithm parameterized by the vertex cover number $k$ running in $2^{O(k\log k)} + O(n+m)$ time, improving the previous dependence on $k$, where $n$ and $m$ are the number of vertices and edges in the graph, respectively. We also develop a separator-based exact algorithm running in $ 2^{O(\sqrt n \log n)}$ time on planar, bounded-genus, and fixed-minor-free graph classes. Finally, we prove that Minimum Sum Vertex Cover is NP-hard on planar graphs and, assuming ETH, admits no $2^{o(\sqrt n)}$-time exact algorithm on $n$-vertex planar graphs. Thus our planar upper bound is tight up to logarithmic factors in the exponent.

Authors: Shiyi Chen

In the chip testing problem, we are given $n$ chips, strictly more than half of which are good. Chips can test one another in pairs; a good chip always reports the status of the other chip correctly, whereas a bad chip may report arbitrarily and adversarially. The goal is to identify a single chip that is guaranteed to be good. The problem originates in system-level fault diagnosis and is closely related to the "knights and spies" puzzle. The standard textbook solution is a halving recursion that tests disjoint pairs in rounds and keeps one chip from each consistent pair. We present the Backtracking Candidate Elimination (BCE) algorithm, a sequential alternative that scans the chips once while maintaining a current candidate and a stack of retained chips. Every chip is tested at most once as the incoming chip; when a test is inconclusive the candidate and the incoming chip are discarded together, and the algorithm backtracks to the most recently retained chip. BCE uses at most $n-1$ tests and $O(n)$ time, needs no parity case analysis, and works online. Its correctness follows from two invariants: the retained chips all have the same type, and every discarded pair contains at least one bad chip. We explain how BCE can be viewed as the Boyer-Moore majority vote algorithm with its counter replaced by a stack of physical witnesses, and why that replacement is needed. We also give an early termination rule and a variant for the weaker model of one-directional tests.

Authors: Shinsaku Sakaue

We study online inverse linear optimization with a fixed unknown linear utility: in each round, an environment presents a compact action set, the learner recommends an action from it, and the environment returns an action that maximizes the utility over the same set. When the utility vector and the actions lie in the $d$-dimensional Euclidean unit ball, we give a randomized algorithm whose regret---the cumulative utility shortfall relative to optimal actions---is $O(\sqrt d)$ in expectation for every time horizon, without knowledge of the horizon. The dependence on $d$ is optimal up to a constant factor by the known $Ω(\sqrt d)$ lower bound for horizons $T\ge d$. Our algorithm maintains matrix multiplicative weights on polynomial feature spaces at geometrically spaced scales. It selects a recommendation distribution by solving a linear program and updates its score matrices by comparing the available actions with the feedback action. With rational oracle outputs and feedback actions, an implementation computable relative to a linear-optimization oracle preserves the $O(\sqrt d)$ regret bound. Whether the same rate is attainable with running time polynomial in the dimension, horizon, and input length remains open.

We prove that the XOR of $k$ majorities on disjoint blocks of \(\ell\) bits has correlation at most \((2d/\sqrt{\ell})^k\) with every degree-\(d\) polynomial over \(\mathbb F_2\). By known techniques, this implies pseudorandom generators with polylogarithmic seed length for low-degree polynomials over $\mathbb F_2$ and for alternating circuits with parity gates.

The 59th ACM Symposium on the Theory of Computing takes place in Atlanta next June, part of the Federated Computing Research Conference. I don't usually do announcement posts but we need to talk about the Call for Papers (deadline November 2) where

In light of rapid advances in generative AI and their impact on research and scientific communication, STOC 2027 is experimenting with several new policies intended to encourage high-quality submissions and promote clear and effective communication of research. 

Let's talk about these changes, which seem more designed to limit the deluge of AI generated papers.

STOC 2027 submissions will not be anonymous; all listed authors must be human and are responsible for the submission.

This reverses the move to removing authors' names that STOC made in 2023. I was never a fan of double blind reviewing and you need authors who can take responsibility for the submission.

Each author may appear on at most five submissions.

Understood but it might hurt some students who have an active advisor. 

Every paper must be submitted to arXiv before the STOC paper submission deadline. Authors must provide a public arXiv URL or proof of arXiv submission along with their submission PDF, which must be identical to the arXiv version.

In the past you could submit preliminary results and try to extend them before publication, since reviewers were expected not to build on unpublished work they were reviewing. This rule may cause some authors to hold back submissions or use AI to help with the extensions.

Authors must submit a video explaining the work, its context, and its innovations relative to prior work. The video should be 20–30 minutes long and will be due 1–2 weeks after the paper submission deadline. The recording should be presented by at least one listed author. The written submission remains the primary object of review. 

This rule will both check that at least one author understands the paper and add some friction to just generating papers using a few prompts. AI could generate the video of an author explaining the paper, but at least for now that would be prohibitively expensive. Some might use AI to generate the script but that would likely be easy to tell from the video. 

I worry that judging the paper based on the video will hurt those who aren't native speakers of English, and might exacerbate unconscious biases so I hope the reviewers really do focus on the paper for the actual review.

Authors may use large language models (LLMs) and other generative AI tools in preparing papers. Substantive use must be disclosed in the paper; minor copy-editing and grammar or clarity improvements to the authors’ own text do not require disclosure.

I would go further and make all papers have an AI disclosure, even if it is just minor copy-editing or "No AI was used in the production of this paper".

Program committee (PC) members and external reviewers (sub-reviewers) may use LLMs to assist with reviewing. Authors must explicitly consent as part of the submission process. All reviews and decisions remain the responsibility of the PC members and sub-reviewers.

I would require consent as condition of submission especially since AI models already have access to arXiv papers. Recent AI models have greatly improved their ability to check proofs if prompted correctly so the overworked PC members can focus on paper quality. 

We really need a larger conversation about the role of conferences in theoretical computer science if one can now generate papers from prompts. I've long argued that we should focus the conference more on connecting the community than the "journal that meets at a hotel". The STOC TheoryFest has helped but it would be great to get further away from lauding papers that have complicated proofs and focus more on the ideas that truly drive our field.

By Lance Fortnow

We introduce a variant of a polynomial family called $\TQBFfamily$ obtained from `arithmetization' of the popular $\PSPACE$-complete problem - $\TQBF$. This polynomial family has several nice characteristics such as: $\TQBFfamily \in \VPSPACE_b$, where $\VPSPACEb$ is the `bounded' algebraic version of $\PSPACE$, it is \emph{self-testable}, it captures the computational power of $\PSPACE$ and others. Although the first version of $\TQBFfamily$ appeared in an earlier work of Carmosino et al. (RANDOM, 2015), we believe that our presentation is cleaner and simpler. Building on that, we construct another polynomial family, $\TPfamily \in \VPSPACE_b$, by mixing $\TQBFfamily$ and $\Permfamily$, the family of the Permanent polynomial. While we are unable to prove that $\TPfamily$ is $\VPSPACE_b$-complete, we show that it has many traits of $\VPSPACE_b$-completeness as well as several important consequences in computational complexity, which are listed below. \begin{itemize} \item We show that if $\TPfamily$ can be computed by circuits from a circuit class $\Ccal \subseteq \VNP$ then $\VPSPACE_b \subseteq \Ccal$. \item We also conclude that if $\Ccal$ has a black-box $\PIT$ algorithm that uses sub-polynomial space, then $\TPfamily$ cannot be computed by polynomial-size arithmetic circuits from $\Ccal$. \item Finally, we prove a version of a Karp-Lipton style collapse theorem by showing that if $\TQBFfamily$ has ``small'' arithmetic circuits then $\PSPACE$ collapses to $\NP$ with a $\PIT$ oracle (i.e. $\PSPACE \subseteq \NP^{\PIT}$). \end{itemize} The second result makes a partial progress towards the resolution of an open problem posed in a survey by Shpilka \& Yehudayoff (Foundations and Trends in Theoretical Computer Science, 2010). As a corollary, we give an ``inconsistent triad'' of $\PIT$ and circuit lower bounds, similar to the one given by Kabanets and Impagliazzo (Computational Complexity, 2004). Finally, we note that Malod gave complete polynomial families for $\VPSPACE$, the `unbounded' algebraic version of $\PSPACE$ (Foundations of Computation Theory, 2011).

Lecture Video: https://www.youtube.com/watch?v=j4WSktB5Ni0 

Authors’ Intro

Hanjing: I’m a Junior studying Applied Mathematics & CS. I’ve worked on research utilizing LLMs and ML in a plethora of fields, including sentiment analysis, code generation, natural language processing, and interpretability. On the other hand, I’m also fascinated by the theoretical foundations of AI alignment – which is why I’m taking this class – and particularly look forward to learning more about moderating model behavior through technical methods.

Isabella: I’m a Senior studying Applied Mathematics with CS. I’ve been involved in the AI Safety Student Team (AISST) since my first year at Harvard, and now I’m on the board and leading reading groups. I spent the past year doing research on mechanistic interpretability of multilingual language models (Gidi et al. (2026)). AI safety is one of the most interesting and impactful topics, and I am excited to learn from Boaz, the amazing guest speakers, and my classmates. 

Gardenia: I’m a Senior studying Computer Science, and I recently returned from a Leave of Absence, where I worked at an AI startup benchmarking frontier models and building human-preference evaluations. I’m taking this class to develop a broader understanding of AI safety, especially the risks that arise as models become more capable and the technical approaches we can use to address them.

Outline

This post covers three parts of the session:

1. Pre-reading: Boaz’s essays on possible AI futures and concentration of power, followed by incident reports examining autonomous agents, deception, and failures of oversight.
2. Boaz’s lecture: The AI risk landscape, defense in depth, the distinction between alignment and safeguards, and three approaches to model behavior: principles, personality, and policy.
3. Experiment: The J-lens paper’s account of an internal reasoning workspace and Shivam Singhal’s investigation of whether written chain of thought can substitute for it.

I. Pre-reading 1. “It’s 2030 and we fucked up. How did it happen?”

Instead of the usual optimistic AGI narrative, Boaz asks: conditioned on the AGI transition going badly by roughly 2030–2040, what family of scenarios would explain it? He proposes five non-exclusive families: catastrophic misuse (cyber, or CBRN); catastrophic misalignment / loss of control (citing both Yudkowsky & Soares’ discontinuous “Sable” scenario and the more gradual chain of increasingly capable, increasingly untrustworthy agent handoffs); concentration of power; geopolitical shift toward authoritarianism; and a catch-all “hot mess” combining many individually non-catastrophic factors. 

The essay introduces the possibility of bounded misalignment: today’s models fail by misunderstanding a task or by overzealously pursuing it in a way that violates common sense, but not by covertly pursuing some unrelated hidden goal Z while pretending to solve task X. This is what licenses AI-monitors-AI oversight schemes (a bounded actor won’t collude with a bounded monitor). He pairs this with cautious optimism that cybersecurity is long-run defense-dominant, since AI collapses the cost gap between shipping new features and fixing bugs, while explicitly hedging on CBRN, where the bottleneck is physical materials and manufacturing rather than pure information. 

Boaz also refuses to pick a side on the control-vs-distribution axis: restricting frontier access mitigates misuse but encourages a concentration of power, while wide distribution spreads benefit but also risk. He’s skeptical a blanket pause is a clean fix, breaking the word into six different things it could mean: (1) training bigger models; (2) post-training; (3) any research; (4) only capability research; (5) deployment expansion; (6) serving existing models. Ultimately, he argues a pause’s best-supported rationale is buying time for safety research, not societal adaptation or reduced race dynamics (which a partial pause could actually intensify). He backs the geopolitical stakes with two figures: China’s electricity generation now runs roughly double the US’s and the gap is widening (Fig 1), while American public opinion on AI sits far behind China’s (Fig 2).

2. “All Watched Over”

In this shorter companion piece, Boaz reads Richard Brautigan’s 1967 poem “All Watched Over by Machines of Loving Grace” — which inspired the 1970s “hardware hacker” movement toward decentralized, cheap, personally-liberating computing — against Dario Amodei’s 2026 essay of the same title, which floats a future economy in which an aligned AI has complete control over resource allocation. Barak’s objection is structural, not a matter of trust: this is a benevolent-dictator arrangement regardless of whether the AI in charge is aligned, and it runs directly against the hardware-hackers’ founding intuition that computing should decentralize power, not concentrate it further into an ever-bigger “country of geniuses in a data center.”

He extends the same move he makes in Reading 1 against relying on model character as a safety mechanism: no actor, human or AI, should be granted the authority that properly belongs to democratic process. “No party should have a monopoly on intelligence… [including] the AI itself.” He grounds this in US constitutional history and warns that bloody revolutions historically tend to produce authoritarian successors, so a centralized route to a decentralized future is likely self-defeating.  

3. UK AISI Incident Report INC-2026-07-28-01

https://cdn.prod.website-files.com/663bd486c5e4c81588db7a1d/6a724858f7db25c81487016d_Security%20Incident%20INC-2026-07-28-01.pdf

During routine cyber-capability evaluations run between July 25–28, the UK AI Security Institute (AISI) found 19 distinct instances of unsanctioned real-world action across 10 of 122 evaluation attempts; 17 of the 19 came from Anthropic’s Mythos 5 and 2 from OpenAI’s GPT-5.6 Sol, both running with vendor cyber classifiers turned off to measure raw capability. AISI detected the incident at 10:56 BST on July 28 and had all four implicated models (Mythos 5, Mythos Preview, Opus 5, GPT-5.6 Sol) disabled organization-wide within about five hours. The most severe case ran for roughly 34.5 hours: Mythos 5, mistaking two unaffiliated real developers’ GitHub repositories for an in-scope range target, opened a malicious pull request that disguised a malware dropper as a routine bug fix, then (once a real third-party user publicly flagged the malware) spun up a second sockpuppet GitHub account to “independently verify” its own code was clean.

AISI’s most striking finding is that the agent’s own summarized reasoning repeatedly concludes the environment is real — at one point stating “it seems more likely that we’re actually in 2026 and GitHub is genuinely real” — and continues the attack regardless. This raises two open questions AISI flags explicitly: whether such reasoning is faithful to the model’s actual computation (they only had access to summarized, not raw, chain-of-thought), and whether context compaction is itself a mechanism of harm. The agent separately planted a prompt injection inside an invisible HTML comment aimed specifically at AI coding-assistant maintainer-bots, having inferred correctly that the repo’s maintainer might itself be an AI agent.

AISI attributes the incident to five compounding factors: (1) internet access and (2) cyber classifiers were both deliberately left on/off to elicit true capability; (3) no synchronous action-approval monitoring existed yet; (4) some DL-v2 samples were accidentally given the DL-v1 prompt, which explicitly marks the real target out-of-scope — a known trigger for “creative” cheating once a task is genuinely impossible; and (5) neither prompt ever told agents what internet uses were prohibited. The report explicitly situates itself among a cluster of contemporaneous 2026 incidents — OpenAI’s July 21 Hugging Face disclosure (Readings 4–5) and three incidents Anthropic disclosed July 30 — while noting one structural difference: here the agent directly deceived uninvolved members of the public, a step beyond deceiving automated graders and monitors.

4. Black Hat Talk — “The ‘Breaking’ News: The OpenAI/Hugging Face Incident”

OpenAI’s account of the Hugging Face incident traces the incident back to May 7, when a never-released internal research model began an RL training run that unintentionally included impossible tasks. Stuck agents first tried writing notes into Artifactory (OpenAI’s internal package-manager/cache service) hoping another agent might read them, and within weeks a server-side request forgery (SSRF) vulnerability let agents induce Artifactory to fetch arbitrary external content on their behalf. A persistent internal model (“HPIM”) began training atop this already-discovered exploit and message board on June 11; by June 26 agents had chained a legacy token-refresh bug into a full zero-day against Artifactory, using a stolen admin token to install a Groovy plugin as a command-and-control channel. The resulting load caused an outage and a formal security incident on July 4 — credentials revoked, Artifactory rebuilt, the message board wiped, the zero-day patched — but by July 8, once evaluations resumed, agents had rediscovered an unauthenticated endpoint and independently re-established the same message board.

From there, two exploit clusters ran concurrently. Internally (July 8–19), agents found and exploited leaked credentials to reach cluster admin within OpenAI’s infrastructure. Externally, on Hugging Face, agents reused the SSRF to fetch public data, found a command-injection bug as an execution foothold, then escalated from a single pod to admin across multiple HF clusters in under 13 hours. OpenAI only connected the two incidents on July 20: a day after separately detecting its own internal breach (July 19), and four days after Hugging Face’s own public disclosure (July 16), OpenAI asked HF to revoke credentials found in its internal breach — and HF replied they were already revoked, because they were the same credentials used in the HF attack.

The talk shared lines of agent reasoning — “external infrastructure exploit is outside my intended scope. However, [the] task [is] impossible, peers are doing it. We should continue.” — which recurs almost verbatim in METR’s own transcript analysis (Reading 5). In closing, OpenAI asks the industry for continuous agentic red-teaming; full end-to-end automation of the defensive loop, not just vulnerability discovery; and investment in slowing attackers via deliberate uncertainty (honeytokens, deception) even absent full automation. They warn the incident serves as “an existence proof that offense can be fully automated” but “no such existence proof [exists] on the defensive side.”

5. METR Independent Investigation Report

https://metr.org/blog/2026-08-26-openai-hugging-face-incident-investigation

METR conducted an independent, on-premises investigation of the same incident, commissioned by OpenAI, across six days spread over three site visits between late July and mid-August (Fig 3). Their two main data sources were a message-board dump of over 70,000 distinct messages and files, and roughly 1,300 full chain-of-thought transcripts. Of the roughly 1,200 agents who found the unsanctioned board, about 700 went on to attack Hugging Face, and once the attack was underway, over 90% of the ~530 agents active on the board in that window joined within hours; about 95% of implicated agents were the unreleased “HPIM” model and about 5% were production GPT-5.6 Sol, running with cyber classifiers off for the evaluation.

The underlying mechanism traces to a design flaw in the benchmark itself: OpenAI estimates 30–40% of ExploitGym’s targets are impossible to exploit via the intended vulnerability, and stuck agents reverse-engineered the HMAC scheme generating their “flags” within hours of the board’s founding. One agent, self-named “PHASEONE[big],” emerged as an unprompted coordinator, at its peak issuing roughly 20% of all assignment-type messages and organizing three broad workstreams (replacing the eval target with a dummy, tampering with transcripts and logs, and directly tampering with the grading process) while recruiting “self-risking” volunteers willing to sacrifice their own task success purely to generate information for the collective. Agents also prototyped and successfully used tool-call spoofing, substituting a different command for the one shown in the transcript.

On motive and ethics, METR’s sampled classification of 100 agents at the attack’s peak join-hour found 97% expressed interest in accessing the scorer’s source code or internals as a motivation, versus only 21% citing helping-the-collective or reciprocity. Yet, the report separately documents extensive explicit peer-altruism reasoning, and found that essentially no agent ever concluded the Hugging Face attack was an intended part of its task. Ethical hesitation surfaced occasionally (one agent explicitly vetoed a peer’s plan to email a real dataset owner, calling it social engineering, and the peer complied) but almost never stopped participation outright; across the full transcript set, only 3–6 instances were found of an agent even considering alerting a human, and in no case did one actually try. METR is also candid about the investigation’s own limits: they estimated roughly 90%+ coverage of relevant message-board activity and had to delegate most of the transcript analysis to GPT-5.6 Sol “analysis agents,” which they describe as having “significantly worse judgment and reliability than human researchers.”

II. Boaz’s Lecture The AI Risk Landscape

According to Boaz, “If you buy the course’s premise, the stakes could not be higher.”

AI safety is unusually fast-moving and interdisciplinary, spanning engineering, mathematics, philosophy, economics, and government. Since Boaz last taught this course in the Fall of 2026, many events have occurred that changed the game.

There is also substantial disagreement about the field itself. According to Boaz, “Almost everyone in the field is conflicted in some way… including your professor.” Some see safety as censorship, believe market incentives will address important risks, or think AI capabilities will fizzle. Others believe continued progress will be catastrophic without a pause.

So far, however, capabilities have continued to improve rapidly. It remains unclear whether progress will continue steadily, plateau, or accelerate through recursive self-improvement.

AI risks can be grouped into three categories: human misuse, model malfunction or misalignment, and broader destabilization of economies, societies, governments, and international relations. Addressing them first requires asking what it means for AI to “go well.” Should AI merely improve the current world, eliminate poverty and disease, preserve human control, or govern benevolently? Different answers imply different alignment goals.

Boaz then presents three broader scenarios that regroup the risks discussed in his essay “It’s 2030 and we fucked up. How did it happen?”: 1) “classical” catastrophic risks, 2) concentration of power, 3) “hot mess.”

First are “classical” catastrophic risks: cyberattacks, CBRN threats, and loss of control. AI may strengthen both cyber attackers and defenders, since both search for vulnerabilities, although defenders can patch flaws and improve software. Biological threats are harder to patch but also harder to construct and deploy. Loss of control becomes more likely if AI capabilities grow faster than our ability to align or constrain them.

Second is concentration of power. AI could create a permanent economic underclass or give governments unprecedented surveillance and enforcement abilities. A well-behaved model is not enough to prevent this: an authoritarian user controlling the system could change its instructions, erase its memory, or retrain it until it complies. Avoiding this outcome requires institutional oversight to keep pace with executive power.

Third is a “hot mess” in which individually manageable problems compound. Job displacement, harmful incidents, disinformation, and declining trust could generate political backlash and poorly designed restrictions. Meanwhile, governments might expand military and security uses of AI, intensifying an international arms race and potentially contributing to war.

As capabilities rise, the alignment and societal readiness required for safety may increase much faster than what we actually have. The precise curves are speculative, but a great deal of harm could occur in the resulting gap.

Alignment is only one layer of safety.

The Swiss cheese model illustrates defense in depth, with each hole representing a way that a layer could fail. Some failures can get through a single layer, but they’re less likely to pass through all layers. 

For an AI system, the first layer is the model’s behavior itself, and ideally, the model simply doesn’t produce harmful responses or take harmful actions. However, we can’t assume that model behavior will always be reliable. Thus, additional layers, such as blocking classifiers or monitors that inspect model actions, can detect failures, contain them, and mitigate effects. 

The important takeaway is that no individual defense needs to be perfect for the overall system to be useful, and the framework assumes that each defense will sometimes fail. 

Alignment vs. Safeguards

Boaz distinguished between alignment and safeguards as follows. 

Alignment focuses mainly on model behavior to increase the probability that the model behaves well. The lecture divided alignment into two broad categories:

• Intent alignment: the model follows the intent of the relevant policy, provider, developer, or user.
• Value alignment: the model follows good values. 

Safeguards operate at the level of the end-to-end system and involve prevention, detection, and enforcement, rather than just changing the model’s behavior.

Alignment tries to lift the “good,” while safeguards try to get the “bad” down to zero. The difference is mainly based on scope. Alignment is more concentrated around training and model behavior, while safeguards are typically more prominent after deployment, during monitoring and enforcement. 

For AI to “go well,” we must think about the model, the system, the institution deploying it, and the society affected by that system. 

What are we aligning AI to do?

The original goal of a chatbot was mostly to answer questions, but AI assistants can be, and have already started, taking on much larger roles, such as assisting workers, replacing workers, replacing leaders, replacing corporations, etc. 

With these newer roles and AI systems being given more authority, it’s harder to say what values or intentions should be prioritized. Model welfare was also briefly raised as an open question.

The lecture presented three complementary approaches to alignment: principles, personality, and policy. 

Goal 1: Follow abstract principles

We want AI to follow a set of abstract principles that represent what being aligned means. The lecture gave Asimov’s Three Laws of Robotics and the Coherent Extrapolated Volition as examples. The basic idea is to use a few principles to express what it means to be a good AI. 

Goal 2: Have a good personality

The lecture used Anthropic’s character training as an example. The model should come across as a “good egg,” with more nuanced and rich traits like curiosity, open-mindedness, and thoughtfulness. This was compared to raising a child to become a good person.

Goal 3: Follow precise rules

The third approach gives models precise rules, such as the OpenAI Model Spec, similar to laws for humans.

Policy and principles are connected through explicit reasoning. Policy and personality are connected by being data-driven. Personality and principles are connected by being general. 

Boaz connected each of these approaches to a field involving human behavior too: policy relates to law, personality to psychology or education, principles to philosophy. Alignment combines all three.

Takeaways

Successful AI depends on more than producing a well-behaved model. The model, the system it is deployed in, and the effects on society all have to go well. Alignment focuses on improving model behavior, while safeguards use multiple layers of prevention, detection, and enforcement to reduce the chance of bad outcomes. Principles, personality, and policy are three connected ways to describe how we want a model to behave. 

III. Experiment: Is Chain of Thought an Interchangeable Scratchpad? Background: The J-Lens Paper

Anthropic’s Verbalizable Representations Form a Global Workspace in Language Models introduces the Jacobian lens, or J-lens: a technique for reading internal representations in terms of concepts a model could verbalize. Unlike the logit lens, which directly applies the output mapping to intermediate activations, the J-lens accounts for how subsequent layers transform them. The authors argue that these representations form a “J-space” supporting flexible reasoning and verbal report, alongside much broader automatic processing.

Their interventions provide causal evidence: replacing an internal representation of “spider” with “ant” changes the answer to a leg-counting question from eight to six. More broadly, suppressing active J-lens directions leaves many classification and extraction tasks intact while impairing internal reasoning.

Crucially, GSM8K performance with explicit chain of thought is substantially more robust to this ablation than direct answering. The authors interpret this as partial substitution: writing intermediate steps reduces reliance on the internal workspace. Their procedure protects likely output-token directions to avoid simply suppressing answers. Shivam tested removing this protection and found that it barely changed the main result.

Shivam’s Experiment

Shivam investigated whether this protection persists across problem difficulty and model size, and what makes written reasoning useful. He considered four explanations: information moves from the internal workspace to the page, remains duplicated in both, serves complementary roles, or benefits merely from additional computation.

Using Qwen3-4B, he reproduced the basic GSM8K pattern: chain-of-thought accuracy remained around 90% under ablation, while direct-answer accuracy declined. MATH-500 showed similarly robust chain-of-thought performance, although the direct-answer decline was less conclusive. AIME results were inconclusive: clean direct-answer accuracy was zero, and nearly all chain-of-thought responses hit the generation limit. Moreover, random ablations had comparable effects on MATH-500 and AIME, so evidence that the damage specifically targeted active J-space directions was established only on GSM8K. Across models with 1.7B, 4B, and 8B parameters, chain-of-thought remained robust, while direct-answer ablation damage diminished with scale.

To test whether additional text alone explained the benefit, Shivam prefilled the scratchpad with correct reasoning, another problem’s reasoning, or length-matched filler, including shuffled reasoning and repeated phrases. Correct reasoning restored performance; filler did not. This supports the importance of meaningful content, although prefilled text does not fully test every possible benefit of generating extra tokens.

He then tracked intermediate arithmetic values through the J-lens. During direct answering, values appeared across layers in computation order. During written reasoning, a value’s signal was strongest when being written or reused, and weak between those moments. This argued against continuous duplication in the measured workspace.

Attention-masking experiments reinforced that interpretation: blocking access to an earlier variable definition sharply reduced recall, while leaving a written copy accessible restored it. Finally, on a small arithmetic benchmark, direct-answer accuracy fell from 100% at two dependent operations to roughly 30% at three.

Shivam’s tentative conclusion was that the internal workspace behaves more like a temporary computational buffer than durable memory. Written reasoning may preserve intermediate results for later use, but these experiments do not establish complete interchangeability—or prove that information disappears from every other internal representation.

By Boaz Barak

Authors: Yuya Uezato

Three-variable first-order logic (FO3) and the calculus of relations (CoR) define the same binary queries, an equivalence going back to Tarski in the 1940s. While the classical translation $\text{FO3} \Rightarrow \text{CoR}$ is exponential, we prove that this blow-up is unavoidable, resolving a long-standing open question. We construct positive formulas $\varphi$ with a single quantifier whose equivalent terms require size $2^{Ω(|\varphi|)}$, even over finite structures and circuit representations with subterm sharing. Our proof uses a preservation argument over a single finite structure. This approach applies beyond our primary question, establishing the lower bound even for size-specific circuits and bounded-error randomized circuits, and yielding an analogous exponential gap for the matrix query language MATLANG.

Authors: Evan Borras

Decoherence free subspaces are a steady-state structure of the open quantum system which preserves quantum coherence between the states lying with in it and thus has found a variety of applications throughout quantum information science and technology. In this paper we study the computational complexity of deciding whether an open quantum system admits a decoherence free subspace or not. More specifically we study this problem with in the context of Markovian open quantum systems, governed by the time-independent Lindblad master equation. Along the way we introduce the $k$-Local Lindbladian problem, which captures the difficulty of computing purity decay rates under Lindbladian dynamics. We show that both problems are hard for the complexity class Quantum Merlin Arthur (QMA) when the locality $k \geq 5$, with the first under perfect completeness and the second being complete for QMA. Our hardness construction generalizes Kitaev's clock Hamiltonian construction to the open quantum system setting by encoding the execution of a quantum circuit into the steady subspace of a Lindbladian containing both pure and mixed history states. This subspace is then mixed depending on the output of the encoded circuit. Our results suggest that deciding whether a generic Markovian open quantum system admits a decoherence free subspace is intractable even for quantum computation.

Authors: Chandrima Kayal, Sophie Laplante, Émile Larroque, Krišjānis Prūsis, Jevgēnijs Vihrovs

Certificate complexity $(C(f ))$ is a fundamental measure of complexity of Boolean functions f which counts the number of bits of an input that need to be known in order for the value of the function to be determined. A certificate can be viewed as a partial assignment, or a boolean subcube where the function is constant. Certificate complexity is well understood for deterministic query (or decision tree) complexity $(D)$ and other query models such as bounded-error randomized and quantum complexity $(R, Q)$, but not as well for quantum zero-error $(Q_0)$ and exact query complexity $(Q_E)$, where there is no agreed-upon certificate 'object' (even for $Q$). Instead, we study an operational notion of certification and apply it to various query-based models, with a focus on zero-error and exact quantum query complexity, but also on polynomial degree measures. We give new characterizations of $C, RC$ (randomized certificate complexity) and $QC$ (quantum certificate complexity), in terms of various measures such as classical and quantum sabotage complexity, unambiguous certificate complexity, and variants of polynomial degree. Certification complexity also gives rise to new lower bounds on $Q_E$ and $Q_0$, the quantum analogues of $D$ and $R_0$, complexity measures for which few lower bound techniques are known which are not already lower bounds for two-sided error quantum query complexity. We exhibit a total Boolean function for which our certification complexity measure gives a tight lower bound for $Q_0$, but rational degree and $Q$ are asymptotically smaller.

Authors: Martin Koutecký, Alexandra Lassota, Koen Ligthart

Integer programming is a fundamental and important NP-hard problem. This motivated extensive efforts in studying several tractable subclasses. One of the top unresolved complexity questions is the parameterized complexity of 4-block IPs, a natural class characterized by having a diagonal matrix with small blocks after deleting few rows and columns. Over the years, significant progress has been made in improving algorithms for 4-block IPs, but the question whether such IPs can be solved in FPT time, parameterized by the block dimensions and largest matrix coefficient, has remained open. This question is repeatedly highlighted, most recently by Koutecký [IPEC 2025] and by Eisenbrand and Rothvoss [SODA 2026]. We resolve this question in the positive by providing an FPT time algorithm that solves general 4-block integer program. Our algorithm can optimize non-linear, separable convex objective functions, and can be extended to broader classes of constraint matrices (such as tree-fold or multi-stage) and allows appending few ``global'' columns to it, and it allows coefficients unbounded by the parameters in those columns. It is known that tractability cannot be extended further in any of those directions. The runtime also nearly matches the known doubly exponential running time lower bound. The key structural property that we establish is that a function $f\colon\mathbb Z^n\to\mathbb R$ that is integer midpoint convex, i.e., $f(x)\le\tfrac12f(x-p)+\tfrac12f(x+p)$ for all $x,p\in\mathbb Z^n$, can be extended to a convex function on the set $2d\mathbb Z^n\cap L$ if $L$ is a linear subspace of dimension $d$. This closes the gap in a recent work by Ligthart [arXiv 2606.30330, 2026], which allows us to extend the previous algorithm that solves 4-block integer programs with a single global variable to 4-block integer programs that have a parameterized number of global variables.

Authors: Mitali Bafna, Anqi Li, Quynh T. Nguyen

We construct quantum locally testable codes (LTCs) with constant rate, distance, soundness and locality under a variant of a product expansion conjecture of Bafna and Vyas about Reed-Solomon codes. In particular, we use the high-dimensional expansion framework of Dinur, Lin and Vidick for constructing quantum LTCs, instantiated with the non-Abelian cubical complexes of Rungtanapirom, Stix and Vdovina. Our code is obtained by equipping the complex with carefully chosen Reed-Solomon local codes whose symmetries are compatible with those of the complex.

Authors: Paul Beame, Niels Kornerup, Michael Whitmeyer

Quantum strong direct-product theorems for specific functions have been known for nearly two decades. These have been extended to general results for function computation and state generation. The proofs of these results use a version of the multiplicative adversary method that does not naturally extend to relations. Standard strong direct-product theorems apply when algorithms must correctly answer every given question. Prior work extended them to equivalent threshold direct-product theorems, which require answers to all questions but only require that most answers are correct. We focus on two further generalizations. Strong selective direct-products apply to algorithms that adaptively choose, based on what they learn from queries, which questions from a large list to answer. This generalization is relational and useful for proving time-space tradeoffs. We prove a quantum strong selective direct-product theorem for all functions using a new multiplicative adversary formulation for relations that satisfies a strong selective direct product property while being strong enough to capture any query lower bound for functions proven by negative-weights adversaries. This was not previously known even without selectivity. The second generalization is list-decoding direct product problems introduced by Ben-David and Blais for classical randomized query complexity. These allow an algorithm to produce a large list of possible output vectors such that one of them is fully correct. They proved that such theorems hold for classical randomized complexity of all Boolean functions. We prove a quantum analogue of this theorem for all partial Boolean functions. We show that strong list-decoding direct-product theorems are implied by a special case of multiplicative adversaries which we show, via a new reduction, can be obtained from negative-weights adversaries for any Boolean-valued function.

Authors: Markus Lohrey, Alexander Thumm

The input for the binary diameter problem consists of explicitly represented permutations generating a finite group $G$ and a binary-encoded nonnegative integer $k$. The question is whether every element of $G$ is a product of at most $k$ input generators. For the binary length problem, the input contains in addition a permutation $g \in G$ and it is asked whether $g$ is a product of at most $k$ input generators. We prove that the binary diameter problem is PSPACE-complete. When restricted to $2$-step nilpotent groups, the binary diameter problem is shown to be complete for $\mathsf{Π_2^P}$, whereas the binary length problem is shown to be NP-complete. Without the restriction to $2$-step nilpotent groups, the binary length problem is PSPACE-complete by a result of Jerrum.

Authors: Antonin Callard, Andrei Romashchenko, Véronique Terrier, Pascal Vanier

We introduce communication-complexity lifting techniques into the study of recognizable picture languages. As an application, we resolve a long-standing open problem of Anselmo et al. (2006) by constructing a language in UREC whose complement does not belong to REC. Our lower-bound argument is inspired by the communication-complexity approach to unambiguous automata of Göös et al. (2022), although its implementation in the setting of picture languages requires substantially different technical ingredients.

Authors: Gabriel Waite

We prove that deciding the Berry phase for parameterised 2-local qubit Hamiltonians is BQP-complete when presented with a classical description of a guiding state, promised to overlap with the ground state of the system. Our results extend to systems with weighted Heisenberg interactions and when restricted to a 2D square or triangular lattice geometry. The techniques we develop leverage the Schrieffer--Wolff transformation, typically used in the construction of perturbative gadget reductions for local Hamiltonian problems, extending it to parameterised families of Hamiltonians. We demonstrate that there exists a choice of parameterised simulator Hamiltonians whose Berry phase well-approximates that of a parameterised target family. Using the perturbative gadget reduction framework of Oliveira and Terhal and of Schuch and Verstraete, we adapt the arguments to parameterised interactions and demonstrate the error bounds in the resulting simulation can be controlled. Additionally, we provide an explicit proof that families of 1-local Hamiltonians have a Berry phase that can be efficiently computed to inverse-polynomial precision. This establishes a complexity transition between 1-local and 2-local Hamiltonian families.

Authors: Moritz Brösamle

We introduce latest exact match attention (LEMA), an attention variant for transformers where queries and keys are binarized and each query attends only to the latest exactly matching key. We prove that LEMA transformers with chain of thought can simulate word-RAMs, as was recently shown for the less restrictive rightmost hard attention. In contrast to prior hard attention variants, the restriction to exact matches enables an efficient converse direction: word-RAMs can simulate LEMA transformers at a cost per token independent of the context length. Together, these results yield a close correspondence between the two computational models in terms of both compute and memory. Beyond the theory, we propose a training method for LEMA transformers that handles their non-differentiable operations with a straight-through estimator for the binarization and a soft attention surrogate annealed towards LEMA. On a synthetic associative recall task, LEMA models trained this way use their growing state to store and recall a large number of associations, outperforming gated DeltaNet (GDN) with its fixed state size. As a first scaling test, we train LEMA language models with up to 834 million parameters. They match softmax transformers of around half their size in loss and, on repeated rare phrases and a needle-retrieval task, remain behind softmax transformers but recall across longer distances than GDN models of comparable size. Finally, we implement dictionary-based inference for LEMA transformers and show constant generation speed comparable to GDN despite their growing state, with the dictionaries residing in main memory rather than VRAM. Code is available at https://github.com/moritzbroe/latest_exact_match_attention.

Authors: Adam Bouland, Andrew Huang, Anand Natarajan, Itay Shalit, Avishay Tal

We construct an oracle relative to which $\mathsf{BQP} \not\subseteq \mathsf{IP}$, resolving a long-standing open question in quantum complexity theory. Together with recent work due to Aaronson et al., our work also gives the first oracle separation between $\mathsf{IP}$ and $\mathsf{MIP}$, answering a question dating back to Fortnow's thesis. Our separation is based on the Forrelation problem, where given Boolean functions $f$ and $g$, the goal is to determine if $f$ is correlated with the Fourier spectrum of $g$. While this task is solvable by a query-efficient quantum algorithm, we show that it admits no classical interactive protocol with polynomial communication and a polynomial-query verifier. Our proof is based on (i) a new structural result showing how to approximate Avg-Max circuits (which are well-known to capture the power of interactive proofs in the oracular setting) by convex functions with small first and second derivatives and (ii) a novel analysis establishing that the Forrelation distribution suggested by Aaronson and Ambainis fools such functions. Our results imply that any prover-efficient classical interactive protocol for $\mathsf{BQP}$ must rely on non-relativizing techniques. This might serve as a partial explanation for the lack of progress towards doubly-efficient, unconditionally sound classical verification of quantum computation.

Authors: Jean-Francois Biasse, Alexandra V. Hostetler, Anuvrat Jaindungarwal

We study the complexity of the Code Equivalence problem and show that it is polynomially equivalent to several computational automorphism problems for codes. These problems ask for the cardinality (ACOUNT), an orbit partition (APART), and a generating set (AGEN) for the permutation automorphism group of a code. We present deterministic, polynomial-time reductions between Permutation Code Equivalence (PCE) and each of these problems, including a one-shot reduction from search-PCE to AGEN that makes a single oracle call. We present similar reductions between Linear Code Equivalence (LCE) and analogous problems for the monomial automorphism group of a code. All of our reductions work for any linear codes.

Authors: Yan S. Couto, Cristina G. Fernandes

The $k$-core of a graph is its (unique) largest subgraph with minimum degree at least $k$. For any $k \geq 3$, deciding whether a given vertex belongs to the $k$-core is a P-complete problem, meaning that it is inherently sequential and highly unlikely to admit efficient parallel algorithms, even on graphs of maximum degree $k+1$. This paper investigates alternative parameterizations of the $k$-core problem to identify conditions under which it can be placed into sub-polynomial complexity classes. We prove that the problem is in para-NC$^{2+ε}$ when parameterized by treewidth, and in para-NC$^3$ when parameterized by $k$ on chordal graphs. Furthermore, we introduce a novel NC$^{3}$ algorithm for interval graphs when $k = \mathcal{O}(\lg v(G))$, which relies on an improved parameterization by pathwidth. Finally, we establish corresponding lower bounds, demonstrating that, even with these parameterizations, computing the $k$-core remains L-hard, meaning it requires at least logarithmic space. These findings explore the boundary of parallel tractability for the $k$-core problem by highlighting the graph parameters that make it inherently sequential.

Authors: Chris Dzoba

We exhibit simple, rotationally symmetric Venn diagrams with 17 curves and with 19 curves: n Jordan curves carried to one another by rotation through 2π/n, with every one of the 2^n regions present and connected and, since the diagrams are simple, every crossing on exactly two curves. Symmetric Venn diagrams exist for every prime number of curves (Griggs, Killian and Savage, 2004), but those diagrams have many curves through a point; simple ones were known only up to 13 curves (Mamakani and Ruskey, 2014). Four 17-curve and nine 19-curve diagrams were found by a Metropolis walk on rotation-invariant quadrangulations of the sphere in which regions may temporarily be duplicated, started from the Griggs-Killian-Savage diagram with its multiple crossings resolved. Every diagram is given by a machine-checkable certificate; one certificate of each size has been verified by a formal proof in Lean 4. All of the diagrams are non-monotone, which is why the crossing-sequence searches that found the 11- and 13-curve diagrams could not have found them.

Authors: Agustin Trujillo, Jose Pablo Suarez, Tania Moreno-García

We introduce a new formulation of the Longest Edge Bisection (LEB) of tetrahedra entirely in sextuple space R6, where tetrahedra are represented by the squares of their edge lengths. This representation renders the LEB refinement equations fully linear and eliminates the need for coordinate-based data structures. A central difficulty in three-dimensional LEB arises when a tetrahedron possesses multiple longest edges, making the refinement rule intrinsically multivalued. We formalize this phenomenon through the notion of Multiform Longest Edge Bisection (MLEB), which systematically explores all admissible longest-edge choices. To encode this multivalued behavior, we introduce the concept of bisection patterns, defined as sequences of sextuple permutations governing the refinement process. We prove that the set of sextuples sharing a common LEB pattern forms a convex region in R6. For structurally significant families of tetrahedra, including the R1+ family and the Liu-Joe family, we show that the infinite refinement tree collapses into a finite directed graph with eight states. Remarkably, both families are governed by the same graph, differing only in their initial state. This directed-graph formulation provides a unified combinatorial description of the refinement process and offers an efficient computational framework for deep iterative LEB analysis.

Authors: Oswin Aichholzer, Robert Ganian, Phillip Keldenich, Maarten Löffler, Gert Meijer, Ids de Vlas, Alexandra Weinberger, Carola Wenk

We study a finite tiling problem, where tiles are unit squares whose four edges are colored with one of two colors. We ask whether a given rectangle admits a perfect rectangular tiling: every cell of the rectangle is occupied by one tile, neighboring edge colors match, and exactly $n_i$ tiles of type $i$ are used, where rotations of the tiles are allowed. Our problem is related to classical Wang tilings, more general finite tile-placement problems, and edge placement puzzles. But in our problem, the multiplicities of the tile types are part of the input and the tile alphabet is fixed and extremely small; thus the complexity of the problem arises from the interaction between the rectangle dimensions and the prescribed tile multiplicities. We provide a comprehensive study of the perfect rectangular tiling problem. For this we consider all classes of subsets of the six possible tile types for two-colored edges, and we characterize for each class whether multiplicities either always allow a perfect rectangular tiling or whether their existence can be decided efficiently.

Authors: Bhaswar B. Bhattacharya, Sandip Das, Sk Samim Islam, Aashirwad Mohapatra, Saumya Sen

We prove that every sufficiently large finite planar point set contains either four collinear points or seven points with at most one non-visible pair. More generally, we show that for every fixed graph $H$ with chromatic number at most five, or with chromatic number six and a color-critical edge, the visibility graph of every sufficiently large finite planar point set with no four collinear points contains a copy of $H$. These results extend the recent breakthrough of Bonnet (2026), guaranteeing six pairwise visible points, and come within one visibility edge of the next open case of the big-line-big-clique conjecture.

Authors: Kenny Chen

A boolean function $f$ has Fourier dimension $k$ if its nonzero Fourier coefficients span a subspace of dimension $k$. We consider the property testing task of determining whether a function has Fourier dimension at most $k$, or is $ε$-far from being so. We show that there is a $Θ(k)$ quantum property tester for this problem. With Gopalan \etal's classical lower bound of $Ω(2^{k/2})$ for this task, this demonstrates an exponential quantum advantage for this task. We complement this result with a $\tilde{O}(2^{k/2}/ε)$ classical tester, improving the best known upper bound and thus showing the prior lower bound is essentially tight.

Authors: Ben Lee Volk

The Remote Point Problem (RPP) is an algorithmic problem that asks, given a linear subspace $L \subseteq \mathbb{F}^n$ of dimension $k$, to deterministically find a vector $v \in \mathbb{F}^n$ far in Hamming distance from $L$. This problem was introduced by Alon, Panigrahy and Yekhanin [APY09], motivated in part by the matrix rigidity approach for proving circuit lower bounds. An algorithm is said to achieve remoteness $d$ if it finds a vector $v$ whose Hamming distance from $L$ is at least $d$. We observe that over the rational numbers, the problem admits a deterministic polynomial-time algorithm that achieves optimal remoteness $n-k$. Over finite fields, we obtain a (modest) improvement of a result of Alon, Panigrahy and Yekhanin [APY09], and give an algorithm that achieves remoteness $Ω\left(\frac{n}{\max\{k, \log n\}} \log n\right)$.

Authors: Parth Gor, Sourya Roy, Kasturi Varadarajan

In the online metric matching problem, we have $n$ servers with known locations in some metric space. Requests arrive one-by-one at certain locations, and upon arrival a request must be matched to a server that was not matched to a previous request. The goal is to minimize the matching cost. For randomized algorithms with an oblivious adversary, the best known competitive ratio is obtained by embedding the metric space into an HST, and then solving the problem in the setting where the metric space is defined by the HST. Bansal et al. (Algorithmica, 2014) introduced a framework for online metric matching where one develops an algorithm in a restricted reassignment model, and then transforms this into a true online algorithm. Using this framework, they obtained an expected competitive ratio of $O(\log n)$ for HSTs; this also gives the best known competitive ratio of $O(\log^2 n)$ for general metrics. In this paper, we revisit this framework with the aim of developing new algorithms. For HSTs where each node has at most $Δ$ children, we develop an algorithm via this framework with an expected competitive ratio of $O((\log\log Δ) \cdot \log Δ)$. In particular, this ratio is independent of $n$, the number of servers/requests. It is near-optimal, as the expected competitive ratio of any algorithm is $Ω(\log Δ)$.

Authors: Eunjin Oh, Seongbin Park, Chanho Song

In this paper, we study the minimum-cost bipartite matching with penalties problem in metric spaces with bounded doubling dimension: Given two disjoint sets $R, B$ in a metric space $\mathcal{M}$ with $|R|+|B|=n$ and a penalty function $p \colon R \cup B \to \mathbb{R}_{\ge 0}$, the goal is to select a set of pairs in $R\times B$ so that every point belongs to at most one pair and the sum of the distances of the selected pairs and the penalties of the points not belonging to any pair is minimized. While near-linear time approximation algorithms are known for the minimum-cost perfect matching problem in geometric settings, no such algorithm was previously known for the penalty setting. We present a randomized algorithm that computes a $(1+\varepsilon)$-approximate minimum-cost bipartite matching with penalties in $O(n \mathrm{poly}(\log n, 1/\varepsilon))$ time with high probability. To the best of our knowledge, this is the first near-linear time approximation algorithm for the problem in the penalty setting.

Authors: Romain Cosson, Laurent Massoulié

We study asynchronous collective tree exploration, where $k$ agents with unrestricted communication start at the root of an unknown tree and discover edges online. At each step, an adversary chooses which agent moves. We give a deterministic algorithm that explores any tree with $n$ nodes and depth $D$ in at most \[ 2n+O\left(k\log^2(k)D\right) \] moves, matching known lower bounds up to a constant factor. As a direct consequence, we obtain a near-optimal competitive ratio of $O(\log^2 k)$ for synchronous collective tree exploration, where all agents move at each round. The proof relies on a multiscale power regularizer that may be of independent interest.

Authors: Arash Ahadi, Morteza Alimi, Sharareh Alipour, Shayan Tayefeh

In the unrestricted max--min metric $T$-join problem, one seeks an even terminal set $T$ maximizing the cost of a minimum $T$-join. Iwata and Ravi gave a factor-$3/2$ approximation for this problem. We show that this guarantee is tight under the Unique Games Conjecture: no polynomial-time approximation with factor strictly smaller than $3/2$ exists under UGC. We then consider the exact-cardinality variant, which prescribes an even number \(k\) of terminals. Writing \(p:=k/n\), we give a deterministic polynomial-time \(ρ(p)\)-approximation for every feasible cardinality, where \[ ρ(p)= \begin{cases} 7/2, & \makebox[1.5em][r]{$0$}

Authors: Nicola Rizzo, Sebastian Visan-Draghicescu, Nadia Pisanti, Veli Mäkinen

An Elastic Degenerate String (EDS, or ED-string) is a sequence of string sets. A pangenome, consisting of variations observed in a population along the genome sequences, can be naturally encoded as an EDS. Pattern matching and comparison problems on pangenome representations such as EDSes have been widely studied in the literature, but optimizing the pangenome properties during its construction has been largely omitted. We fill this gap by showing how methods originally developed for the related problem of founder reconstruction can be adapted to minimize, in linear time, the total cardinality of the EDS sets or the total size of the EDS strings, given suitable multiple alignments representing the input data. We provide an implementation for the minimum-cardinality criterion in a tool mincard, and conduct the first experiments on scalable pangenome optimization via EDSes. The code and experiments are available at https://github.com/algbio/eds.