Theory of Computing Report

Authors: Florian Galliot

We study two positional games where two players take turns picking a previously unpicked vertex of a hypergraph $H$. We say a player fills an edge of $H$ if that player has picked all the vertices of that edge. In the Maker-Maker game, whoever first fills an edge wins, or we get a draw if no edge is filled. In the Maker-Breaker game, the first player aims at filling an edge while the second player aims at preventing the first player from filling an edge. We show that, for both games, deciding whether the first player has a winning strategy is a PSPACE-complete problem even when restricted to 4-uniform hypergraphs. For the Maker-Maker game, this improves on a previous result for hypergraphs of rank 4. For the Maker-Breaker game, this improves on a previous result for 5-uniform hypergraphs, and closes the complexity gap as the problem for hypergraphs of rank 3 is known to be solvable in polynomial time.

Authors: Ryu Hayakawa, Kazuki Sakamoto, Chusei Kiumi

The Berry phase is a fundamental quantity in the classification of topological phases of matter. In this paper, we present a new quantum algorithm and several complexity-theoretical results for the Berry phase estimation (BPE) problems. Our new quantum algorithm achieves BPE in a more general setting than previously known quantum algorithms, with a theoretical guarantee. For the complexity-theoretic results, we consider three cases. First, we prove $\mathsf{BQP}$-completeness when we are given a guiding state that has a large overlap with the ground state. This result establishes an exponential quantum speedup for estimating the Berry phase. Second, we prove $\mathsf{dUQMA}$-completeness when we have \textit{a priori} bound for ground state energy. Here, $\mathsf{dUQMA}$ is a variant of the unique witness version of $\mathsf{QMA}$ (i.e., $\mathsf{UQMA}$), which we introduce in this paper, and this class precisely captures the complexity of BPE without the known guiding state. Remarkably, this problem turned out to be the first natural problem contained in both $\mathsf{UQMA}$ and $\mathsf{co}$-$\mathsf{UQMA}$. Third, we show $\mathsf{P}^{\mathsf{dUQMA[log]}}$-hardness and containment in $\mathsf{P}^{\mathsf{PGQMA[log]}}$ when we have no additional assumption. These results advance the role of quantum computing in the study of topological phases of matter and provide a pathway for clarifying the connection between topological phases of matter and computational complexity.

Authors: Mikhail Goncharov, Alexander S. Kulikov, Georgie Levtsov

Bit addition arises virtually everywhere in digital circuits: arithmetic operations, increment/decrement operators, computing addresses and table indices, and so on. Since bit addition is such a basic task in Boolean circuit synthesis, a lot of research has been done on constructing efficient circuits for various special cases of it. A vast majority of these results are devoted to optimizing the circuit depth (also known as delay). In this paper, we investigate the circuit size (also known as area) over the full binary basis of bit addition. Though most of the known circuits are built from Half Adders and Full Adders, we show that, in many interesting scenarios, these circuits have suboptimal size. Namely, we improve an upper bound $5n-3m$ to $4.5n-2m$, where $n$ is the number of input bits and $m$ is the number of output bits. In the regimes where $m$ is small compared to $n$ (for example, for computing the sum of $n$ bits or multiplying two $n$-bit integers), this leads to $10\%$ improvement. We complement our theoretical result by an open-source implementation of generators producing circuits for bit addition and multiplication. The generators allow one to produce the corresponding circuits in two lines of code and to compare them to existing designs.

Authors: Yan S. Couto, Cristina G. Fernandes

The k-core of a graph is its maximal subgraph with minimum degree at least k, and the core value of a vertex u is the largest k for which u is contained in the k-core of the graph. Among cohesive subgraphs, k-core and its variants have received a lot of attention recently, particularly on dynamic graphs, as reported by Hanauer, Henzinger, and Schulz in their recent survey on dynamic graph algorithms. We answer questions on k-core stated in the survey, proving that there is no efficient dynamic algorithm for k-core or to find (2 - {\epsilon})-approximations for the core values, unless we can improve decade-long state-of-the-art algorithms in many areas including matrix multiplication and satisfiability, based on the established OMv and SETH conjectures. Some of our results show that there is no dynamic algorithm for k-core asymptotically faster than the trivial ones. This explains why most recent research papers in this area focus not on a generic efficient dynamic algorithm, but on finding a bounded algorithm, which is fast when few core values change per update. However, we also prove that such bounded algorithms do not exist, based on the OMv conjecture. We present lower bounds also for a directed version of the problem, and for the edge variant of the problem, known as k-truss. On the positive side, we present a polylogarithmic dynamic algorithm for 2-core.

Authors: Zheng Luo, Wim Van den Broeck, Guy Van den Broeck, Yisu Remy Wang

Most research on query optimization has centered on binary join algorithms like hash join and sort-merge join. However, recent years have seen growing interest in theoretically optimal algorithms, notably Yannakakis' algorithm. These algorithms rely on join trees, which differ from the operator trees for binary joins and require new optimization techniques. We propose three approaches to constructing join trees for acyclic queries. First, we give an algorithm to enumerate all join trees of an alpha-acyclic query by edits with amortized constant delay, which forms the basis of a cost-based optimizer for acyclic joins. Second, we show that the Maximum Cardinality Search algorithm by Tarjan and Yannakakis constructs a unique shallowest join tree, rooted at any relation, for a Berge-acyclic query; this tree enables parallel execution of large join queries. Finally, we prove that any connected left-deep linear plan for a gamma-acyclic query can be converted into a join tree by a simple algorithm, allowing reuse of optimization infrastructure developed for binary joins.

Authors: Tsz Chiu Kwok, Zhewei Wei, Mingji Yang

We initiate a study of solving a row/column diagonally dominant (RDD/CDD) linear system $Mx=b$ in sublinear time, with the goal of estimating $t^{\top}x^*$ for a given vector $t\in R^n$ and a specific solution $x^*$. This setting naturally generalizes the study of sublinear-time solvers for symmetric diagonally dominant (SDD) systems [AKP19] to the asymmetric case. Our first contributions are characterizations of the problem's mathematical structure. We express a solution $x^*$ via a Neumann series, prove its convergence, and upper bound the truncation error on this series through a novel quantity of $M$, termed the maximum $p$-norm gap. This quantity generalizes the spectral gap of symmetric matrices and captures how the structure of $M$ governs the problem's computational difficulty. For systems with bounded maximum $p$-norm gap, we develop a collection of algorithmic results for locally approximating $t^{\top}x^*$ under various scenarios and error measures. We derive these results by adapting the techniques of random-walk sampling, local push, and their bidirectional combination, which have proved powerful for special cases of solving RDD/CDD systems, particularly estimating PageRank and effective resistance on graphs. Our general framework yields deeper insights, extended results, and improved complexity bounds for these problems. Notably, our perspective provides a unified understanding of Forward Push and Backward Push, two fundamental approaches for estimating random-walk probabilities on graphs. Our framework also inherits the hardness results for sublinear-time SDD solvers and local PageRank computation, establishing lower bounds on the maximum $p$-norm gap or the accuracy parameter. We hope that our work opens the door for further study into sublinear solvers, local graph algorithms, and directed spectral graph theory.

Authors: Danila Valko, Rohan Paranjpe, Jorge Marx Gómez

Efficient routing is critical for payment channel networks (PCNs) such as the Lightning Network (LN), where most clients currently rely on Dijkstra-based algorithms for payment pathfinding. While Dijkstra's algorithm has long been regarded as optimal on sparse graphs, recent theoretical work challenges this view. The new Bounded Multi-Source Shortest Path (BMSSP) algorithm by Duan et al. theoretically achieves $O(m~log^{2/3}~n)$ runtime, which is asymptotically faster than Dijkstra's $O(m + n~log~n)$ on sparse directed graphs. In this paper, we implement BMSSP on Rust and compare its performance against Dijkstra's using real LN topology data. Our evaluation, based on multiple randomized trials and statistical tests, shows that current implementations of BMSSP do not significantly outperform Dijkstra's in practice, and speedups are smaller than what theory predicts, possibly due to implementation and constant factor overheads. These results provide the first empirical evidence of BMSSP's potential to accelerate LN routing and inform future optimizations of PCN pathfinding algorithms.

Polynomial bounds for the Chowla cosine problem were achieved independently in two very recent works.

Zhihan Jin, Aleksa Milojević, István Tomon, Shengtong Zhang: From small eigenvalues to large cuts, and Chowla’s cosine problem;

Benjamin Bedert: Polynomial bounds for the Chowla Cosine Problem

Abstract (JMTZ’s paper): We show that there exists an absolute constant such that for every we have

This gives the first polynomial bound for Chowla’s cosine problem from 1965.

To show this, we prove structural statements about graphs whose smallest eigenvalue is small in absolute value. As another application, we show that any graph with edges and no clique of size has a cut of size at least for some . This proves a weak version of a celebrated conjecture of Alon, Bollob’as, Krivelevich, and Sudakov.

Our proofs are based on novel spectral and linear algebraic techniques, involving subspace compressions and Hadamard products of matrices.

Abstract (Bedert’s paper): Let be a finite set of positive integers, and consider the cosine sum . We prove that there exists an absolute constant such that

establishing polynomial bounds for the Chowla cosine problem.

These new breakthroughs look wonderful and further commentary in the comment section is very welcome. Chowla conjectured that is the answer. 

History. Both papers gives the interesting history of the problem. In 1948 Ankeny and Chowla asked if for every large enough set and some the some of cosines is smaller than for arbitrary large real . This was solved by M. Uchiyama and S. Uchiyama in 1960. In 1965 Sarvadaman Chowla asked if putting , can be taken as .  Achieving followed from the resolution of a well-known problem by Littlewood and breaking the barrier was achieved by Bourgain and greatly improved by Rusza to .

Spectral graph theory. The paper by Jin, Milojević, Tomon, and Zhang reduces the problem to a question in spectral graph theory. The authors also prove a weak version of another conjecture in spectral graph theory by Alon, Bollobás, Krivelevich, and Sudakov. 

Sum-free subsets of sets of integers. Benjamin Bedert recently solved a well-known question in additive combinatorics about sum free subsets of sets of integers  his work is related to the same Littlewood problem mentioned above, and to a work by Bourgain. The interesting story behind it was told in a Quanta Magazine article by Leila Sloman.

h/t Nati Linial.  I did not know about the problem (although it is problem #81 on Green’s 100 problems list),  but Nati wrote me:  “In ancient times when I thought about KKL, I used to read everything in the library about Harmonic analysis and I came across this conjecture.”

By Gil Kalai

October 10-12, 2025 Pittsburgh, PA https://sites.google.com/andrew.cmu.edu/acorn-2025/home Carnegie Mellon University will be hosting the 2025 ACORN (Algorithms, Combinatorics, and Optimization Research Network) Workshop, October 10-12, 2025. Registration is now open at the website here: https://sites.google.com/andrew.cmu.edu/acorn-2025/home ACORN (Algorithms, Combinatorics, and Optimization Research Network) is a group of institutions, departments, and researchers committed to the principle that the … Continue reading ACORN Workshop at Carnegie Mellon University

By shacharlovett

When announcing Open-AI's latest release last month, Sam Altman said "GPT-5 is the first time that it really feels like talking to an expert in any topic, like a PhD-level expert." Before we discuss whether GPT-5 got there, what does "PhD-Level intelligence" even mean?

We could just dismiss the idea but I'd rather try to formulate a reasonable definition, which I would expect from a good PhD student. It's not about knowing stuff, which we can always look up, but the ability to talk and engage about current research. Here is my suggestion.

The ability to understand a (well-presented) research paper or talk in the field.

The word "field" has narrowed over time as knowledge has become more specialized, but since the claim is that GPT-5 is an expert over all fields, that doesn't matter. The word "understand" causes more problems, it is hard to define for humans let alone machines.

In many PhD programs, there's an oral exam where we have previously given the candidate a list of research papers and they are expected to answer questions about these papers. If we claim a LLM has "PhD-level" knowledge, I'd expect the LLM to pass this test.

Does GPT-5 get there? I did an experiment with two recent papers, one showing Dijkstra's algorithm was optimal and another showing Dijkstra is not optimal. I used the GPT 5 Thinking model and GPT 5 Pro on the last question about new directions. A little more technical answers than I would have liked but it would likely have passed the oral exam. A good PhD student may work harder to get a more intuitive idea of the paper in order to understand it, and later on extend it.

You could ask for far more--getting a PhD requires significant original research, and LLMs for the most part haven't gotten there (yet). I've not had luck getting any large-language model to make real progress on open questions and haven't seen many successful examples from other people trying to do the same. 

So while large-language models might have PhD-level expertise they can't replace PhD students who actually do the research.

By Lance Fortnow

Authors: C. Ramya, Pratik Shastri

The complexity of representing a polynomial by a Read-Once Oblivious Algebraic Branching Program (ROABP) is highly dependent on the chosen variable ordering. Bhargava et al. prove that finding the optimal ordering is NP-hard, and provide some evidence (based on the Small Set Expansion hypothesis) that it is also hard to approximate the optimal ROABP width. In another work, Baraskar et al. show that it is NP-hard to test whether a polynomial is in the $\mathrm{GL}_n$ orbit of a polynomial of sparsity at most $s$. Building upon these works, we show the following results: first, we prove that approximating the minimum ROABP width up to any constant factor is NP-hard, when the input is presented as a circuit. This removes the reliance on stronger conjectures in the previous work. Second, we show that testing if an input polynomial given in the sparse representation is in the affine $\mathrm{GL}_n$ orbit of a width-$w$ ROABP is NP-hard. Furthermore, we show that over fields of characteristic $0$, the problem is NP-hard even when the input polynomial is homogeneous. This provides the first NP-hardness results for membership testing for a dense subclass of polynomial sized algebraic branching programs (VBP). Finally, we locate the source of hardness for the order finding problem at the lowest possible non-trivial degree, proving that the problem is NP-hard even for quadratic forms.

Authors: Daniel Altman

Designing a deterministic polynomial time algorithm for factoring univariate polynomials over finite fields remains a notorious open problem. In this paper, we present an unconditional deterministic algorithm that takes as input an irreducible polynomial $f \in \mathbb{Z}[x]$, and computes the factorisation of its reductions modulo $p$ for all primes $p$ up to a prescribed bound $N$. The \emph{average running time per prime} is polynomial in the size of the input and the degree of the splitting field of $f$ over $\mathbb{Q}$. In particular, if $f$ is Galois, we succeed in factoring in (amortised) deterministic polynomial time.

Authors: Shannon Cheng, Anna Chlopecki, Saarah Nazar, Eric Samperton

We give a new, elementary proof of what we believe is the simplest known example of a ``natural'' problem in computational 3-dimensional topology that is $\mathsf{NP}$-hard -- namely, the \emph{Trivial Sublink Problem}: given a diagram $L$ of a link in $S^3$ and a positive integer $k$, decide if $L$ contains a $k$ component sublink that is trivial. This problem was previously shown to be $\mathsf{NP}$-hard in independent works of Koenig-Tsvietkova and de Mesmay-Rieck-Sedgwick-Tancer, both of which used reductions from $\mathsf{3SAT}$. The reduction we describe instead starts with the Independent Set Problem, and allows us to avoid the use of Brunnian links such as the Borromean rings. On the technical level, this entails a new conceptual insight: the Trivial Sublink Problem is hard entirely due to mod 2 pairwise linking, with no need for integral or higher order linking. On the pedagogical level, the reduction we describe is entirely elementary, and thus suitable for introducing undergraduates and non-experts to complexity-theoretic low-dimensional topology. To drive this point home, in this work we assume no familiarity with low-dimensional topology, and -- other than Reidemeister's Theorem and Karp's result that the Clique Problem is $\mathsf{NP}$-hard -- we provide more-or-less complete definitions and proofs. We have also constructed a web app that accompanies this work and allows a user to visualize the new reduction interactively.

Authors: Waseem Akram, Katsuhisa Yamanaka

Let $S$ be a set of $n$ points in the Euclidean plane and general position i.e., no three points are collinear. An \emph{at most $k$-out polygon of $S$} is a simple polygon such that each vertex is a point in $S$ and there are at most $k$ points outside the polygon. In this paper, we consider the problem of enumerating all the at most $k$-out polygon of $S$. We propose a new enumeration algorithm for the at most $k$-out polygons of a point set. Our algorithm enumerates all the at most $k$-out polygons in $\mathcal{O}(n^2 \log{n})$ delay, while the running time of an existing algorithm is $\mathcal{O}(n^3 \log{n})$ delay.

Authors: Weiming Feng, Zelin Li, Pan Peng

We study sublinear-time algorithms for solving linear systems $Sz = b$, where $S$ is a diagonally dominant matrix, i.e., $|S_{ii}| \geq \delta + \sum_{j \ne i} |S_{ij}|$ for all $i \in [n]$, for some $\delta \geq 0$. We present randomized algorithms that, for any $u \in [n]$, return an estimate $z_u$ of $z^*_u$ with additive error $\varepsilon$ or $\varepsilon \lVert z^*\rVert_\infty$, where $z^*$ is some solution to $Sz^* = b$, and the algorithm only needs to read a small portion of the input $S$ and $b$. For example, when the additive error is $\varepsilon$ and assuming $\delta>0$, we give an algorithm that runs in time $O\left( \frac{\|b\|_\infty^2 S_{\max}}{\delta^3 \varepsilon^2} \log \frac{\| b \|_\infty}{\delta \varepsilon} \right)$, where $S_{\max} = \max_{i \in [n]} |S_{ii}|$. We also prove a matching lower bound, showing that the linear dependence on $S_{\max}$ is optimal. Unlike previous sublinear-time algorithms, which apply only to symmetric diagonally dominant matrices with non-negative diagonal entries, our algorithm works for general strictly diagonally dominant matrices ($\delta > 0$) and a broader class of non-strictly diagonally dominant matrices $(\delta = 0)$. Our approach is based on analyzing a simple probabilistic recurrence satisfied by the solution. As an application, we obtain an improved sublinear-time algorithm for opinion estimation in the Friedkin--Johnsen model.

Authors: Pietro Armenante, Kai Huang, Nikhil Jha, Luca Vassio

Origin-Destination (OD) matrices are a core component of research on users' mobility and summarize how individuals move between geographical regions. These regions should be small enough to be representative of user mobility, without incurring substantial privacy risks. There are two added values of the NetMob2025 challenge dataset. Firstly, the data is extensive and contains a lot of socio-demographic information that can be used to create multiple OD matrices, based on the segments of the population. Secondly, a participant is not merely a record in the data, but a statistically weighted proxy for a segment of the real population. This opens the door to a fundamental shift in the anonymization paradigm. A population-based view of privacy is central to our contribution. By adjusting our anonymization framework to account for representativeness, we are also protecting the inferred identity of the actual population, rather than survey participants alone. The challenge addressed in this work is to produce and compare OD matrices that are k-anonymous for survey participants and for the whole population. We compare several traditional methods of anonymization to k-anonymity by generalizing geographical areas. These include generalization over a hierarchy (ATG and OIGH) and the classical Mondrian. To this established toolkit, we add a novel method, i.e., ODkAnon, a greedy algorithm aiming at balancing speed and quality. Unlike previous approaches, which primarily address the privacy aspects of the given datasets, we aim to contribute to the generation of privacy-preserving OD matrices enriched with socio-demographic segmentation that achieves k-anonymity on the actual population.

Authors: Christian L. Hines, Samuel Spillard, Daniel P. Martin

TimeCluster is a visual analytics technique for discovering structure in long multivariate time series by projecting overlapping windows of data into a low-dimensional space. We show that, when Principal Component Analysis (PCA) is chosen as the dimensionality reduction technique, this procedure is mathematically equivalent to classical linear subspace identification (block-Hankel matrix plus Singular Vector Decomposition (SVD)). In both approaches, the same low-dimensional linear subspace is extracted from the time series data. We first review the TimeCluster method and the theory of subspace system identification. Then we show that forming the sliding-window matrix of a time series yields a Hankel matrix, so applying PCA (via SVD) to this matrix recovers the same principal directions as subspace identification. Thus the cluster coordinates from TimeCluster coincide with the subspace identification methods. We present experiments on synthetic and real dynamical signals confirming that the two embeddings coincide. Finally, we explore and discuss future opportunities enabled by this equivalence, including forecasting from the identified state space, streaming/online extensions, incorporating and visualising external inputs and robust techniques for displaying underlying trends in corrupted data.

Authors: Shyan Akmal, Tomohiro Koana

In the $\ell$-Coloring Problem, we are given a graph on $n$ nodes, and tasked with determining if its vertices can be properly colored using $\ell$ colors. In this paper we study below-guarantee graph coloring, which tests whether an $n$-vertex graph can be properly colored using $g-k$ colors, where $g$ is a trivial upper bound such as $n$. We introduce an algorithmic framework that builds on a packing of co-triangles $\overline{K_3}$ (independent sets of three vertices): the algorithm greedily finds co-triangles and employs a win-win analysis. If many are found, we immediately return YES; otherwise these co-triangles form a small co-triangle modulator, whose deletion makes the graph co-triangle-free. Extending the work of [Gutin et al., SIDMA 2021], who solved $\ell$-Coloring (for any $\ell$) in randomized $O^*(2^{k})$ time when given a $\overline{K_2}$-free modulator of size $k$, we show that this problem can likewise be solved in randomized $O^*(2^{k})$ time when given a $\overline{K_3}$-free modulator of size~$k$. This result in turn yields a randomized $O^{*}(2^{3k/2})$ algorithm for $(n-k)$-Coloring (also known as Dual Coloring), improving the previous $O^{*}(4^{k})$ bound. We then introduce a smaller parameterization, $(\omega+\overline{\mu}-k)$-Coloring, where $\omega$ is the clique number and $\overline{\mu}$ is the size of a maximum matching in the complement graph; since $\omega+\overline{\mu}\le n$ for any graph, this problem is strictly harder. Using the same co-triangle-packing argument, we obtain a randomized $O^{*}(2^{6k})$ algorithm, establishing its fixed-parameter tractability for a smaller parameter. Complementing this finding, we show that no fixed-parameter tractable algorithm exists for $(\omega-k)$-Coloring or $(\overline{\mu}-k)$-Coloring under standard complexity assumptions.

The story of how diffusion models create—and what they leave behind

I’m excited to share my new piece, How AI Generates: From Noise to Form.

Diffusion models are behind much of today’s generative AI—image synthesis, text-to-art, even video. But how do they actually work? And what are their limits?

My goal in this essay is to give readers a way in—to make the core ideas approachable while still keeping the essentials intact. Along the way, I walk through:

• Why diffusion models corrupt data step by step, then learn to reverse the damage
• How generation reduces to a series of prediction tasks
• Why prompts guide but cannot fully constrain creations
• And what glitches like the six-fingered hand reveal about the gap between surface and meaning

I start with a scene from the US Open to set the stage, but the heart of the piece is about how these models generate—and what they leave behind.

Subscribe here (it’s free!) and read: https://nisheethvishnoi.substack.com/

If it resonates, I’d love for you to share it with others who might enjoy exploring the mechanics of generation.

By nisheethvishnoi

Authors: Partha Mukhopadhyay, C Ramya, Pratik Shastri

We design the first efficient polynomial identity testing algorithms over the nonassociative polynomial algebra. In particular, multiplication among the formal variables is commutative but it is not associative. This complements the strong lower bound results obtained over this algebra by Hrube\v{s}, Yehudayoff, and Wigderson (2010) and Fijalkow, Lagarde, Ohlmann, and Serre (2021) from the identity testing perspective. Our main results are the following: (1) We construct nonassociative algebras (both commutative and noncommutative) which have no low degree identities. As a result, we obtain the first Amitsur-Levitzki type theorems over nonassociative polynomial algebras. As a direct consequence, we obtain randomized polynomial-time black-box PIT algorithms for nonassociative polynomials which allow evaluation over such algebras. (2) On the derandomization side, we give a deterministic polynomial-time identity testing algorithm for nonassociative polynomials given by arithmetic circuits in the white-box setting. Previously, such an algorithm was known with the additional restriction of noncommutativity. (3) In the black-box setting, we construct a hitting set of quasipolynomial-size for nonassociative polynomials computed by arithmetic circuits of small depth. Understanding the black-box complexity of identity testing, even in the randomized setting, was open prior to our work.

Authors: C. Ramya, Pratik Shastri

Arithmetic circuits are a natural well-studied model for computing multivariate polynomials over a field. In this paper, we study planar arithmetic circuits. These are circuits whose underlying graph is planar. In particular, we prove an $\Omega(n\log n)$ lower bound on the size of planar arithmetic circuits computing explicit bilinear forms on $2n$ variables. As a consequence, we get an $\Omega(n\log n)$ lower bound on the size of arithmetic formulas and planar algebraic branching programs computing explicit bilinear forms on $2n$ variables. This is the first such lower bound on the formula complexity of an explicit bilinear form. In the case of read-once planar circuits, we show $\Omega(n^2)$ size lower bounds for computing explicit bilinear forms on $2n$ variables. Furthermore, we prove fine separations between the various planar models of computations mentioned above. In addition to this, we look at multi-output planar circuits and show $\Omega(n^{4/3})$ size lower bound for computing an explicit linear transformation on $n$-variables. For a suitable definition of multi-output formulas, we extend the above result to get an $\Omega(n^2/\log n)$ size lower bound. As a consequence, we demonstrate that there exists an $n$-variate polynomial computable by an $n^{1 + o(1)}$-sized formula such that any multi-output planar circuit (resp., multi-output formula) simultaneously computing all its first-order partial derivatives requires size $\Omega(n^{4/3})$ (resp., $\Omega(n^2/\log n)$). This shows that a statement analogous to that of Baur, Strassen (1983) does not hold in the case of planar circuits and formulas.

Authors: Alessandro Giovanni Alberti, Flavio Chierichetti, Mirko Giacchini, Daniele Muscillo, Alessandro Panconesi, Erasmo Tani

The New York Times (NYT) games have found widespread popularity in recent years and reportedly account for an increasing fraction of the newspaper's readership. In this paper, we bring the computational lens to the study of New York Times games and consider four of them not previously studied: Letter Boxed, Pips, Strands and Tiles. We show that these games can be just as hard as they are fun. In particular, we characterize the hardness of several variants of computational problems related to these popular puzzle games. For Letter Boxed, we show that deciding whether an instance is solvable is in general NP-Complete, while in some parameter settings it can be done in polynomial time. Similarly, for Pips we prove that deciding whether a puzzle has a solution is NP-Complete even in some restricted classes of instances. We then show that one natural computational problem arising from Strands is NP-Complete in most parameter settings. Finally, we demonstrate that deciding whether a Tiles puzzle is solvable with a single, uninterrupted combo requires polynomial time.

Authors: Jules Armand, Prateek Dwivedi, Magnus Rahbek Dalgaard Hansen, Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas

We investigate the closure properties of read-once oblivious Algebraic Branching Programs (roABPs) under various natural algebraic operations and prove the following. - Non-closure under factoring: There is a sequence of explicit polynomials $(f_n(x_1,\ldots, x_n))_n$ that have $\mathsf{poly}(n)$-sized roABPs such that some irreducible factor of $f_n$ does not have roABPs of superpolynomial size in any order. - Non-closure under powering: There is a sequence of polynomials $(f_n(x_1,\ldots, x_n))_n$ with $\mathsf{poly}(n)$-sized roABPs such that any super-constant power of $f_n$ does not have roABPs of polynomial size in any order (and $f_n^n$ requires exponential size in any order). - Non-closure under symmetric compositions: There are symmetric polynomials $(f_n(e_1,\ldots, e_n))_n$ that have roABPs of polynomial size such that $f_n(x_1,\ldots, x_n)$ do not have roABPs of subexponential size. (Here, $e_1,\ldots, e_n$ denote the elementary symmetric polynomials in $n$ variables.) These results should be viewed in light of known results on models such as algebraic circuits, (general) algebraic branching programs, formulas and constant-depth circuits, all of which are known to be closed under these operations. To prove non-closure under factoring, we construct hard polynomials based on expander graphs using gadgets that lift their hardness from sparse polynomials to roABPs. For symmetric compositions, we show that the circulant polynomial requires roABPs of exponential size in every variable order.

Authors: Yumou Fei, Dor Minzer, Shuo Wang

We show a dichotomy result for $p$-pass streaming algorithms for all CSPs and for up to polynomially many passes. More precisely, we prove that for any arity parameter $k$, finite alphabet $\Sigma$, collection $\mathcal{F}$ of $k$-ary predicates over $\Sigma$ and any $c\in (0,1)$, there exists $00$ there is a constant pass, $O_{\varepsilon}(\log n)$-space randomized streaming algorithm solving the promise problem $\text{MaxCSP}(\mathcal{F})[c,s-\varepsilon]$. That is, the algorithm accepts inputs with value at least $c$ with probability at least $2/3$, and rejects inputs with value at most $s-\varepsilon$ with probability at least $2/3$. 2. For all $\varepsilon>0$, any $p$-pass (even randomized) streaming algorithm that solves the promise problem $\text{MaxCSP}(\mathcal{F})[c,s+\varepsilon]$ must use $\Omega_{\varepsilon}(n^{1/3}/p)$ space. Our approximation algorithm is based on a certain linear-programming relaxation of the CSP and on a distributed algorithm that approximates its value. This part builds on the works [Yoshida, STOC 2011] and [Saxena, Singer, Sudan, Velusamy, SODA 2025]. For our hardness result we show how to translate an integrality gap of the linear program into a family of hard instances, which we then analyze via studying a related communication complexity problem. That analysis is based on discrete Fourier analysis and builds on a prior work of the authors and on the work [Chou, Golovnev, Sudan, Velingker, Velusamy, J.ACM 2024].

Authors: Hui Li, Shiyuan Deng, Xiao Yan, Xiangyu Zhi, James Cheng

Approximate Nearest Neighbor Search (ANNS) plays a critical role in applications such as search engines, recommender systems, and RAG for LLMs. Vector quantization (VQ), a crucial technique for ANNS, is commonly used to reduce space overhead and accelerate distance computations. However, despite significant research advances, state-of-the-art VQ methods still face challenges in balancing encoding efficiency and quantization accuracy. To address these limitations, we propose a novel VQ method called SAQ. To improve accuracy, SAQ employs a new dimension segmentation technique to strategically partition PCA-projected vectors into segments along their dimensions. By prioritizing leading dimension segments with larger magnitudes, SAQ allocates more bits to high-impact segments, optimizing the use of the available space quota. An efficient dynamic programming algorithm is developed to optimize dimension segmentation and bit allocation, ensuring minimal quantization error. To speed up vector encoding, SAQ devises a code adjustment technique to first quantize each dimension independently and then progressively refine quantized vectors using a coordinate-descent-like approach to avoid exhaustive enumeration. Extensive experiments demonstrate SAQ's superiority over classical methods (e.g., PQ, PCA) and recent state-of-the-art approaches (e.g., LVQ, Extended RabitQ). SAQ achieves up to 80% reduction in quantization error and accelerates encoding speed by over 80x compared to Extended RabitQ.

Authors: Xi He

Decision trees are a ubiquitous model for classification and regression tasks due to their interpretability and efficiency. However, solving the optimal decision tree (ODT) problem remains a challenging combinatorial optimization task. Even for the simplest splitting rules--axis-parallel hyperplanes--it is NP-hard to optimize. In Part I of this series, we rigorously defined the proper decision tree model through four axioms and, based on these, introduced four formal definitions of the ODT problem. From these definitions, we derived four generic algorithms capable of solving ODT problems for arbitrary decision trees satisfying the axioms. We also analyzed the combinatorial geometric properties of hypersurfaces, showing that decision trees defined by polynomial hypersurface splitting rules satisfy the proper axioms that we proposed. In this second paper (Part II) of this two-part series, building on the algorithmic and geometric foundations established in Part I, we introduce the first hypersurface decision tree (HODT) algorithm. To the best of our knowledge, existing optimal decision tree methods are, to date, limited to hyperplane splitting rules--a special case of hypersurfaces--and rely on general-purpose solvers. In contrast, our HODT algorithm addresses the general hypersurface decision tree model without requiring external solvers. Using synthetic datasets generated from ground-truth hyperplane decision trees, we vary tree size, data size, dimensionality, and label and feature noise. Results showing that our algorithm recovers the ground truth more accurately than axis-parallel trees and exhibits greater robustness to noise. We also analyzed generalization performance across 30 real-world datasets, showing that HODT can achieve up to 30% higher accuracy than the state-of-the-art optimal axis-parallel decision tree algorithm when tree complexity is properly controlled.

Authors: Bart M. P. Jansen, Jeroen S. K. Lamme, Ruben F. A. Verhaegh

We study the parameterized complexity of a recently introduced multi-agent variant of the Kidney Exchange problem. Given a directed graph $G$ and integers $d$ and $k$, the standard problem asks whether $G$ contains a packing of vertex-disjoint cycles, each of length $\leq d$, covering at least $k$ vertices in total. In the multi-agent setting we consider, the vertex set is partitioned over several agents who reject a cycle packing as solution if it can be modified into an alternative packing that covers more of their own vertices. A cycle packing is called rejection-proof if no agent rejects it and the problem asks whether such a packing exists that covers at least $k$ vertices. We exploit the sunflower lemma on a set packing formulation of the problem to give a kernel for this $\Sigma_2^P$-complete problem that is polynomial in $k$ for all constant values of $d$. We also provide a $2^{\mathcal{O}(k \log k)} + n^{\mathcal{O}(1)}$ algorithm based on it and show that this FPT algorithm is asymptotically optimal under the ETH. Further, we generalize the problem by including an additional positive integer $c$ in the input that naturally captures how much agents can modify a given cycle packing to reject it. For every constant $c$, the resulting problem simplifies from being $\Sigma_2^P$-complete to NP-complete. With a single-exponential algorithm for the setting where $c = 1$, we show this to be strictly easier under the ETH than when $c = 2$. In turn, we show that any $c \geq 2$ yields a problem that is essentially as hard as the original problem with $c$ unbounded. This displays an interesting discrepancy between the classical and parameterized complexity of the problem and gives a good view of what makes it hard.

Authors: Debojyoti Bhattacharya, Subhabrata Paul

Let $G=(V, E)$ be a simple undirected graph. A closed neighbourhood of an edge $e=uv$ between two vertices $u$ and $v$ of $G$, denoted by $N_G[e]$, is the set of vertices in the neighbourhood of $u$ and $v$ including $\{u,v\}$. A subset $L$ of $V$ is said to be liar's vertex-edge dominating set if $(i)$ for every edge $e\in E$, $|N_G[e]\cap L|\geq 2$ and $(ii)$ for every pair of distinct edges $e,e'$, $|(N_G[e]\cup N_G[e'])\cap L|\geq 3$. The minimum liar's vertex-edge domination problem is to find the liar's vertex-edge dominating set of minimum cardinality. In this article, we show that the liar's vertex-edge domination problem is NP-complete in unit disk graphs, and we design a polynomial time approximation scheme(PTAS) for the minimum liar's vertex-edge domination problem in unit disk graphs.

Authors: Soichiro Migita, Kyotaro Uehata, Tomohiro I

A Straight-Line Program (SLP) for a stirng $T$ is a context-free grammar in Chomsky normal form that derives $T$ only, which can be seen as a compressed form of $T$. Kida et al.\ introduced collage systems [Theor. Comput. Sci., 2003] to generalize SLPs by adding repetition rules and truncation rules. The smallest size $c(T)$ of collage systems for $T$ has gained attention to see how these generalized rules improve the compression ability of SLPs. Navarro et al. [IEEE Trans. Inf. Theory, 2021] showed that $c(T) \in O(z(T))$ and there is a string family with $c(T) \in \Omega(b(T) \log |T|)$, where $z(T)$ is the number of Lempel-Ziv parsing of $T$ and $b(T)$ is the smallest size of bidirectional schemes for $T$. They also introduced a subclass of collage systems, called internal collage systems, and proved that its smallest size $\hat{c}(T)$ for $T$ is at least $b(T)$. While $c(T) \le \hat{c}(T)$ is obvious, it is unknown how large $\hat{c}(T)$ is compared to $c(T)$. In this paper, we prove that $\hat{c}(T) = \Theta(c(T))$ by showing that any collage system of size $m$ can be transformed into an internal collage system of size $O(m)$ in $O(m^2)$ time. Thanks to this result, we can focus on internal collage systems to study the asymptotic behavior of $c(T)$, which helps to suppress excess use of truncation rules. As a direct application, we get $b(T) = O(c(T))$, which answers an open question posed in [Navarro et al., IEEE Trans. Inf. Theory, 2021]. We also give a MAX-SAT formulation to compute $\hat{c}(T)$ for a given $T$.

Authors: Antonio Cruciani, Leonardo Pellegrina

In this work we present PercIS, an algorithm based on Importance Sampling to approximate the percolation centrality of all the nodes of a graph. Percolation centrality is a generalization of betweenness centrality to attributed graphs, and is a useful measure to quantify the importance of the vertices in a contagious process or to diffuse information. However, it is impractical to compute it exactly on modern-sized networks. First, we highlight key limitations of state-of-the-art sampling-based approximation methods for the percolation centrality, showing that in most cases they cannot achieve accurate solutions efficiently. Then, we propose and analyze a novel sampling algorithm based on Importance Sampling, proving tight sample size bounds to achieve high-quality approximations. Our extensive experimental evaluation shows that PercIS computes high-quality estimates and scales to large real-world networks, while significantly outperforming, in terms of sample sizes, accuracy and running times, the state-of-the-art.

Authors: Amirali Madani, Anil Maheshwari, Babak Miraftab, Paweł Żyliński

The widely studied edge modification problems ask how to minimally alter a graph to satisfy certain structural properties. In this paper, we introduce and study a new edge modification problem centered around transforming a given graph into a triangle-covered graph (one in which every vertex belongs to at least one triangle). We first present tight lower bounds on the number of edges in any connected triangle-covered graph of order $n$, and then we characterize all connected graphs that attain this minimum edge count. For a graph $G$, we define the notion of a $\Delta$-completion set as a set of non-edges of $G$ whose addition to $G$ results in a triangle-covered graph. We prove that the decision problem of finding a $\Delta$-completion set of size at most $t\geq0$ is $\mathbb{NP}$-complete and does not admit a constant-factor approximation algorithm under standard complexity assumptions. Moreover, we show that this problem remains $\mathbb{NP}$-complete even when the input is restricted to connected bipartite graphs. We then study the problem from an algorithmic perspective, providing tight bounds on the minimum $\Delta$-completion set size for several graph classes, including trees, chordal graphs, and cactus graphs. Furthermore, we show that the triangle-covered problem admits an $(\ln n +1)$-approximation algorithm for general graphs. For trees and chordal graphs, we design algorithms that compute minimum $\Delta$-completion sets. Finally, we show that the threshold for a random graph $\mathbb{G}(n, p)$ to be triangle-covered occurs at $n^{-2/3}$.

Authors: Hins Hu, Rhea Goswami, Hongyi Jiang, Samitha Samaranayake

Micro-transit services offer a promising solution to enhance urban mobility and access, particularly by complementing existing public transit. However, effectively designing these services requires determining optimal service zones for these on-demand shuttles, a complex challenge often constrained by operating budgets and transit agency priorities. This paper presents a novel two-phase algorithmic framework for designing optimal micro-transit service zones based on the objective of maximizing served demand. A key innovation is our adaptation of the shareability graph concept from its traditional use in dynamic trip assignment to the distinct challenge of static spatial zoning. We redefine shareability by considering geographical proximity within a specified diameter constraint, rather than trip characteristics. In Phase 1, the framework employs a highly scalable algorithm to generate a comprehensive set of candidate zones. In Phase 2, it formulates the selection of a specified number of zones as a Weighted Maximum Coverage Problem, which can be efficiently solved by an integer programming solver. Evaluations on real-world data from Chattanooga, TN, and synthetic datasets show that our framework outperforms a baseline algorithm, serving 27.03% more demand in practice and up to 49.5% more demand in synthetic settings.

Authors: John Peca-Medlin

The Horton-Strahler number (HS) is a measure of branching complexity of rooted trees, introduced in hydrology and later studied in parallel computing under the name register function. While its order of growth is well understood for classical random trees, fluctuation behavior has largely resisted analysis. In this work we investigate the HS in the setting of butterfly trees -- binary trees constructed from butterfly permutations, a rich class of separable permutations with origins in numerical linear algebra and parallel architectures. For the subclass of simple butterfly trees, we exploit their recursive gluing structure to model the HS as an additive functional of a finite-state Markov process. This framework yields sharp distributional results, including a law of large numbers and a Central Limit Theorem with explicit variance growth, providing what appears to be the first genuine Gaussian limit law for the HS in a nontrivial random tree model. Extending to biased constructions, we further establish functional limit theorems via analytic and probabilistic tools. For general butterfly trees, while exact analysis remains open, empirical sampling shows that the HS distribution is confined to a narrower support than in classical models, and appears to concentrate tightly near the upper bound $\lfloor \log_4 N\rfloor$.

Authors: Surya Teja Gavva, Peng Zhang

The Marcus-Spielman-Srivastava theorem (Annals of Mathematics, 2015) for the Kadison-Singer conjecture implies the following result in spectral graph theory: For any undirected graph $G = (V,E)$ with a maximum edge effective resistance at most $\alpha$, there exists a partition of its edge set $E$ into $E_1 \cup E_2$ such that the two edge-induced subgraphs of $G$ spectrally approximates $(1/2)G$ with a relative error $O(\sqrt{\alpha})$. However, the proof of this theorem is non-constructive. It remains an open question whether such a partition can be found in polynomial time, even for special classes of graphs. In this paper, we explore polynomial-time algorithms for partitioning circulant graphs via partitioning their generators. We develop an efficient algorithm that partitions a circulant graph whose generators form an arithmetic progression, with an error matching that in the Marcus-Spielman-Srivastava theorem and optimal, up to a constant. On the other hand, we prove that if the generators of a circulant graph are ``far" from an arithmetic progression, no partition of the generators can yield two circulant subgraphs with an error matching that in the Marcus-Spielman-Srivastava theorem. In addition, we extend our algorithm to Cayley graphs whose generators are from a product of multiple arithmetic progressions.

Authors: Xi He

In the first paper (part I) of this series of two, we introduce four novel definitions of the ODT problems: three for size-constrained trees and one for depth-constrained trees. These definitions are stated unambiguously through executable recursive programs, satisfying all criteria we propose for a formal specification. In this sense, they resemble the "standard form" used in the study of general-purpose solvers. Grounded in algebraic programming theory-a relational formalism for deriving correct-by-construction algorithms from specifications-we can not only establish the existence or nonexistence of dynamic programming solutions but also derive them constructively whenever they exist. Consequently, the four generic problem definitions yield four novel optimal algorithms for ODT problems with arbitrary splitting rules that satisfy the axioms and objective functions of a given form. These algorithms encompass the known depth-constrained, axis-parallel ODT algorithm as the special case, while providing a unified, efficient, and elegant solution for the general ODT problem. In Part II, we present the first optimal hypersurface decision tree algorithm and provide comprehensive experiments against axis-parallel decision tree algorithms, including heuristic CART and state-of-the-art optimal methods. The results demonstrate the significant potential of decision trees with flexible splitting rules. Moreover, our framework is readily extendable to support algorithms for constructing even more flexible decision trees, including those with mixed splitting rules.

Authors: Benjamin Berger

This paper presents the Chonkers algorithm, a novel content-defined chunking method providing simultaneous strict guarantees on chunk size and edit locality. Unlike existing algorithms such as Rabin fingerprinting and anchor-based methods, Chonkers achieves bounded propagation of edits and precise control over chunk sizes. I describe the algorithm's layered structure, theoretical guarantees, implementation considerations, and introduce the Yarn datatype, a deduplicated, merge-tree-based string representation benefiting from Chonkers' strict guarantees.

• A crowdsourced project to link erdosproblems.com with OEIS (\(\mathbb{M}\), see also), launched by Thomas Bloom and Terry Tao.

• WeakC4, or distilling an emergent object (\(\mathbb{M}\), livestream). A project to compress a search-free strategy for winning Connect 4 into as few bits as possible, by storing a game graph for a small opening book of nodes combined with an efficient encoding of simple winning strategies at the leaves of the graph. So far they are down to 9221 nodes and roughly 150kbytes. See also their visualization of the opening book graph.

• New Good Article on Wikipedia: Pythagorean addition (\(\mathbb{M}\)). This is the operation of computing the hypotenuse of a right triangle from its two sides. Because this is commutative and associative, it defines a commutative monoid, and Knuth defined it as a built-in binary operation in metafont, writing that it could likely replace most uses of square roots in software.

  Back when people used slide rules instead of computers, some slide rules had special scales (positioning numbers by their square roots rather than their logs) that would allow them to perform this calculation, for instance in converting from Cartesian to polar coordinates: see “Find absolute value” on p.3 of this slide-rule instruction guide.

  Nowadays most programming language libraries provide this operation as hypot.

• Problematic new licensing requirements from Springer journals: you are forbidden from including any post-submission improvements in your openly-licensed preprints, must add a disclaimer to the preprints saying they are unimproved, are forbidden from creating any later version that makes changes to the format or content of the Springer-published version, and are not given any opportunity to object to or modify the terms of the license.

• Somehow cleveref is broken despite not having been updated in 7 years, after a LaTeX kernel change from November 2024 was included in recent TeXlive updates. A workaround using aliascnt may be possible, if you are not using amsmath (!) and have control over when cleveref is loaded.

• Right kite reptile tessellations, Dani Laura. The right kite with side ratio \(\sqrt2\) lets the tiles fit together particularly nicely, with some larger sides bisected by smaller sides of tiles.

• Wikipedia is getting rid of its mobile specific subdomain (\(\mathbb{M}\)), and there was much rejoicing.

• What is the minimum number of faces in a polyhedron all of whose faces are non-convex (\(\mathbb{M}\))? My answer is an eight-sided hexagonal torus credited by Grünbaum and Szilassi to a 1988 German diploma thesis of Schwörbel, modified to reduce its face count to seven. But it does not fit some definitions of polyhedra, because it has pairs of faces with disconnected intersections.

• Fraudulent publishing in the mathematical sciences (\(\mathbb{M}\), via): part I of a report of a joint committee of IMU and ICIAM consisting of Ilka Agricola, Lynn Heller, Wil Schilders, Moritz Schubotz, Peter Taylor, and Luis Vega. Part I is “where are we now” and part II (to come) is “what can we do”. I saw Agricola speak on this sort of thing a year ago and she tells a compelling story about how fraudulent publishing practices (by both publishers and authors) are damaging mathematics.

• The recent unpleasantness over Poland is already causing me minor repercussions here in California (\(\mathbb{M}\)): my coauthor doesn’t want to risk flying to Warsaw, a potential repeat of this happening, and getting stranded there. So he has canceled his travel to ESA / ALGO to present our joint paper on bandwidth and BFS. Instead it will be presented as a prerecorded video.

  I guess Europeans traveling to ALGO can always count on taking a train instead, a little more reliably than air travel to Warsaw after recent events, so I hope a dent in intercontinental attendees doesn’t hurt the conference too much. Anyway, best wishes to all in attendance, and of course to all in Poland and Ukraine who have more significant consequences to worry about.

• In a “McCarthy era move”, UC Berkeley gives Trump administration 160 names of students and faculty investigated for “alleged antisemitic incidents” (\(\mathbb{M}\), see also, archived). The Guardian quotes one of the targeted scholars, Judith Butler: “We have a right to know the charges against us, to know who has made the charges and to review them and defend ourselves. But none of that has happened, which is why we’re in Kafka-land … It is an enormous breach of trust.” They added that “the university’s normal procedures for handling complaints had been suspended, which has seemingly stripped faculty of their rights to respond to claims or get basic information about the inquiries”.

• Matroid bingo (\(\mathbb{M}\)). The requirements that no bingo card be empty, that everyone can win (no card has a subset of numbers of another card), and that no two players can win simultaneously (no union of two cards has a third card as a subset) turn out to match the axioms for the cycles in a matroid. It is not required that everyone have equal probability of winning, but the dual Fano matroid turns out to be particularly fair in this sense.

• Wikipedia is resilient because it is boring (\(\mathbb{M}\), archived). Josh Dzieza, The Verge.

By David Eppstein

 "I'll be on vacation so I won't be checking email.''

"I can't be at the meeting since I will be out of town''

Technology has made it so that:

a) You really CAN get email when you are on vacation.

b) You really CAN go to a meeting if you are out of town (if the meeting is on Zoom which is becoming more and more common).  (My proofreader tells me that Zoom is spelled with a capital Z.  I did not know that! The phrase I  Googled is formally correct, though I googled is acceptable. I have never seen anyone say or write I Binged  or I binged  for searching, though I have seen I binged watched Babylon Five  for example.  I have never seen  I Yahooed or I yahooed  for search or for any other reason. Fun fact: the term Yahoo was coined by Jonathan Swift for use in the book Gulliver's Travels.) 

Caveats:

1) You are on vacation! You DO NOT WANT to answer email!

2) You are out of town at a conference and the meeting is at the same time as a talk you want to go to.

3) There are too many meetings so it's good to have an excuse to not go to some. 

Personal:

This is one issue where I may be LESS of a Luddite than Lance:

When Lance is on vacation, he DOES NOT get email.

When I am out of town, I DO get email, and respond to it. This first struck me when I was on a riverboat cruise in France and I got an email from my chairman asking if I would be on some committee (I said yes).  I was more `in contact' than people on campus who don't respond to email. 

How we talk about things: My advisor told me he would be giving a talk in Zurich. I azoomed he meant a talk on Zoom. He actually meant in person. Fortunately it was recorded so I didn't have to get up at 5:00 a.m.  to see it. (My spellcheck thinks azoomed is not a word. It is correct. For now.)

By gasarch

In this blog post, we will talk about some recent advances in algorithms for approximately solving Shapley Games.

What is a Shapley Game?

At an intuitive level, Shapley games capture the idea of extending one-shot 2-player games to be occurring over multiple stages.

Explicitly, Shapley games are played on an underlying state space . At each , the two players can each choose one of actions. Based on their choices and , the first player receives a reward (and the second player receives ) and the game moves to state with probability . Furthermore, at each time step there is a probability that the game ends (thus, ). The goal of each player is to maximize their earnings.

These games were introduced by [Shapley’53], where he also proved that when , the Shapley game has a value: that is, this maximum exists.

Furthermore, this value can be characterized as the solution to a specific fixed point equation: defining to be the optimal payoff of a two-player game on the payoff matrix , the value of a Shapley Game is the unique vector satisfying for all (here, ). Intuitively, this makes sense: a player’s expected payoff at a given state is determined exactly by their current payoff and their future payoff .

We are often interested in the setting where is exponentially small (in fact, it was later proven that Shapley games have a value when but we will not focus on this case).

Connecting Shapley Games to Fixed Point Theorems

As we talked about above, the value of a Shapley Game is the unique vector satisfying for all . If we define to be the vector consisting of the right hand side over all $\latex v\in V$, then it turns out that in addition to being polynomial-time computable, actually satisfies two special properties:

• Monotonicity: for every ,
• Contraction: for every ,
  • Later, we will also care about defining a contraction property for discrete functions: in this case, we loosen the constraint to be (else, all values are actually equal)

By Tarski’s Fixed Point Theorem, every monotone function has a fixed point; and by Banach’s Fixed Point Theorem, every contracting function also has a fixed point.

For our algorithms, we will not be interested in the exact Shapley value, but just an -approximation of it. To define this, let and .

Then, [EPRY’20] constructs a (discrete) monotone contraction such that

1. A query to requires one query to an oracle for .
2. Given any with , we can construct in polynomial time an such that .
3. satisfies that . This last condition is an implementation detail which will make some of the later exposition simpler.

With this reduction in mind, the challenge for approximately solving Shapley Games has just become one of finding monotone/contracting/both fixed points of a function over . In the next few sections, we will talk about some recent algorithms for accomplishing this.

It’s important to note which factors are important for the runtime and query and complexity here: we will often consider and to be “reasonable” (since this is the size of the state space and the bit complexity of the input, respectively). In a reasonable application, we would expect to generally be fairly small, likely .

Complexity Implications

Before describing algorithms for approximately solving Shapley Games, let’s take a look at the complexity landscape surrounding it.

Above is a diagram of the relevant complexity classes surrounding Shapley Games. These are, in order:

1. PPAD: A prototypical complete problem for PPAD is End-Of-Line: Given an (exponentially large) directed graph consisting of lines and cycles and a start point of a line, find the end of one of the lines. Two famous examples of problems complete for PPAD are finding (approximate) Nash Equilibria and Brouwer Fixed Points (Given a compact domain and a continuous function , find an such that ).
2. PLS (Polynomial Local Search): A prototypical complete problem for PLS is the following: given an (exponentially large) DAG and a potential function which only decreases along directed edges, find a local optimum. It is believed that neither PLS nor PPAD are subsets of each other.
3. CLS (Continuous Local Search): An example complete problem for CLS is Gradient Descent. It is also known that (shown in [FGHS’22]).
4. UEOPL (Unique End of Potential Line): There is a hidden class not in the above diagram: EOPL (End Of Potential Line). This marries the prototypical complete problems for PPAD and PLS by adding a potential function to End-Of-Line. Building on this, UEOPL asks for there to be exactly one line (and hence exactly one solution). By definition, this lies within .

From first principles, it is true that computing the (approximate) Shapley values lies both within PPAD and PLS (and hence within CLS), by noticing that it is a special case of Brouwer’s Fixed Point Theorem and admits the potential function , respectively. Furthermore, by Shapley’s Theorem, we know that there is a unique solution. Recently, [BFGMS’25] showed that computing approximate Shapley Values is within UEOPL. More generally, they showed that computing a fixed point of any monotone contraction is within UEOPL.

Algorithms

Inefficient Algorithms

Let’s begin by “forgetting” the contracting constraint and just trying to find a fixed point of a monotone . A simple algorithm for this task is to consider the sequence of iterates . Since is monotone, , and for all , it follows that there must be a repeat in this sequence. Unfortunately, the query complexity of this algorithm is . Since we are often interested in the setting where and are exponentially small, this is too slow.

In the opposite direction, suppose we just knew that was contracting, and not monotone. In this case, we can find an -approximate fixed point of directly by starting at an arbitrary point and considering the sequence which will require iterations and is also too slow.

On the other hand, exciting new work by [CLY’24] gave an algorithm with query complexity for the task when is just contracting. Unfortunately, the runtime of this algorithm depends on factors of at-least (there is a brute-force grid search over between each query).

By contrast, in the upcoming algorithms, we will have the property that the “external” runtime is at most some times the query complexity. Here, by external runtime, we mean the work in between oracle calls to .

We will now describe some algorithms for computing fixed points of monotone contractions. The current state of the art is an algorithm by [BFGMS’25] that takes queries to to find such a fixed point. Here, we will present a simplified version of this algorithm that takes queries to find this fixed point.

First Pass: Monotone Fixed Point Algorithms

On the path to faster algorithms, let’s begin with . Here, we know that and . We can then binary search for a fixed point, preserving the invariant that and at each iteration. This takes queries to .

Similarly, we can do a recursive -layer binary search to find a fixed point when is -dimensional, which requires queries to .

To improve this algorithm, let’s decompose it into two parts: a base case and a gluing theorem.

1. The base case here is solving in queries.
2. The “gluing theorem” says that if we can find a fixed point of a -dimensional in time , then we can find a fixed point of a -dimensional in time .

One road to improving the runtime of this algorithm is to improve the base case. That is, is there some fixed constant where we can find a fixed point of a -dimensional in queries?

Recent work in [BPR’25] has given a lower bound of for all , and there is a natural lower bound for . However, we can do better for , as shown in [FPS’22]:

Given a monotone , there is an algorithm which takes queries and outputs an for which .

Immediately, this implies an algorithm taking queries for finding a fixed point of a -dimensional . However, this is not the end of the story, as we can also derive a more general gluing theorem, also shown in [FPS’22]:

If we can find fixed points of dimensional s in query complexity respectively, then we can find the fixed point of a dimensional in query complexity .

Together, these imply an algorithm running in time for finding a fixed point.

Gluing Theorem

Let’s begin by discussing a variant of the gluing theorem from [BFGMS’25]. In particular, suppose that we have oracles and for the and dimensional monotone contraction problems, respectively.

As a first pass, consider giving to the function : in other words, call on the slice where the first coordinates are fixed to be and return the result of calling on this fixed point. Naively, this seems reasonable: is guaranteed to return a fixed point and hence when returns a fixed point in the first coordinates it must be the case that we know its fixed part in the last coordinates.

The issue, however is that is not monotone nor contracting: for example, suppose that was just the identity function: now, is free to return any point in on each run. To fix this, we will follow [BFGMS’25] and suppose that, magically, and both return the Least Fixed Point (LFP) of their input function (by Tarski’s Theorem, the set of fixed points form a sublattice so there exists an LFP: the meet of all of the fixed points).

Proof

We claim that this is sufficient to force to be a monotone contraction. To prove this, suppose we have two queries and , and suppose that and . We show the two necessary facts:

1. If , then .
2. It is true that (we prove this when , which can then be extended by induction)

To prove the first fact, we claim that for every such that , there exists a with such that , and that a similar statement holds in reverse (i.e., given a we can find with similar properties). The key observation is that , where the last inequality follows from .

Thus, we may consider the sequence . Each of these is upper bounded by and they form an increasing sequence, so one of the values among them must yield a fixed point . We can do a similar argument in the reverse direction, so this implies that when we also have . Furthermore, this also implies that .

Now, suppose and are incomparable. Then, compute (the meet of the two) and (the join of the two) which satisfy . It follows that if and are the least fixed points for and (and, as before, and are the fixed points we are looking for), then and thus . Hence, we are done.

With this in mind, the final question is: how can we find a Least Fixed Point? If were just monotone, then [EPRY’20] showed that this was NP-Hard. It turns out that when is -dimensional, there is a reduction from [BFGMS’25] that gives us the LFP with constantly many extra queries. We now have that the query complexity of gluing the two instances requires queries to .

Base Case of [FPS’22]

We will briefly describe the parts of the base case algorithm from [FPS’22] that we will later use to inform our algorithm for monotone contractions.

To describe the base case algorithm, we need the following definition:

Given a function , we let and .

Finding a fixed point is equivalent to finding a point in . With this definition in mind, we can break up the [FPS’22] base case algorithm into two steps:

1. For a fixed , find some vector with in queries.
2. Binary search on to find a fixed point.

Overall we run the first step times which gives the final number of queries.

Brief Aside: Gluing Up & Down Points

Before discussing the [BFGMS’25] result, it’s worth mentioning that it is also possible to write a gluing theorem which uses just the first step of the above base case: that is, given oracles which compute either an Up or Down point (given a fixed coordinate), glue them together to find either an Up or Down point of a -dimensional instance. This result was shown in [CL’22] and immediately gives an algorithm running in time and queries .

The Power of Monotone Contractions

We are finally ready to bring everything together to describe our algorithm. The key idea is to strip wasteful work from the above base case. In particular, when we search for an Up or Down point along a particular slice , we are often redoing similar work (for example, we may have gained some information telling us that there is no Up/Down point in a given region of the grid, so there is no use re-searching there).

We will apply this idea to re-use work from prior iterations, so that the total amortized cost of the binary searches comes out to . In [BFGMS’25], they do this directly on -dimensional instances. In this overview, we will instead show how to compute a LFP of a -dimensional monotone contraction in queries, which, combined with the above gluing theorem, yields the desired query complexity.

We will require two properties to hold for our :

1. : recall that we have this for free from the [EPRY’20] reduction.
2. If then there exists no other with ; and similarly for . Equivalently, each -dimensional slice of has a unique fixed point.
   • We can achieve this as follows: if and , then set (else, set it to ). We can do the same in the direction. In this way, a consecutive sequence of fixed points will all move down except for the first instance.

Since each -dimensional slice of now has a unique fixed point, let’s define to be the unique fixed point for a given , and similarly define .

With this in mind, we can plot these functions:

Here, the blue line corresponds to and the red line corresponds to (we have also increased the bounds so that hits both the top and bottom edge). In fact, we can also say more: the salmon-colored region is exactly the Up set and the green region is exactly the Down set, and where the two lines meet is the set of fixed points!

Note that both and have slope at most in their respective directions, which suggests the following: if and , then , and similarly (but in the opposite direction) for the Down set. The reasoning for this is simply the observation that the distance between the two lines is non-increasing.

From this, we can derive our final algorithm: for a given , conduct a binary search to find either an Up or Down point (we are guaranteed at most one, unless there is a fixed point), but keep track of the interval which contains the whole Up/Down slice along that value. In future binary searches, reuse this interval (shifted appropriately by ) instead of starting with . In this way, the total number of queries is since over the course of the algorithm we do at most two full binary searches (one for Up and one for Down points).

Open Problems

There are a wealth of open problems left here, but we’ll mention two.

• What is the true complexity of computing fixed points of monotone, contracting, and monotone contracting functions? This includes both the query complexity and the runtime, as currently we have a large gap between lower and upper bounds.
• Are there other properties of Shapley Games that allow us to get faster approximate algorithms beyond just using monotonicity and contraction?

Acknowledgements: I would like to thank my quals committee: Nima Anari, Aviad Rubinstein, and Tselil Schramm for the useful feedback on my quals talk and some suggestions on this blog post. I would also like to thank Spencer Compton for valuable comments on this blog post.

References

[BFGMS’25] Batziou, E., Fearnley, J., Gordon, S., Mehta, R., & Savani, R. (2025, June). Monotone Contractions. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing (pp. 507-517).

[BPR’25] Brânzei, S., Phillips, R., & Recker, N. (2025). Tarski Lower Bounds from Multi-Dimensional Herringbones. arXiv preprint arXiv:2502.16679.

[CL’22] Chen, X., & Li, Y. (2022, July). Improved upper bounds for finding tarski fixed points. In Proceedings of the 23rd ACM Conference on Economics and Computation (pp. 1108-1118).

[CLY’24] Chen, X., Li, Y., & Yannakakis, M. (2024, June). Computing a Fixed Point of Contraction Maps in Polynomial Queries. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing (pp. 1364-1373).

[EPRY’20] Etessami, K., Papadimitriou, C., Rubinstein, A., & Yannakakis, M. (2020). Tarski’s Theorem, Supermodular Games, and the Complexity of Equilibria. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020) (pp. 18-1). Schloss Dagstuhl–Leibniz-Zentrum für Informatik.

[FGHS’22] Fearnley, J., Goldberg, P., Hollender, A., & Savani, R. (2022). The complexity of gradient descent: CLS= PPAD∩ PLS. Journal of the ACM, 70(1), 1-74.

[FPS’22] Fearnley, J., Pálvölgyi, D., & Savani, R. (2022). A faster algorithm for finding Tarski fixed points. ACM Transactions on Algorithms (TALG), 18(3), 1-23.

[Shapley’53] Shapley, L. S. (1953). Stochastic games. Proceedings of the national academy of sciences, 39(10), 1095-1100.

By mishai

Authors: Alexandru Cojocaru, Juan Garay, Qipeng Liu, Fang Song

We give novel lifting theorems for security games in the quantum random oracle model (QROM) in Noisy Intermediate-Scale Quantum (NISQ) settings such as the hybrid query model, the noisy oracle and the bounded-depth models. We provide, for the first time, a hybrid lifting theorem for hybrid algorithms that can perform both quantum and classical queries, as well as a lifting theorem for quantum algorithms with access to noisy oracles or bounded quantum depth. At the core of our results lies a novel measure-and-reprogram framework, called hybrid coherent measure-and-reprogramming, tailored specifically for hybrid algorithms. Equipped with the lifting theorem, we are able to prove directly NISQ security and complexity results by calculating a single combinatorial quantity, relying solely on classical reasoning. As applications, we derive the first direct product theorems in the average case, in the hybrid setting-i.e., an enabling tool to determine the hybrid hardness of solving multi-instance security games. This allows us to derive in a straightforward manner the NISQ hardness of various security games, such as (i) the non-uniform hardness of salted games, (ii) the hardness of specific cryptographic tasks such as the multiple instance version of one-wayness and collision-resistance, and (iii) uniform or non-uniform hardness of many other games.

Authors: Alexandru Cojocaru, Juan Garay, Qipeng Liu, Fang Song

We give a tighter lifting theorem for security games in the quantum random oracle model. At the core of our main result lies a novel measure-and-reprogram framework that we call coherent reprogramming. This framework gives a tighter lifting theorem for query complexity problems, that only requires purely classical reasoning. As direct applications of our lifting theorem, we first provide a quantum direct product theorem in the average case - i.e., an enabling tool to determine the hardness of solving multi-instance security games. This allows us to derive in a straightforward manner the hardness of various security games, for example (i) the non-uniform hardness of salted games, (ii) the hardness of specific cryptographic tasks such as the multiple instance version of one-wayness and collision-resistance, and (iii) uniform or non-uniform hardness of many other games.

Authors: Jaehoon Chung, Kazuo Iwama, Chung-Shou Liao, Hee-Kap Ahn

We study the problem of partitioning a polygon into the minimum number of subpolygons using cuts in predetermined directions such that each resulting subpolygon satisfies a given width constraint. A polygon satisfies the unit-width constraint for a set of unit vectors if the length of the orthogonal projection of the polygon on a line parallel to a vector in the set is at most one. We analyze structural properties of the minimum partition numbers, focusing on monotonicity under polygon containment. We show that the minimum partition number of a simple polygon is at least that of any subpolygon, provided that the subpolygon satisfies a certain orientation-wise convexity with respect to the polygon. As a consequence, we prove a partition analogue of Bang's conjecture about coverings of convex regions in the plane: for any partition of a convex body in the plane, the sum of relative widths of all parts is at least one. For any convex polygon, there exists a direction along which an optimal partition is achieved by parallel cuts. Given such a direction, an optimal partition can be computed in linear time.

Authors: Michelle Döring, Jan Fehse, Tobias Friedrich, Paula Marten, Niklas Mohrin, Kirill Simonov, Farehe Soheil, Jakob Timm, Shaily Verma

The Vehicle Routing Problem (VRP) is a popular generalization of the Traveling Salesperson Problem. Instead of one salesperson traversing the entire weighted, undirected graph $G$, there are $k$ vehicles available to jointly cover the set of clients $C \subseteq V(G)$. Every vehicle must start at one of the depot vertices $D \subseteq V(G)$ and return to its start. Capacitated Vehicle Routing (CVRP) additionally restricts the route of each vehicle by limiting the number of clients it can cover, the distance it can travel, or both. In this work, we study the complexity of VRP and the three variants of CVRP for several parameterizations, in particular focusing on the treewidth of $G$. We present an FPT algorithm for VRP parameterized by treewidth. For CVRP, we prove paraNP- and $W[\cdot]$-hardness for various parameterizations, including treewidth, thereby rendering the existence of FPT algorithms unlikely. In turn, we provide an XP algorithm for CVRP when parameterized by both treewidth and the vehicle capacity.

Authors: Andreas Bluhm, Matthias C. Caro, Francisco Escudero Gutiérrez, Aadil Oufkir, Cambyse Rouzé

In this work, we study the problems of certifying and learning quantum Ising Hamiltonians. Our main contributions are as follows: Certification of Ising Hamiltonians. We show that certifying an Ising Hamiltonian in normalized Frobenius norm via access to its time-evolution operator requires only $\widetilde O(1/\varepsilon)$ time evolution. This matches the Heisenberg-scaling lower bound of $\Omega(1/\varepsilon)$ up to logarithmic factors. To our knowledge, this is the first nearly-optimal algorithm for testing a Hamiltonian property. A key ingredient in our analysis is the Bonami Lemma from Fourier analysis. Learning Ising Gibbs states. We design an algorithm for learning Ising Gibbs states in trace norm that is sample-efficient in all parameters. In contrast, previous approaches learned the underlying Hamiltonian (which implies learning the Gibbs state) but suffered from exponential sample complexity in the inverse temperature. Certification of Ising Gibbs states. We give an algorithm for certifying Ising Gibbs states in trace norm that is both sample and time-efficient, thereby solving a question posed by Anshu (Harvard Data Science Review, 2022). Finally, we extend our results on learning and certification of Gibbs states to general $k$-local Hamiltonians for any constant $k$.

Authors: Étienne Grandjean, Louis Jachiet

In this paper, we study the class $\mathtt{cstPP}$ of operations $\mathtt{op}: \mathbb{N}^k\to\mathbb{N}$, of any fixed arity $k\ge 1$, satisfying the following property: for each fixed integer $d\ge 1$, there exists an algorithm for a RAM machine which, for any input integer $N\ge 2$, - pre-computes some tables in $O(N)$ time, - then reads $k$ operands $x_1,\ldots,x_k1$, or conversely, is reduced to $N^{\varepsilon}$, for any positive $\varepsilon<1$ (provided the set of primitive operation includes $+$, $\mathtt{div}$ and $\mathtt{mod}$). To complete the picture, we demonstrate that the $\mathtt{cstPP}$ class degenerates if the preprocessing time reduces to $N^{o(1)}$.

Authors: Amira Abbas, Nunzia Cerrato, Francisco Escudero Gutiérrez, Dmitry Grinko, Francesco Anna Mele, Pulkit Sinha

We study the problem of learning Hamiltonians $H$ that are $s$-sparse in the Pauli basis, given access to their time evolution. Although Hamiltonian learning has been extensively investigated, two issues recur in much of the existing literature: the absence of matching lower bounds and the use of mathematically convenient but physically opaque error measures. We address both challenges by introducing two physically motivated distances between Hamiltonians and designing a nearly optimal algorithm with respect to one of these metrics. The first, time-constrained distance, quantifies distinguishability through dynamical evolution up to a bounded time. The second, temperature-constrained distance, captures distinguishability through thermal states at bounded inverse temperatures. We show that $s$-sparse Hamiltonians with bounded operator norm can be learned in both distances with $O(s \log(1/\epsilon))$ experiments and $O(s^2/\epsilon)$ evolution time. For the time-constrained distance, we further establish lower bounds of $\Omega((s/n)\log(1/\epsilon) + s)$ experiments and $\Omega(\sqrt{s}/\epsilon)$ evolution time, demonstrating near-optimality in the number of experiments. As an intermediate result, we obtain an algorithm that learns every Pauli coefficient of $s$-sparse Hamiltonians up to error $\epsilon$ in $O(s\log(1/\epsilon))$ experiments and $O(s/\epsilon)$ evolution time, improving upon several recent results. The source of this improvement is a new isolation technique, inspired by the Valiant-Vazirani theorem (STOC'85), which shows that NP is as easy as detecting unique solutions. This isolation technique allows us to query the time evolution of a single Pauli coefficient of a sparse Hamiltonian--even when the Pauli support of the Hamiltonian is unknown--ultimately enabling us to recover the Pauli support itself.

Authors: Alexander Taveira Blomenhofer, Benjamin Lovitz

We propose a linear-time algorithm to compute low-rank Chow decompositions. Our algorithm can decompose concise symmetric 3-tensors in n variables of Chow rank n/3. The algorithm is pencil based, hence it relies on generalized eigenvalue computations. We also develop sub-quadratic time algorithms for higher order Chow decompositions, and Chow decompositions of 3-tensors into products of linear forms which do not lie on the generic orbit. In particular, we obtain a sub-quadratic-time algorithm for decomposing a symmetric 3-tensor into a linear combination of W-tensors.

Authors: Simen Storesund, Kristian Valset Aars, Robin Dietrich, Nicolai Waniek

Efficient planning and sequence selection are central to intelligence, yet current approaches remain largely incompatible with biological computation. Classical graph algorithms like Dijkstra's or A* require global state and biologically implausible operations such as backtracing, while reinforcement learning methods rely on slow gradient-based policy updates that appear inconsistent with rapid behavioral adaptation observed in natural systems. We propose a biologically plausible algorithm for shortest-path computation that operates through local spike-based message-passing with realistic processing delays. The algorithm exploits spike-timing coincidences to identify nodes on optimal paths: Neurons that receive inhibitory-excitatory message pairs earlier than predicted reduce their response delays, creating a temporal compression that propagates backwards from target to source. Through analytical proof and simulations on random spatial networks, we demonstrate that the algorithm converges and discovers all shortest paths using purely timing-based mechanisms. By showing how short-term timing dynamics alone can compute shortest paths, this work provides new insights into how biological networks might solve complex computational problems through purely local computation and relative spike-time prediction. These findings open new directions for understanding distributed computation in biological and artificial systems, with possible implications for computational neuroscience, AI, reinforcement learning, and neuromorphic systems.

Authors: Yixin Cao, Yiren Lu, Junhong Nie, Xiaoming Sun, Guojing Tian

Quantum circuits composed of CNOT and $R_z$ are fundamental building blocks of many quantum algorithms, so optimizing the synthesis of such quantum circuits is crucial. We address this problem from a theoretical perspective by studying the graphic parity network synthesis problem. A graphic parity network for a graph $G$ is a quantum circuit composed solely of CNOT gates where each edge of $G$ is represented in the circuit, and the final state of the wires matches the original input. We aim to synthesize graphic parity networks with the minimum number of gates, specifically for quantum algorithms addressing combinatorial optimization problems with Ising formulations. We demonstrate that a graphic parity network for a connected graph with $n$ vertices and $m$ edges requires at least $m+n-1$ gates. This lower bound can be improved to $m+\Omega(m) = m+\Omega(n^{1.5})$ when the shortest cycle in the graph has a length of at least five. We complement this result with a simple randomized algorithm that synthesizes a graphic parity network with expected $m + O(n^{1.5}\sqrt{\log n})$ gates. Additionally, we begin exploring connected graphs that allow for graphic parity networks with exactly $m+n-1$ gates. We conjecture that all such graphs belong to a newly defined graph class. Furthermore, we present a linear-time algorithm for synthesizing minimum graphic parity networks for graphs within this class. However, this graph class is not closed under taking induced subgraphs, and we show that recognizing it is $\textsf{NP}$-complete, which is complemented with a fixed-parameter tractable algorithm parameterized by the treewidth.

Authors: Zhuowei Zhao, Zhuo Zhang, Hanzhi Wang, Junhao Gan, Zhifeng Bao, Jianzhong Qi

We revisit Approximate Graph Propagation (AGP), a unified framework which captures various graph propagation tasks, such as PageRank, feature propagation in Graph Neural Networks (GNNs), and graph-based Retrieval-Augmented Generation (RAG). Our work focuses on the settings of dynamic graphs and dynamic parameterized queries, where the underlying graphs evolve over time (updated by edge insertions or deletions) and the input query parameters are specified on the fly to fit application needs. Our first contribution is an interesting observation that the SOTA solution, AGP-Static, can be adapted to support dynamic parameterized queries; however several challenges remain unresolved. Firstly, the query time complexity of AGP-Static is based on an assumption of using an optimal algorithm for subset sampling in its query algorithm. Unfortunately, back to that time, such an algorithm did not exist; without such an optimal algorithm, an extra $O(\log^2 n)$ factor is required in the query complexity, where $n$ is the number of vertices in the graphs. Secondly, AGP-Static performs poorly on dynamic graphs, taking $O(n\log n)$ time to process each update. To address these challenges, we propose a new algorithm, AGP-Static++, which is simpler yet reduces roughly a factor of $O(\log^2 n)$ in the query complexity while preserving the approximation guarantees of AGP-Static. However, AGP-Static++ still requires $O(n)$ time to process each update. To better support dynamic graphs, we further propose AGP-Dynamic, which achieves $O(1)$ amortized time per update, significantly improving the aforementioned $O(n)$ per-update bound, while still preserving the query complexity and approximation guarantees. Last, our comprehensive experiments validate the theoretical improvements: compared to the baselines, our algorithm achieves speedups of up to $177\times$ on update time and $10\times$ on query efficiency.