Theory of Computing Report

Authors: Kaushik Sankar

We study the question of how much classical communication is needed when Alice is given a classical description of a quantum state $|\psi\rangle$ for Bob to recover any expectation value $\langle \psi | M |\psi\rangle$ given an observable $M$ with $M$ Hermitian and $||M||_{\text{op}} \leq 1$. This task, whose study was initiated by Raz (ACM 1999) and more recently investigated by Gosset and Smolin (TQC 2019), can be thought of as a fully classical version of the pure state case of the well-known classical shadows problem in quantum learning theory. We show how the hardness of these two seemingly distinct problems are connected. We first consider the relative error version of the communication question and prove a lower bound of $\Omega(\sqrt{2^{n}}\epsilon^{-2})$ on the one-way randomized classical communication, improving upon an additive error lower bound of $\Omega(\sqrt{2^{n}})$ as shown by Gosset and Smolin. Notably, we show that this lower bound holds not only for the set of all observables but also when restricted to just the class of Pauli observables. This fact implies a $\Omega(\sqrt{2^{n}})$ versus $O(\text{poly}(n))$ separation in the compression size between the relative and additive error settings for non-adaptive Pauli classical shadows with classical memory. Extending this framework, we prove randomized communication lower bounds for other relative error one-way classical communication tasks: an $\Omega(2^{n}\epsilon^{-2})$ lower bound when instead Alice is given an observable and Bob is given a quantum state and they are asked to estimate the expectation value, an $\Omega(\sqrt{n}\epsilon^{-2})$ lower bound when restricted to Paulis, and an $\Omega(\sqrt{2^{n}}\epsilon^{-2})$ lower bound when Alice and Bob are both given quantum states and asked to estimate the inner product.

Authors: Pablo Concha-Vega, Kévin Perrot

We investigate the computational complexity of the timed prediction problem in two-dimensional sandpile models. This question refines the classical prediction problem, which asks whether a cell q will eventually become unstable after adding a grain at cell p from a given configuration. The prediction problem has been shown to be P-complete in several settings, including for subsets of the Moore neighborhood, but its complexity for the von Neumann neighborhood remains open. In a previous work, we provided a complete characterization of crossover gates (a key to the implementation of non-planar monotone circuits) for these small neighborhoods, leading to P-completeness proofs with only 4 and 5 neighbors among the eight adjancent cells. In this paper, we introduce the timed setting, where the goal is to determine whether cell q becomes unstable exactly at time t. We distinguish several cases: some neighborhoods support complete timed toolkits (including timed crossover gates) and exhibit P-completeness; others admit timed crossovers but suffer from synchronization issues; planar neighborhoods provably do not admit any timed crossover; and finally, for some remaining neighborhoods, we conjecture that no timed crossover is possible.

Authors: Sándor P. Fekete, Kai Kobbe, Dominik Krupke, Joseph S. B. Mitchell, Christian Rieck, Christian Scheffer

We investigate the Dispersive Art Gallery Problem with vertex guards and rectangular visibility ($r$-visibility) for a class of orthogonal polygons that reflect the properties of real-world floor plans: these office-like polygons consist of rectangular rooms and corridors. In the dispersive variant of the Art Gallery Problem, the objective is not to minimize the number of guards but to maximize the minimum geodesic $L_1$-distance between any two guards, called the dispersion distance. Our main contributions are as follows. We prove that determining whether a vertex guard set can achieve a dispersion distance of $4$ in office-like polygons is NP-complete, where vertices of the polygon are restricted to integer coordinates. Additionally, we present a simple worst-case optimal algorithm that guarantees a dispersion distance of $3$ in polynomial time. Our complexity result extends to polyominoes, resolving an open question posed by Rieck and Scheffer (CGTA 2024). When vertex coordinates are allowed to be rational, we establish analogous results, proving that achieving a dispersion distance of $2+\varepsilon$ is NP-hard for any $\varepsilon > 0$, while the classic Art Gallery Problem remains solvable in polynomial time for this class of polygons. Furthermore, we give a straightforward polynomial-time algorithm that computes worst-case optimal solutions with a dispersion distance of $2$. On the other hand, for the more restricted class of hole-free independent office-like polygons, we propose a dynamic programming approach that computes optimal solutions. Moreover, we demonstrate that the problem is practically tractable for arbitrary orthogonal polygons. To this end, we compare solvers based on SAT, CP, and MIP formulations. Notably, SAT solvers efficiently compute optimal solutions for randomly generated instances with up to $1600$ vertices in under $15$s.

Authors: Ziad Ismaili Alaoui, Namrata, Sebastian Wild

Computing over compressed data combines the space saving of data compression with efficient support for queries directly on the compressed representation. Such data structures are widely applied in text indexing and have been successfully generalised to trees. For graphs, support for computing over compressed data remains patchy; typical results in the area of succinct data structures are restricted to a specific class of graphs and use the same, worst-case amount of space for any graph from this class. In this work, we design a data structure whose space usage automatically improves with the compressibility of the graph at hand, while efficiently supporting navigational operations (simulating adjacency-list access). Specifically, we show that the space usage approaches the instance-optimal space when the graph is drawn according to the classic Barab\'asi-Albert model of preferential-attachment graphs. Our data-structure techniques also work for arbitrary graphs, guaranteeing a size asymptotically no larger than an entropy-compressed edge list. A key technical contribution is the careful analysis of the instance-optimal space usage.

Authors: Vikrant Ashvinkumar, Rezaul Chowdhury, Jie Gao, Mayank Goswami, Joseph S. B. Mitchell, Valentin Polishchuk

Motivated by the problem of estimating bottleneck capacities on the Internet, we formulate and study the problem of vantage point selection. We are given a graph $G=(V, E)$ whose edges $E$ have unknown capacity values that are to be discovered. Probes from a vantage point, i.e, a vertex $v \in V$, along shortest paths from $v$ to all other vertices, reveal bottleneck edge capacities along each path. Our goal is to select $k$ vantage points from $V$ that reveal the maximum number of bottleneck edge capacities. We consider both a non-adaptive setting where all $k$ vantage points are selected before any bottleneck capacity is revealed, and an adaptive setting where each vantage point selection instantly reveals bottleneck capacities along all shortest paths starting from that point. In the non-adaptive setting, by considering a relaxed model where edge capacities are drawn from a random permutation (which still leaves the problem of maximizing the expected number of revealed edges NP-hard), we are able to give a $1-1/e$ approximate algorithm. In the adaptive setting we work with the least permissive model where edge capacities are arbitrarily fixed but unknown. We compare with the best solution for the particular input instance (i.e. by enumerating all choices of $k$ tuples), and provide both lower bounds on instance optimal approximation algorithms and upper bounds for trees and planar graphs.

Authors: Fedor V. Fomin, Petr A. Golovach, Danil Sagunov, Kirill Simonov

Covering and partitioning the edges of a graph into cliques are classical problems at the intersection of combinatorial optimization and graph theory, having been studied through a range of algorithmic and complexity-theoretic lenses. Despite the well-known fixed-parameter tractability of these problems when parameterized by the total number of cliques, such a parameterization often fails to be meaningful for sparse graphs. In many real-world instances, on the other hand, the minimum number of cliques in an edge cover or partition can be very close to the size of a maximum independent set \alpha(G). Motivated by this observation, we investigate above \alpha parameterizations of the edge clique cover and partition problems. Concretely, we introduce and study Edge Clique Cover Above Independent Set (ECC/\alpha) and Edge Clique Partition Above Independent Set (ECP/\alpha), where the goal is to cover or partition all edges of a graph using at most \alpha(G) + k cliques, and k is the parameter. Our main results reveal a distinct complexity landscape for the two variants. We show that ECP/\alpha is fixed-parameter tractable, whereas ECC/\alpha is NP-complete for all k \geq 2, yet can be solved in polynomial time for k \in {0,1}. These findings highlight intriguing differences between the two problems when viewed through the lens of parameterization above a natural lower bound. Finally, we demonstrate that ECC/\alpha becomes fixed-parameter tractable when parameterized by k + \omega(G), where \omega(G) is the size of a maximum clique of the graph G. This result is particularly relevant for sparse graphs, in which \omega is typically small. For H-minor free graphs, we design a subexponential algorithm of running time f(H)^{\sqrt{k}}n^{O(1)}.

Authors: Alexander Dobler, Martin Nöllenburg

Stacked area charts are a widely used visualization technique for numerical time series. The x-axis represents time, and the time series are displayed as horizontal, variable-height layers stacked on top of each other. The height of each layer corresponds to the time series values at each time point. The main aesthetic criterion for optimizing the readability of stacked area charts is the amount of vertical change of the borders between the time series in the visualization, called wiggle. While many heuristic algorithms have been developed to minimize wiggle, the computational complexity of minimizing wiggle has not been formally analyzed. In this paper, we show that different variants of wiggle minimization are NP-hard and even hard to approximate. We also present an exact mixed-integer linear programming formulation and compare its performance with a state-of-the-art heuristic in an experimental evaluation. Lastly, we consider a special case of wiggle minimization that corresponds to the fundamentally interesting and natural problem of ordering a set of numbers as to minimize their sum of absolute prefix sums. We show several complexity results for this problem that imply some of the mentioned hardness results for wiggle minimization.

Authors: Tatsuya Gima, Soh Kumabe, Yuichi Yoshida

Lipschitz continuity of algorithms, introduced by Kumabe and Yoshida (FOCS'23), measures the stability of an algorithm against small input perturbations. Algorithms with small Lipschitz continuity are desirable, as they ensure reliable decision-making and reproducible scientific research. Several studies have proposed Lipschitz continuous algorithms for various combinatorial optimization problems, but these algorithms are problem-specific, requiring a separate design for each problem. To address this issue, we provide the first algorithmic meta-theorem in the field of Lipschitz continuous algorithms. Our result can be seen as a Lipschitz continuous analogue of Courcelle's theorem, which offers Lipschitz continuous algorithms for problems on bounded-treewidth graphs. Specifically, we consider the problem of finding a vertex set in a graph that maximizes or minimizes the total weight, subject to constraints expressed in monadic second-order logic (MSO_2). We show that for any $\varepsilon>0$, there exists a $(1\pm \varepsilon)$-approximation algorithm for the problem with a polylogarithmic Lipschitz constant on bounded treewidth graphs. On such graphs, our result outperforms most existing Lipschitz continuous algorithms in terms of approximability and/or Lipschitz continuity. Further, we provide similar results for problems on bounded-clique-width graphs subject to constraints expressed in MSO_1. Additionally, we construct a Lipschitz continuous version of Baker's decomposition using our meta-theorem as a subroutine.

Authors: Gleb Smirnov, Roman Vershynin

The discrepancy between two independent samples \(X_1,\dots,X_n\) and \(Y_1,\dots,Y_n\) drawn from the same distribution on $\mathbb{R}^d$ typically has order \(O(\sqrt{n})\) even in one dimension. We give a simple online algorithm that reduces the discrepancy to \(O(\log^{2d} n)\) by discarding a small fraction of the points.

Authors: Nikhil Kumar, Chaitanya Swamy

We consider the \emph{$k$-edge connected spanning subgraph} (kECSS) problem, where we are given an undirected graph $G = (V, E)$ with nonnegative edge costs $\{c_e\}_{e\in E}$, and we seek a minimum-cost \emph{$k$-edge connected} subgraph $H$ of $G$. For even $k$, we present a polytime algorithm that computes a $(k-2)$-edge connected subgraph of cost at most the optimal value $LP^*$ of the natural LP-relaxation for kECSS; for odd $k$, we obtain a $(k-3)$-edge connected subgraph of cost at most $LP^*$. Since kECSS is APX-hard for all $k\geq 2$, our results are nearly optimal. They also significantly improve upon the recent work of Hershkowitz et al., both in terms of solution quality and the simplicity of algorithm and its analysis. Our techniques also yield an alternate guarantee, where we obtain a $(k-1)$-edge connected subgraph of cost at most $1.5\cdot LP^*$; with unit edge costs, the cost guarantee improves to $(1+\frac{4}{3k})\cdot LP^*$, which improves upon the state-of-the-art approximation for unit edge costs, but with a unit loss in edge connectivity. Our kECSS-result also yields results for the \emph{$k$-edge connected spanning multigraph} (kECSM) problem, where multiple copies of an edge can be selected: we obtain a $(1+2/k)$-approximation algorithm for even $k$, and a $(1+3/k)$-approximation algorithm for odd $k$. Our techniques extend to the degree-bounded versions of kECSS and kECSM, wherein we also impose degree lower- and upper- bounds on the nodes. We obtain the same cost and connectivity guarantees for these degree-bounded versions with an additive violation of (roughly) $2$ for the degree bounds. These are the first results for degree-bounded \{kECSS,kECSM\} of the form where the cost of the solution obtained is at most the optimum, and the connectivity constraints are violated by an additive constant.

Authors: Pranay Mundra, Charalampos Papamanthou, Julian Shun, Quanquan C. Liu

The rise of massive networks across diverse domains necessitates sophisticated graph analytics, often involving sensitive data and raising privacy concerns. This paper addresses these challenges using local differential privacy (LDP), which enforces privacy at the individual level, where no third-party entity is trusted, unlike centralized models that assume a trusted curator. We introduce novel LDP algorithms for two fundamental graph statistics: k-core decomposition and triangle counting. Our approach leverages input-dependent private graph properties, specifically the degeneracy and maximum degree of the graph, to improve theoretical utility. Unlike prior methods, our error bounds are determined by the maximum degree rather than the total number of edges, resulting in significantly tighter guarantees. For triangle counting, we improve upon the work of Imola, Murakami, and Chaudhury~\cite{IMC21locally, IMC21communication}, which bounds error in terms of edge count. Instead, our algorithm achieves bounds based on graph degeneracy by leveraging a private out-degree orientation, a refined variant of Eden et al.'s randomized response technique~\cite{ELRS23, and a novel analysis, yielding stronger guarantees than prior work. Beyond theoretical gains, we are the first to evaluate local DP algorithms in a distributed simulation, unlike prior work tested on a single processor. Experiments on real-world graphs show substantial accuracy gains: our k-core decomposition achieves errors within 3x of exact values, far outperforming the 131x error in the baseline of Dhulipala et al.~\cite{DLRSSY22}. Our triangle counting algorithm reduces multiplicative approximation errors by up to six orders of magnitude, while maintaining competitive runtime.

Authors: Alexandr Andoni, Shunhua Jiang, Omri Weinstein

We present a general framework for designing efficient data structures for high-dimensional pattern-matching problems ($\exists \;? i\in[n], f(x_i,y)=1$) through communication models in which $f(x,y)$ admits sublinear communication protocols with exponentially-small error. Specifically, we reduce the data structure problem to the Unambiguous Arthur-Merlin (UAM) communication complexity of $f(x,y)$ under product distributions. We apply our framework to the Partial Match problem (a.k.a, matching with wildcards), whose underlying communication problem is sparse set-disjointness. When the database consists of $n$ points in dimension $d$, and the number of $\star$'s in the query is at most $w = c\log n \;(\ll d)$, the fastest known linear-space data structure (Cole, Gottlieb and Lewenstein, STOC'04) had query time $t \approx 2^w = n^c$, which is nontrivial only when $c<1$. By contrast, our framework produces a data structure with query time $n^{1-1/(c \log^2 c)}$ and space close to linear. To achieve this, we develop a one-sided $\epsilon$-error communication protocol for Set-Disjointness under product distributions with $\tilde{\Theta}(\sqrt{d\log(1/\epsilon)})$ complexity, improving on the classical result of Babai, Frankl and Simon (FOCS'86). Building on this protocol, we show that the Unambiguous AM communication complexity of $w$-Sparse Set-Disjointness with $\epsilon$-error under product distributions is $\tilde{O}(\sqrt{w \log(1/\epsilon)})$, independent of the ambient dimension $d$, which is crucial for the Partial Match result. Our framework sheds further light on the power of data-dependent data structures, which is instrumental for reducing to the (much easier) case of product distributions.

Alberto Fraile and Daniel Fernández guest post on random walks generated by the distribution of prime numbers.

In our recent papers, we explored the sequence of prime numbers by defining "random walks" governed by simple algorithms applied to their sequence.

We introduced a prime number visualization called Jacob’s Ladder. The algorithm plots numbers on a 2D graph that oscillates up and down based on the presence of prime numbers, creating a ladder-like structure. The path ascends or descends based on the primality of subsequent numbers. When a prime number is encountered, the path alters direction, leading to a zig-zag pattern. Number 2 is prime, so it flips and goes down. Now 3 is prime, so the next step changes direction and goes up again, so we move up. But 4 is not a prime, so it continues up, and on it goes.

Jacob’s Ladder from 1 to 100,000 (Top) and from 1 to 1,000,000 (Bottom). The blue line represents y=0, or sea level.

The x-axis can be imagined as sea level, the zig-zag above it as mountains, and those below as ocean chasms. Our intrepid navigator sails eastward, occasionally discovering new lands—sometimes tiny islands, other times vast continents.

As we chart this new world, it is natural to wonder about the location of the next continent (if any), the height of its highest mountain, or the depth of its deepest ocean. One thing we know for sure is that gaps between primes can become arbitrarily large. This suggests there may be no upper bound on the mountains’ heights or the chasms’ depths.

A natural question arises: if the voyage continues into infinity, would this world contain equal amounts of land and sea? Or, more formally, does the construction exhibit symmetry in the limit, with equal numbers of positive and negative points? The beauty of Jacob’s Ladder lies in its simplicity, yet it raises many questions that are surprisingly difficult to answer.

Prime Walk

In our second study, we examined the behavior of a 2D "random walk" determined by the sequence of prime numbers, known as the prime walk (PW), choosing a direction based on the last digit of the next prime (1 down, 3 up, 7 right, 9 left) ignoring the primes 2 and 5.

Graphical representation of three different PWs up to N=108. Color coding represents step progression.

Observing the PW in action raises numerous questions.

For instance, will this PW eventually cover the entire plane as N → ∞? Will the area explored continue expanding indefinitely, or will it reach a limit? Initially, we conjectured the area would be unbounded.

We thought this conjecture might remain unanswered indefinitely, so we challenged the community with a modest prize for anyone who could prove it within two years of publication. Surprisingly, we found the solution ourselves, detailed in our recent work.

Moreover, within the explored region, certain points remain unvisited—small regions or isolated spots. Could some points remain unreachable forever? These straightforward questions, intriguingly, remain remarkably difficult to answer.

By Lance Fortnow

Authors: Malik Magdon-Ismail, Khai Dong

Period finding and phase estimation are fundamental in quantum computing. Prior work has established lower bounds on their success probabilities. We improve these results by deriving tight upper and lower bounds on the success probability that converge to 1.

Authors: Jan Krajicek

Motivated by the theory of proof complexity generators we consider the following $\Sigma^p_2$ search problem $\mbox{DD}_P$ determined by a propositional proof system $P$: given a $P$-proof $\pi$ of a disjunction $\bigvee_i \alpha_i$, no two $\alpha_i$ having an atom in common, find $i$ such that $\alpha_i \in \mbox{TAUT}$. We formulate a hypothesis (ST) that for some strong proof system $P$ the problem $\mbox{DD}_P$ is not solvable in the student-teacher model with a p-time student and a constant number of rounds. The hypothesis follows from the existence of hard one-way permutations. We prove, using a model-theoretic assumption, that (ST) implies $NP \neq coNP$. The assumption concerns the existence of extensions of models of a bounded arithmetic theory and it is open at present if it holds.

Authors: Arash Vaezi

We address the problem of covering a target segment $\overline{uv}$ using a finite set of guards $\mathcal{S}$ placed on a source segment $\overline{xy}$ within a simple polygon $\mathcal{P}$, assuming weak visibility between the target and source. Without geometric constraints, $\mathcal{S}$ may be infinite, as shown by prior hardness results. To overcome this, we introduce the {\it line aspect ratio} (AR), defined as the ratio of the \emph{long width} (LW) to the \emph{short width} (SW) of $\mathcal{P}$. These widths are determined by parallel lines tangent to convex vertices outside $\mathcal{P}$ (LW) and reflex vertices inside $\mathcal{P}$ (SW), respectively. Under the assumption that AR is constant or polynomial in $n$ (the polygon's complexity), we prove that a finite guard set $\mathcal{S}$ always exists, with size bounded by $\mathcal{O}(\text{AR})$. This AR-based framework generalizes some previous assumptions, encompassing a broader class of polygons. Our result establishes a framework guaranteeing finite solutions for segment guarding under practical and intuitive geometric constraints.

Authors: Marco Ricci, Jonathan Rollin, André Schulz, Alexandra Weinberger

A geometric graph is a drawing of a graph in the plane where the vertices are drawn as points in general position and the edges as straight-line segments connecting their endpoints. It is plane if it contains no crossing edges. We study plane cycles in geometric complete multipartite graphs. We prove that if a geometric complete multipartite graph contains a plane cycle of length $t$, with $t \geq 6$, it also contains a smaller plane cycle of length at least $\lfloor t/2\rfloor + 1$. We further give a characterization of geometric complete multipartite graphs that contain plane cycles with a color class appearing at least twice. For geometric drawings of $K_{n,n}$, we give a sufficient condition under which they have, for each $s \leq n$, a plane cycle of length 2s. We also provide an algorithm to decide whether a given geometric drawing of $K_{n,n}$ contains a plane Hamiltonian cycle in time $O(n \log n + nk^2) + O(k^{5k})$, where k is the number of vertices inside the convex hull of all vertices. Finally, we prove that it is NP-complete to decide if a subset of edges of a geometric complete bipartite graph H is contained in a plane Hamiltonian cycle in H.

Authors: Jasmine George, Oscar Lledo Osborn, Elizabeth Munch, Messiah Ridgley II, Elena Xinyi Wang

The Euler Characteristic Transform (ECT) is a robust method for shape classification. It takes an embedded shape and, for each direction, computes a piecewise constant function representing the Euler Characteristic of the shape's sublevel sets, which are defined by the height function in that direction. It has applications in TDA inverse problems, such as shape reconstruction, and is also employed with machine learning methodologies. In this paper, we define a distance between the ECTs of two distinct geometric embeddings of the same abstract simplicial complex and provide an upper bound for this distance. The Super Lifted Euler Characteristic Transform (SELECT), a related construction, extends the ECT to scalar fields defined on shapes. We establish a similar distance bound for SELECT, specifically when applied to fields defined on embedded simplicial complexes.

Authors: Yotam Kenneth-Mordoch, Robert Krauthgamer

In the cut-query model, the algorithm can access the input graph $G=(V,E)$ only via cut queries that report, given a set $S\subseteq V$, the total weight of edges crossing the cut between $S$ and $V\setminus S$. This model was introduced by Rubinstein, Schramm and Weinberg [ITCS'18] and its investigation has so far focused on the number of queries needed to solve optimization problems, such as global minimum cut. We turn attention to the round complexity of cut-query algorithms, and show that several classical problems can be solved in this model with only a constant number of rounds. Our main results are algorithms for finding a minimum cut in a graph, that offer different tradeoffs between round complexity and query complexity, where $n=|V|$ and $\delta(G)$ denotes the minimum degree of $G$: (i) $\tilde{O}(n^{4/3})$ cut queries in two rounds in unweighted graphs; (ii) $\tilde{O}(rn^{1+1/r}/\delta(G)^{1/r})$ queries in $2r+1$ rounds for any integer $r\ge 1$ again in unweighted graphs; and (iii) $\tilde{O}(rn^{1+(1+\log_n W)/r})$ queries in $4r+3$ rounds for any $r\ge1$ in weighted graphs. We also provide algorithms that find a minimum $(s,t)$-cut and approximate the maximum cut in a few rounds.

Authors: Lorenzo Bini, Stephane Marchand-Maillet

We present LaplaceGNN, a novel self-supervised graph learning framework that bypasses the need for negative sampling by leveraging spectral bootstrapping techniques. Our method integrates Laplacian-based signals into the learning process, allowing the model to effectively capture rich structural representations without relying on contrastive objectives or handcrafted augmentations. By focusing on positive alignment, LaplaceGNN achieves linear scaling while offering a simpler, more efficient, self-supervised alternative for graph neural networks, applicable across diverse domains. Our contributions are twofold: we precompute spectral augmentations through max-min centrality-guided optimization, enabling rich structural supervision without relying on handcrafted augmentations, then we integrate an adversarial bootstrapped training scheme that further strengthens feature learning and robustness. Our extensive experiments on different benchmark datasets show that LaplaceGNN achieves superior performance compared to state-of-the-art self-supervised graph methods, offering a promising direction for efficiently learning expressive graph representations.

Authors: Xiaoyu Li, Zhao Song, Jiahao Zhang

The explosive growth of AI research has driven paper submissions at flagship AI conferences to unprecedented levels, necessitating many venues in 2025 (e.g., CVPR, ICCV, KDD, AAAI, IJCAI, WSDM) to enforce strict per-author submission limits and to desk-reject any excess papers by simple ID order. While this policy helps reduce reviewer workload, it may unintentionally discard valuable papers and penalize authors' efforts. In this paper, we ask an essential research question on whether it is possible to follow submission limits while minimizing needless rejections. We first formalize the current desk-rejection policies as an optimization problem, and then develop a practical algorithm based on linear programming relaxation and a rounding scheme. Under extensive evaluation on 11 years of real-world ICLR (International Conference on Learning Representations) data, our method preserves up to $19.23\%$ more papers without violating any author limits. Moreover, our algorithm is highly efficient in practice, with all results on ICLR data computed within at most 53.64 seconds. Our work provides a simple and practical desk-rejection strategy that significantly reduces unnecessary rejections, demonstrating strong potential to improve current CS conference submission policies.

Authors: Hiroki Shibata, Yuto Nakashima, Yutaro Yamaguchi, Shunsuke Inenaga

An LZ-like factorization of a string is a factorization in which each factor is either a single character or a copy of a substring that occurs earlier in the string. While grammar-based compression schemes support efficient random access with linear space in the size of the compressed representation, such methods are not known for general LZ-like factorizations. This has led to the development of restricted LZ-like schemes such as LZ-End [Kreft and Navarro, 2013] and height-bounded (LZHB) [Bannai et al., 2024], which trade off some compression efficiency for faster access. We introduce LZ-Start-End (LZSE), a new variant of LZ-like factorizations in which each copy factor refers to a contiguous sequence of preceding factors. By its nature, any context-free grammar can easily be converted into an LZSE factorization of equal size. Further, we study the greedy LZSE factorization, in which each copy factor is taken as long as possible. We show how the greedy LZSE factorization can be computed in linear time with respect to the input string length, and that there exists a family of strings for which the size of the greedy LZSE factorization is of strictly lower order than that of the smallest grammar. These imply that our LZSE scheme is stronger than grammar-based compressions in the context of repetitiveness measures. To support fast queries, we propose a data structure for LZSE-compressed strings that permits $O(\log n)$-time random access within space linear in the compressed size, where $n$ is the length of the input string.

Authors: Robin Bowers, Marius Garbea, Emmanouil Pountourakis, Samuel Taggart

This paper derives polynomial-time approximation schemes for several NP-hard stochastic optimization problems from the algorithmic mechanism design and operations research literatures. The problems we consider involve a principal or seller optimizing with respect to a subsequent choice by an agent or buyer. These include posted pricing for a unit-demand buyer with independent values (Chawla et al., 2007, Cai and Daskalakis, 2011), assortment optimization with independent utilities (Talluri and van Ryzin, 2004), and delegated choice (Khodabakhsh et al., 2024). Our results advance the state of the art for each of these problems. For unit-demand pricing with discrete distributions, our multiplicative PTAS improves on the additive PTAS of Cai and Daskalakis, and we additionally give a PTAS for the unbounded regular case, improving on the latter paper's QPTAS. For assortment optimization, no constant approximation was previously known. For delegated choice, we improve on both the $3$-approximation for the case with no outside option and the super-constant-approximation with an outside option. A key technical insight driving our results is an economically meaningful property we term utility alignment. Informally, a problem is utility aligned if, at optimality, the principal derives most of their utility from realizations where the agent's utility is also high. Utility alignment allows the algorithm designer to focus on maximizing performance on realizations with high agent utility, which is often an algorithmically simpler task. We prove utility alignment results for all the problems mentioned above, including strong results for unit-demand pricing and delegation, as well as a weaker but very broad guarantee that holds for many other problems under very mild conditions.

Authors: Amir Abboud, Nick Fischer, Ce Jin, Virginia Vassilevska Williams, Zoe Xi

We study the central All-Pairs Shortest Paths (APSP) problem under the restriction that there are at most $d$ distinct weights on the outgoing edges from every node. For $d=n$ this is the classical (unrestricted) APSP problem that is hypothesized to require cubic time $n^{3-o(1)}$, and at the other extreme, for $d=1$, it is equivalent to the Node-Weighted APSP problem. We present new algorithms that achieve the following results: 1. Node-Weighted APSP can be solved in time $\tilde{O}(n^{(3+\omega)/2}) = \tilde{O}(n^{2.686})$, improving on the 15-year-old subcubic bounds $\tilde{O}(n^{(9+\omega)/4}) = \tilde{O}(n^{2.843})$ [Chan; STOC '07] and $\tilde{O}(n^{2.830})$ [Yuster; SODA '09]. This positively resolves the question of whether Node-Weighted APSP is an ``intermediate'' problem in the sense of having complexity $n^{2.5+o(1)}$ if $\omega=2$, in which case it also matches an $n^{2.5-o(1)}$ conditional lower bound. 2. For up to $d \leq n^{3-\omega-\epsilon}$ distinct weights per node (where $\epsilon > 0$), the problem can be solved in subcubic time $O(n^{3-f(\epsilon)})$ (where $f(\epsilon) > 0$). In particular, assuming that $\omega = 2$, we can tolerate any sublinear number of distinct weights per node $d \leq n^{1-\epsilon}$, whereas previous work [Yuster; SODA '09] could only handle $d \leq n^{1/2-\epsilon}$ in subcubic time. This promotes our understanding of the APSP hypothesis showing that the hardest instances must exhaust a linear number of weights per node. Our result also applies to the All-Pairs Exact Triangle problem, thus generalizing a result of Chan and Lewenstein on "Clustered 3SUM" from arrays to matrices. Notably, our technique constitutes a rare application of additive combinatorics in graph algorithms.

Authors: Russell A. Brown

The original description of the k-d tree recognized that rebalancing techniques, such as used to build an AVL tree or a red-black tree, are not applicable to a k-d tree. Hence, in order to build a balanced k-d tree, it is necessary to find the median of a set of data for each recursive subdivision of that set. The sort or selection used to find the median, and the technique used to partition the set about that median, strongly influence the computational complexity of building a k-d tree. This article describes and contrasts three variants of the k-d tree that differ in their technique used to partition the set, and compares the performance of those variants. In addition, dual-threaded execution is proposed and analyzed for one of the three variants.

Authors: Kartik Anand, Kabgyun Jeong, Junseo Lee

We investigate structural properties of quantum proof systems by establishing collapse results that uncover simplifications in their complexity landscape. We extend classical results such as the Karp-Lipton theorem to quantum polynomial hierarchy with quantum proofs and establish uniqueness preservation for quantum-classical probabilistically checkable proof systems. Our main contributions are threefold. First, we prove that restricting quantum-classical PCP systems to uniqueness does not reduce computational power: $\mathsf{UniqueQCPCP} = \mathsf{QCPCP}$ under $\mathsf{BQ}$-operator and randomized reductions, demonstrating robustness similar to the $\mathsf{UniqueQCMA} = \mathsf{QCMA}$ result. Second, we establish a non-uniform quantum analogue of the Karp-Lipton theorem, showing that if $\mathsf{QMA} \subseteq \mathsf{BQP}/\mathsf{qpoly}$, then $\mathsf{QPH} \subseteq \mathsf{Q\Sigma}_2/\mathsf{qpoly}$, extending the classical collapse theorem to quantum complexity with quantum advice. Third, we introduce a consistent variant of the quantum polynomial hierarchy ($\mathsf{CQPH}$) with consistency constraints across interaction rounds while maintaining product-state proofs, proving its unconditional collapse $\mathsf{CQPH} = \mathsf{CQ\Sigma}_2$. This contrasts with prior work on quantum-entangled polynomial hierarchy, showing that consistency rather than entanglement drives the collapse. These results contribute to understanding structural boundaries in quantum complexity theory and the interplay between constraint types in quantum proof systems.

Authors: Gwendal Ducloz, Ahmed Shalaby, Damien Woods

To understand and engineer biological and artificial nucleic acid systems, algorithms are employed for prediction of secondary structures at thermodynamic equilibrium. Dynamic programming algorithms are used to compute the most favoured, or Minimum Free Energy (MFE), structure, and the Partition Function (PF), a tool for assigning a probability to any structure. However, in some situations, such as when there are large numbers of strands, or pseudoknoted systems, NP-hardness results show that such algorithms are unlikely, but only for MFE. Curiously, algorithmic hardness results were not shown for PF, leaving two open questions on the complexity of PF for multiple strands and single strands with pseudoknots. The challenge is that while the MFE problem cares only about one, or a few structures, PF is a summation over the entire secondary structure space, giving theorists the vibe that computing PF should not only be as hard as MFE, but should be even harder. We answer both questions. First, we show that computing PF is #P-hard for systems with an unbounded number of strands, answering a question of Condon Hajiaghayi, and Thachuk [DNA27]. Second, for even a single strand, but allowing pseudoknots, we find that PF is #P-hard. Our proof relies on a novel magnification trick that leads to a tightly-woven set of reductions between five key thermodynamic problems: MFE, PF, their decision versions, and #SSEL that counts structures of a given energy. Our reductions show these five problems are fundamentally related for any energy model amenable to magnification. That general classification clarifies the mathematical landscape of nucleic acid energy models and yields several open questions.

Authors: C. S. Bhargav, Prateek Dwivedi, Nitin Saxena

Polynomial factorization is a fundamental problem in computational algebra. Over the past half century, a variety of algorithmic techniques have been developed to tackle different variants of this problem. In parallel, algebraic complexity theory classifies polynomials into complexity classes based on their perceived `hardness'. This raises a natural question: Do these classes afford efficient factorization? In this survey, we revisit two pivotal techniques in polynomial factorization: Hensel lifting and Newton iteration. Though they are variants of the same theme, their distinct applications across the literature warrant separate treatment. These techniques have played an important role in resolving key factoring questions in algebraic complexity theory. We examine and organise the known results through the lens of these techniques to highlight their impact. We also discuss their equivalence while reflecting on how their use varies with the context of the problem. We focus on four prominent complexity classes: circuits of polynomial size ($\text{VP}_{\text{nb}}$), circuits with both polynomial size and degree (VP and its border $\overline{\text{VP}}$), verifier circuits of polynomial size and degree (VNP), and polynomial-size algebraic branching programs (VBP). We also examine more restricted models, such as formulas and bounded-depth circuits. Along the way, we list several open problems that remain unresolved.

Authors: Tomoyuki Morimae, Yuki Shirakawa, Takashi Yamakawa

Indistinguishability obfuscation (iO) has emerged as a powerful cryptographic primitive with many implications. While classical iO, combined with the infinitely-often worst-case hardness of $\mathsf{NP}$, is known to imply one-way functions (OWFs) and a range of advanced cryptographic primitives, the cryptographic implications of quantum iO remain poorly understood. In this work, we initiate a study of the power of quantum iO. We define several natural variants of quantum iO, distinguished by whether the obfuscation algorithm, evaluation algorithm, and description of obfuscated program are classical or quantum. For each variant, we identify quantum cryptographic primitives that can be constructed under the assumption of quantum iO and the infinitely-often quantum worst-case hardness of $\mathsf{NP}$ (i$.$e$.$, $\mathsf{NP}$ $\not\subseteq$ $\mathsf{i.o.BQP}$). In particular, we construct pseudorandom unitaries, QCCC quantum public-key encryption and (QCCC) quantum symmetric-key encryption, and several primitives implied by them such as one-way state generators, (efficiently-verifiable) one-way puzzles, and EFI pairs, etc. While our main focus is on quantum iO, even in the classical setting, our techniques yield a new and arguably simpler construction of OWFs from classical (imperfect) iO and the infinitely-often worst-case hardness of $\mathsf{NP}$.

Authors: Lumi Christensen, Thomas C. Hull, Emma O'Neil, Valentina Pappano, Natalya Ter-Saakov, Kacey Yang

Given an origami crease pattern $C=(V,E)$, a straight-line planar graph embedded in a region of $\mathbb{R}^2$, we assign each crease to be either a mountain crease (which bends convexly) or a valley crease (which bends concavely), creating a mountain-valley (MV) assignment $\mu:E\to\{-1,1\}$. An MV assignment $\mu$ is locally valid if the faces around each vertex in $C$ can be folded flat under $\mu$. In this paper, we investigate locally valid MV assignments of the Miura-ori, $M_{m,n}$, an $m\times n$ parallelogram tessellation used in numerous engineering applications. The origami flip graph $OFG(C)$ of $C$ is a graph whose vertices are locally valid MV assignments of $C$, and two vertices are adjacent if they differ by a face flip, an operation that swaps the MV-parity of every crease bordering a given face of $C$. We enumerate the number of vertices and edges in $OFG(M_{2,n})$ and prove several facts about the degrees of vertices in $OFG(M_{2,n})$. By finding recurrence relations, we show that the number of vertices of degree $d$ and $2n-a$ (for $0\leq a$) are both described by polynomials of particular degrees. We then prove that the diameter of $OFG(M_{2,n})$ is $\lceil \frac{n^2}{2}\rceil$ using techniques from 3-coloring reconfiguration graphs.

Authors: Marat Zaidyn, Sayat Akhtanov, Dana Turlykozhayeva, Symbat Temesheva, Almat Akhmetali, Alisher Skabylov, Nurzhan Ussipov

Wireless mesh networks (WMNs) depend on the spatial distribution of nodes, which directly influences connectivity, routing efficiency, and overall network performance. Conventional models typically assume uniform or random node placement, which inadequately represent the complex, hierarchical spatial patterns observed in practical deployments. In this study, we present a novel algorithm that constructs WMN topologies with tunable fractal dimensions, allowing precise control over spatial self-similarity. By systematically varying the fractal dimension, the algorithm generates network layouts spanning a continuum of spatial complexities, ranging from sparse fragmented clusters to dense, cohesive structures. Through NS-3 simulations, Key performance metrics including throughput, latency, jitter, and packet delivery ratio were evaluated across a range of fractal dimensions. Comparative evaluations against classical random, small-world, and scale-free network models reveal that high-dimensional fractal topologies achieve enhanced resilience and throughput under equivalent conditions. These findings demonstrate the potential of fractal geometry as a design paradigm for scalable and efficient WMN architectures.

Authors: Chao Yang, Zhujun Zhang

The translational tiling problem, dated back to Wang's domino problem in the 1960s, is one of the most representative undecidable problems in the field of discrete geometry and combinatorics. Ollinger initiated the study of the undecidability of translational tiling with a fixed number of tiles in 2009, and proved that translational tiling of the plane with a set of $11$ polyominoes is undecidable. The number of polyominoes needed to obtain undecidability was reduced from $11$ to $7$ by Yang and Zhang, and then to $5$ by Kim. We show that translational tiling of the plane with a set of $4$ (disconnected) polyominoes is undecidable in this paper.

Authors: Malory Marin, Rémi Watrigant

A subcoloring of a graph is a partition of its vertex set into subsets (called colors), each inducing a disjoint union of cliques. It is a natural generalization of the classical proper coloring, in which each color must instead induce an independent set. Similarly to proper coloring, we define the subchromatic number of a graph as the minimum integer k such that it admits a subcoloring with k colors, and the corresponding problem k-Subcoloring which asks whether a graph has subchromatic number at most k. In this paper, we initiate the study of the subcoloring of (unit) disk graphs. One motivation stems from the fact that disk graphs can be seen as a dense generalization of planar graphs where, intuitively, each vertex can be blown into a large clique--much like subcoloring generalizes proper coloring. Interestingly, it can be observed that every unit disk graph admits a subcoloring with at most 7 colors. We first prove that the subchromatic number can be 3-approximated in polynomial-time in unit disk graphs. We then present several hardness results for special cases of unit disk graphs which somehow prevents the use of classical approaches for improving this result. We show in particular that 2-subcoloring remains NP-hard in triangle-free unit disk graphs, as well as in unit disk graphs representable within a strip of bounded height. We also solve an open question of Broersma, Fomin, Ne\v{s}et\v{r}il, and Woeginger (2002) by proving that 3-Subcoloring remains NP-hard in co-comparability graphs. Finally, we prove that every $n$-vertex disk graph admits a subcoloring with at most $O(\log^3(n))$ colors and present a $O(\log^2(n))$-approximation algorithm for computing the subchromatic number of such graphs. This is achieved by defining a decomposition and a special type of co-comparability disk graph, called $\Delta$-disk graphs, which might be of independent interest.

Authors: Kristóf Bérczi, Karthekeyan Chandrasekaran, Tamás Király, Daniel P. Szabo

The submodular partitioning problem asks to minimize, over all partitions P of a ground set V, the sum of a given submodular function f over the parts of P. The problem has seen considerable work in approximability, as it encompasses multiterminal cuts on graphs, k-cuts on hypergraphs, and elementary linear algebra problems such as matrix multiway partitioning. This research has been divided between the fixed terminal setting, where we are given a set of terminals that must be separated by P, and the global setting, where the only constraint is the size of the partition. We investigate a generalization that unifies these two settings: minimum submodular matroid-constrained partition. In this problem, we are additionally given a matroid over the ground set and seek to find a partition P in which there exists some basis that is separated by P. We explore the approximability of this problem and its variants, reaching the state of the art for the special case of symmetric submodular functions, and provide results for monotone and general submodular functions as well.

Authors: Neil Scheidwasser, Ayush Nag, Matthew J Penn, Anthony MV Jakob, Frederik Mølkjær Andersen, Mark P Khurana, Landung Setiawan, Madeline Gordon, David A Duchêne, Samir Bhatt

Phylogenetics is a fundamental component of many analysis frameworks in biology as well as linguistics to study the evolutionary relationships of different entities. Recently, the advent of large-scale genomics and the SARS-CoV-2 pandemic has underscored the necessity for phylogenetic software to handle large datasets of genomes or phylogenetic trees. While significant efforts have focused on scaling optimisation algorithms, visualization, and lineage identification, an emerging body of research has been dedicated to efficient representations of data for genomes and phylogenetic trees such as phylo2vec. Compared to traditional tree representations such as the Newick format, which represents trees using strings of nested parentheses, modern representations of phylogenetic trees utilize integer vectors to define the tree topology traversal. This approach offers several advantages, including easier manipulability, increased memory efficiency, and applicability to downstream tasks such as machine learning. Here, we present the latest release of phylo2vec (or Phylo2Vec), a high-performance software package for encoding, manipulating, and analysing binary phylogenetic trees. At its core, the package is based on the phylo2vec representation of binary trees, which defines a bijection from any tree topology with $n$ leaves into an integer vector of size $n-1$. Compared to the traditional Newick format, phylo2vec is designed to enable fast sampling and comparison of binary trees. This release features a core implementation in Rust, providing significant performance improvements and memory efficiency, while remaining available in Python (superseding the release described in the original paper) and R via dedicated wrappers, making it accessible to a broad audience in the bioinformatics community.

Authors: Yang P. Liu

We give an algorithm that takes a directed graph $G$ undergoing $m$ edge insertions with lengths in $[1, W]$, and maintains $(1+\epsilon)$-approximate shortest path distances from a fixed source $s$ to all other vertices. The algorithm is deterministic and runs in total time $m^{1+o(1)}\log W$, for any $\epsilon > \exp(-(\log m)^{0.99})$. This is achieved by designing a nonstandard interior point method to crudely detect when the distances from $s$ other vertices $v$ have decreased by a $(1+\epsilon)$ factor, and implementing it using the deterministic min-ratio cycle data structure of [Chen-Kyng-Liu-Meierhans-Probst, STOC 2024].

Authors: Benjamin Brock, Willow Ahrens, Hameer Abbasi, Timothy A. Davis, Juni Kim, James Kitchen, Spencer Patty, Isaac Virshup, Erik Welch

Sparse matrices and tensors are ubiquitous throughout multiple subfields of computing. The widespread usage of sparse data has inspired many in-memory and on-disk storage formats, but the only widely adopted storage specifications are the Matrix Market and FROSTT file formats, which both use ASCII text. Due to the inefficiency of text storage, these files typically have larger file sizes and longer parsing times than binary storage formats, which directly store an in-memory representation to disk. This can be a major bottleneck; since sparse computation is often bandwidth-bound, the cost of loading or storing a matrix to disk often exceeds the cost of performing a sparse computation. While it is common practice for practitioners to develop their own, custom, non-portable binary formats for high-performance sparse matrix storage, there is currently no cross-platform binary sparse matrix storage format. We present Binsparse, a cross-platform binary sparse matrix and tensor format specification. Binsparse is a modular, embeddable format, consisting of a JSON descriptor, which describes the matrix or tensor dimensions, type, and format, and a series of binary arrays, which can be stored in all modern binary containers, such as HDF5, Zarr, or NPZ. We provide several reference implementations of Binsparse spanning 5 languages, 5 frameworks, and 4 binary containers. We evaluate our Binsparse format on every matrix in the SuiteSparse Matrix Collection and a selection of tensors from the FROSTT collection. The Binsparse HDF5 CSR format shows file size reductions of 2.4x on average without compression and 7.5x with compression. We evaluate our parser's read/write performance against a state-of-the-art Matrix Market parser, demonstrating warm cache mean read speedups of 26.5x without compression and 2.6x with compression, and write speedups of 31x without compression and 1.4x with compression.

[Crossposted on LessWrong]

Throughout history, technological and scientific advances have had both good and ill effects, but their overall impact has been overwhelmingly positive. Thanks to scientific progress, most people on earth live longer, healthier, and better than they did centuries or even decades ago. 

I believe that AI (including AGI and ASI) can do the same and be a positive force for humanity. I also believe that it is possible to solve the “technical alignment” problem and build AIs that follow the words and intent of our instructions and report faithfully on their actions and observations.

I will not defend these two claims here. However, even granting these optimistic premises, AI’s positive impact is not guaranteed. In this essay, I will:

1. Define what I mean by “solving” the technical alignment problem via training AIs to be faithful and obedient.
2. Discuss some of the potential risks that still remain even if we do solve this problem.
3. Talk about some scenarios that could make these risks more likely, and how do we avoid them.

In the next decade, AI progress will be extremely rapid, and such periods of sharp transition can be risky.  What we — in industry, academia, and government—  do in the coming years will matter a lot to ensure that AI’s benefits far outweigh its costs.

Faithful, obedient, superintelligent.

Currently, it is very challenging to train AIs to achieve tasks that are too hard for humans to supervise. I believe that (a) we will need to solve this challenge to unlock “self-improvement” and superhuman AI, and (b) we will be able to solve it.  I do not want to discuss here why I believe these statements. I would just say that if you assume (a) and not (b), then the capabilities of AIs, and hence their risks, will be much more limited.

Ensuring AIs accurately follow our instructions, even in settings too complex for direct human oversight, is one such hard-to-supervise objective. Getting AIs to be maximally honest, even in settings that are too hard for us to verify, is another such objective. I am optimistic about the prospects of getting AIs to maximize these objectives. I believe it will be possible train AIs with an arbitrary level of intelligence that:

1. Follow the principles, regulations, and instructions that they are given, doing their best to follow not just the words but our intent, in all situations. Their sole reward or goal would be maximum obedience to our instructions.
2. We could probe these AIs (whether by simply asking them, looking at their chains of thought, or using interpretability methods) and get precise and faithful representations of their reasoning, actions, observations, and choices at every level of granularity we want.

This is what I mean by “solving” the technical alignment problem. Note that this does not require AIs to have an inherent love for humanity, or be fundamentally incapable of carrying out harmful instructions if those are given to them or they are fine-tuned to do so. However, it does require these AIs to reasonably generalize our intent into new situations– what I called before “robust reasonable compliance.”

Intelligence and obedience are independent qualities. It is possible to have a maximally obedient AI capable of planning and carrying out arbitrarily complex tasks—like proving the Riemann hypothesis, figuring out fusion power, or curing cancer—that have so far proven beyond humanity’s collective intelligence. Thus, faithful and obedient AIs can function as incredibly useful “superintelligent tools”. For both commercial and cultural reasons, I believe such AIs would be the dominant consumers of inference-time compute throughout the first years/decades of AGI/ASI, and as such account for the vast majority of “total worldwide intelligence.” (I expect this to hold even if people experiment with endowing AIs with a “sense of self”, “free will” and/or functioning as independent moral agents.)

The precise “form factor” of faithful obedient AIs is still unknown. It will depend on their capability and alignment profile, as well on their most lucrative or beneficial applications, and all of these could change with time. For example, it may turn out that for a long time AIs will be able to do 95% of the tasks of 95% of human workers, but there will still be a “long tail” of tasks that humans do better, and hence benefit from AI/human collaboration. Also, even if the total amount of intelligence is equivalent to “a country of geniuses in a data center,” this does not mean that this is how we will use AI. Perhaps it will turn out more economically efficient to simulate 1,000 geniuses and ten countries of knowledge workers. Or we would integrate AIs in our economy in other ways that don’t correspond to drop-in replacement of humans. 

What does it mean to “solve” alignment? Like everything with AI, we should not expect 100% guarantees, but rather increasingly better approximations of obedience and faithfulness. The pace at which these approximations improve relative to the growth in capabilities and high-stakes deployment could significantly affect AI outcomes.

A good metaphor is cryptography and information security. Cryptography is a “solved” problem in the sense that we have primitives such as encryption and digital signatures for which we can arbitrarily decrease the probability of attacker success as an inverse exponential function of the size of our key. Of course, even with these primitives, there are still many challenges in cybersecurity. Part of this is because even specifying what it means for a system to be secure is difficult, and we also need to deal with implementation bugs. I suspect we will have similar challenges in AI. 

That said, cybersecurity is an encouraging example since we have been able to iteratively improve the security of real world systems. For example, every generation of iPhone has become more secure than previous ones, to the extent that even nation states find it difficult to hack. Note that we were extremely lucky in cryptography that the attacker’s resources scale exponentially with the defender’s (i.e. key size and computation of encryption/signing. etc.). Security would have required much more overhead if the dependence was, for example, quadratic. It is still unknown which dependencies of alignment reliability to resources such as train and test time compute can be achieved.

Even if we “solve” alignment and train faithful and obedient AIs, that does not guarantee that all AIs in existence are faithful and obedient, or that they obey good instructions. However, I believe that we can handle a world with such “bad AIs” as long as (1) the vast majority of inference compute (or in other words, the vast majority of “intelligence”) is deployed via AIs that are faithful and obedient to responsible actors, and (2) we do the work (see below) to tilt the offense/defense balance to the side of the defender.

Are we there yet?

You might imagine that by positing that technical alignment is solvable, I “assumed away” all the potential risks with AI. However, I do not believe this to be the case. The “transition period” as AI capability and deployment rapidly ramps up will be inherently risky. Some potential dangers include:

Risk of reaching the alignment “uncanny valley” and unexpected interactions. Even if technical alignment is solvable, it does not mean that we will solve it in time and in particular get sufficiently good guarantees on obedience and faithfulness. In fact, I am more worried about partial success than total failure in aligning AIs. In particular, I am concerned that we will end up in the “uncanny valley,” where we succeed in aligning AIs to a sufficient level for deployment, but then discover too late some “edge cases” in the real world that have a large negative impact. Note that the world in which future AIs will be deployed will be extraordinarily complex, with a combination of new applications, and a plethora of actors that would also include other AIs (that may not be as faithful or obedient, or obey bad actors).  The more we encounter such crises, whether through malfunction, misalignment, misuse, or their combination, the less stable AI’s trajectory will be, and the less likely it is to end up well.

Risk of a literal AI arms race. AI will surely drive a period of intense competition. This competition can be economic, scientific, or military in nature. The economic competition between the U.S. and China has been intense, but has also had beneficial outcomes, including a vast reduction in Chinese poverty. I hope companies and countries will compete for AI leadership in commerce and science, rather than a race to develop more deadly weapons with an incentive to deploy them before the other side does.

Risk of a surveillance state. AI could radically alter the balance of power between citizens and governments, although it is challenging to predict in which direction. One possibility is that instead of empowering individuals,  AI will enable authoritarian governments to better control and surveil their citizens.

Societal upheaval. Even if in the long run AI will “lift all boats”, if in the short term there are more losers than winners, this could lead to significant societal instability. This will largely depend on the early economic and social impact of AI. Will AI be first used to broaden access to quality healthcare and education? Or will it be largely used to automate away jobs in the hope that the benefits will eventually “trickle down”?

Risky scenarios

There are several scenarios which can make the risks above more likely.

Pure internal deployment. One potential scenario is that labs decide that the best way to preserve a competitive edge is not to release their models and use them purely for internal AI R&D. Releasing models creates value for consumers and developers. But beyond that, not releasing models yields a significant risk in creating a feedback cycle where a model is used to train new versions of itself, without the testing and exposure that comes with an external release. Like the (mythical) New York subway albino crocodiles or the (real) “Snake Island” golden lanceheads, models that develop without contact with the outside world could be vulnerable and dangerous in ways that are hard to predict. No amount of internal testing, whether by the model maker or third parties, could capture the complexities that one discovers in real-world usage (with OpenAI’s sycophancy incident being a case in point). Also, no matter how good the AI is, there are always risks and uncertainties when using it to break new ground, even internally. If you are using AI to direct a novel training run, one that is bigger than any prior ones, then by definition, it would be “out of distribution” as no such run exists in the training set. 

Single monopoly: Lack of competition can enable the “pure internal deployment” scenario. If a single company is by far and away the market leader, it will be tempting for it to keep its best models to itself and use them to train future models. But if two companies have models of similar capabilities, the one that releases its model will get more market share, mindshare, and resources. So the incentive is to share your models with the world, which I believe is a good thing. This does not mean labs would not use their models for internal AI R&D. But hopefully, they would also release them and not keep their best models secret for extended periods. Of course, releases must still be handled responsibly, with thorough safety testing and transparent disclosure of risks and limitations. Beyond this, while a single commercial monopoly is arguably not as risky as an authoritarian government, the concentration of power with any actor is bad in itself.

Zero-sum instead of positive-sum. Like natural intelligence, artificial intelligence has an unbounded number of potential applications. Whether it is addressing long-standing scientific and technological challenges, discovering new medicines, or extending the reach of education, there are many ways in which AI can improve people’s lives. The best way to spread these benefits quickly is through commercial innovation, powered by the free market. However, it is also possible that as AI’s power becomes more apparent, governments will want to focus its development toward military and surveillance applications. While I am not so naive as to imagine that advances in AI would not be used in the military domain, I hope that the majority of progress will continue in applications that “lift all boats.” I’d much rather have a situation where the most advanced AI is used by startups who are trying to cure cancer, revolutionize education, or even simply make money, than for killer drones or mass surveillance.

Overly obedient AI. Part of the reason I fear AI usage for government control of citizens is precisely because I believe we would be able to make AIs simultaneously super intelligent and obedient. Governments are not likely to deploy AIs that, like Ed Snowden or Mark Felt (aka “Deep Throat”), would leak to the media if the NSA is spying on our own citizens or the president is spying on the opposing party. Similarly, I don’t see governments willingly deploying an AI that, like Stanislav Petrov, would disobey its instructions and refuse to launch a nuclear weapon. Yet, historically, such “disobedient employees” have been essential to protecting humanity.  Preserving our freedoms in a world where the government can have an endless supply of maximally obedient and highly intelligent agents is nontrivial, and we would stand a better chance if we first evolved both AI and our understanding of it in the commercial sector. 

There are mitigations for this scenario. First, we should maintain “humans in the loop” in high-stakes settings and make sure that these humans do not become mere “rubber stamps” to AI decisions. Also, if done right, AI can also increase transparency in government, as long as we maintain the invariant that AI communication is faithful and legible. For example, we could demand that all AIs used in government follow a model spec that adheres first to the constitution and other laws. In particular, unlike some humans, a law-abiding AI will not try to circumvent transparency regulations, and all its prompts and communication will be accessible to FOIA requests.

Offensive vs. defensive applications. As the name indicates, AGI is a very general technology. It can be used for both developing vaccines and engineering new viruses, for both software verification as well as discovering new vulnerabilities. Moreover, there is significant overlap between such “offensive” and “defensive” uses of AI, and they cannot always be cleanly separated. In the long run, I believe both offensive and defensive applications of AI will be explored. But the order in which these applications are developed can make a huge difference as to whether AI is harmful or beneficial. If we use AI to strengthen our security or vaccine-development infrastructure, then we will be in a much better position if AI is later used to enable attacks.

It’s not always easy to distinguish “offensive” vs. “defensive” applications of AI. For example, even offensive autonomous weapons can be used in a defensive war. But generally, even if we trust ourselves to only use an offensive AI technology X “for a good cause,” we still must contend with the fact that:

1. Developing X makes it more likely that our adversaries will do the same. Either because the details of X leak or even simply because the fact that it exists already gives our adversary motivation and proof of concept that it is possible to build it. This was the dynamic behind the development of nuclear weapons.
2. The more we remove humans from the chain of command of lethal weapons, the more we open a new and yet poorly understood surface for a catastrophe: a bug in a line of code, a hack, or a misaligned AI could end up unleashing these weapons in ways we did not envision.

Thus, when exploring potential applications of AI, we should ask questions such as: (1) if everyone (including our adversaries) had access to this technology, would it have a stabilizing or destabilizing effect? (2) What could happen if malicious parties (or misaligned AIs)  got access to this technology? If companies and governments choose to invest resources in AI applications that have stabilizing or defensive impacts and strengthen institutions and societies, and decline or postpone pursuing destabilizing or offensive impacts, then we will be more likely to navigate the upcoming AI transition safely.

Safety underinvestment. There is a tension between safety and the other objectives of intense competition and iterative deployment. If we deploy AI widely and quickly, it will also be easier for bad actors to get it. Since iterative deployment is its own good, we should compensate for this by overinvesting in safety. While there are market incentives for AI safety, the competitive pressure to be first to market, and the prevalence of “tail risks” that could take time to materialize and require significant investment to even quantify, let alone mitigate, means that we are unlikely to get a sufficient investment in safety through market pressure alone. As mentioned above, we may find ourselves in the “alignment uncanny valley,” where our models appear “safe enough to deploy” and even profitable in the short term, but are vulnerable or misaligned in ways that we will only discover too late. In AI, “unknown unknowns” are par for the course, and it is society at large that will bear the cost if things go very wrong. Labs should invest in AI safety, particularly in solving the “obedience and faithfulness” task to multiple 9’s of reliability, before deploying AIs in applications that require this.

AI has the potential to unleash, within decades, advances in human flourishing that would eclipse those of the last three centuries. But any period of quick change carries risks, and our actions in the next few years will have outsize impacts. We have multiple technical, social, and policy problems to tackle for it to go well. We’d better get going.

Notes and acknowledgements. Thanks to Josh Achiam, Sam Altman, Naomi Bashkansky, Ronnie Chatterji, Kai Chen, Jason Kwon, Jenny Nitshinskaya, Gabe Wu, and Wojciech Zaremba for comments on this post. However, all responsibility for the content is mine. The opinions in this post are my own and do not necessarily reflect my employer’s or my colleagues. The title of the post is inspired by Dario Amodei’s highly recommended essay “Machines of Loving Grace.”

By Boaz Barak

In this post, I discuss a remarkable new paper

Cubulating the sphere with many facets by Sergey Avvakumov and Alfredo Hubard

Abstract: For each we construct cube complexes homeomorphic to the -sphere with vertices in which the number of facets (assuming constant) is .

This disproves a conjecture of Kalai’s stating that the number of faces (of all dimensions) of cubical spheres is maximized by the boundaries of neighbourly cubical polytopes. The conjecture was already known to be false for , . Our construction disproves it for all and sufficiently large. Moreover, since neighborly cubical polytopes have roughly facets, we show that even the order of growth (at least for the number of facets) in the conjecture is wrong.

Avvakumov and Hubard’s result about cubical two dimensional manifolds

A crucial ingredient in the proof is a theorem about cubical 2-dimensional manifolds. Sergey and Alfredo proved that for any there is a “cubulation” of a closed orientable 2-surface with vertices and squares. This result appears related to the 1890 Heawood Conjecture for the existence of triangulated surfaces with “many” triangles.

The paper is accompanied by beautiful, illuminating figures.

Updates regarding previous posts.

1. Noga Alon and Shakhar Smorodinsky uploaded to the arXiv their paper Extended VC-dimension, and Radon and Tverberg type theorems for unions of convex sets. We briefly talked about the Radon type result (an old question of mine) in this post. Moving from a Radon-type theorem to a Tverberg-type theorem required an extended notion of VC dimension that is of independent interest and may have further applications. There are also various remaining questions that I find interesting.  

2. To my previous post I added a Trivia question –  which mathematician is connected to both Abraham Fraenkel and Akitsugu Kawaguchi’s famous works (on different topics).  Hint: chess.

 

Some background and history for Avvakumov and Hubard’s New Result

A cubical complex is a collection of cubes (called “faces”) of various dimensions so that:

(1) A face of a cube in also belongs to ,

(2) The intersection of two faces of is a  face of both.

Alternatively you can consider a cubical complex as a poset with the lattice property so that every proper lower interval  is isomorphic to the face lattice of a cube.

A cubical complex realizes a topological space denoted by . If is a sphere we call a cubical sphere. Special cases of cubical spheres are the boundary complexes of cubical polytopes.

All these definitions are analogous to the definitions for simplicial complexes, simplicial spheres, and simplicial polytopes. However, the theory of simplicial polytopes and spheres is much more developed compared to the theory of cubical polytopes and spheres.

Questions about Cubical Polytopes and Spheres from the early-mid 90s.

In the early 90s Ron Adin proposed his well known and still open “generalized lower bound inequalities” for cubical polytopes. Those include, as a special case, conjectured lower bounds for the number of facets as a function of the dimension and the number of vertices. (Those lower bounds are also still open.) We discussed Adin’s conjecture in Item D) of this post.

The upper bound theorem for simplicial polytopes (and spheres) asserts that the number of facets (and -faces) for a simplicial -polytope (and a simplicial -sphere) is maximized by the cyclic -polytope with vertices. When is fixed the number of facets behaves like . What is the upper bound for the number of facets in the cubical case?

Proposition: Let be a cubical polytope (or, in fact cubical complex) with vertices and -dimensional faces. Then

.

Proof: For every -face , , consider its (large) diagonals. Every pair of (non-adjacent) vertices can occur only once as such a large diagonal.

Here are two conjectures that I proposed in the mid 90s  regarding upper bounds.

Conjecture 1: There are cubical convex -polytopes (and cubical -spheres) with vertices where , that have the same -skeleton as , the dimensional cube, .

For cubical spheres, this conjecture was proved by Eric Babson, Lou Billera and Clara Chan in 1997. Neighborly cubical polytopes were constructed by Michael Joswig and Günter Ziegler in 2000. 

Conjecture 2: The objects from Conjecture 1 attain the maximum number of k-faces among all cubical -polytopes (and even -dimensional spheres).

In their same paper Joswig and Ziegler disproved conjecture 2 for . Conjecture 2 would imply that the number of facets of a -polytope with vertices is bounded by .

The new paper by Sergey and Alfredo shows that the number of facets of cubical spheres can be much much larger – .  This is a major advance in our state of knowledge!

It would be very interesting to find cubical polytopes where the number of facets is more than . Also, as far as I know, there is no known upper bound smaller than . 

Jockusch’s 1993 Result 

Conjectures 1 and 2 were motivated by a 1993 paper by William Jockusch who showed that there are cubical 4-polytopes where the number of facets is larger than 5/4 times the number of vertices. This disproved an earlier conjecture that for every cubical polytope has fewer facets than vertices (or at least, perhaps the ratio is bounded).  This early conjecture in its stronger form was motivated by the interesting fact that there is no cubical sphere whose dual is also a cubical sphere. Until Jockusch’s paper, cubical zonotopes looked like candidates for the upper bound and for them the number of facets is always smaller than the number of vertices.  The papers by Babson, Billera, and Chan, and by Joswig and Ziegler showed that the ratio between the number of facets and the number of vertices can be unbounded. 

By Gil Kalai

I’m on vacation this week and am handing over the blog controls to Jessica Dai. Jessica is a PhD student in my group and also a cofounder of Reboot and an editor of Kernel. This blog post covers work she’s been leading for the past year on how we ought to make statistics out of individuals.

I am a critic at heart, but an impatient one, which gives me a complicated relationship to the world of “responsible AI.” On the one hand, structural critiques are almost always true — AI tends to concentrate power, market incentives accelerate harm, structural forces will necessarily compromise any proposed “solution.” On the other hand, I am, as I mentioned, impatient. That these forces are so entrenched is precisely why we ought to try to take action in spite of them, rather than remain, safely, in the critic’s seat.1

Over the last few years, I’ve accumulated a long list of grievances about this area of research: the glut of methods and metrics that remained disconnected from real-world deployment; the way that such methods relied on the good faith of model developers, while almost never leaving room for the agency of the everyday people who actually experience the model.

I really wanted to understand what should be done instead. The result, a very long time in the making, was a theory(ish) paper, written with my dear friends/neighbors/labmates Paula and Deb. In this paper, we describe and analyze a system that addresses at least some of these critiques; in doing so, we are explicitly prescriptive about a world we hope to see.

The paper is titled, somewhat floridly but hopefully also descriptively, From Individual Experience to Collective Evidence: A Reporting-Based Framework for Identifying Systemic Harms. Suppose there existed a mechanism where individuals could report a problematic experience with a specific system (e.g., perceived mistreatment by a predictive algorithm that affected loan allocations). Then, as reports arrive over time, we show how it’s possible to quickly identify whether there was a particular subset of the population that was disproportionately experiencing harm (e.g., actually experienced elevated rates of loan denials even conditioned on financial health), and do so with some sense of statistical rigor.2

The core concept is individual reporting as a means to build collective knowledge: intuitively, if one person had one bad experience, that by itself doesn’t necessarily mean that there was something wrong with the entire system. But if lots of people start reporting the same problem — and, if those people appear to be similar in important ways — then that seems like it might constitute a true, underlying problem with the system.

This collective knowledge, by virtue of being tied to a specific system, is also therefore actionable: it describes real, known patterns of behavior that e.g., a model developer might then be able to fix, or e.g., a third-party or government body (RIP) might use as evidence to hold the model owner accountable. In this way, individual reporting also becomes a new lens for evaluation, and thus a pathway for post-deployment monitoring that is not doomed to be solely descriptive of past harm but can rather also be

What we did in this particular paper was fairly specific to the problem of fairness, in that the “problem” we were trying to identify was intrinsically about identifying subgroups that experienced disproportionate rates of harm. But I believe very strongly that individual reporting mechanisms, as described in the previous paragraph, are valuable in a much broader sense. (I make this general case in greater detail in a new preprint — Aggregated Individual Reporting for Post-Deployment Evaluation — which elaborates on the arguments in this post.3)

Of course, there’s the general case for thinking about what happens post-deployment: it is quite literally impossible for even the most well-intentioned model developers to fully predict, measure, and mitigate problems before seeing how people are actually engaging with the system. This is especially true for more complex systems like LLMs, and the sentiment around needing careful analysis of actual usage is in fact starting to percolate to practical systems. On the general-purpose end, some of Anthropic’s recent posts gesture at the importance of understanding actual usage; on the task-specific end, UCSF is piloting more targeted monitoring for AI systems in clinical applications.

What’s unique, I think, about the individual reporting approach to post-deployment monitoring is that it relies on two crucial beliefs: first, that those interacting with the system have unique and valuable perspectives on its failure modes, and second, that they ought to be able to express those perspectives in a nontrivial way. While these statements feel natural to me personally, mainstream practice in AI evaluation seems to be rarely consistent with them. The word I’ve been dancing around, perhaps, is values: if you’ll forgive my elementary STS facility, one might say that the values or politics expressed by typical approaches to evaluation do not include respect for or valorization of individual agency.

My personal feelings about these values are why I care about individual reporting. But why should you, or anyone with decision-making power to actually implement a system like this, care? Normative considerations aside, I suspect that there could be really interesting substantive information that might come out of reports. I say suspect, because, of course, this is an empirical question and, for the most part, individual reporting mechanisms for AI do not exist. On the other hand, in other domains where individual reporting has been established as standard practice — notably, vaccines and pharmaceuticals — these individual reports have surfaced interesting, important, and consequential information about their effects at a population level.

Today, individual experiences with AI systems are captured largely informally — Reddit discussions and Twitter memes that sometimes make it to reported journalistic stories. To me, the ChatGPT personality flip-flop from late April is instructive. (In case you missed it, OpenAI rolled out a change to the ChatGPT system prompt that made it seem much friendlier and “personable” — then reverted that change, no doubt in large part because of a wave of semi-viral tweets showing dangerously sycophantic responses.)

It goes without saying that x dot com is not in fact a structured repository for problems with chatgpt dot com, but I do think what happened here is an illustration of what individual reports have to offer as an evaluation mechanism. OpenAI wasn’t able to identify ahead of time that this “personality” update was problematic, in part because it is hard to anticipate the richness of usage patterns and therefore failure modes. People thought the problems were egregious enough that it motivated them to tweet. Enough people — importantly, LLM-twitter-famous people — tweeted about the same problem that OpenAI noticed.

This ChatGPT personality problem was serious, widespread, and was therefore caught. But what other, subtler, non-Twitter-viral patterns are happening? What more could we understand about the fractal, “jagged” edges of AI system deployments if we had better ways to listen to the people who interact with them?

Something that we talk about a lot in Ben’s group is that if you were to believe the titles and abstracts of the ML theory x society work from the last few years, you might think that all manner of societal problems—from data sharing to social media polarization to democratic decisionmaking—had been solved, and optimally at that. (And yet.)

In that sense, we’re not completely guiltless. This paper lays out a pretty ambitious vision. At the same time, an uncharitable but not inaccurate characterization of what we’ve actually done in the paper would be that it’s not much. The HCI-oriented reader might be rightfully skeptical of all of our assumptions. The capital-s Statisticians in the audience — I am assuming there are a few among typical argmin readers, if I haven’t lost you yet — might be unimpressed by the technical results. (What, so this was just sequential mean testing with a Bonferroni correction all along?4)

I say this not for cosmetic humility but because I want to be honest about what we’ve done, and what’s left to be done, which is most of it. Our paper was fairness-oriented, sure, and thus much narrower than the high-level vision for individual reporting mechanisms in general. Still, this paper, as a concrete instantiation of an individual reporting system, helped me to crystallize what the big challenges might look like in any other instantiation: How would the system be scoped? What counts as “harm”? What information is communicated in a report? How should the dynamics of reporting behaviors be understood and addressed?

Ultimately, I think of this initial paper as a fundamentally optimistic artifact. The paper is speculative, in a hopefully constructive way; it’s as concrete an answer to “what’s the alternative” as we could come up with. To repeat a sentence from above: for the most part, individual reporting mechanisms for AI do not currently exist! I can’t, of course, promise with complete certainty that they would actually always generate substantively useful insights.5 But, at the very least, I think it’s worth trying to find out.

Subscribe now

By jessica dai

Polynomial factorization is a fundamental problem in computational algebra. Over the past half century, a variety of algorithmic techniques have been developed to tackle different variants of this problem. In parallel, algebraic complexity theory classifies polynomials into complexity classes based on their perceived `hardness'. This raises a natural question: Do these classes afford efficient factorization? In this survey, we revisit two pivotal techniques in polynomial factorization: Hensel lifting and Newton iteration. Though they are variants of the same theme, their distinct applications across the literature warrant separate treatment. These techniques have played an important role in resolving key factoring questions in algebraic complexity theory. We examine and organise the known results through the lens of these techniques to highlight their impact. We also discuss their equivalence while reflecting on how their use varies with the context of the problem. We focus on four prominent complexity classes: circuits of polynomial size ($\text{VP}_{\text{nb}}$), circuits with both polynomial size and degree (VP and its border $\overline{\text{VP}}$), verifier circuits of polynomial size and degree (VNP), and polynomial-size algebraic branching programs (VBP). We also examine more restricted models, such as formulas and bounded-depth circuits. Along the way, we list several open problems that remain unresolved.

Even with everything happening in the Middle East right now, even with (relatedly) everything happening in my own family (my wife and son sheltering in Tel Aviv as Iranian missiles rained down), even with all the rather ill-timed travel I’ve found myself doing as these events unfolded (Ecuador and the Galapagos and now STOC’2025 in Prague) … there’s been another thing, a huge one, weighing on my soul.

Ray Laflamme played a major role in launching the whole field of quantum computing and information, and also a major role in launching my own career. The world has lost him too soon. I’ve lost him too soon.

After growing up in Quebec—I still hear his French-Canadian accent, constantly on the verge of laughter, as I’m writing this—Ray went into physics and became a PhD student of Stephen Hawking. No, not a different Stephen Hawking. If you’ve read or watched anything by or about Hawking, including A Brief History of Time, you might remember the story where Hawking believed for a while that time would reverse itself as the universe contracted in a Big Crunch, with omelettes unscrambling themselves, old people turning into children, etc. etc., but then two graduate students persuaded him that that was totally wrong, and entropy would continue to increase like normal. Anyway, Ray was one of those students (Don Page was the other). I’d always meant to ask Ray to explain what argument changed Hawking’s mind, since the idea of entropy decreasing during contraction just seemed obviously wrong to me! Only today, while writing this post, did I find a 1993 paper by Hawking, Laflamme, and Lyons that explains the matter perfectly clearly, including three fallacious intuitions that Hawking had previously held. (Even though, as they comment, “the anatomy of error is not ruled by logic.”)

Anyway, in the mid-1990s, starting at Los Alamos National Lab and continuing at the University of Waterloo, Ray became a pioneer of the then-new field of quantum computing and information. In 1997, he was a coauthor of one of the seminal original papers that proved the possibility of fault-tolerant quantum computation with a constant error rate, what we now call the Threshold Theorem (Aharonov and Ben-Or had such a result independently). He made lots of other key early contributions to the theory of quantum error-correcting codes and fault-tolerance.

When it comes to Ray’s scientific achievements after his cosmology work with Hawking and after quantum fault-tolerance—well, there are many, but let me talk about two. Perhaps the biggest is the KLM (Knill-Laflamme-Milburn) Theorem. It would be fair to say that KLM started the entire field of optical or photonic quantum computation, as it’s existed in the 21^st century. In one sentence, what KLM showed is that it’s possible to build a universal quantum computer using only

1. identical single-photon states,
2. a network of “linear-optical elements” (that is, beamsplitters and phaseshifters) that the photons travel through, and
3. feedforward measurements—that is, measurements of an optical mode that tell you how many photons are there, in such a way that you can condition (using a classical computer) which optical elements to apply next on the outcome of the measurement.

All of a sudden, there was a viable path to building a quantum computer out of photons, where you wouldn’t need to get pairs of photons to interact with each other, which had previously been the central sticking point. The key insight was that feedforward measurements, combined with the statistical properties of identical bosons (what the photons are), are enough to simulate the effect of two-photon interactions.

Have you heard of PsiQuantum, the startup in Palo Alto with a $6 billion valuation and hundreds of employees that’s right now trying to build an optical quantum computer with a million qubits? Or Xanadu, its competitor in Toronto? These, in some sense, are companies that grew out of a theorem: specifically the KLM Theorem.

For me, though, the significance of KLM goes beyond the practical. In 2011, I used the KLM Theorem, together with the fact (known since the 1950s) that photonic amplitudes are the permanents of matrices, to give a new proof of Leslie Valiant’s celebrated 1979 theorem that calculating the permanent is a #P-complete problem. Thus, as I pointed out in a talk two years ago at Ray’s COVID-delayed 60^th birthday conference, entitled Ray Laflamme, Complexity Theorist (?!), KLM had said something new about computational complexity, without any intention of doing so. More generally, KLM was crucial backdrop to my and Alex Arkhipov’s later work on BosonSampling, where we gave strong evidence that some classical computational hardness—albeit probably not universal quantum computation—remains in linear optics, even if one gets rid of KLM’s feedforward measurements.

(Incidentally, I gave my talk at Ray’s birthday conference by Zoom, as I had a conflicting engagement. I’m now sad about that: had I known that that would’ve been my last chance to see Ray, I would’ve cancelled any other plans.)

The second achievement of Ray’s that I wanted to mention was his 1998 creation, again with his frequent collaborator Manny Knill, of the One Clean Qubit or “DQC1” model of quantum computation. In this model, you get to apply an arbitrary sequence of 2-qubit unitary gates, followed by measurements at the end, just like in standard quantum computing—but the catch is that the initial state consists of just a single qubit in the state |0⟩, and all other qubits in the maximally mixed state. If all qubits started in the maximally mixed state, then nothing would ever happen, because the maximally mixed state is left invariant by all unitary transformations. So it would stand to reason that, if all but one of the qubits start out maximally mixed, then almost nothing happens. The big surprise is that this is wrong. Instead you get a model that, while probably not universal for quantum computation, can do a variety of things in polynomial time that we don’t know how to do classically, including estimating the traces of exponentially large unitary matrices and the Jones polynomials of trace closures of braids (indeed, both of these problems turn out to be DQC1-complete). The discovery of DQC1 was one of the first indications that there’s substructure within BQP. Since then, the DQC1 model has turned up again and again in seemingly unrelated investigations in quantum complexity theory—way more than you’d have any right to expect a priori.

Beyond his direct contributions to quantum information, Ray will be remembered as one of the great institution-builders of our field. He directed the Institute for Quantum Computing (IQC) at the University of Waterloo in Canada, from its founding in 2002 until he finally stepped down in 2017. This includes the years 2005-2007, when I was a postdoc at IQC—two of the most pivotal years of my life, when I first drove a car and went out on dates (neither of which I do any longer, for different reasons…), when I started this blog, when I worked on quantum money and learnability of quantum states and much more, and when I taught the course that turned into my book Quantum Computing Since Democritus. I fondly remember Ray, as my “boss,” showing me every possible kindness. He even personally attended the Quantum Computing Since Democritus lectures, which is why he appears as a character in the book.

As if that wasn’t enough, Ray also directed the quantum information program of the Canadian Institute for Advanced Research (CIFAR). If you ever wondered why Canada, as a nation, has punched so far above its weight in quantum computing and information for the past quarter-century—Ray Laflamme is part of the answer.

At the same time, if you imagine the stereotypical blankfaced university administrator, who thinks and talks only in generalities and platitudes (“how can we establish public-private partnerships to build a 21^st-century quantum workforce?”) … well, Ray was whatever is the diametric opposite of that. Despite all his responsibilities, Ray never stopped being a mensch, a friend, an intellectually curious scientist, a truth-teller, and a jokester. Whenever he and I talked, probably at least a third of the conversation was raucous laughter.

I knew that Ray had spent many years battling cancer. I naïvely thought he was winning, or had won. But as so often with cancer, it looks like the victory was only temporary. I miss him already. He was a ray of light in the world—a ray that sparkles, illuminates, and as we now know, even has the latent power of universal quantum computation.

By Scott

Authors: Roni Con, Ray Li

We construct deletion error-correcting codes in the oblivious model, where errors are adversarial but oblivious to the encoder's randomness. Oblivious errors bridge the gap between the adversarial and random error models, and are motivated by applications like DNA storage, where the noise is caused by hard-to-model physical phenomena, but not by an adversary. (1) (Explicit oblivious) We construct $t$ oblivious deletion codes, with redundancy $\sim 2t\log n$, matching the existential bound for adversarial deletions. (2) (List decoding implies explicit oblivious) We show that explicit list-decodable codes yield explicit oblivious deletion codes with essentially the same parameters. By a work of Guruswami and H\r{a}stad (IEEE TIT, 2021), this gives 2 oblivious deletion codes with redundancy $\sim 3\log n$, beating the existential redundancy for 2 adversarial deletions. (3) (Randomized oblivious) We give a randomized construction of oblivious codes that, with probability at least $1-2^{-n}$, produces a code correcting $t$ oblivious deletions with redundancy $\sim(t+1)\log n$, beating the existential adversarial redundancy of $\sim 2t\log n$. (4) (Randomized adversarial) Studying the oblivious model can inform better constructions of adversarial codes. The same technique produces, with probability at least $1-2^{-n}$, a code correcting $t$ adversarial deletions with redundancy $\sim (2t+1)\log n$, nearly matching the existential redundancy of $\sim 2t\log n$. The common idea behind these results is to reduce the hash size by modding by a prime chosen (randomly) from a small subset, and including a small encoding of the prime in the hash.

Authors: Javier Esparza, Valentin Krasotin

Regular model checking is a well-established technique for the verification of regular transition systems (RTS): transition systems whose initial configurations and transition relation can be effectively encoded as regular languages. In 2008, To and Libkin studied RTSs in which the reachability relation (the reflexive and transitive closure of the transition relation) is also effectively regular, and showed that the recurrent reachability problem (whether a regular set $L$ of configurations is reached infinitely often) is polynomial in the size of RTS and the transducer for the reachability relation. We extend the work of To and Libkin by studying the decidability and complexity of verifying almost-sure reachability and recurrent reachability -- that is, whether $L$ is reachable or recurrently reachable w.p. 1. We then apply our results to the more common case in which only a regular overapproximation of the reachability relation is available. In particular, we extend recent complexity results on verifying safety using regular abstraction frameworks -- a technique recently introduced by Czerner, the authors, and Welzel-Mohr -- to liveness and almost-sure properties.

Authors: Jeong-Hoon Ju, Susana Lopez-Moreno

In this paper we study the computation of both algebraic and non-algebraic tensor functions under the tensor-tensor multiplication with linear maps. In the case of algebraic tensor functions, we prove that the asymptotic exponent of both the tensor-tensor multiplication and the tensor polynomial evaluation problem under this multiplication is the same as that of the matrix multiplication, unless the linear map is injective. As for non-algebraic functions, we define the tensor geometric mean and the tensor Wasserstein mean for pseudo-positive-definite tensors under the tensor-tensor multiplication with invertible linear maps, and we show that the tensor geometric mean can be calculated by solving a specific Riccati tensor equation. Furthermore, we show that the tensor geometric mean does not satisfy the resultantal (determinantal) identity in general, which the matrix geometric mean always satisfies. Then we define a pseudo-SVD for the injective linear map case and we apply it on image data compression.

Authors: Dror Chawin, Ishay Haviv

The low-rank matrix completion problem asks whether a given real matrix with missing values can be completed so that the resulting matrix has low rank or is close to a low-rank matrix. The completed matrix is often required to satisfy additional structural constraints, such as positive semi-definiteness or a bounded infinity norm. The problem arises in various research fields, including machine learning, statistics, and theoretical computer science, and has broad real-world applications. This paper presents new $\mathsf{NP} $-hardness results for low-rank matrix completion problems. We show that for every sufficiently large integer $d$ and any real number $\varepsilon \in [ 2^{-O(d)},\frac{1}{7}]$, given a partial matrix $A$ with exposed values of magnitude at most $1$ that admits a positive semi-definite completion of rank $d$, it is $\mathsf{NP}$-hard to find a positive semi-definite matrix that agrees with each given value of $A$ up to an additive error of at most $\varepsilon$, even when the rank is allowed to exceed $d$ by a multiplicative factor of $O (\frac{1}{\varepsilon ^2 \cdot \log(1/\varepsilon)} )$. This strengthens a result of Hardt, Meka, Raghavendra, and Weitz (COLT, 2014), which applies to multiplicative factors smaller than $2$ and to $\varepsilon $ that decays polynomially in $d$. We establish similar $\mathsf{NP}$-hardness results for the case where the completed matrix is constrained to have a bounded infinity norm (rather than be positive semi-definite), for which all previous hardness results rely on complexity assumptions related to the Unique Games Conjecture. Our proofs involve a novel notion of nearly orthonormal representations of graphs, the concept of line digraphs, and bounds on the rank of perturbed identity matrices.

Authors: Stefan Mengel

In this tutorial, we will survey known results on the complexity of conjunctive query evaluation in different settings, ranging from Boolean queries over counting to more complex models like enumeration and direct access. A particular focus will be on showing how different relatively recent hypotheses from complexity theory connect to query answering and allow showing that known algorithms in several cases can likely not be improved.

Authors: Lukas Retschmeier

For a given graph $G = (V, E)$, a subset of the vertices $D\subseteq V$ is called a semitotal dominating set, if $D$ is a dominating set and every vertex $v \in D$ is within distance two to another witness $v' \in D$. We want to find a semitotal dominating set of minimum cardinality. We show that the problem is $\mathrm{W}[2]$-hard on bipartite and split graphs when parameterized by the solution size $k$. On the positive side, we extend the kernelization technique of Alber, Fellows, and Niedermeier [JACM 2004] to obtain a linear kernel of size $358k$ on planar graphs. This result complements known linear kernels already known for several variants, including Total, Connected, Red-Blue, Efficient, Edge, and Independent Dominating Set.

Authors: Marcus Schaefer, Daniel Štefankovič

A set is star-shaped if there is a point in the set that can see every other point in the set in the sense that the line-segment connecting the points lies within the set. We show that testing whether a non-empty compact smooth region is star-shaped is $\forall\mathbb{R}$-complete. Since the obvious definition of star-shapedness has logical form $\exists\forall$, this is a somewhat surprising result, based on Krasnosel'ski\u{\i}'s theorem from convex geometry; we study several related complexity classifications in the real hierarchy based on other results from convex geometry.

Authors: Naoya Oda, Yosuke Onoue

Word cloud use is a popular text visualization technique that scales font sizes based on word frequencies within a defined spatial layout. However, traditional word clouds disregard semantic relationships between words, arranging them without considering their meanings. Semantic word clouds improved on this by positioning related words in proximity; however, still struggled with efficient space use and representing frequencies through font size variations, which can be misleading because of word length differences. This paper proposes StoryGem, a novel text visualization approach that addresses these limitations. StoryGem constructs a semantic word network from input text data, performs hierarchical clustering, and displays the results in a Voronoi treemap. Furthermore, this paper proposes an optimization problem to maximize the font size within the regions of a Voronoi treemap. In StoryGem, word frequencies map to area sizes rather than font sizes, allowing flexible text sizing that maximizes use of each region's space. This mitigates bias from varying word lengths affecting font size perception. StoryGem strikes a balance between a semantic organization and spatial efficiency, combining the strengths of word clouds and treemaps. Through hierarchical clustering of semantic word networks, it captures word semantics and relationships. The Voronoi treemap layout facilitates gapless visualization, with area sizes corresponding to frequencies for clearer representation. User study across diverse text datasets demonstrate StoryGem's potential as an effective technique for quickly grasping textual content and semantic structures.