Theory of Computing Report

May 15-25, 2026 STOC 2026/TCS4All events https://sigact.org/tcsforall/ Submission deadline: May 24, 2026 This year, TCS for All *Registration Scholarships* will cover the early registration cost at STOC 2026. The scholarships are intended for researchers at the beginning of their careers and they are being made available for all students in TCS. This scholarship is open … Continue reading TCS for All Spotlight Workshop at STOC 2026: Conference registration grants and call for speaker nominations

By shacharlovett

We present the first algorithms for polynomial identity testing (PIT) of read-$4$ arithmetic formulas in the non-multilinear setting. Specifically, we give a polynomial-time PIT algorithm in the whitebox model and a quasi-polynomial-time algorithm in the blackbox model. Since our techniques are based on proving hardness of representation results, we extend our algorithms to orbits of read-$4$ formulas under the action of the affine linear group. Prior to our work, no subexponential white- or blackbox algorithms were known for this class of formulas. All our results hold over any field $\mathbb{F}$ with $\text{char}(\mathbb{F}) = 0$ or $\text{char}(\mathbb{F}) \ge 5$. Prior work addressed only restricted cases. Anderson, van Melkebeek, and Volkovich (Computational Complexity, 2015) studied multilinear read-$k$ formulas, giving a polynomial-time whitebox PIT algorithm and a quasi-polynomial-time blackbox algorithm. Without the multilinearity restriction, Mahajan, Rao, and Sreenivasaiah (TCS, 2014) gave polynomial-time whitebox algorithms for read-$2$ and read-$3$ formulas, Prakriya (Doctoral Thesis, 2019) obtained quasi-polynomial-time blackbox PIT algorithm for both read-$2$ and read-$3$ formulas. Independently, Shamir (Master's Thesis, 2022) obtained a quasi-polynomial-time blackbox PIT algorithm for read-$2$ formulas. For bounded-depth read-$k$ formulas, Agrawal, Saha, Saptharishi, and Saxena (SICOMP, 2016) obtained a polynomial-time blackbox algorithm in the non-multilinear case. The running time of their algorithm is $n^{k^{2^\Delta}}$ for read-$k$, depth-$\Delta$ formulas, and hence it is applicable only to constant depth. Partial derivatives are a central tool in the study of deterministic PIT for bounded-read formulas. However, for non-multilinear R$k$Fs, differentiation may increase the number of reads. To address this, we develop new structural results that ensure ``nice behavior'' of derivatives. Specifically, we introduce a new Fragmentation Lemma that reduces the PIT problem for general R$k$Fs to simpler models via differentiation. In addition, we define the notion of dominating degree patterns and show that, in certain cases, taking partial derivatives with respect to these patterns preserves the read count.

Authors: Yuzhen Zhang, Isaac H. Kim, Yimu Bao, Sagar Vijay

We show that the low-energy states of non-Abelian topological orders possess extensive magic which is long-ranged, and cannot be eliminated by a constant-depth local unitary circuit. This refines conventional notions of complexity beyond the linear circuit depth which is required to prepare any topological phase, and provides a new resource-theoretic characterization of topological orders. A central technical result is a no-go theorem establishing that stabilizer states--even up to constant-depth local unitarie--cannot approximate low-energy states of non-Abelian string-net models which satisfy the entanglement bootstrap axioms. Moreover, we show that stabilizer-realizable Abelian string-net phases have mutual braiding phases quantized by the on-site qudit dimension, and that any violation of this condition necessarily implies extensive long-range magic. Extending to higher spatial dimensions, we argue that any state obeying an entanglement area law and hosting excitations with nontrivial fusion spaces must exhibit extensive long-range magic. This applies, in particular, to ground-states and low-energy states of higher-dimensional quantum double models.

Authors: Dmitry Chistikov, Luisa Estrada, Mike Paterson, Paolo Turrini

Agents in social networks with threshold-based dynamics change opinions when influenced by sufficiently many peers. Existing literature typically assumes that the network structure and dynamics are fully known, which is often unrealistic. In this work, we ask how to learn a network structure from samples of the agents' synchronous opinion updates. Firstly, if the opinion dynamics follow a threshold rule in which a fixed number of influencers prevent opinion change (e.g., unanimity and quasi-unanimity), we provide an efficient PAC learning algorithm provided that the number of influencers per agent is bounded. Secondly, under standard computational complexity assumptions, we prove that if agents' opinions follow the majority of their influencers, then there is no efficient PAC learning algorithm. We propose a polynomial-time heuristic that successfully learns consistent networks in over $98\%$ of our simulations on random graphs, with no failures for some specified conditions on the numbers of agents and opinion diffusion examples.

Authors: Paul Beame, Glenn Sun

Because CDCL produces proofs in the Resolution proof system, problems provably hard for Resolution are also provably hard for CDCL. Exponentially shorter proofs can sometimes be found using stronger proof systems such as $\text{Res}(\oplus)$, a generalization of Resolution to XNF formulas, whose constraints are disjunctions of parity equations ("linear clauses") such as $(x \oplus y) \lor \lnot (y \oplus z)$. While some modern solvers like CryptoMiniSAT reason on Boolean clauses with separate parity equations, reasoning about more general linear clauses is less explored. We present $\text{CDCL}(\oplus)$, a generalization of CDCL to XNF formulas, and prove a bidirectional connection with $\text{Res}(\oplus)$: $\text{CDCL}(\oplus)$ not only produces $\text{Res}(\oplus)$ proofs, but also polynomially simulates $\text{Res}(\oplus)$ given nondeterministic decisions and restarts, mirroring the classical relationship between CDCL and Resolution. Our key technical tool is a new set of inference rules for $\text{Res}(\oplus)$ that helps us translate Resolution-based subroutines such as 1-UIP clause learning. Altogether, $\text{CDCL}(\oplus)$'s parity reasoning includes branching on arbitrary parity equations, linear-algebraic reasoning during unit propagation, and learning linear clauses through conflict analysis. We provide a proof-of-concept implementation of $\text{CDCL}(\oplus)$ called Xorcle, which includes adaptations of existing CDCL heuristics to XNF formulas and an extension of LRUP proof logging that we call $\text{LRUP}(\oplus)$. On a selected suite of benchmarks focusing on native XNF formulas, Xorcle outperforms existing solvers such as Kissat and CryptoMiniSAT. Additionally, on Tseitin formulas written in CNF, even without preprocessing, Xorcle's running time appears to scale nearly polynomially.

Authors: A. R. Balasubramanian, Franzisco Schmidt

Nested counter systems (NCS) are a generalization of counter systems to higher-order counters. Here, a higher-order counter is allowed to have other (lower-order) counters as elements, instead of just a number. Such systems can be viewed as working on trees, where the height of the tree naturally corresponds to the highest order counter that the system is working with. It is known that the coverability problem for NCS, which asks if a given final tree can be covered from a given initial tree, is $\mathbf{F}_{ε_0}$-complete. Here $\mathbf{F}_{ε_0}$ is a class in the fast-growing hierarchy of complexity classes. In this paper, we consider an extension of NCS called nested reset counter systems (NRCS) that extends NCS with resets. We show that coverability for NRCS over order-$k$ counters is $\mathbf{F}_{Ω_k}$-complete where $Ω_k$ is the tower of height $k$ of the $ω$ ordinal. This gives the first natural hierarchy of complete problems for all of these classes. Furthermore, to prove our upper bounds, we also develop length function theorems for any fixed amount of applications of the multiset operation on finite sets. As an application of our results, we improve existing upper bounds for various problems from XML processing, graph transformation systems, $π$-calculus, logic and parameterized verification. Furthermore, using our completeness results for $k$-NRCS, we also prove $\mathbf{F}_{Ω_k}$-completeness of the considered problems from the realms of parameterized verification and logic, for all $k$.

Authors: Leslie G. Valiant

In current Large Language Models we can trust the production of smoothly flowing prose on the basis of the principles of machine learning. However, there is no comparably principled basis to justify trust in the content of the text produced. It appears to be conventional wisdom that addressing this issue by adding more principled reasoning is not computationally affordable. Here we propose a principled method of reasoning that is efficient enough to be practical for large language models. Further, the method allows the retention of much of the currently used software and hardware base. Our method for improving the functioning of large language models consists of a first stage of preprocessing that recodes the data to a Unary Relational Integracode that is more explicit about the relationships among the objects described in the text, followed as a second stage by a standard but possibly streamlined machine learning process that then also learns to predict these relationships. The method may be viewed as realizing a world model and applying beyond natural language, to vision and actions, for example, where the multiple properties of an object referred to in an input are brought together explicitly, rather than remaining distributed in the various references to it in the input. We articulate its advantages in terms of Robust Logic, a system for performing principled chaining on learned, and hence uncertain, information. We show that this recoding has the surprising and fortuitous property that, while succinct, it makes the task of learning a core subset of relational rules that hold in the world described in the training data polynomial time learnable in a defined sense, the polynomial depending on the complexity of the rule. This gives support for sound reasoning within each single call of the learned classifier as well as between multiple calls.

Authors: Ana Dodik, Isabella Yu, Kartik Chandra, Jonathan Ragan-Kelley, Joshua Tenenbaum, Vincent Sitzmann, Justin Solomon

Impossible objects, geometric constructions that humans can perceive but that cannot exist in real life, have been a topic of intrigue in visual arts, perception, and graphics, yet no satisfying computer representation of such objects exists. Previous work embeds impossible objects in 3D, cutting them or twisting/bending them in the depth axis. Cutting an impossible object changes its local geometry at the cut, which can hamper downstream graphics applications, such as smoothing, while bending makes it difficult to relight the object. Both of these can invalidate geometry operations, such as distance computation. As an alternative, we introduce Meschers, meshes capable of representing impossible constructions akin to those found in M.C. Escher's woodcuts. Our representation has a theoretical foundation in discrete exterior calculus and supports the use-cases above, as we demonstrate in a number of example applications. Moreover, because we can do discrete geometry processing on our representation, we can inverse-render impossible objects. We also compare our representation to cut and bend representations of impossible objects.

Authors: Kunal Bhosikar, Preet Savalia, Lokender Tiwari, Brojeshwar Bhowmick

The rapid growth of 3D content from modern reconstruction and generative pipelines, such as neural rendering and large-scale 3D asset generation, has led to an abundance of dense, noisy, and often non-manifold meshes. While these representations achieve high visual fidelity, their complexity poses significant challenges for downstream applications in simulation, AR/VR, and scientific computing, where efficient and reliable geometry is essential. This necessitates mesh simplification methods that are not only fast and robust to "in-the-wild" inputs, but also capable of preserving fine geometric structures and high-quality appearance. In this paper, we propose Feature-Aware Quadric Error Metric (FA-QEM), a comprehensive mesh simplification pipeline designed for modern 3D assets. Our approach introduces a novel multi-term quadric error formulation that jointly encodes geometric deviation, boundary curvature, and surface normal consistency, enabling optimal vertex placement that preserves sharp features even under aggressive simplification. Furthermore, we show that high-fidelity geometric simplification significantly improves downstream appearance transfer, serving as a superior front-end for texture mapping via successive mapping techniques. We conduct extensive evaluations on both AI-generated meshes and large-scale real-world datasets, including Thingi10K and the Real-World Textured Things dataset. Our results demonstrate that FA-QEM achieves consistently lower geometric error, better visual fidelity, and substantially faster runtimes compared to existing methods, while maintaining robustness across diverse and challenging inputs. These properties make FA-QEM a practical and effective component for scalable 3D reconstruction and generation pipelines.

Authors: Aleksey Upirvitskiy, Aleksandr Levin

We study leaf-to-ancestor path-minimum queries on a rooted, weighted tree in the oracle model, where the only allowed value operation is a comparison oracle on edge (or node) weights. We give a static data structure that, after O(n log h) preprocessing time, space, and oracle calls (where $n$ is the number of nodes and $h$ is the tree height), answers any leaf-to-ancestor query in O(1) worst-case time with zero oracle calls at query time. The method combines (I) an edge-to-node weight conversion with a deterministic tie-break to obtain a total order; (II) ladder (longest-path) decomposition; (III) binary lifting; and (IV) sparse-table RMQ built over ladder arrays, storing indices selected via the oracle during preprocessing. We also show that the preprocessing oracle-comparison bound is tight in the deterministic comparison model.

Authors: Amatya Sharma, Santhoshini Velusamy

Non-redundancy, introduced by Bessiere, Carbonnel, and Katsirelos (AAAI 2020), is a structural parameter for Constraint Satisfaction Problems ($\mathsf{CSPs}$) that governs kernelization, exact and approximate sparsification, and exact streaming complexity. It is the largest size of a $\mathsf{CSP}$ instance admitting no smaller subinstance with the same satisfying assignments. We study non-redundancy $\mathsf{NRD}_n(R)$ for Boolean symmetric $\mathsf{CSPs}$ defined by an $r$-ary relation $R$ whose value depends only on Hamming weight. An instance of $\mathsf{CSP}(R)$ has $n$ variables and constraints given by $r$-tuples; a constraint is satisfied exactly when the induced tuple lies in $R$. This class includes natural predicates such as cuts and $k$-SAT clauses. Our main result is a near-complete classification of the asymptotic growth of $\mathsf{NRD}_n(R)$ for symmetric Boolean predicates of arity at most $5$. Using computational experiments and algebraic upper- and lower-bound criteria, we resolve every predicate of arity at most $4$ and all but two predicates of arity $5$. For upper bounds, we introduce $t$-balancedness, a lifted, higher-degree version of the balancedness notion of Chen, Jansen, and Pieterse (Algorithmica 2020). We prove that $t$-balancedness is equivalent to the existence of degree-$t$ multilinear polynomials capturing $R$, and hence implies $\mathsf{NRD}_n(R)=O(n^t)$. For lower bounds, we use Carbonnel's (CP 2022) framework: predicates admitting a special reduction from $k$-ary OR inherit OR's lower bound $Ω(n^k)$. The only unresolved arity-$5$ predicates in our framework have bounds $Ω(n^2)$ and $O(n^3)$; we reduce their exact classification to natural extremal set-system questions.

Authors: Yuto Okada

In this paper, we show that it is NP-hard to determine whether a given graph admits a min-1-planar drawing. A drawing of a graph is min-$k$-planar if, for every crossing in the drawing, at least one of the two crossing edges involves at most $k$ crossings. This notion of min-$k$-planarity was introduced by Binucci, Büngener, Di Battista, Didimo, Dujmović, Hong, Kaufmann, Liotta, Morin, and Tappini [GD 2023; JGAA, 2024] as a generalization of $k$-planarity.

Authors: Rajiv Raman, Siddhartha Sarkar, Jatin Yadav

We study a geometric hitting-set problem in which the input consists of a set $P$ of weighted points and a family $S=H\cup V$ of axis-parallel segments in the plane. The goal is to select a minimum-weight subset of $P$ that hits every segment in $S$. Even restricted geometric hitting-set problems are known to be computationally hard, and for axis-parallel segments the standard decomposition into horizontal and vertical sub-instances yields only a simple factor-$2$ approximation. We present an LP-rounding algorithm that breaks the factor-2 barrier. For the weighted problem, we obtain a randomized $(1+2/e)$-approximation by combining systematic rounding on horizontal lines with an exact repair step on residual vertical sub-instances. In the unweighted case, a sharper analysis gives a $(1+1/(e-1))$-approximation. Finally, we consider the case where one of the sub-instances consists of lines instead of line segments, a problem considered by Fekete et al. (Geometric Hitting Set for Segments of Few Orientations, Theor. Comp. Sys., 62 (2) 2018),. In this case, we improve their result to obtain an approximation factor of $1+1/e$ and show that the problem is APX-hard. We also present algorithms for the generalization to $d$ orientations, as well as PTASes for bounded-complexity subclasses of the unweighted Hitting Set problem.

Authors: Quinten De Man, Gilvir Gill, Michael A. Bender, Laxman Dhulipala, David Tench

Dynamic connectivity is a fundamental dynamic graph problem, and recent algorithmic breakthroughs on dynamic graph sketching have reshaped what is theoretically possible: by encoding the graph as per-vertex linear sketches, these algorithms solve dynamic connectivity in only $Θ(V \log^2 V)$ space, independent of the number of edges,outperforming lossless $Θ(V+E)$-space structures that grow as the graph becomes denser. Prior to this work, no practical dynamic connectivity algorithm has been able to translate these theoretical breakthroughs into space savings on real-world graphs. The main obstacle is that per-vertex sketches cost thousands of bytes per vertex, so sketching only pays off once the graph becomes extremely dense. We observe that sparse real-world graphs are often not uniformly sparse, these graphs can contain dense cores on a small subset of vertices that account for a large fraction of edges. We exploit this structure via hybrid sketching: sketch only the dense core, and store the sparse periphery losslessly. We design new hybrid algorithms for fully-dynamic and semi-streaming connectivity with space $O(\min\{V+E, V \log V \log(2+E/V)\})$ w.h.p., simultaneously matching the lossless bound on sparse graphs, the sketching bound on dense graphs, and improving on both in an intermediate regime. A key component is BalloonSketch, a new l0-sampler reducing per-vertex sketch sizes by up to 8x. We implement HybridSCALE, a modular system treating the lossless and sketch-based components as subroutines. HybridSCALE is the first sketch-based dynamic connectivity system to save space on common real-world graphs. Compared to the state-of-the-art lossless baseline, HybridSCALE saves up to 15% space on sparse graphs (average degree < 100), up to 92% on intermediate density graphs (average degree ~ 100-1000), and up to 97% on dense graphs (average degree > 1000).

Authors: Ainesh Bakshi, Arpon Basu, Pravesh Kothari, Anqi Li

We prove that the maximum eigenvalue of the (both signed and unsigned) Laplacian of level $k$ Kikuchi graph of any graph $G$ with $m$ edges is at most $m+k$. This confirms four recent conjectures of Apte, Parekh, and Sud. As applications, we obtain that tensor products of one and two qubit product states achieve an approximation ratio of $5/8$ for Quantum Max Cut and $5/7$ for the XY Hamiltonian. Moreover, combining our bounds with the algorithms analyzed by Apte, Parekh, and Sud, yields efficient algorithms achieving an approximation ratio of $0.614$ for Quantum Max Cut and $0.674$ for the XY Hamiltonian. Finally, we also make modest progress on Brouwer's conjecture and improve Lew's bound on the sum of the top-$k$ eigenvalues of a Graph Laplacian.

Authors: Dario Cavallaro, Maximilian Gorsky, Stephan Kreutzer, Dimitrios M. Thilikos, Sebastian Wiederrecht

The Graph Minors Series of Robertson and Seymour forms the foundation of algorithmic structural graph theory, yielding fixed-parameter algorithms for problems such as Disjoint Paths, Rooted Minor Checking, and Folio. A key ingredient behind the fixed-parameter tractability of the $k$-Disjoint Paths problem is the irrelevant-vertex technique. This machinery is governed by the Vital Linkage Theorem and the so-called Linkage Function $\ell$. However, despite its foundational role, the best known bounds on the Linkage Function are enormous and are only implicitly understood. The quantitative bounds behind these results have traditionally been so large that the resulting algorithms are regarded as "galactic". Our main result is a general irrelevant-vertex theorem for a common generalisation of $k$-Disjoint Paths and Rooted Minor Checking for graphs of size at most $d,$ commonly called the $(k,d)$-Folio problem. Specifically, we show that for any graph $G$ in which the $k$ terminals are chosen from some set $R,$ if the treewidth of $G$ exceeds $β(k,b,d)\in$ $2^{{\bf poly}(b + d)}$ $\cdot {\bf poly}(k)$ then we can locate an irrelevant vertex for the $(k,d)$-Folio problem. Here, the quantity $b$ is the bidimensionality of $R,$ that is, the largest $b$ for which a $(b\times b)$-grid minor in $G$ can be rooted on $R$. Thus, the exponential component of the irrelevant-vertex threshold is driven by the bound on the bidimensionality, rather than by the number of terminals, and we argue that this dependence is essentially optimal up to polynomial factors. As a consequence, the Linkage Function satisfies $\ell(k) \in 2^{{\bf poly}(k)}$. Beyond its structural significance, our result yields improved parameter dependencies for algorithms for Disjoint Paths and Rooted Minor Checking}, and provides a quantitative improvement for a broad range of graph-minor-based algorithmic frameworks.

Authors: Dhanyamol Antony, L. Sunil Chandran, Anita Das, Shirish Gosavi, Dalu Jacob, Shashanka Kulamarva

The Burning Number Problem (BNP) models the spread of information or contagion in a network through a discrete-time process on a graph. At each step, one new vertex is selected as a burning source, while fire simultaneously spreads from previously burned vertices to their neighbors. The burning number of a graph is the minimum number of steps required to burn all vertices. The decision version asks whether the burning number is at most a given integer $k$. BNP is known to be NP-complete even on restricted graph classes such as path forests. We study BNP on connected regular graphs, a natural and previously unexplored graph class. We prove that BNP is NP-complete on connected cubic graphs, and moreover APX-hard under this restriction. We further show that BNP remains APX-hard on connected $d$-regular graphs for every fixed $d \geq 4$.

Authors: Mujin Choi, Tuukka Korhonen, Sang-il Oum

For an $n$-element matroid $M$ given by an $n \times n$ matrix representation over a finite field $\mathbb F$ and an integer $k$, we present an $(O_{k,\mathbb F}(n^2)+O(n^ω))$-time algorithm that either finds a branch-decomposition of $M$ of width at most $k$, or confirms that the branch-width of $M$ is more than $k$, where $ω< 2.3714$ is the matrix multiplication exponent, and the $O_{k,\mathbb F}(\cdot)$-notation hides factors that depend on $k$ and $\mathbb F$ in a computable manner. All previous algorithms including Hliněný and Oum [SIAM J. Comput. (2008)] and Jeong, Kim, and Oum [SIAM J. Discrete Math. (2021)] run in at least $Ω(n^3)$ time. Moreover, if the input matrix representation is given by a standard form, our algorithm runs in $O_{k,\mathbb F}(n^2)$-time, since $O(n^ω)$-time is only needed for finding a standard form of the input matrix. When $M$ is given by an $m \times n$ matrix, the overhead for finding a standard form is $O(mn \min(m,n)^{ω-2})$. As corollaries, we obtain faster algorithms for rank-width of directed graphs and path-width of matroids represented over a fixed finite field. Furthermore, we also present an approximation algorithm for finding branch-width that works on infinite fields provided that the input matrix is of a standard form and contains a bounded number of distinct values of entries. To suggest that our algorithm is optimal, we observe that for every field $\mathbb F$, deciding whether the branch-width of a matroid represented over $\mathbb F$ is $0$ is as hard as deciding whether a square matrix over $\mathbb F$ is singular. Under the assumption that singularity testing requires $Ω(n^ω)$-time, this implies that the overhead of $O(n^ω)$ is unavoidable. We also show strengthenings of this observation to rule out some approximations under this assumption.

Authors: Hriday Jain, Ketan Sabale, Aditya Shastri, Hiren Kumar Thakkar, Ashutosh Londhe

Sorting is a foundational primitive in modern data processing, influencing the execution speed of high-performance data pipelines. However, the algorithmic landscape is currently bifurcated by a pervasive "Stability Tax": practitioners must sacrifice either order preservation for high throughput or execution speed for stability. To address these limitations, this paper introduces, zSort, an adaptive z-score based distribution sorting algorithm that guarantees stability while avoiding pass complexity that scales with key-width. The performance of the proposed technique is evaluated using Microarchitectural analysis and experimental results. Microarchitectural analysis shows that zSort achieves a lower bad-speculation overhead (19.7%) than both stable baselines and several high-performance unstable algorithms and sustains a competitive IPC of 1.44. Empirical evaluation across diverse input distributions and datasets of up to 10^7 elements (64 bit) demonstrates that zSort consistently outperforms widely used comparison based stable sorting algorithms, achieving up to 3x-4.5x speedups, and a relatively better performance compared to LSD Radix, with larger gains on duplicate heavy and partially ordered inputs. Despite providing stability, zSort achieves comparable throughput as compared to high-performance unstable algorithms such as Skasort. It also maintains this performance on adaptive workloads where methods like Pdqsort typically excel and doesn't exhibit any extreme worst case. These results indicate that zSort substantially narrows the traditional performance gap between stable and unstable sorting and provides an efficient, stable sorting alternative.

Authors: Fabien Dufoulon, William K. Moses, Gopal Pandurangan

We study gossip algorithms for the fundamental rumor spreading problem, where the goal is to disseminate a rumor from a given source node to all nodes in an arbitrary (and unknown) graph. Gossip algorithms allow each node to call only one neighbor per round and are therefore highly message-efficient, with low per-node communication overhead per round. The state of the art present fast gossip algorithms, however they typically leverage large-sized messages. This undermines the light-weight communication advantage of gossip, since even though only one neighbor is contacted per round, the message size can be linear in $n$, the network size. Hence, a fundamental question is whether one can perform fast gossip using small messages. The main contribution of this paper is to answer the above question in the affirmative and present two gossip algorithms that achieve fast rumor spreading using messages of polylog{n} size. Specifically, we present the following algorithms: 1. An algorithm that runs in $O(c \log n / Φ_c)$ rounds for every $c \geq 1$, and $Φ_c$ is the weak conductance. Our bound in terms of weak conductance is essentially optimal. 2. An algorithm that depends on the network diameter (and is independent of the graph's conductance), which runs in $\tilde{O}(D+\sqrt{n})$ rounds with high probability. Our algorithm can be modified to output a minimum spanning tree (MST) in the same number of rounds, which is essentially round-optimal (even for non-gossip algorithms). Our gossip algorithms use graph sketches [Ahn, Guha, McGregor, SODA 2012] in a novel way to overcome communication bottlenecks and achieve small communication overhead with small message sizes.

Authors: Niv Buchbinder, Moran Feldman, Siyue Liu, Sherry Sarkar

We study random order semi-streaming algorithms for submodular maximization under a wide range of combinatorial constraint classes, including matroids, matroid $p$-parity, $p$-exchange systems and $p$-systems. For most of these classes of constraints, our results are the first improvement over what is known to be achievable for adversarial order. For matroids, matching and $p$-matchoids, previous random order results were known, and we improve over some of these as well. In the case of matroids, our improved results show a separation between adversarial and random order semi-streaming algorithms, and exponentially improve the number of passes necessary for getting $1 - 1/e - \varepsilon$ approximation for maximizing a monotone submodular function subject to a matroid constraint. We also prove a new hardness result showing a similar separation for $p$-systems. Our results are based on two new technical tools. One tool provides a general way to translate offline algorithms for many classes of constraints into random order semi-streaming algorithms. The other tool is a semi-streaming variant of a recently proposed offline algorithm for matroid constraints.

Authors: Sara Ahmadian, Edith Cohen, Mohammad Roghani

The classic online stochastic matching problem typically requires immediate and irrevocable matching decisions. However, in many modern decentralized systems such as real-time ride-hailing and distributed cloud computing, the primary bottleneck is often local communication bandwidth rather than the timing of the match itself. We formalize this challenge by introducing a two-stage local sparsification framework. In this setting, arriving requests must prune their realized compatibility sets to a strict budget of $k$ edges before a central coordinator optimizes the global matching. This creates a "middle ground" between local information constraints and global optimization utility. We propose a local selection strategy, parametrized by a fractional solution of the expected instance. Theoretically, we quantify the approximation ratio as a function of the solution's {\em spread}. We prove that under sufficient spread, our sparsifier globally preserves the expected size of the maximum matching. Empirically, we demonstrate the robustness of our approach using the New York City ride-hailing datasets and adversarial synthetic benchmarks. Our results show that near-optimal global matching is achievable even with highly constrained local budgets, significantly outperforming standard online baselines.

Authors: Devin Smedira, Abhijith Jayakumar, Sidhant Misra, Marc Vuffray, Andrey Y. Lokhov

Learning of continuous exponential family distributions with unbounded support remains an important area of research for both theory and applications in high-dimensional statistics. In recent years, score matching has become a widely used method for learning exponential families with continuous variables due to its computational ease when compared against maximum likelihood estimation. However, theoretical understanding of the statistical properties of score matching is still lacking. In this work, we provide a non-asymptotic sample complexity analysis for learning the structure of exponential families of polynomials with score matching. The derived sample bounds show a polynomial dependence on the model dimension. These bounds are the first of its kind, as all prior work has shown only asymptotic bounds on the sample complexity.

Authors: Sanjay Jain, Junqiang Peng, Frank Stephan, Haoyun Tang, Mingyu Xiao

Parity-SAT is the problem of determining whether a given CNF formula has an odd number of satisfying assignments. As a canonical $\oplus$P-complete problem, it represents a fundamental variant of the exact model counting problem (#SAT). Under the Strong Exponential Time Hypothesis (SETH), Parity-SAT admits no $O^*((2-\varepsilon)^n)$-time or $O^*((2-\varepsilon)^m)$-time algorithm for any constant $\varepsilon>0$, where $n$ and $m$ denote the numbers of variables and clauses, respectively. Thus, breaking the $2^n$ or $2^m$ barrier appears impossible in full generality. In this work, we revisit this barrier through structural restrictions and a refined exploitation of parity. We study Parity-$d$-occ-SAT, where each variable appears in at most $d$ clauses, and obtain three main results. First, we design {a randomized} $O^*(2^{m(1-1/O(d))})$-time algorithm, thereby breaking the $2^m$ barrier for every fixed $d$. Second, for the special case $d=2$, we develop a significantly sharper branching algorithm running in $O^*(1.1193^n)$ time or $O^*(1.3248^m)$ time. Third, leveraging the structural insights underlying the $d=2$ case, we obtain an $O^*(1.1052^L)$-time algorithm for general Parity-SAT, where $L$ denotes the formula length. All algorithms use only polynomial space. Notably, our running-time bounds are better than the best known bounds for the corresponding exact counting counterparts, highlighting a genuine algorithmic advantage of parity over counting. Conceptually, our results demonstrate that parity admits finer structural reductions and more efficient branching than exact model counting, and that bounded occurrence can be systematically leveraged to circumvent classical exponential barriers.

Authors: Daniel Hathcock, R. Ravi, Amitabh Sinha

In e-retail, order fulfillment speed has become one of the most important metrics affecting customer satisfaction. While common wisdom dictates that maintaining a large global fulfillment network maximizes efficiency via economies of scale, recent evidence has shown that breaking up the network into smaller regions can yield significant speed improvements. In this paper, we consider a simple abstract model of order fulfillment by which we explain this phenomenon. We characterize fulfillment assignments satisfying an equilibrium condition based on the greedy fulfillment strategy, and quantify how the resulting fulfillment delay can be decreased by regionalizing the network. Finally, we provide some algorithmic results for computing low delay assignments, and some simulations supporting our equilibrium framework.

The next TCS+ talk will take place this coming Wednesday, May 20th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Shyamal Patel from Columbia University will speak about “Learning Functions of Halfspaces” (abstract below).

You can reserve a spot as an individual or a group to join us live by signing up on the online form. Registration is not required to attend the interactive talk, and the link will be posted on the website the day prior to the talk; however, by registering in the form, you will receive a reminder, along with the link. (The recorded talk will also be posted on our website afterwards) As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see the website.

Abstract: Learning halfspaces is one of the most basic and fundamental problems in learning theory. While we have a good understanding of the problem, simple generalizations such as learning an intersection of halfspaces appear much more challenging. While learning an intersection of halfspaces can be done efficiently if we assume our data is drawn from a uniform or log-concave distribution, there are large gaps in our understanding when we make no assumptions on the background distribution. In particular, even for learning an intersection of two halfspaces, we have no non-trivial learning algorithms and no evidence that the problem requires super-polynomial time.
In this talk, we’ll describe a sub-exponential time algorithm for learning an intersection of halfspaces and more generally for learning an arbitrary function of halfspaces (joint work with Josh Alman and Rocco Servedio).

By plustcs

The Fibonacci heap is a priority queue data structure in which finding and removing the top-priority item takes logarithmic time (like a binary heap) but reprioritizing items to have higher priority takes only constant time, under amortized time analysis. This property is useful for speeding up the time complexity of algorithms including Dijkstra’s algorithm for shortest paths and Jarník’s algorithm for minimum spanning trees, so that they take logarithmic time per vertex and constant time per edge.

In its internal structure, the Fibonacci heap is a forest of trees, with one tree node per prioritized object, higher priorities towards to roots of the trees. The analysis of its logarithmic-time find-and-remove operation can be split into two parts: showing that the time of this operation is proportional to the maximum number of children of any node in this tree (the degree of the node), and showing that the degree is logarithmic. It is the second part of this analysis that gives the data structure its name: a node with degree \(d\) must be the root of a subtree at least a Fibonacci number of nodes, \(F_{d+2}\) (numbering the Fibonacci numbers starting from \(F_0=0\) and \(F_1=1\)). For instance, a subtree whose root has three children must contain at least five nodes, etc. Therefore, in a Fibonacci heap that reaches a maximum size of \(n\), the degree is bounded by the requirement that \(F_{d+2}\le n\), for otherwise we would have a tree with more elements than the entire heap. But this standard analysis, which you can find in the original Fibonacci heap paper, Wikipedia, or the textbook Introduction to Algorithms, is not tight! It turns out that the actual requirement is \(F_{d+3}\le n\). Or in other words, the degrees of the trees in a Fibonacci heap are smaller by one than the bound given by the standard analysis.

To prove that each subtree has a Fibonacci number of nodes, one uses a lemma that the \(i\)th child of any node (in the order that it was added as a child) must itself have degree at least \(i-2\). This follows from the three ways that the Fibonacci heap data structure can change its forest. First, a deletion operation can remove the root of its tree, making its children into roots, but their degrees remain unchanged. Second, any deletion triggers a cleanup phase in which pairs of trees with equal numbers of children are merged by making one root into the child of another. If this merge adds a node as the \(i\)th child of the merged root, the new child had the same degree as the root before the merge, \(i-1\). And third, a change of priority can trigger the removal of some tree edges (promoting the child of a node to become a new tree root), but every node that is not a tree root can have only one child removed while it is not a root. Thus, the \(i\)th child of a node, which was at least the \(i\)th child and had degree at least \(i-1\) when it first became a child, can only have its degree decrease by one, to \(i-2\).

Based on this lemma, one can construct a sequence of the smallest trees \(T_d\) with each root degree \(d\). In this sequence, each tree \(T_d\) is formed from \(T_{d-1}\) by adding to it another child with \(d-2\) grandchildren (the minimum allowed by the lemma). The added child’s subtree takes the form of \(T_{d-2}\), the smallest subtree that could give that number of grandchildren. Thus, \(T_d=T_{d-1}+T_{d-2}\) for an addition operation on trees that adds the second tree argument of the operation as a child of the first tree argument. This is the Fibonacci recurrence, and these trees have a Fibonacci number of nodes.

But now, instead of looking at the minimum size of a tree with degree \(d\), let’s consider what situation has to occur for a tree with degree \(d\) to be created. As a base case, a tree with degree one is created by merging two trees of degree zero. For this merge to happen, the Fibonacci heap needs to perform a deletion operation (to trigger the merge) in a state where there are already two trees of degree zero to be merged. Thus, creating a tree with degree one requires there to exist three heap elements, before the deletion operation: one to be deleted and two more in the merged trees. Similarly, to create a tree with degree two, we need to merge two trees of degree one (with at least two nodes each), triggered by a deletion of another element. So this creation requires five elements: four in the two merged trees and one to be deleted to trigger a merge or sequence of merges that ends up merging two degree-one trees.

More generally, we can prove by induction that creating a tree of degree \(d\) can only happen after the heap has reached a size of \(F_{d+3}\). To create a tree of degree \(d\), we need the first of two trees of degree \(d-1\) to be created (in the same merge step or in an earlier merge step as the one creating the tree of degree \(d\)), and then the second, and then a merge of the two. When the first tree is created, it contains at least \(F_{d+1}\) elements that cannot participate in the creation of the second tree, by the tree size bound from the old analysis of Fibonacci heaps. When the second tree is created, the trees that merge to form it and the deleted element that trigger the merge comprise at least \(F_{d+2}\) elements, by the induction hypothesis. Together these give \(F_{d+1}+F_{d+2}=F_{d+3}\) elements in the heap, just before the deletion that triggered the creation of the second merged subtree and then the merge of the two degree-\((d-1)\) trees into a single degree-\(d\) tree.

This induction proof also guides a construction of a sequence of operations that creates a degree-\(d\) tree, and then trims it down to the form \(T_{d-1}\), while keeping the maximum number of elements in the heap at most \(F_{d+3}\). As a base case, inserting three elements into an empty heap and deleting one will create a degree-one tree \(T_1\), with no trimming needed. Then for any degree \(d>1\), create a degree-\((d-1)\) tree and trim it to the form \(T_{d-1}\) recursively. Then, create a second degree-\((d-1)\) tree. The merge step that creates it will also merge it with the first \(T_{d-1}\); assign priorities in such a way that the second tree becomes a child of the first \(T_{d-1}\). Continue performing improve-priority and delete operations that trim the second tree to the form \(T_{d-1}\), while it remains a subtree of the first tree, producing a tree formed by merging two copies of \(T_{d-1}\). Then, use additional improve-priority and delete operations to remove the last child of the last child of the root, producing a tree in the form of \(T_d\). The number of elements in the heap rises to \(F_{d+2}\) while creating the first \(T_{d-1}\), falls back down to \(F_{d+1}\), and then rises to \(F_{d+1}+F_{d+2}=F_{d+3}\) while finishing the construction, matching the lower bound.

(Discuss on Mastodon)

By David Eppstein

For those very long-time readers this blog extensively covered prediction markets from 2006 to 2008. In a prediction market, you have a future event, such as the winner of an election, and a market that pays off one dollar if that event happens and nothing if it doesn't. The price of this market corresponds to a predicted probability that the event will happen. 

I worked with David Pennock and Yiling Chen to create an interactive map that colored every state based on how likely it was to go Democratic or Republican for both the presidential, gubernatorial and Senate races.

This all ended when Intrade, the source of the data that we used, went out of business after its CEO died climbing Mount Everest and may have embezzled money from the company.

In 2016 prediction markets went out of favor after badly predicting against Brexit once and Trump twice. 

But what's old becomes new again. Prediction markets are back with a bang, with Kalshi and Polymarket providing real money markets open to U.S. citizens, something we didn't legally have, except for very low stakes, twenty years ago.

Prediction markets play two distinct roles:

1. As a betting system so people can put their "money where their mouth is" based on their beliefs.
2. As an information aggregation system, to use the wisdom of the crowds to predict future events.

By Lance Fortnow

This post gives a fixed view schedule version of Simplex, called Simplex FVS, with the advantages of a fixed view schedule discussed here. In the FVS design, the start and end times of each view are fixed in advance; this requires synchronized clocks. We number protocol views starting at $1$, and view $v$ starts at time $3v\Delta$. After a view ends, parties no longer sign new messages for it, but...

By Ittai Abraham

Authors: Christopher Williamson

A pair of probability distributions over $\{0,1\}^n$ is said to be $(k,δ)$-wise indistinguishable if all of the size $k$ marginals are within statistical distance at most $δ$. Previous works introduced this concept and study when and how well one can distinguish between such a pair of symmetric distributions by observing $t$ bits. We use a simple hypergeometric smoothing approach and Hahn polynomials to obtain new upper bounds that apply across a wider range of parameters and improve previously available bounds in several regimes. In particular, prior works left open the basic question of whether there exist constants $0

Authors: Yuetai Li, Fengqing Jiang, Yichen Feng, Kaiyuan Zheng, Luyao Niu, Bhaskar Ramasubramanian, Basel Alomair, Linda Bushnell, Radha Poovendran

Many online decision problems over combinatorial actions are addressed via convex relaxations, leading to online convex optimization with piecewise linear objectives and induced polyhedral structure. We show that regret in such problems is governed by \emph{polyhedral instability}: the number of changes of the active region. Under full information feedback and fixed partition assumptions, if $\mathrm{RS}_T$ denotes the number of region switches and $V_{\max}$ the maximum number of vertices per region, we prove $\Regret_T= Θ(\sqrt{(1+\mathrm{RS}_T)\,T\,\log V_{\max}})$ interpolating between experts-like and dimension-dependent OCO rates. For online submodular--concave games under Lovász convexification, this reduces to the permutation-switch count $\mathrm{SC}_T$, yielding the matching rate $\Regret_T= Θ(\sqrt{(1+\mathrm{SC}_T)\,T\,\log n})$. Experiments on synthetic and real combinatorial problems (shortest path, influence maximization) validate the predicted scaling and indicate that low-instability regimes can arise in practice without explicit enumeration of actions.

Authors: Tatiana Rocha Avila, Julian Christoph Brinkmann, Alexander Leonhardt, Conrad Schecker

We consider the Minimum-$(k,ρ)$-$\mathrm{Shortcut}$ problem ($\min(k,ρ)\text{-}\mathrm{Shortcut}$), where the goal is to find the smallest set of shortcut edges such that every vertex in a given graph can reach its $ρ$ closest vertices using paths of at most $k$ edges. This is a fundamental graph optimization problem used to accelerate parallel shortest path algorithms. It is well-known that the problem is trivially solvable for the cases $k=1$ and $k\geqρ$. While recent work by Leonhardt, Meyer, and Penschuck (ESA 2024) showed that in undirected graphs $\min(k,ρ)\text{-}\mathrm{Shortcut}$ is NP-hard for $k\geq 3$ if $ρ=Θ(n^ε)$, the boundary where the problem transitions from polynomial-time solvable to NP-hard remained open. In this paper, we narrow this gap significantly. We present a simpler and more direct reduction from the Hitting Set problem which establishes that $\min(k,ρ)\text{-}\mathrm{Shortcut}$ is NP-hard for $k\geq2$ and $ρ\geq k+2$ in both directed and undirected graphs. Complementing this, we use the symmetry of the undirected case to show that $ρ=k+1$ is solvable in polynomial time, a regime where the directed version remains a candidate for NP-hardness. Therefore, we obtain an almost complete characterization of the complexity of $\min(k,ρ)\text{-}\mathrm{Shortcut}$, with the sole remaining open case being $ρ= k+1$ in the directed setting.

Authors: Johannes K. Fichte, Markus Hecher, Yasir Mahmood, Zhengjun Wang

Argumentation is an important topic of AI for modelling and reasoning about arguments. In abstract argumentation, we consider directed graphs, so-called argumentation frameworks (AF), that express conflicts between arguments. The semantics is defined by the notion of extensions, which are sets of arguments that satisfy particular relationship conditions in the AF. Usually, standard reasoning in argumentation do not reveal how far apart extensions are. We introduce a quantitative notion of diversity of extensions based on the symmetric difference and provide a systematic complexity classification. Intuitively, diversity captures whether extensions of a framework (accepted viewpoints) differ only marginally or represent fundamentally incompatible sets of arguments. We study whether an AF admits k-diverse extensions, admits k-diverse extensions covering specific arguments, and to compute the largest k for which an AF admits k-diverse extensions. We outline a prototype and provide an evaluation for computing diversity levels.

Authors: Arshia Soltani Moakahr, Faraz Ghahremani, Kiarash Banihashem, MohammadTaghi Hajiaghayi

Decision tree learning has long been a central topic in theoretical computer science, driven by its practical importance. A fundamental and widely used method for decision tree construction is the top-down greedy heuristic, which recursively splits on the most influential variable. Despite its empirical success, theoretical analysis of this heuristic has been limited. A recent breakthrough by Blanc et al. (ITCS, 2020) provided the first rigorous theoretical guarantees for the greedy approach, but only under the uniform distribution. We extend this analysis to the more general and practically relevant setting of arbitrary product distributions. Our main result shows that for any function $f$ computable by an optimal decision tree of size $s$, maximum depth $D_{\text{opt}}$, and average depth $Δ_{\text{opt}}$, the greedy heuristic constructs an $ε$-approximating tree whose size grows at most with $\exp\bigl(Δ_{\text{opt}} D_{\text{opt}} \log(e/ε)\bigr)$. In the special case where the optimal tree is a full binary tree, this bound improves upon the bound of Blanc et al. and holds under a strictly broader class of distributions. Moreover, we present an algorithm based on the top-down greedy heuristic that is entirely parameter-free -- it requires no prior knowledge of the optimal tree's size or depth -- offering a practical advantage over Blanc et al.'s method.

Authors: Nathaniel Glover, Jan Hoffmann

Hofmann (1999) introduced the functional programming language LFPL to characterize the functions computable in polynomial time using an affine type system. LFPL enables a natural programming style, including nested recursion, and has inspired the development of type systems for automatic cost analysis, linear dependent type theories, and efficient memory management in functional programming languages. Despite its prominence, there does not exist a self-contained presentation, let alone a full mechanization, of LFPL and its core metatheory. This article presents a modern account and mechanization of LFPL and its metatheory with the goal of being self-contained and accessible while streamlining the strongest-known soundness and completeness results. The soundness proof works with the language LFPL+, which extends LFPL with additional language features. The proof is novel, adapting a technique by Aehlig and Schwichtenberg (2002) to construct explicit polynomials that bound the cost of an LFPL+ expression with respect to a big-step cost semantics. The completeness proof shows that LFPL programs can simulate polynomial-time Turing machines while only relying on restricted forms of linear functions and lists. It has the same structure as the original proof by Hofmann (2002) but greatly simplifies the core argument with a novel stack-like data structure that is implemented with first-class functions and lists. The mechanization includes the full soundness and completeness proofs, and serves as one of the first case studies of mechanized metatheory in the recently developed proof assistant Istari.

Authors: Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti, Timothé Picavet, Gustav Schmid

One of the central models in distributed computing is Linial's LOCAL model [SIAM J. Comp. 1992]. Over time, researchers have studied distributed graph problems in the LOCAL model under slightly different assumptions, such as whether nodes know the exact network size $n$, only a polynomial upper bound on $n$, or nothing at all. We ask whether these differences are merely technical or fundamentally affect the theory of Locally Checkable Labelings (LCLs), one of the most studied problem classes. LCLs are graph problems whose valid solutions can be characterized by a finite set of allowed constant-radius neighborhoods. Since their introduction by Naor and Stockmeyer [FOCS 1995], they have become central in distributed computing, and the last decade has seen major progress in understanding their complexity. For example, Chang, Kopelowitz, and Pettie [FOCS 2016] showed that the randomized complexity of any LCL on $n$-node graphs is at least its deterministic complexity on $\sqrt{\log n}$-node graphs. Later, Chang and Pettie [FOCS 2017] showed that any randomized $n^{o(1)}$-round algorithm for LCLs on bounded-degree trees can be turned into a deterministic $O(\log n)$-round algorithm. Then, Balliu et al. [STOC 2018] showed that such automatic speedups are impossible for general bounded-degree graphs. However, these results fundamentally rely on nodes knowing $n$. How much does this assumption affect the theory of LCLs? Our work shows that if nodes are oblivious to $n$, or know only a polynomial upper bound on it, then even on trees, the theory of LCLs changes significantly. While the fundamental classification of problems remains the same, we show the landscape becomes much more complex: for example, for LCLs, randomness helps in more cases; some problems have very unnatural complexities; and some have a lower bound that depends on which definition of $Ω$ we use!

Authors: Alexandru Gheorghiu, Dale Jacobs, Saeed Mehraban, Arsalan Motamedi

We study the computational complexity of quantum state isomorphism problems under group actions: given two quantum circuits that prepare pure or mixed states, decide whether the two states are related by a group action. This can be seen as a quantum state version of the Hidden Shift Problem, in much the same way that the State Hidden Subgroup Problem is a quantum version of the ordinary Hidden Subgroup Problem. We prove several results for this computational problem: - For the pure-state version, we show that the problem is BQP-hard for all nontrivial groups, and contained in QCMA $\cap$ QCSZK. We further obtain refined results for specific groups of interest: for abelian groups we show that the problem reduces to the state hidden subgroup problem over the generalized dihedral group; for the Clifford group, the problem is at least as hard as Graph Isomorphism under polynomial-time reductions; for the Pauli group it is BQP-complete. - For the mixed-state version, for nontrivial, finite and efficiently representable groups, the problem is QSZK-complete. - We also study a variant of this problem over an infinite group, in particular, the bosonic linear optical unitaries. We show that in the setting where the classical description of the quantum state is given in a suitable wave function representation known as the stellar representation, the problem is at least as hard as Graph Isomorphism, and is contained in NP $\cap$ SZK. Prior to our work, state isomorphism problems had only been studied for the symmetric group [LG17]. As a consequence of our results, we resolve an open question posed in [HEC25] about the existence of a quantum algorithm for the abelian state hidden subgroup problem on mixed states. We show that this problem is QSZK-hard in the worst case, thereby ruling out an efficient quantum algorithm unless QSZK = BQP.

Authors: Dongzhe Zheng, Tao Zhong, Christine Allen-Blanchette

In this paper, we study solution operators of physical field equations on geometric meshes from a function-space perspective. We reveal that Hodge orthogonality fundamentally resolves spectral interference by isolating unlearnable topological degrees of freedom from learnable geometric dynamics, enabling an additive approximation confined to structure-preserving subspaces. Building on Hodge theory and operator splitting, we derive a principled operator-level decomposition. The result is a Hybrid Eulerian-Lagrangian architecture with an algebraic-level inductive bias we call Hodge Spectral Duality (HSD). In our framework, we use discrete differential forms to capture topology-dominated components and an orthogonal auxiliary ambient space to represent complex local dynamics. Our method achieves superior accuracy and efficiency on geometric graphs with enhanced fidelity to physical invariants. Our code is available at https://github.com/ContinuumCoder/Hodge-Spectral-Duality

Authors: Martino Bernasconi, Matteo Castiglioni, Andrea Celli, Alexandros Hollender

We study the query complexity of min-max optimization of a nonconvex-nonconcave function $f$ over $[0,1]^d \times [0,1]^d$. We show that, given oracle access to $f$ and to its gradient $\nabla f$, any algorithm that finds an $\varepsilon$-approximate stationary point must make a number of queries that is exponential in $1/\varepsilon$ or $d$.

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

We construct an explicit distribution $\mathbf{D}$ over $\{0,1\}^N$ that exhibits an essentially optimal separation between adaptive and non-adaptive cell-probe sampling. The distribution can be sampled exactly when each output bit is allowed two adaptive probes to an arbitrarily long sequence of independent uniform symbols from $[N]$. In contrast, any non-adaptive sampler requires $\widetildeΩ(N)$ non-adaptive cell probes to generate a distribution with total variation distance less than $1-o(1)$ from $\mathbf{D}$. This provides a $2$-vs-$\widetildeΩ(N)$ separation for sampling with adaptive versus non-adaptive cell probes, improving upon the $2$-vs-$\widetildeΩ(\log N)$ separation of Yu and Zhan (ITCS '24) and the $(\log N)^{O(1)}$-vs-$N^{Ω(1)}$ separation of Alekseev, Göös, Myasnikov, Riazanov, and Sokolov (STOC '26).

Authors: Joshua M. Courtney

Multivariate quantum signal processing (M-QSP) has recently been shown to be applicable for non-Hermitian Hamiltonian simulation, opening several problems regarding the optimization landscape, angle-finding, and constant-factor analysis. We resolve several of these problems here. We find the anti-Hermitian query complexity $d_I = Θ(\betaI T + \log(1/\varepsilon)/\log\log(1/\varepsilon))$ to be tight, established via Chebyshev coefficient bounds, modified Bessel function asymptotics, and Lambert~$W$ inversion. Fast-forwarding to $d_I = \mathcal{O}(\sqrt{\betaI T})$ is impossible in the bivariate polynomial model, though a linear state-dependent improvement to $d_I = \mathcal{O} β_{\mathrm{eff}} T + \log(1/\varepsilon)/\log\log(1/\varepsilon))$ is achievable. The optimization landscape of M-QSP admits spurious local minima, but a warm-start basin guarantee ensures the two-stage algorithm converges. CRC-exploiting block peeling reduces angle-finding from $\mathcal{O}(d^3)$ to $\mathcal{O}(d^2)$ classical operations, and optimized error allocation yields a leading constant of approximately~$2$ relative to the information-theoretic lower bound. A constant-ratio condition extends to non-identical signal operators, enabling time-dependent non-Hermitian simulation with query complexity $\mathcal{O}(\int_0^T(\alphaR(s) + \betaI(s))\,ds + \log(1/\varepsilon)/\log\log(1/\varepsilon))$. Block-encoding overhead $e^{-2\betaI T}$ holds across all function classes within the walk-operator oracle model, and dilational methods (Schrödingerization) achieve the walk-operator barrier. A precisely characterized direct-access construction achieves the intrinsic barrier $e^{-2ωT}$ (with $ω< \betaI$ for non-commuting Hamiltonians) on a restricted domain, though extension to the full bitorus remains open.

Authors: Steve Hanneke, Anay Mehrotra, Grigoris Velegkas, Manolis Zampetakis

Valiant's 1984 paper is widely credited with introducing the PAC learning model, but it, in fact, introduced a different model: unlike PAC learning, the learner receives only positives, may issue membership queries, and must output a hypothesis with no false positives. Prior work characterized variants, including the case without queries. We revisit Valiant's original model and ask: *Which classes are learnable in it?* For every finite domain, including Valiant's Boolean-hypercube setting, we show that a class is learnable if and only if every realizable positive sample can be certified by a poly-size adaptive query-compression scheme. This is a new variant of sample compression where the learner certifies samples via a short interaction with the membership oracle. Our characterization shows that learnability in Valiant's model is strictly sandwiched between learnability in the PAC model and the variant of Valiant's model without membership queries. This is one of the rare cases where introducing membership queries changes the set of learnable classes, and not just the sample or computational complexity. Next, we study the natural extension of the model to arbitrary domains. While we do not obtain an exact characterization, our techniques readily generalize and show that the same strict sandwiching persists. Finally, we show that $d$-dimensional halfspaces, which are not learnable without queries, are learnable with queries: we give a $\mathrm{poly}(d) \tilde{O}(1/ε)$ sample and $\mathrm{poly}(d) \mathrm{polylog}(1/ε)$ query algorithm, and prove that at least $Ω(d)$ samples or queries are necessary. To our knowledge, this is the first algorithm for halfspaces in Valiant's model. Together, these results uncover a surprisingly rich theory behind Valiant's original notion of learnability and introduce ideas that may be of independent interest in learning theory.

Authors: Ying Feng, Piotr Indyk, Michael Kapralov, Dmitry Krachun, Boris Prokhorov

Vector quantization via random projection followed by scalar quantization is a fundamental primitive in machine learning, with applications ranging from similarity search to federated learning and KV cache compression. While dense random rotations yield clean theoretical guarantees, they require $Θ(d^2)$ time. The randomized Hadamard transform $HD$ reduces this cost to $O(d \log d)$, but its discrete structure complicates analysis and leads to weaker or purely empirical compression guarantees. In this work, we study a variant of this approach: dithered quantization with a single randomized Hadamard transform. Specifically, the quantizer applies $HD$ to the input vector and subtracts a random scalar offset before quantizing, injecting additional randomness at negligible cost. We prove that this approach is unbiased and provides mean squared error bounds that asymptotically match those achievable with truly random rotation matrices. In particular, we prove that a dithered version of TurboQuant achieves mean squared error $\bigl(π\sqrt{3}/2 + o(1)\bigr) \cdot 4^{-b}$ at $b$ bits per coordinate, where the $o(1)$ term vanishes uniformly over all unit vectors and all dimensions as the number of quantization levels grows.

Authors: Dipan Dey, Telikepalli Kavitha

Our input is a directed graph $G = (V,E)$ on $n$ vertices and $m$ edges with a designated root vertex $r$ and a function $cost: E \rightarrow \mathbb{R}_{\geq 0}$. The problem is to maintain a min-cost arborescence in $G$ in the presence of edge faults (a single fault at a time). Edge faults are transient and once the faulty edge is repaired, the original min-cost arborescence $\mathcal{T}$ is restored. Whenever an edge fault happens, we need to update $\mathcal{T}$ to a min-cost arborescence in $G-f$, where $f$ is the faulty edge. Since computing a min-cost arborescence in $G - f$ takes $O(m + n\log n)$ time, we seek to construct a sparse subgraph $H$ in a preprocessing step such that in the event of any edge $f$ failing, it suffices to compute a min-cost arborescence in $H - f$ in order to find a low-cost arborescence in $G - f$. In the unweighted setting, this is the fault-tolerant subgraph problem for single-source {\em reachability}. Baswana, Choudhary, and Roditty (SICOMP, 2018) showed a $k$-fault tolerant reachability subgraph of size $O(2^kn)$, where $k$ is the number of edge faults. We show a simple polynomial-time algorithm to construct a subgraph $H$ of size $O(n^{3/2})$ such that, for any $f \in E$, a min-cost arborescence in $H-f$ is a 2-approximation of a min-cost arborescence in $G-f$. Thus whenever an edge fault happens, we can find a 2-approximate min-cost arborescence in $G-f$ in $O(n^{3/2})$ time. Our second problem is in the matroid setting. The input is a matroid $M = (E, {\cal I})$ with a function $cost: E \rightarrow \mathbb{R}$. The problem is to compute a sparse $S \subseteq E$ (called a $k$-fault tolerant preserver) such that for any $F \subseteq E$ with $|F| \le k$, the matroid $M|(S\setminus F)$ contains a min-cost basis of $M|(E\setminus F)$. We show a tight bound of $k.rank(E)$ on the size of a $k$-fault tolerant preserver.

Authors: Christian Møller Mikkelstrup, Anders Bjorholm Dahl, Philip Bille, Vedrana Andersen Dahl, Inge Li Gørtz

Computing a minimum $s$-$t$ cut in a graph is a solution to a wide range of computer vision problems, and is often done using the Boykov-Kolmogorov (BK) algorithm. In this paper, we revisit the BK algorithm from both a theoretical and practical point of view. We improve the analysis of the time complexity of the BK algorithm to $O(mn|C|)$ and propose a new algorithm, the fast and compact BK (fcBK) algorithm, with a time complexity of $O(m|C|)$, where $m$, $n$, and $|C|$ are the number of edges, number of vertices, and the capacity of the cut, respectively. We additionally propose a compact graph representation that allows our implementation to find a minimum $s$-$t$ cut in a graph with upwards of $10^9$ vertices and $10^{10}$ edges on a machine with 128 GB of memory. We find our implementation of the BK algorithm to be the fastest available implementation of the BK algorithm when evaluating on a comprehensive set of benchmark datasets, highlighting the importance of memory-efficient implementations. We make our implementations publicly available for further research and implementation development within minimum $s$-$t$ cut algorithms.

Authors: Asaf Lev-Ran, Pavel Arkhipov, Vladimir Kolmogorov

We consider the MAP-MRF inference task, that is, minimizing a function of discrete variables represented as a sum of unary and pairwise terms. A prominent approach for tackling this NP-hard problem in practice is to solve its natural LP relaxation and then iteratively tighten the relaxation by adding clusters. Based on some theoretical observations, we propose a new technique for identifying such clusters. It works by running the Singleton Arc Consistency algorithm in a certain CSP instance. Experimental results indicate that the new tightening technique outperforms the previous approach by [Sontag et al. UAI 2012] that searches for frustrated cycles. Our code will be made available at https://github.com/vnk-ist/MAP-MRF/.

Authors: Samuel German

A vertex-coloring of a connected graph $G$ is a strong conflict-free vertex-connection coloring if every two distinct vertices are joined by a shortest path on which some color appears exactly once. The minimum number of colors in such a coloring is the strong conflict-free vertex-connection number $\operatorname{svcfc}(G)$. We study this problem under the parameter twin cover. Let $X$ be a twin cover of $G$ of size $t$, and let $k$ be the target number of colors. In our first result, given $(G,k)$ together with a twin cover $X$, we reduce in polynomial time to an equivalent annotated instance on at most $\max\{2,t+(t+1)k2^{t+k-1}\}$ vertices. Hence the annotated version of Strong CFVC Number, in which a twin cover is supplied as part of the input, is fixed-parameter tractable parameterized by $t+k$. Using this bound, we then obtain a kernel parameterized by $\operatorname{tc}(G)+k$; in particular, for every fixed $k$, the problem is fixed-parameter tractable parameterized by the twin-cover number alone. In our second result, we prove every connected graph $G$ with twin cover $X$ of size $t$ satisfies $χ(G)\le \operatorname{svcfc}(G)\le χ(G)+t$. More generally, if $Y\subseteq X$ intersects every shortest path of length at least $3$, then $\operatorname{svcfc}(G)\le χ(G)+|Y|$. We also derive an exact expression for the chromatic number on graphs of bounded twin-cover number: for every proper coloring $\varphi$ of $G[X]$, the minimum number of colors needed to extend $\varphi$ to all of $G$ is $K_\varphi=\max_{S\subseteq X}(|\varphi(S)|+m(S))$, and hence $χ(G)=\min_{\varphi\text{ proper on }G[X]} K_\varphi$. Our results provide the first evidence that twin cover is a useful parameter for strong conflict-free vertex-connection and show that, once a twin cover is fixed, the remaining difficulty is concentrated in a bounded additive gap above the chromatic number.

Authors: Peter Davies-Peck

The classic lower bound of Kuhn, Moscibroda and Wattenhofer [JACM 2016] states that approximate maximum matching and approximate vertex cover (among other problems) in the LOCAL model require $Ω(\min\{\sqrt{\frac{\log n}{\log\log n}}, \frac{\log Δ}{\log\log Δ}\})$ rounds, for any polylogarithmic or smaller approximation ratio. As a function of $Δ$, this complexity was subsequently matched for constant-approximate weighted vertex cover [Bar-Yehuda, Censor-Hillel and Schwartzman, JACM 2017] and constant-approximate maximum matching [Bar-Yehuda, Censor-Hillel, Ghaffari and Schwartzman, PODC 2017]. One might expect, therefore, that the true complexity should be $Θ(\frac{\log Δ}{\log\log Δ})$, and the $n$-dependent term in the lower bound is just an artefact of the proof method. We show that this is not the case, and a term dependent on $n$ is in fact required. Specifically, we show randomized algorithms for $2+\varepsilon$-approximate maximum matching and approximate (weighted) minimum vertex cover taking $O(\frac{\log n}{\log^2 \log n})$ rounds. Our algorithms are based on a novel graph decomposition result generalizing the method of Miller, Peng and Xu [SPAA 2013], which we use to reduce the `effective' degree of high-degree graphs. We expect that this decomposition may be of further use for other problems.

Authors: Sebastian Schmidt, Juha Harviainen, Corentin Moumard, Aleksandr Politov, Francisco Sena, Alexandru I. Tomescu

Bidirected graphs are a common generalisation of directed graphs where arcs can also be incoming to both their incident nodes, or outgoing from both their incident nodes. Such arcs allow a walk to change direction. Some algorithms can easily be adapted from directed graphs to bidirected graphs, such as shortest path algorithms. These adaptions are already used in practice, and implicitly use the graph doubling technique to apply an algorithm for directed graphs to bidirected graphs. In other cases, the applicability of graph doubling is not that obvious. For example, superbubbles and their generalisation to bidirected graphs ultrabubbles. Ultrabubbles are a common structure in bidirected biological graphs which carries biological meaning, but also functions as a nested clustering method, since an ultrabubble is separated by only two nodes from the rest of the graph. There is an existing method that enumerates a structure similar to ultrabubbles by enumerating (weak) superbubbles in the doubled graph. However, the literature does not make any direct connection between superbubbles and ultrabubbles except that a superbubble is an ultrabubble in a directed graph. Only a partial result connecting superbubbles and ultrabubbles exists by Harviainen et al. (2026). Graph doubling on the other hand maintains connectivity, and allows to draw a direct connection between ultrabubbles and weak superbubbles. This results in the first linear-time reduction-based algorithm for computing ultrabubbles on any bidirected graph. Together with the fact that graph doubling is already used implicitly in simple cases, our result motivates that graph doubling is a powerful yet simple technique to apply algorithms for directed graphs to bidirected graphs.

Authors: Dinesh Kumar Baghel, Alex Ravsky, Erel Segal-Halevi

Given items of different sizes and a fixed bin capacity, the bin-packing problem is to pack these items into the minimum number of bins such that the sum of the item sizes in each bin does not exceed the capacity. We define a new variant, k-times bin-packing (kBP), in which the goal is to pack the items so that each item appears exactly k times in k different bins. We generalize existing approximation algorithms for bin-packing to solve kBP and analyze their performance ratios. The fair electricity division problem motivates the study of kBP. The goal is to allocate the available supply among households using some fairness criteria, such as the egalitarian principle. We prove that every electricity division problem can be solved by k-times bin-packing for some finite k, which depends only on the number of households. We implement generalizations of the First-Fit and First-Fit Decreasing bin-packing algorithms to solve kBP and apply them to real electricity demand data. We show that our generalizations outperform existing heuristic solutions to the same problem in terms of the egalitarian allocation of connection time. We study another variant of the egalitarian allocation problem, in which the goal is to maximize the minimum number of watts allocated to a household. For this variant, we prove an impossibility result: there does not exist such a k that depends only on the number of agents. This impossibility result motivates us to develop four different heuristic algorithms to solve the egalitarian allocation of watts problem. We evaluate the heuristics by summing the minimum watts allocated to any household in each hour, yielding a fairness metric that reflects the lowest watt allocation across all hours. A higher total minimum of watts indicates a more equitable distribution. Thus, we establish new benchmarks for fair allocation of watts.