Last Update

OPML feed of all feeds.

Subscribe to the Atom feed, RSS feed to stay up to date.

Thank you to arXiv for use of its open access interoperability.

Note: the date of arXiv entries announced right after publication holidays might incorrectly show up as the date of the publication holiday itself. This is due to our ad hoc method of inferring announcement dates, which are not returned by the arXiv API.

Powered by Pluto.

Source on GitHub.

Maintained by Nima Anari, Arnab Bhattacharyya, Gautam Kamath.

Theory of Computing Report

Monday, August 24

Math after AI

from Windows on Theory
For a very long time, my favorite activity was to sit and think about mathematical questions. Staring at a blank sheet of paper, trying to grasp in my mind abstract concepts, bouncing ideas off colleagues and students. There is nothing quite like the feeling that you are exploring the unknown by only using your mind.  … Continue reading Math after AI

For a very long time, my favorite activity was to sit and think about mathematical questions. Staring at a blank sheet of paper, trying to grasp in my mind abstract concepts, bouncing ideas off colleagues and students. There is nothing quite like the feeling that you are exploring the unknown by only using your mind. 

Mathematicians have different styles and motivations for doing math. For some, it is about the challenge of solving hard problems. Others might have some application in mind, or a question they feel compelled to find the answer to. But I believe that none would stick with this profession if they did not find the process of doing mathematics satisfying. We cannot deny that this process is going through a profound change with AI. Some mathematicians have been meeting this change with excitement, while others with grief. I share both sentiments.

When considering the future of math (and science at large), it is worth reflecting on its past. For centuries, mathematicians and scientists typically worked under the patronage of nobles and royals: Archimedes advised King Hiero II, al-Khwarizmi was supported by the Abbasid caliphs, and Galileo by the Medicis, while medieval universities remained largely teaching institutions. It was only after the emergence of the royal academies and research universities from the seventeenth century onwards that scientists were paid by the state for pure research. Beyond patrons and academies, scientists have supported themselves in varied ways: military engineering (Archimedes), day jobs in law (Fermat), personal wealth (Darwin), the Royal Mint (Newton), tax farming (Lavoisier), and of course, examining patents.

But if there is one constant that has held true from Archimedes to our time, it is the importance of a scientific community. Scientific communication evolved from personal correspondence and networks of letters, through academies, to modern journals. But throughout this evolution, scientists valued the community of their peers.

What these communities focused on has changed over time. These days proving theorems is considered the prized activity in mathematics, but throughout much of history, the focus was on calculations or solving problems, rather than rigor. In the sixteenth century, Italian mathematicians earned jobs through equation-solving duels, which caused them to keep formulas such as the solution to the cubic equation secret. Euclid and al-Khwarizmi are known to this day not because of their new discoveries as much as for organizing known results.

Today, there are many self-selected and self-organizing scientific communities, which set up their own publication venues, norms, and processes. They are by and large self-governing, and each scientist chooses in which of these communities to participate. The university, which typically pays the scientist’s salary, largely defers to the judgment of their community as to the value of their work. Together with the mechanism of tenure, this leads to a remarkable lack of direct employer oversight of scientists’ output. 

Many discussions of science’s culture, including peer review, the publication process, and tenure, focus on their various defects and problematic cases. Yet science has been immensely successful. To use AI terminology, the last “pretrain” humanity got was hundreds of thousands of years ago with Homo sapiens (internal codename: homo-erectus-v5-pro-max). And yet we have managed to advance so much on that basis.

I am also surprised by how we managed to keep science legible. Theories like general relativity and quantum mechanics are the results of hundreds, if not thousands, of years of work by humanity’s most brilliant scientists and mathematicians. And yet we are able to routinely teach them to undergraduate students.

Impact of AI on Math

At this point, it is undeniable that AI can make significant contributions to solving mathematical problems. Solving open problems has been a prized activity in mathematics for a long time. One reason is that it is the easiest way to verify that one has done something that is both novel and interesting. And if we’re lucky and the problem was chosen well, the solution will not be a highly specific trick, but a more general insight or technique that can be used broadly. However, this does not mean that solving open problems is the only or even the most important contribution, and thankfully the “inefficiency” of the mechanisms for evaluating researchers allows many other types of contributions to still flourish.

For the same reason as above, solving open problems with AI is a straightforward way to dispel the skepticism of people who believe it cannot do research-level mathematics. But once we go beyond such skepticism, it is not clear that solving open problems should be the only or even the main use of AI. If you hope or believe AI is inherently incapable of posing problems, writing exposition, or building theories, then you are bound to be disappointed. 

What does this mean for mathematics and the role of human mathematicians? There have been radically different responses to this. On one extreme, Weinreich called for a “total opposition to artificial mathematics,” and in particular for mathematics departments to “[establish] anti-AI policies for student work, [reserve] hire lines for mathematicians who eschew AI, [and value] AI-free papers more highly in tenure promotion.” (It is unclear if, under his proposal, “AI-free” papers would be allowed to cite results that did use AI.) On the other hand, Tao said that AI will change how we do math, and that “we do have to somehow let go of conventional assumptions of what intellect is.”

Weinreich’s point of view resonates with the view of mathematics as an art, which is about human expression. On the other hand, many of the strongest mathematicians in history, including Archimedes, Newton, Euler, Gauss, and von Neumann, had a deep interest in its applications. If you care about mathematics’ applications, eschewing AI-enabled discoveries is not an option. Hence, I do not believe that an AI-free vision of mathematics, of the type promoted by Weinreich, is a viable future for it as an academic field. Recreational and competitive mathematics will have different standards, but the lessons of chess (which is actually thriving!) suggest that a complete rejection of AI is unwise even in these domains.

This does not mean that we will have no need for human mathematicians. As mentioned above, the modes of scholarship and funding models for mathematicians have changed over the years, and can change again. In particular, education has long been one of the primary missions and occupations of mathematicians, and it will be as important as ever. If we want (as I do) humans to keep control of their destiny, an educated society will be only more important as AI systems become more powerful.

I believe that human curiosity and legibility will also continue to play a crucial role in science and mathematics. One lesson from history is that it’s extremely hard to predict which directions will have practical applications, and the answers to questions pursued out of pure intellectual curiosity can have great practical impact. In 1940, the mathematician G. H. Hardy wrote that “Real mathematics has no effects on war. No one has yet discovered any warlike purpose to be served by the theory of numbers or relativity, and it seems very unlikely that anyone will do so for many years.” Needless to say, since then people have found many useful, and even warlike applications for these fields, and in particular GPS and public-key cryptography.

Given the track record of curiosity-based science, it would not be wise to eliminate humans from this process and replace them with “artificial scholarly communities” any time soon. Even if it were possible to get the same value, given the unpredictability and time lag of basic science applications, we will not be able to verify this in the near future. Also—and here I am biased—curiosity-based science is good in itself. Number theory is beautiful and would have been beautiful even without cryptography.

Could humans even keep up with understanding AI advances? I believe the answer is yes. Humans have always developed increasingly powerful abstractions to handle complexity. This is the only way we can use brains much like those of our cave-dwelling ancestors to grasp quantum mechanics, write complex software, manage companies, and organize societies many orders of magnitude larger than they did. Abstraction is what allowed us to compress thousands of years of scientific progress into an undergraduate program, and will allow AI to compress its findings and make them legible to us. It may well be that such levels of abstraction will mean that we do not always follow all steps of a proof, just like we do not verify today that a program correctly multiplied two large numbers.

AI will impact much more than science and math. Mathematicians are people too, and they face many greater risks (as well as potential benefits) from AI than those related to its impact on their profession. If AI leads (as I very much hope) to a flourishing human society, then it would be one that values education, curiosity and creativity. We might not explore math using a blank sheet of paper in the same way as I did as a graduate student, but we would still be making and sharing new discoveries. Emma Goldman is often (mis)quoted as saying “If I can’t dance, I don’t want to be part of your revolution.” Similarly, I don’t want to be part of an AI revolution that has no room for human scientists, mathematicians, or artists.

By Boaz Barak

Generalizing Soft Tissue Deformation and Force Prediction Across Material Stiffness and Geometry

from arXiv: Computational Geometry

Authors: Madina Kojanazarova, Sidaty El Hadramy, Philippe C. Cattin

Accurate soft tissue simulation is essential for surgical training, pre-operative planning, and haptic feedback systems. While learning-based surrogate models trained on data using the finite element method (FEM) offer a promising path to real-time inference, their reliability depends on well-calibrated constitutive models. Existing approaches neither provide systematic guidance on model selection across stiffness levels, nor generalize across different tissue stiffnesses or geometries. We perform a comprehensive calibration of hyperelastic constitutive models in the SOFA Framework using gravity-loaded silicone beams with different stiffnesses. Using calibrated simulations as training data, we use a softness conditioned equivariant graph neural network, enabling deformation and force prediction across multiple tissue types and unseen geometries. Our model achieves sub-millimeter mean deformation accuracy at 0.010s inference time, while showing that force prediction quality is directly tied to upstream calibration consistency.

Authors: Madina Kojanazarova, Sidaty El Hadramy, Philippe C. Cattin

Accurate soft tissue simulation is essential for surgical training, pre-operative planning, and haptic feedback systems. While learning-based surrogate models trained on data using the finite element method (FEM) offer a promising path to real-time inference, their reliability depends on well-calibrated constitutive models. Existing approaches neither provide systematic guidance on model selection across stiffness levels, nor generalize across different tissue stiffnesses or geometries. We perform a comprehensive calibration of hyperelastic constitutive models in the SOFA Framework using gravity-loaded silicone beams with different stiffnesses. Using calibrated simulations as training data, we use a softness conditioned equivariant graph neural network, enabling deformation and force prediction across multiple tissue types and unseen geometries. Our model achieves sub-millimeter mean deformation accuracy at 0.010s inference time, while showing that force prediction quality is directly tied to upstream calibration consistency.

Truthful Calibration Measures for Sequential Prediction

from arXiv: Data Structures and Algorithms

Authors: Anagha Gokul, Jason Hartline, Lunjia Hu, Jonathan Ullman, Yifan Wu

Calibration requires probabilistic reports to be conditionally unbiased and reliably interpretable as probabilities. A calibration measure assigns numerical error to miscalibrated reports. Haghtalab et al. (2024) proposed an approximately truthful calibration measure for online prediction, leaving open whether exact truthfulness is compatible with completeness and soundness. We resolve this question negatively for sequential binary prediction: exact truthfulness is incompatible with completeness and soundness, even for independent outcomes. We then show that this impossibility is specific to exact truthfulness. We give two general reductions from a base calibration measure, producing additively and multiplicatively approximately truthful calibration measures, respectively. Applying the multiplicative reduction, for every $0 < \varepsilon < 1$ we construct a sound and complete calibration measure that is $(1+\exp(-T^{(1-\varepsilon)/2}/2))$-multiplicatively truthful. This improves the approximate-truthfulness guarantee of Haghtalab et al. (2024).

Authors: Anagha Gokul, Jason Hartline, Lunjia Hu, Jonathan Ullman, Yifan Wu

Calibration requires probabilistic reports to be conditionally unbiased and reliably interpretable as probabilities. A calibration measure assigns numerical error to miscalibrated reports. Haghtalab et al. (2024) proposed an approximately truthful calibration measure for online prediction, leaving open whether exact truthfulness is compatible with completeness and soundness. We resolve this question negatively for sequential binary prediction: exact truthfulness is incompatible with completeness and soundness, even for independent outcomes. We then show that this impossibility is specific to exact truthfulness. We give two general reductions from a base calibration measure, producing additively and multiplicatively approximately truthful calibration measures, respectively. Applying the multiplicative reduction, for every $0 < \varepsilon < 1$ we construct a sound and complete calibration measure that is $(1+\exp(-T^{(1-\varepsilon)/2}/2))$-multiplicatively truthful. This improves the approximate-truthfulness guarantee of Haghtalab et al. (2024).

T-Robinson Spaces: Structure, Recognition, and Applications to Real Data

from arXiv: Data Structures and Algorithms

Authors: Patricio Asenjo, Sergio Cavero, Mauricio Soto-Gomez, Christopher Thraves Caro

We study \emph{$T$-Robinson spaces}, a tree-based generalization of Robinson spaces in which every path of a compatible tree induces a Robinson subspace. This framework extends the classical notion of Robinsonian representations from linear orderings to tree structures, allowing the modeling of hierarchical and branching data. We establish a complete combinatorial characterization of $T$-Robinson spaces by proving their equivalence with several graph- and hypergraph-theoretic properties. In particular, we show that a dissimilarity space is $T$-Robinson if and only if all its level graphs are dually chordal with a common compatible tree. Combined with the characterization of hypertrees established by Brucker~\cite{brucker2005hypertrees}, this yields the equivalent characterization in terms of the associated cluster, ball, and 2-ball hypergraphs being hypertrees. Building upon these structural results, we develop a recognition algorithm with complexity \(O(K n^{2})\), where \(K\) denotes the number of minimum spanning trees of the dissimilarity space, improving upon existing hypertree-based approaches whenever \(K\) remains moderate. We further introduce a quantitative measure of $T$-Robinson structure that evaluates the extent to which an arbitrary dissimilarity space admits a tree-like representation. Finally, we discuss applications to real-world datasets, illustrating how $T$-Robinson spaces provide an interpretable framework for analyzing and organizing relational data.

Authors: Patricio Asenjo, Sergio Cavero, Mauricio Soto-Gomez, Christopher Thraves Caro

We study \emph{$T$-Robinson spaces}, a tree-based generalization of Robinson spaces in which every path of a compatible tree induces a Robinson subspace. This framework extends the classical notion of Robinsonian representations from linear orderings to tree structures, allowing the modeling of hierarchical and branching data. We establish a complete combinatorial characterization of $T$-Robinson spaces by proving their equivalence with several graph- and hypergraph-theoretic properties. In particular, we show that a dissimilarity space is $T$-Robinson if and only if all its level graphs are dually chordal with a common compatible tree. Combined with the characterization of hypertrees established by Brucker~\cite{brucker2005hypertrees}, this yields the equivalent characterization in terms of the associated cluster, ball, and 2-ball hypergraphs being hypertrees. Building upon these structural results, we develop a recognition algorithm with complexity \(O(K n^{2})\), where \(K\) denotes the number of minimum spanning trees of the dissimilarity space, improving upon existing hypertree-based approaches whenever \(K\) remains moderate. We further introduce a quantitative measure of $T$-Robinson structure that evaluates the extent to which an arbitrary dissimilarity space admits a tree-like representation. Finally, we discuss applications to real-world datasets, illustrating how $T$-Robinson spaces provide an interpretable framework for analyzing and organizing relational data.

Generalized Balls into Bins

from arXiv: Data Structures and Algorithms

Authors: Zhiyi Huang, Kaifeng Lin, Qinpei Lou, Xinyue Xiang, Peilin Yang

Consider a set of bins and two-choice balls arriving by a Poisson process. We must allocate each incoming ball immediately to one of two incident bins. For a given function $f$ and every bin, we aim to bound the expectation of $f(L)$---where $L$ is the bin's final load---based on the arrival rate of balls incident to that bin. We call this problem Generalized Balls into Bins, capturing many problems as special cases including the original Balls into Bins by Azar et al. (1994) and Online Stochastic Matching by Feldman et al. (2009). We show that Greedy provides optimal amortized bounds for all convex and concave functions $f$. Further, we propose another algorithm that achieves non-trivial bounds without amortization. As an application, we design a competitive algorithm for a stochastic model of completion time minimization on unrelated machines.

Authors: Zhiyi Huang, Kaifeng Lin, Qinpei Lou, Xinyue Xiang, Peilin Yang

Consider a set of bins and two-choice balls arriving by a Poisson process. We must allocate each incoming ball immediately to one of two incident bins. For a given function $f$ and every bin, we aim to bound the expectation of $f(L)$---where $L$ is the bin's final load---based on the arrival rate of balls incident to that bin. We call this problem Generalized Balls into Bins, capturing many problems as special cases including the original Balls into Bins by Azar et al. (1994) and Online Stochastic Matching by Feldman et al. (2009). We show that Greedy provides optimal amortized bounds for all convex and concave functions $f$. Further, we propose another algorithm that achieves non-trivial bounds without amortization. As an application, we design a competitive algorithm for a stochastic model of completion time minimization on unrelated machines.

Maximum Covering Network Design on Graphs with Low Connectivity: Dynamic Programming and Block-Cut Trees

from arXiv: Data Structures and Algorithms

Authors: Felix Rauh, Jannik Matuschke, Hande Yaman

Planning accessible public services such as health care, emergency response, and schools often requires not only choosing where to open facilities but also improving the network that connects people to them, for example upgrading flood-prone roads in vulnerable regions. Most location models, however, take the network as fixed and the budget as given. We study the Maximum Covering Network Design Problem, in which a single budget is shared between opening facilities and upgrading weak links to maximize the population within a target travel distance of an open facility. The problem is hard even on the simplest networks, and planners usually want to see how coverage grows with the budget, not a single plan. We develop an exact dynamic-programming framework that exploits a property common to real road networks: their low connectivity, with many cut points whose removal disconnects the network. On trees, the recursion is self-contained: each state reduces to a few simple facility and upgrade choices that are fast to compute without a solver, giving predictable running times; for larger budgets and travel distances it outperforms solving the MILP formulation directly. On general low-connectivity networks, the framework decomposes the problem at the cut points and embeds a given MILP formulation to solve the resulting pieces, coordinating them through coverage conditions at the interfaces. This lets us compare a formulation on its own against the same formulation inside the framework: across 306 test cases the framework matches or outperforms direct solving on more than 80% of instances. Because it evaluates all budget levels in a single run, it also yields the full coverage-versus-budget curve at no extra cost, whereas direct solving must split its time across individual budgets.

Authors: Felix Rauh, Jannik Matuschke, Hande Yaman

Planning accessible public services such as health care, emergency response, and schools often requires not only choosing where to open facilities but also improving the network that connects people to them, for example upgrading flood-prone roads in vulnerable regions. Most location models, however, take the network as fixed and the budget as given. We study the Maximum Covering Network Design Problem, in which a single budget is shared between opening facilities and upgrading weak links to maximize the population within a target travel distance of an open facility. The problem is hard even on the simplest networks, and planners usually want to see how coverage grows with the budget, not a single plan. We develop an exact dynamic-programming framework that exploits a property common to real road networks: their low connectivity, with many cut points whose removal disconnects the network. On trees, the recursion is self-contained: each state reduces to a few simple facility and upgrade choices that are fast to compute without a solver, giving predictable running times; for larger budgets and travel distances it outperforms solving the MILP formulation directly. On general low-connectivity networks, the framework decomposes the problem at the cut points and embeds a given MILP formulation to solve the resulting pieces, coordinating them through coverage conditions at the interfaces. This lets us compare a formulation on its own against the same formulation inside the framework: across 306 test cases the framework matches or outperforms direct solving on more than 80% of instances. Because it evaluates all budget levels in a single run, it also yields the full coverage-versus-budget curve at no extra cost, whereas direct solving must split its time across individual budgets.

Compact Representations of Geometric Bipartite Graphs via Weighted Biclique Covers

from arXiv: Data Structures and Algorithms

Authors: Aryan Esmailpour, Khoi Le, Stavros Sintos

Bipartite graphs are a fundamental representation for relational data arising in recommendation systems, social networks, and communication graphs. A key challenge in these settings is to store and transmit large bipartite graphs compactly while preserving exact structural and path information. We study biclique-based representations of bipartite graphs $\boldsymbol{G}=(\boldsymbol{V},\boldsymbol{U},\boldsymbol{E})$, where the edge set is encoded using a collection of complete bipartite subgraphs. We focus on the Weighted Biclique Covering problem, which minimizes the total number of vertices used across all bicliques, and introduce a generalized variant that additionally penalizes the number of bicliques, capturing practical overheads in storage, transmission, and model complexity. While the weighted biclique covering problem is known to be $\mathsf{NP}$-Complete, we show that the generalized variant is also $\mathsf{NP}$-Complete. Despite this hardness, many real-world bipartite graphs admit low-dimensional geometric embeddings or can be well approximated by them. Leveraging this observation, we develop the first approximation algorithms with provable guarantees for the (generalized) weighted biclique covering problem on geometric bipartite graphs. Specifically, for $δ$-disk bipartite graphs in low-dimensional $\ell_\infty^d$ spaces, we design a polynomial-time algorithm that achieves an $O(\log |\boldsymbol{U}| \cdot \log^d |\boldsymbol{V}|)$-approximation, combining ideas from greedy set cover, geometric range searching, and densest subgraph optimization. We also show how our algorithms extend to $\ell_α^d$ metrics for any $α\geq 1$. Finally, we evaluate our algorithms on real-world bipartite datasets and show that they efficiently compute significantly smaller biclique-based representations than natural baselines, while scaling to large graphs.

Authors: Aryan Esmailpour, Khoi Le, Stavros Sintos

Bipartite graphs are a fundamental representation for relational data arising in recommendation systems, social networks, and communication graphs. A key challenge in these settings is to store and transmit large bipartite graphs compactly while preserving exact structural and path information. We study biclique-based representations of bipartite graphs $\boldsymbol{G}=(\boldsymbol{V},\boldsymbol{U},\boldsymbol{E})$, where the edge set is encoded using a collection of complete bipartite subgraphs. We focus on the Weighted Biclique Covering problem, which minimizes the total number of vertices used across all bicliques, and introduce a generalized variant that additionally penalizes the number of bicliques, capturing practical overheads in storage, transmission, and model complexity. While the weighted biclique covering problem is known to be $\mathsf{NP}$-Complete, we show that the generalized variant is also $\mathsf{NP}$-Complete. Despite this hardness, many real-world bipartite graphs admit low-dimensional geometric embeddings or can be well approximated by them. Leveraging this observation, we develop the first approximation algorithms with provable guarantees for the (generalized) weighted biclique covering problem on geometric bipartite graphs. Specifically, for $δ$-disk bipartite graphs in low-dimensional $\ell_\infty^d$ spaces, we design a polynomial-time algorithm that achieves an $O(\log |\boldsymbol{U}| \cdot \log^d |\boldsymbol{V}|)$-approximation, combining ideas from greedy set cover, geometric range searching, and densest subgraph optimization. We also show how our algorithms extend to $\ell_α^d$ metrics for any $α\geq 1$. Finally, we evaluate our algorithms on real-world bipartite datasets and show that they efficiently compute significantly smaller biclique-based representations than natural baselines, while scaling to large graphs.

A new analysis of the randomly pivoted Cholesky algorithm

from arXiv: Data Structures and Algorithms

Authors: Ethan N. W. Epperly

The randomly pivoted Cholesky algorithm is one of the leading methods for computing a low-rank approximation to a large positive-semidefinite matrix. However, while it consistently achieves accuracy comparable to or better than competing methods of its type in experiments, its theoretical analysis lags somewhat behind other methods. This paper closes this gap, proving that randomly pivoted Cholesky produces an approximation with expected error within a $1+\varepsilon$ factor of the optimal rank-$r$ approximation in $\mathcal{O}(r/\varepsilon + r\sqrt{\log r})$ steps. This result nearly matches the optimal complexity $Θ(r/\varepsilon)$ for any low-rank approximation method based on a partial Cholesky decomposition (also known as a column Nyström approximation). The paper also presents bounds on the randomly pivoted Cholesky trace and spectral-norm errors that hold with high probability. The mathematical argument is largely due to GPT 5.6-Sol (Pro), with some refinements by the author.

Authors: Ethan N. W. Epperly

The randomly pivoted Cholesky algorithm is one of the leading methods for computing a low-rank approximation to a large positive-semidefinite matrix. However, while it consistently achieves accuracy comparable to or better than competing methods of its type in experiments, its theoretical analysis lags somewhat behind other methods. This paper closes this gap, proving that randomly pivoted Cholesky produces an approximation with expected error within a $1+\varepsilon$ factor of the optimal rank-$r$ approximation in $\mathcal{O}(r/\varepsilon + r\sqrt{\log r})$ steps. This result nearly matches the optimal complexity $Θ(r/\varepsilon)$ for any low-rank approximation method based on a partial Cholesky decomposition (also known as a column Nyström approximation). The paper also presents bounds on the randomly pivoted Cholesky trace and spectral-norm errors that hold with high probability. The mathematical argument is largely due to GPT 5.6-Sol (Pro), with some refinements by the author.

Stochastic Multi-Robot Monitoring on Graphs under Markovian Mobility

from arXiv: Data Structures and Algorithms

Authors: Walid Ben-Ameur, Tijani Chahed, Shamisa Nematollahi

We study a stochastic multi-robot monitoring problem on a connected graph $G=(V,E)$, where each robot moves according to a Markov chain on $G$ and monitors the closed neighborhood of its current vertex. The performance of $r$ robots is evaluated in steady state via two objectives: average-case coverage (the expected number of covered vertices) and worst-case coverage (the minimum coverage probability over all vertices). We consider three models: independent homogeneous strategies, where all robots share the same stationary distribution; independent heterogeneous strategies, where robots use different stationary distributions; and centralized strategies, allowing arbitrary correlations between robot locations. For the heterogeneous model, we prove that maximizing average coverage is NP-hard even for two robots, and that replicating an easy-to-compute optimal homogeneous strategy yields a \(\left(1-\left(1-\frac{1}{r}\right)^r\right)\)-approximation for both objective functions in the heterogeneous setting; moreover, no polynomial-time algorithm can achieve a ratio better than \(1-\nicefrac{1}{e}\) unless \(\text{P}=\text{NP}\). Centralized strategies can exploit correlations to reduce redundancy. We develop a hierarchy of approximation factors: for any positive integer \(r'\le r\), writing \(r=hr'+b\) with \(0\le b

Authors: Walid Ben-Ameur, Tijani Chahed, Shamisa Nematollahi

We study a stochastic multi-robot monitoring problem on a connected graph $G=(V,E)$, where each robot moves according to a Markov chain on $G$ and monitors the closed neighborhood of its current vertex. The performance of $r$ robots is evaluated in steady state via two objectives: average-case coverage (the expected number of covered vertices) and worst-case coverage (the minimum coverage probability over all vertices). We consider three models: independent homogeneous strategies, where all robots share the same stationary distribution; independent heterogeneous strategies, where robots use different stationary distributions; and centralized strategies, allowing arbitrary correlations between robot locations. For the heterogeneous model, we prove that maximizing average coverage is NP-hard even for two robots, and that replicating an easy-to-compute optimal homogeneous strategy yields a \(\left(1-\left(1-\frac{1}{r}\right)^r\right)\)-approximation for both objective functions in the heterogeneous setting; moreover, no polynomial-time algorithm can achieve a ratio better than \(1-\nicefrac{1}{e}\) unless \(\text{P}=\text{NP}\). Centralized strategies can exploit correlations to reduce redundancy. We develop a hierarchy of approximation factors: for any positive integer \(r'\le r\), writing \(r=hr'+b\) with \(0\le b

Sublinear Algorithms for Estimating the Number of Hyperedges in Arbitrary Hypergraphs

from arXiv: Data Structures and Algorithms

Authors: Deeparnab Chakrabarty, Cooper LaPorte, C. Seshadhri

We study the problem of estimating the number of hyperedges in an arbitrary $n$-vertex hypergraph using sublinear in $n$ queries. Note that the number of hyperedges, $m$, can be exponential in $n$. For $k$-uniform hypergraphs, estimating $m$ is equivalent to estimating the average vertex degree, a problem studied in Barhum's Master's thesis (Weizmann Inst., 2007) under the standard access model of sampling random vertices, querying vertex degrees, and accessing incident hyperedges. Barhum's techniques do not extend to arbitrary hypergraphs, and simple lower-bound examples show that the standard access model cannot yield strongly sublinear algorithms when hyperedges have unbounded size. To obtain non-trivial sublinear bounds, we consider a natural generalization of the access model called the \emph{dual access model}, which allows sampling (labels of) random hyperedges, querying edge sizes, and accessing vertices in a hyperedge. In this model, we give a randomized algorithm that returns a $(1+\varepsilon)$-approximation to $m$ with high probability, making $O(\varepsilon^{-2}\sqrt{n} + \sqrt{n}\log n)$ queries. Complementing our algorithm, we prove a nearly matching lower bound showing that $Ω(\sqrt{n})$ queries are necessary for any algorithm that obtains a constant factor approximation to $m$.

Authors: Deeparnab Chakrabarty, Cooper LaPorte, C. Seshadhri

We study the problem of estimating the number of hyperedges in an arbitrary $n$-vertex hypergraph using sublinear in $n$ queries. Note that the number of hyperedges, $m$, can be exponential in $n$. For $k$-uniform hypergraphs, estimating $m$ is equivalent to estimating the average vertex degree, a problem studied in Barhum's Master's thesis (Weizmann Inst., 2007) under the standard access model of sampling random vertices, querying vertex degrees, and accessing incident hyperedges. Barhum's techniques do not extend to arbitrary hypergraphs, and simple lower-bound examples show that the standard access model cannot yield strongly sublinear algorithms when hyperedges have unbounded size. To obtain non-trivial sublinear bounds, we consider a natural generalization of the access model called the \emph{dual access model}, which allows sampling (labels of) random hyperedges, querying edge sizes, and accessing vertices in a hyperedge. In this model, we give a randomized algorithm that returns a $(1+\varepsilon)$-approximation to $m$ with high probability, making $O(\varepsilon^{-2}\sqrt{n} + \sqrt{n}\log n)$ queries. Complementing our algorithm, we prove a nearly matching lower bound showing that $Ω(\sqrt{n})$ queries are necessary for any algorithm that obtains a constant factor approximation to $m$.

Sunday, August 23

Research Fellow at MATS (apply by September 6, 2026)

from CCI: jobs
MATS Winter 2027 is a fully funded, 12-week AI safety research and field-building fellowship in Berkeley and London, with seven tracks, mentorship from researchers at Anthropic, Google DeepMind, OpenAI and more, a $6,400/month stipend, up to $16,000/month for technical participants, and housing, meals, travel and office space covered. Website: www.matsprogram.org/apply?utm_source=cstheory-jobs&utm_medium=job-board&utm_campaign=w27 Email: applications@matsprogram.org

MATS Winter 2027 is a fully funded, 12-week AI safety research and field-building fellowship in Berkeley and London, with seven tracks, mentorship from researchers at Anthropic, Google DeepMind, OpenAI and more, a $6,400/month stipend, up to $16,000/month for technical participants, and housing, meals, travel and office space covered.

Website: https://www.matsprogram.org/apply?utm_source=cstheory-jobs&utm_medium=job-board&utm_campaign=w27
Email: applications@matsprogram.org

By shacharlovett

Saturday, August 22

Anthropic’s LLM watermarking

from Scott Aaronson
So yeah, Anthropic has announced that it’s now watermarking the outputs of Claude, using a scheme based on Google’s SynthID, which is in turn based on the Gumbel Softmax scheme that I proposed at OpenAI back in 2022—as far as I know, the first LLM watermarking proposal, though far from the last one. I’m gratified […]

So yeah, Anthropic has announced that it’s now watermarking the outputs of Claude, using a scheme based on Google’s SynthID, which is in turn based on the Gumbel Softmax scheme that I proposed at OpenAI back in 2022—as far as I know, the first LLM watermarking proposal, though far from the last one. I’m gratified that Anthropic credits me for this, even though I shirked my duty by never publishing a paper about it (by the time I sat down to write one, it seemed like the whole field had already assimilated my scheme and moved beyond it—AI just moves too fast for me!).

For those who don’t know, watermarking means slightly changing the way that an LLM operates to insert a subtle signal that lets you prove later, with high statistical confidence, that a text indeed came from your specific LLM. It uses the randomness that’s already present anyway in LLM outputs, replacing some of it by pseudorandomness that favors certain word combinations over others in a way that’s later detectable, given only the sequence of tokens itself (not the prompt or the probabilities) along with the key of the pseudorandom generator. Christ, Gunn, and Zamir then substantially improved my scheme to get true cryptographic indistinguishability, and there have been other improvements since.

I’d been meaning to blog about this for days. Thankfully, Zvi Mowshowitz, the world’s foremost blogger about AI, has now written a wonderful post, entitled AI Text Watermarking Is Free And Good, which saves me from the need to write my own long post. In particular, Zvi masterfully explains the central point that I needed to explain to everyone back in 2022-23: why, contrary to many people’s intuitions, there’s no inherent tradeoff between watermarking and the quality of LLM output. Basically, nearly every LLM output was already a sample from a cloud of exponentially many possibilities, all of them about equally good, so there’s plenty of room to steer within that cloud without affecting anything that an ordinary user would notice. As my kids would put it, the math mathes.

As Zvi explains, the central technical drawback of watermarking schemes like the one I proposed, and what Anthropic is now using, is that it’s possible to remove the watermarks with a little extra work (even stuff as simple as, e.g., translating between English and French, asking the LLM for words interspersed with emojis and then removing the emojis, or using an open model to paraphrase the output). Zvi gives detailed arguments for why he expects watermarking to remain a net positive in practice despite this vulnerability.

I could add that, in addition, there’s recent progress (see here for example) on what I’ve called “semantic watermarking,” or watermarking at the level of the underlying concept vectors rather than the tokens themselves. This actually seems to work, albeit with no theoretical guarantees, and will hopefully make removing watermarks a lot harder—although the Barak et al. impossibility result suggests that under plausible assumptions, no LLM watermarking method will be completely foolproof.

Anyway, I worked out my scheme in Fall 2022, then gave lots of talks about it (including, as it happens, at Anthropic), and also worked with Hendrik Kirchner at OpenAI, who actually implemented and tested my scheme. Unfortunately, OpenAI leadership decided against deploying watermarking, worried mostly about risks to the product (i.e., customers disliking the idea, and leaving for a competing LLM that doesn’t watermark). You can read this Wall Street Journal investigation from two years ago for more. I was hopeful that the State of California was going to solve the collective-action problem by mandating watermarking for AI models, but then they decided to do that for audiovisual content only, for some reason exempting text.

Nevertheless, Google DeepMind implemented something very similar to my proposal in its SynthID, deployed in all its Gemini text models. But they heavily restricted who gets to detect the watermark, which made their admirable decision of limited use to my academic colleagues, who’ve been begging me for a way to detect whether their students are using AI to cheat. (For now, I mainly send them to Pangram, a leading AI detector not based on watermarking, as a first line of defense.)

And now, apparently to comply with EU regulations, Anthropic says they’ve deployed a watermarking scheme like mine where anyone will be able to do detection (though they also say in their FAQ that they’re still working on the detection API). Even OpenAI suggests that it plans to follow suit. So, four years after I seriously thought about this, it looks to my surprise like this is actually happening. Thanks, EU!

Tell you what: read Zvi’s post, and then whatever questions you still have, you can come here and ask in the comments. Just please don’t use Claude to write the comments. With any luck, I’ll eventually be able catch you if you do.

By Scott

TR26-153 | Blocky Matrices and Group Idempotents | Gaia Carenini

from ECCC Papers
We prove a common generalization of two structure theorems: the dimension-free decomposition theorem for idempotent Schur multipliers and the idempotent theorem in harmonic analysis. Roughly speaking, our result shows that an invariant integer-valued kernel with Hilbert-space factorization norm $\gamma$ admits a signed decomposition into at most $2^{O(\gamma^4)}$ elementary pieces. In the matrix setting these pieces are blocky matrices, while in the group setting they are indicators of cosets. In the locally compact abelian setting this quantitatively strengthens the theorem of Green and Sanders, while in the non-abelian setting it gives a quantitative strengthening of Host's idempotent theorem and, for finite groups, of Sanders's quantitative result. It also improves the exponent in the dimension-free matrix decomposition from $\gamma^6$ to $\gamma^4$.
We prove a common generalization of two structure theorems: the dimension-free decomposition theorem for idempotent Schur multipliers and the idempotent theorem in harmonic analysis. Roughly speaking, our result shows that an invariant integer-valued kernel with Hilbert-space factorization norm $\gamma$ admits a signed decomposition into at most $2^{O(\gamma^4)}$ elementary pieces. In the matrix setting these pieces are blocky matrices, while in the group setting they are indicators of cosets. In the locally compact abelian setting this quantitatively strengthens the theorem of Green and Sanders, while in the non-abelian setting it gives a quantitative strengthening of Host's idempotent theorem and, for finite groups, of Sanders's quantitative result. It also improves the exponent in the dimension-free matrix decomposition from $\gamma^6$ to $\gamma^4$.

Friday, August 21

TR26-152 | Low-Degree Testing Over Boolean Slices | Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan, Madhu Sudan, Sophus Valentin Willumsgaard

from ECCC Papers
We study low-degree testing for group-valued functions over a Boolean slice. Specifically given a degree parameter $d$ and oracle access to a function $f:\{0,1\}^n_{n/2} \to G$ where $\{0,1\}^n_k$ denotes the set of vectors in $\{0,1\}^n$ of Hamming weight $k$ and $G$ is an Abelian group (not necessarily finite), the low-degree testing problem asks us to distinguish the case where $f$ is a polynomial of degree at most $d$ (with coefficients from $G$) or is $\varepsilon$-far from the set of all such polynomials. Classical works in this area considered functions with domain $\mathbb{F}_q^n$ and range $\mathbb{F}_q$. More recent works have considered the setting where the domain is the Boolean cube [Bafna, Srinivasan, Sudan (Random Structures and Algorithms 2020), Amireddy, Srinivasan, Sudan (RANDOM 2023)], or when the domain is the slice (i.e., $\{0,1\}^n_{k}$) and the range is $\mathbb{F}_2$ [David, Dinur, Goldenberg, Kindler and Shinkar (SIAM Journal on Computing 2017), Kalai, Lifshitz, Minzer and Ziegler (FOCS 2024)]. Each of the changes introduces new challenges in designing and analyzing low-degree tests and this happens again in our setting with domain being a slice and range is general. Indeed the previous methods fail even when the domain is a Boolean slice and the range is $\mathbb{F}_3$. Our main theorem gives a test that makes $O_d(1)$ (specifically $\exp(d^{O(1)})$) queries to $f$ and accepts degree-$d$ functions while rejecting functions that are $\varepsilon$-far with probability $\Omega(\varepsilon)$. The central proof idea is to reduce this low-degree testing problem to the problem of low-degree testing on the cube. Specifically we show how to randomly embed the $n/2$-dimensional cube $\{0,1\}^{n/2}$ in the $n$-dimensional slice while nearly preserving the proximity of $f$ to the space of degree-$d$ polynomials on this cube (with high probability). While the embedding is simple and natural, the analysis involves a careful induction (seen in some prior works on low-degree testing) with a novel use of a basis of degree-$d$ polynomials on slices (from a work of Anstee, Rónyai and Sali (Graphs and Combinatorics 2002)). Such a basis of functions is non-trivial and has several nice combinatorial and algebraic closure properties. We show how these properties are useful by using them to analyze our low-degree tests.
We study low-degree testing for group-valued functions over a Boolean slice. Specifically given a degree parameter $d$ and oracle access to a function $f:\{0,1\}^n_{n/2} \to G$ where $\{0,1\}^n_k$ denotes the set of vectors in $\{0,1\}^n$ of Hamming weight $k$ and $G$ is an Abelian group (not necessarily finite), the low-degree testing problem asks us to distinguish the case where $f$ is a polynomial of degree at most $d$ (with coefficients from $G$) or is $\varepsilon$-far from the set of all such polynomials. Classical works in this area considered functions with domain $\mathbb{F}_q^n$ and range $\mathbb{F}_q$. More recent works have considered the setting where the domain is the Boolean cube [Bafna, Srinivasan, Sudan (Random Structures and Algorithms 2020), Amireddy, Srinivasan, Sudan (RANDOM 2023)], or when the domain is the slice (i.e., $\{0,1\}^n_{k}$) and the range is $\mathbb{F}_2$ [David, Dinur, Goldenberg, Kindler and Shinkar (SIAM Journal on Computing 2017), Kalai, Lifshitz, Minzer and Ziegler (FOCS 2024)]. Each of the changes introduces new challenges in designing and analyzing low-degree tests and this happens again in our setting with domain being a slice and range is general. Indeed the previous methods fail even when the domain is a Boolean slice and the range is $\mathbb{F}_3$. Our main theorem gives a test that makes $O_d(1)$ (specifically $\exp(d^{O(1)})$) queries to $f$ and accepts degree-$d$ functions while rejecting functions that are $\varepsilon$-far with probability $\Omega(\varepsilon)$. The central proof idea is to reduce this low-degree testing problem to the problem of low-degree testing on the cube. Specifically we show how to randomly embed the $n/2$-dimensional cube $\{0,1\}^{n/2}$ in the $n$-dimensional slice while nearly preserving the proximity of $f$ to the space of degree-$d$ polynomials on this cube (with high probability). While the embedding is simple and natural, the analysis involves a careful induction (seen in some prior works on low-degree testing) with a novel use of a basis of degree-$d$ polynomials on slices (from a work of Anstee, Rónyai and Sali (Graphs and Combinatorics 2002)). Such a basis of functions is non-trivial and has several nice combinatorial and algebraic closure properties. We show how these properties are useful by using them to analyze our low-degree tests.

Interview with Krishnendu Chatterjee, Tom Henzinger and Nir Piterman, CONCUR 2026 ToT Award recipients

from Luca Aceto

Krishnendu Chatterjee, Thomas Henzinger and Nir Piterman will receive one of the two CONCUR 2026 Test-of-Time Awards at CONCUR 2026. Those colleagues kindly agreed to answer some questions of mine on their award-winning paper via email. You can find their answers to my questions below. I hope you'll enjoy reading them as much as I did. Thanks, Krishnendu, Nir and Tom!


Luca: You receive the CONCUR ToT Award 2026 for your paper Strategy Logic, which appeared at CONCUR 2007 and, in archival form, in Information and Computation. In that article, you introduced a seminal logic for expressing properties of strategies over two-player games on graphs.  Could you briefly explain to our readers what the main features of strategy logic are? Could you also tell us how you came to study the question addressed in your award-winning article? Which of the results in your paper did you find most surprising or challenging?

Krishnendu, Nir and Tom (henceforth abbreviated to KNT): The defining feature of Strategy Logic is that it treats strategies as explicit, first-class objects: strategies are named by variables, and the logic can quantify over them. Our main motivation was to express central concepts from game theory, such as equilibria, within a logical framework for games on graphs. As for the results, what we find most appealing is that a logic this expressive still admits decidability, and that several natural fragments come with clean and reasonable computational complexity. Establishing these decidability and complexity results for various fragments was also the most technically challenging part of the work.

Luca: With the benefit of hindsight, having a logic to describe properties of games that treats strategies as first-class objects sounds like an extremely natural idea. However, previous logics such as ATL, ATL*, the alternating-time µ-calculus  and game logic followed a different path. Do you recall how you came to the realisation that treating strategies explicitly was the "way to go"?

KNT: One of the key application areas for graph games has been reactive synthesis, and until 2004 reactive synthesis was studied primarily as an adversarial game. Hence logics such as ATL, ATL*, alternating-time µ-calculus, and game logic, all focus on strictly competitive or cooperative behaviors of game theory. Around 2004-2005, we started working on connections between algorithmic game theory and graph games. As a consequence we considered aspects of Nash equilibria and other not strictly competitive notions of game theory (such as secure equilibria) in graph games. A natural question was to build a logical framework that can express these aspects of game theory, which led to Strategy Logic. In fact we first isolated the one-alternation fragment, which suffices to express these equilibria, and only afterwards arrived at the full, more expressive logic. In hindsight, the shift to treating strategies explicitly was driven by the questions we were asking rather than by a single eureka moment.

Luca: Strategy logic builds on LTL, which is a very natural choice, IMHO. Did you consider defining a version of strategy logic basing it on the (linear-time) modal μ--calculus? Would it be worth doing so and how would such a logic relate to the alternating-time μ-calculus?

KNT: There is always a tension between LTL and stronger formalisms that can recognize all ω-regular languages. Following the tradition of ATL and ATL*, we naturally chose to go with LTL for defining the (linear-time) objectives of players. As the techniques that we developed were automata based, it was clear that extensions of LTL that can express all ω-regular languages would be handled by the same techniques. The exact choice of the linear-time formalism (for example, ETL, QLTL, LDL, or the linear-time μ-calculus) is not very important as long as it can be readily translated to automata. In the alternating-time μ-calculus, however, by carefully nesting fixpoints and coalition quantification, we can define infinitely many changes of strategic context. But only in a completely adversarial manner.

Luca: As you are hinting, in your paper, amongst other results, you showed that the alternating-time μ-calculus and strategy logic have incomparable expressive power. Would a fixed-point version of strategy logic, based on the modal μ-calculus, be a way of achieving a logic that offers the "best of both worlds" while maintaining some of the good computational properties of strategy logic? Has anyone worked on such a logic?

KNT: We did not consider such a version of Strategy Logic. Intuitively, both classical and alternating-time μ-calculi combine local, single-transition branching operators such as Pre with fixpoint operators, whereas strategies express global behavioral choices and the objectives of players are defined on outcomes that are linear paths. An important expressive difference between the alternating-time μ-calculus and Strategy Logic is therefore due to the distinction between branching and linear time. 
It seems interesting to consider a logic that would combine two types of pre operators: those that continue exploring pre-defined strategies and their induced behaviors and those that allow to change the strategic context starting a new behavioral exploration. But we believe that the techniques that handle alternating-time mu-calculus would work for such a logic and the mix of behavior and control might be very hard to understand.

Luca: Did you or anyone else ever implement the model-checking algorithms you present in your award-winning paper? If the answer is negative, do you think that there would still be interest in such a model checker and in its experimental evaluation?

KNT: As far as we know there is no full implementation of Strategy Logic. In general, we have very good implementations supporting the manipulation and analysis of automata on infinite words (such as Spot and Owl). They are also used as a basis for creating tools that solve reactive synthesis. But we do not have good tool support for using automata on infinite trees, which would be required in order to fully support Strategy Logic. The community studying Multi-Agent Systems adopted Strategy Logic and they have some support for the analysis of some questions. There are implementations of equilibrium checking and rational synthesis in the tool Eve that is developed in the group of Michael Wooldridge in Oxford. They support the analysis of concurrent game structures for such questions. There is also a restricted version of an epistemic extension of Strategy Logic that is included in the model checker MCMAS for Multi-Agent Systems, which was developed in the group of Alessio Lumoscio in Imperial College London. 
MCMAS also supports ATL model checking and, in principle, it is possible to reduce the one-alternation fragment of Strategy Logic to ATL model checking, but we are not aware of this having been implemented.

Luca: You mentioned the uptake of strategy logic by the multi-agent systems community. How is strategy logic relevant and did you think that this work would be relevant to multi-agent systems?

KNT: Strategy Logic answered a natural need in Multi-Agent Systems research. For MAS, questions about the goals of agents and hence strategies are very natural. Many questions relate to rational behavior: whether agents have an incentive to follow a protocol, stability of behavior, what can coalitions do, and whether individuals can profitably deviate. The way Strategy Logic puts strategies in the center as explicit objects makes it very natural to study these questions. 
We wouldn’t say that we saw it coming, but the signs of early adoption of strategic reasoning by the MAS community were already there. The uptake of ATL and ATL* started in the early 2000s and by 2004-2005 people were using it regularly. We are also very happy that some of the major developments of Strategy Logic came from this community.

Luca: Are there any problems that you left open in your award-winning article that you'd still love to see solved? Did you or any colleagues study the problem of "strategy synthesis"?

KNT: Definitely. For the complete logic, our paper established only a non-elementary upper bound and left the matching lower bound open. This gap was later closed by colleagues, who proved a matching non-elementary lower bound and thereby settled the computational complexity of the full logic. We also concentrated on the case of two-player games rather than multi-player games. The interaction between the logic and the game structure means that the two-player framework, in a sense, already captures the complexity of the logic. Indeed, the same techniques based on tree automata were later used by others to extend the logic to the multi-player setting (and concurrent game structures).

Luca: I am interested in how research collaborations start, as I like to tell "research-life stories" to PhD students and young researchers of all ages. Could you tell us how you started your collaboration on the award-winning paper?

KNT: The collaboration grew naturally out of a question from Tom (Thomas Henzinger): could notions such as the equilibria we had been studying be expressed in ATL or ATL*, and if not, what would be a natural and concise logic that could express them? Pursuing this led us to the one-alternation fragment. We then realized that strategies can be viewed as trees, which meant tree automata were the right tool — and Nir (Nir Piterman) was our automata expert. So the paper really came together at the meeting point of three ingredients: the study of non-zero-sum games, the wish for a logical framework to express their concepts, and tree-automata techniques.

Luca: How did the results and the techniques you developed in your award-winning paper influence your subsequent research? Is there any result obtained by other researchers that builds on your work and that you like in particular?

KNT: The result had a lasting influence. The interplay between games and automata that we exploited in the paper fed directly into later lines of work. e.g., from the connection of games and automata the notion of good-for-games (a.k.a. history-deterministic) automata emerged. Among the results by others that build on Strategy Logic, the matching non-elementary lower bound and the work on special classes of strategies — such as the distinction between behavioral and non-behavioral strategies — are very elegant.

Luca:  To my mind, games on graphs ought to be viewed as one of the unifying themes within TCS, bridging the Volume A-Volume B divide, and I am happy to see that there is a book-length treatment covering the subject now. What is your view on this matter?  What impact do you think that your work has had, if any, on the community working on algorithmic game theory, broadly construed? (I am reminded of the slides for a, typically thought-provoking, talk delivered by Moshe Vardi.) What has our community learnt from the work done in the field of computational game theory? And what, if anything, did they learn from the work done within the concurrency theory community?

KNT: Indeed, games on graphs is one of the unifying themes between Volume A and Volume B: it connects with logic and automata theory from Vol. B, and it connects with the notion of alternation from complexity theory and graph algorithms from Vol. A. The inflow of ideas from algorithmic game theory, or game theory in general, is a key source of ideas in this work, e.g., to express equilibria in a logical framework. Other notions of equilibria have also been studied in the context of reactive synthesis (e.g., rational synthesis), and Vol. B researchers have explored many concepts from general game theory beyond strictly competitive games. The broad area of algorithmic game theory also benefited from logical reasoning grounded in concurrency theory, e.g., Strategy Logic is the key logic for reasoning about behaviors in Multi-Agent Systems, and axiomatic characterizations for reasoning about strategy spaces have been influential in evolutionary game theory. There is also work using Strategy Logic in mechanism design.

Luca: What are the research topics related to logics for games on graphs that you find most interesting right now?

KNT: We can think of several interesting open questions: (i) the relationship between games and automata through the lens of history-determinism and similar concepts is an exciting direction; (ii) algorithmic bounds for several fundamental problems remain open, e.g., a polynomial-time algorithm for parity games; (iii) the degree to which sources of randomness can be shared between different players is an active area of research in concurrent games; and (iv) the study of computationally efficient logics which lie between ATL* and Strategy Logic is also under-explored.

Luca: What advice would you give to a young researcher who is keen to start working on topics related to logics for games and other computational problems related to games?

KNT: The rapid progress in AI makes this question a difficult one. We believe that formal methods in general will become a central part of computing, more than they have ever been, because AI-generated software needs checks even more than software written by humans, but even more so, because modern AI can, for the first time, provide or at least support such checks on a scale that was hitherto impossible. Formal checks do not necessarily have to take the form of, say, Lean proofs, but they could also include state-based reasoning involving automata and games. It is always difficult to predict the future, but finding the right place for our field in this future seems a uniquely exciting opportunity.

By Luca Aceto

Krishnendu Chatterjee, Thomas Henzinger and Nir Piterman will receive one of the two CONCUR 2026 Test-of-Time Awards at CONCUR 2026. Those colleagues kindly agreed to answer some questions of mine on their award-winning paper via email. You can find their answers to my questions below. I hope you'll enjoy reading them as much as I did. Thanks, Krishnendu, Nir and Tom!


Luca: You receive the CONCUR ToT Award 2026 for your paper Strategy Logic, which appeared at CONCUR 2007 and, in archival form, in Information and Computation. In that article, you introduced a seminal logic for expressing properties of strategies over two-player games on graphs.  Could you briefly explain to our readers what the main features of strategy logic are? Could you also tell us how you came to study the question addressed in your award-winning article? Which of the results in your paper did you find most surprising or challenging?

Krishnendu, Nir and Tom (henceforth abbreviated to KNT): The defining feature of Strategy Logic is that it treats strategies as explicit, first-class objects: strategies are named by variables, and the logic can quantify over them. Our main motivation was to express central concepts from game theory, such as equilibria, within a logical framework for games on graphs. As for the results, what we find most appealing is that a logic this expressive still admits decidability, and that several natural fragments come with clean and reasonable computational complexity. Establishing these decidability and complexity results for various fragments was also the most technically challenging part of the work.

Luca: With the benefit of hindsight, having a logic to describe properties of games that treats strategies as first-class objects sounds like an extremely natural idea. However, previous logics such as ATL, ATL*, the alternating-time µ-calculus  and game logic followed a different path. Do you recall how you came to the realisation that treating strategies explicitly was the "way to go"?

KNT: One of the key application areas for graph games has been reactive synthesis, and until 2004 reactive synthesis was studied primarily as an adversarial game. Hence logics such as ATL, ATL*, alternating-time µ-calculus, and game logic, all focus on strictly competitive or cooperative behaviors of game theory. Around 2004-2005, we started working on connections between algorithmic game theory and graph games. As a consequence we considered aspects of Nash equilibria and other not strictly competitive notions of game theory (such as secure equilibria) in graph games. A natural question was to build a logical framework that can express these aspects of game theory, which led to Strategy Logic. In fact we first isolated the one-alternation fragment, which suffices to express these equilibria, and only afterwards arrived at the full, more expressive logic. In hindsight, the shift to treating strategies explicitly was driven by the questions we were asking rather than by a single eureka moment.

Luca: Strategy logic builds on LTL, which is a very natural choice, IMHO. Did you consider defining a version of strategy logic basing it on the (linear-time) modal μ--calculus? Would it be worth doing so and how would such a logic relate to the alternating-time μ-calculus?

KNT: There is always a tension between LTL and stronger formalisms that can recognize all ω-regular languages. Following the tradition of ATL and ATL*, we naturally chose to go with LTL for defining the (linear-time) objectives of players. As the techniques that we developed were automata based, it was clear that extensions of LTL that can express all ω-regular languages would be handled by the same techniques. The exact choice of the linear-time formalism (for example, ETL, QLTL, LDL, or the linear-time μ-calculus) is not very important as long as it can be readily translated to automata. In the alternating-time μ-calculus, however, by carefully nesting fixpoints and coalition quantification, we can define infinitely many changes of strategic context. But only in a completely adversarial manner.

Luca: As you are hinting, in your paper, amongst other results, you showed that the alternating-time μ-calculus and strategy logic have incomparable expressive power. Would a fixed-point version of strategy logic, based on the modal μ-calculus, be a way of achieving a logic that offers the "best of both worlds" while maintaining some of the good computational properties of strategy logic? Has anyone worked on such a logic?

KNT: We did not consider such a version of Strategy Logic. Intuitively, both classical and alternating-time μ-calculi combine local, single-transition branching operators such as Pre with fixpoint operators, whereas strategies express global behavioral choices and the objectives of players are defined on outcomes that are linear paths. An important expressive difference between the alternating-time μ-calculus and Strategy Logic is therefore due to the distinction between branching and linear time.
 
It seems interesting to consider a logic that would combine two types of pre operators: those that continue exploring pre-defined strategies and their induced behaviors and those that allow to change the strategic context starting a new behavioral exploration. But we believe that the techniques that handle alternating-time mu-calculus would work for such a logic and the mix of behavior and control might be very hard to understand.

Luca: Did you or anyone else ever implement the model-checking algorithms you present in your award-winning paper? If the answer is negative, do you think that there would still be interest in such a model checker and in its experimental evaluation?

KNT: As far as we know there is no full implementation of Strategy Logic. In general, we have very good implementations supporting the manipulation and analysis of automata on infinite words (such as Spot and Owl). They are also used as a basis for creating tools that solve reactive synthesis. But we do not have good tool support for using automata on infinite trees, which would be required in order to fully support Strategy Logic. The community studying Multi-Agent Systems adopted Strategy Logic and they have some support for the analysis of some questions. There are implementations of equilibrium checking and rational synthesis in the tool Eve that is developed in the group of Michael Wooldridge in Oxford. They support the analysis of concurrent game structures for such questions. There is also a restricted version of an epistemic extension of Strategy Logic that is included in the model checker MCMAS for Multi-Agent Systems, which was developed in the group of Alessio Lumoscio in Imperial College London.
 
MCMAS also supports ATL model checking and, in principle, it is possible to reduce the one-alternation fragment of Strategy Logic to ATL model checking, but we are not aware of this having been implemented.

Luca: You mentioned the uptake of strategy logic by the multi-agent systems community. How is strategy logic relevant and did you think that this work would be relevant to multi-agent systems?

KNT: Strategy Logic answered a natural need in Multi-Agent Systems research. For MAS, questions about the goals of agents and hence strategies are very natural. Many questions relate to rational behavior: whether agents have an incentive to follow a protocol, stability of behavior, what can coalitions do, and whether individuals can profitably deviate. The way Strategy Logic puts strategies in the center as explicit objects makes it very natural to study these questions.
 
We wouldn’t say that we saw it coming, but the signs of early adoption of strategic reasoning by the MAS community were already there. The uptake of ATL and ATL* started in the early 2000s and by 2004-2005 people were using it regularly. We are also very happy that some of the major developments of Strategy Logic came from this community.

Luca: Are there any problems that you left open in your award-winning article that you'd still love to see solved? Did you or any colleagues study the problem of "strategy synthesis"?

KNT: Definitely. For the complete logic, our paper established only a non-elementary upper bound and left the matching lower bound open. This gap was later closed by colleagues, who proved a matching non-elementary lower bound and thereby settled the computational complexity of the full logic. We also concentrated on the case of two-player games rather than multi-player games. The interaction between the logic and the game structure means that the two-player framework, in a sense, already captures the complexity of the logic. Indeed, the same techniques based on tree automata were later used by others to extend the logic to the multi-player setting (and concurrent game structures).

Luca: I am interested in how research collaborations start, as I like to tell "research-life stories" to PhD students and young researchers of all ages. Could you tell us how you started your collaboration on the award-winning paper?

KNT: The collaboration grew naturally out of a question from Tom (Thomas Henzinger): could notions such as the equilibria we had been studying be expressed in ATL or ATL*, and if not, what would be a natural and concise logic that could express them? Pursuing this led us to the one-alternation fragment. We then realized that strategies can be viewed as trees, which meant tree automata were the right tool — and Nir (Nir Piterman) was our automata expert. So the paper really came together at the meeting point of three ingredients: the study of non-zero-sum games, the wish for a logical framework to express their concepts, and tree-automata techniques.

Luca: How did the results and the techniques you developed in your award-winning paper influence your subsequent research? Is there any result obtained by other researchers that builds on your work and that you like in particular?

KNT: The result had a lasting influence. The interplay between games and automata that we exploited in the paper fed directly into later lines of work. e.g., from the connection of games and automata the notion of good-for-games (a.k.a. history-deterministic) automata emerged. Among the results by others that build on Strategy Logic, the matching non-elementary lower bound and the work on special classes of strategies — such as the distinction between behavioral and non-behavioral strategies — are very elegant.

Luca:  To my mind, games on graphs ought to be viewed as one of the unifying themes within TCS, bridging the Volume A-Volume B divide, and I am happy to see that there is a book-length treatment covering the subject now. What is your view on this matter?  What impact do you think that your work has had, if any, on the community working on algorithmic game theory, broadly construed? (I am reminded of the slides for a, typically thought-provoking, talk delivered by Moshe Vardi.) What has our community learnt from the work done in the field of computational game theory? And what, if anything, did they learn from the work done within the concurrency theory community?

KNT: Indeed, games on graphs is one of the unifying themes between Volume A and Volume B: it connects with logic and automata theory from Vol. B, and it connects with the notion of alternation from complexity theory and graph algorithms from Vol. A. The inflow of ideas from algorithmic game theory, or game theory in general, is a key source of ideas in this work, e.g., to express equilibria in a logical framework. Other notions of equilibria have also been studied in the context of reactive synthesis (e.g., rational synthesis), and Vol. B researchers have explored many concepts from general game theory beyond strictly competitive games. The broad area of algorithmic game theory also benefited from logical reasoning grounded in concurrency theory, e.g., Strategy Logic is the key logic for reasoning about behaviors in Multi-Agent Systems, and axiomatic characterizations for reasoning about strategy spaces have been influential in evolutionary game theory. There is also work using Strategy Logic in mechanism design.

Luca: What are the research topics related to logics for games on graphs that you find most interesting right now?

KNT: We can think of several interesting open questions: (i) the relationship between games and automata through the lens of history-determinism and similar concepts is an exciting direction; (ii) algorithmic bounds for several fundamental problems remain open, e.g., a polynomial-time algorithm for parity games; (iii) the degree to which sources of randomness can be shared between different players is an active area of research in concurrent games; and (iv) the study of computationally efficient logics which lie between ATL* and Strategy Logic is also under-explored.

Luca: What advice would you give to a young researcher who is keen to start working on topics related to logics for games and other computational problems related to games?

KNT: The rapid progress in AI makes this question a difficult one. We believe that formal methods in general will become a central part of computing, more than they have ever been, because AI-generated software needs checks even more than software written by humans, but even more so, because modern AI can, for the first time, provide or at least support such checks on a scale that was hitherto impossible. Formal checks do not necessarily have to take the form of, say, Lean proofs, but they could also include state-based reasoning involving automata and games. It is always difficult to predict the future, but finding the right place for our field in this future seems a uniquely exciting opportunity.

By Luca Aceto

Runbooks for Microconferences

from Ben Recht
A few fun ideas on how to organize, implement, and archive your microconference.

Thanks to everyone for the constructive feedback on Monday’s microconferences post. I wanted to take a beat to engage with two salient themes in the replies: runbooks and homophily. I’ll start with runbooks today, and tackle homophily next week.

No two microconferences are alike, and we shouldn’t impose hard-and-fast rules on their structure. One of the fun things about small conferences is you can tailor them to particular goals and dreams. And there are so many ways to do this well.

However, I think it will be useful to compile a runbook of agreements, strategies, and rules that you can use to help modularly assemble your ideal microconference. Today, I’ll run down a bunch of disorganized examples. You tell me your favorite ideas in the comments. I’ll assemble these more coherently into a document that I’ll widely share.

We can learn a lot from existing institutions, and many people spoke fondly of places I should have shouted out in the first post, e.g., BIRS, Oberwolfach, Dagstuhl.1 I also adore the quirkiness of the American Institute of Mathematics, which has a very particular and very fun way to run a microconference, disallowing canned and prepared talks.2 I am inspired by unconferences that bring together dozens of people to spontaneously generate many microconferences. All of their best practices should be part of the runbook.

I’ve found an easy model for microconferences is a bundle of short, 5-10 minute talks with adjoined group discussions led by the speakers. The past four microconferences I’ve attended have run this way. Short talks are fun because they force people to think hard about messaging and concision, and lead to a lot of interesting back-and-forth with the right serendipitous assignments. I was somewhat randomly assigned to a panel with Dan Wang and Dan Davies on cybernetics, and it was probably the most fun and rewarding 90 minutes I’ve ever had at a conference. That single brief session reshaped the narrative arc of The Irrational Decision.

Johan Ugander raised several good ideas in his comment. About archiving and proceedings, he wrote: “The non-proceedings nature of workshops is key to drawing in a diverse set of people.” I agree. We should think broadly about what should count as “proceedings” or “archiving.” I liked Johan’s suggestion of simply inviting participants to submit to a special issue. You could consider this series of blogs ([1], [2], [3], [4]) and this youtube video the “proceedings” of the Cultural AI workshop organized by Leif Weatherby and Tyler Shoemaker this spring. I just want to suggest that we explore creative ways to archive, evaluate, and credit microconferences in the broader academic ecosystem. I’d add to my list of core microconference values that “archiving should encourage, not discourage dissemination and broader engagement.”

As Johan wrote:

“ACM EC has a forward-to-journal mechanism, which gets Computer Science, Operations Research, and Economics folks together for a coherent conference but lets them still go harvest their respective tokens. The EC reviews get passed to the journal. And EC also organizes a ‘Highlights beyond EC’ session, which lets people request to present work recently/already published “elsewhere” but relevant to the community. Both of these mechanisms help keep the ‘conference’ and ‘publication’ goals separate.”

Endorsed!

Anna Gilbert raised the idea of “bump sessions”:

“The Dagstuhl and Oberwolfach type conferences in TCS used to also have “bump sessions” (maybe they were called rump!) where people proposed open problems, noodled over difficulties, etc. Sometimes these micro workshops even “published” open problems from these bump sessions. They were quite useful and engaging!”

Anna also raised one of my favorite ideas, which I’m looking for an opportunity to try:

“Another model I’d like to advocate for is to have members of a PC present the papers they selected (see my rant about paper reviewing and big conferences) and then an audience discussion. Like what the statisticians do but in person and with a publication resulting for the authors.”

I call this the “Not-so-royal Society.” The conference or session would center on a single paper written before the conference is organized. The organizers invite discussants to compose a response/review of this paper. The meeting could start with a presentation of the paper by the author. Many papers have multiple authors, and the presentation can be as collaborative as the writing. The author’s presentation is followed by commentary from the discussants. The remainder of the session is a conversation that invites commentary from the rest of the workshop participants.

After the workshop, the author can revise the paper, the discussants can write formal commentaries, and the author can write a rejoinder if they choose. All of this writing could be posted to arXiv as refereed conference proceedings and linked from the microconference proceedings webpage. This format might be the most legible in the current regime of bean counting and could perhaps serve as a “gentle introduction” to the microconference format. If you have ideas of papers we should use as testbeds for this format, reach out! I’d love to help set something like this up.

Finally, I want to give a shout out to Henry Farrell and Cosma Shalizi, who have been experimenting with clever microconference formats for years. Cosma wrote up the idea of having people present others’ work. Everyone writes a talk or slides, but then the presentation is assigned to someone else. They found that doing this at the start of the workshop creates a shared comprehension, allowing for a lot of multidisciplinary crosstalk. And they also found that speakers had to work extra hard to make their points comprehensible.

This is by no means an exhaustive list of ideas. And it shouldn’t be. My next major to-do is posting a working document of this runbook somewhere. But before I jump in and commit myself to a design, I’m looking for pointers to good online institutional memories that allow for edits and revisions. I love the minimalism of PMLR and bactra.org, but I also want to host a living mission statement and runbook on the same site. Let me know what platforms I should look into. Tech tips would be most appreciated!

Subscribe now

1

You can get a sense of the skew of my readership by the institutions they love.

2

I also love that it used to be in the backrooms of a Fry’s Electronics store

By Ben Recht

TR26-151 | Sparse polynomials and orthogonal representations of combinatorial graphs | Siddharth Iyer, Pavel Hrubes

from ECCC Papers
We give quantitative bounds on the sparsity of a real polynomial with non-negative coefficients vanishing on a slice of the Boolean cube $\{\pm1\}^n$. We obtain similar bounds on the dimension of real orthogonal representations of (the complement of) Johnson-type graphs. The estimates are related to the classical problem about coloring of $\mathbb{R}^n$, as well as the existence of error-correcting codes. We also give a simple combinatorial application to $k$-fold Hadamard matrices.
We give quantitative bounds on the sparsity of a real polynomial with non-negative coefficients vanishing on a slice of the Boolean cube $\{\pm1\}^n$. We obtain similar bounds on the dimension of real orthogonal representations of (the complement of) Johnson-type graphs. The estimates are related to the classical problem about coloring of $\mathbb{R}^n$, as well as the existence of error-correcting codes. We also give a simple combinatorial application to $k$-fold Hadamard matrices.

Pod-Deployability in Kubernetes with Inter-Pod Affinity Constraints is PSPACE-Complete

from arXiv: Computational Complexity

Authors: Saverio Giallorenzo, Jacopo Mauro, Gianluigi Zavattaro

Kubernetes is the de-facto platform for container orchestration. Its scheduler combines resource capacities with label-based affinity and anti-affinity rules, and the interaction of these features can make the eventual placement of a pod. In this paper, we study the pod-deployability problem: given an initial cluster, a pod type, and a designated node, does some legal sequence of pod deployments and deletions cover the target pair? We give three complexity results. First, when dynamic constraints contain no affinity (anti-affinity is allowed), pod-deployability is decidable in polynomial time. Second, required affinity together with required anti-affinity makes the problem PSPACE-complete. Third, required affinity alone is already enough for PSPACE-completeness on a single node with one scalar capacity. The lower bounds encode, respectively, 1-safe Petri-net coverability and bounded black pebbling. These results isolate two independent sources of state-space complexity in Kubernetes scheduling: logical exclusion and resource-bounded prerequisite management.

Authors: Saverio Giallorenzo, Jacopo Mauro, Gianluigi Zavattaro

Kubernetes is the de-facto platform for container orchestration. Its scheduler combines resource capacities with label-based affinity and anti-affinity rules, and the interaction of these features can make the eventual placement of a pod. In this paper, we study the pod-deployability problem: given an initial cluster, a pod type, and a designated node, does some legal sequence of pod deployments and deletions cover the target pair? We give three complexity results. First, when dynamic constraints contain no affinity (anti-affinity is allowed), pod-deployability is decidable in polynomial time. Second, required affinity together with required anti-affinity makes the problem PSPACE-complete. Third, required affinity alone is already enough for PSPACE-completeness on a single node with one scalar capacity. The lower bounds encode, respectively, 1-safe Petri-net coverability and bounded black pebbling. These results isolate two independent sources of state-space complexity in Kubernetes scheduling: logical exclusion and resource-bounded prerequisite management.

Constant-round quantum advantage in communication complexity for total functions

from arXiv: Computational Complexity

Authors: Atsuya Hasegawa, François Le Gall

We show that there exists a total function for which there is a polynomial gap between the randomized and the constant-round quantum communication complexity. Previously, such a separation was known only for quantum protocols using polynomially many rounds.

Authors: Atsuya Hasegawa, François Le Gall

We show that there exists a total function for which there is a polynomial gap between the randomized and the constant-round quantum communication complexity. Previously, such a separation was known only for quantum protocols using polynomially many rounds.

Proof of the hiding conjecture for Gaussian boson sampling with an arbitrary number of squeezed input modes

from arXiv: Computational Complexity

Authors: Laura Shou, Alexey V. Gorshkov, Victor Galitski, Sarah H. Miller

Gaussian boson sampling (GBS) is a sampling task proposed to demonstrate quantum advantage. We consider Gaussian boson sampling on $M$ optical modes, with $K$ equally squeezed input modes and $N$ observed photon counts. We complete the proof of the hiding conjecture for Gaussian boson sampling with an arbitrary number of squeezers $K$, which is a part of the argument for classical hardness of GBS. In particular, we show that for any $K$ and $N=o(\sqrt{K})$, the symmetric product $MK^{-1/2}U_{NK}U_{NK}^T$, for $U_{NK}$ the top left $N\times K$ submatrix of an $M\times M$ Haar random unitary $U$, is close in total variation distance to both an $N\times N$ symmetric complex Gaussian matrix $\mathbf G$ with independent entries, and the symmetric product $GG^T/\sqrt{K}$ for $G$ an $N\times K$ matrix of iid standard complex Gaussians. We show however that the density-based instance generating method of [Aaronson and Arkhipov, Theory Comput. 9, 143 (2013), Lemma 5.8] used to efficiently implement a hiding procedure fails for Gaussian boson sampling with $K=cM$ if $c<1/2$. Instead we use approximate instance generating to implement the hiding for the usual classical hardness reduction.

Authors: Laura Shou, Alexey V. Gorshkov, Victor Galitski, Sarah H. Miller

Gaussian boson sampling (GBS) is a sampling task proposed to demonstrate quantum advantage. We consider Gaussian boson sampling on $M$ optical modes, with $K$ equally squeezed input modes and $N$ observed photon counts. We complete the proof of the hiding conjecture for Gaussian boson sampling with an arbitrary number of squeezers $K$, which is a part of the argument for classical hardness of GBS. In particular, we show that for any $K$ and $N=o(\sqrt{K})$, the symmetric product $MK^{-1/2}U_{NK}U_{NK}^T$, for $U_{NK}$ the top left $N\times K$ submatrix of an $M\times M$ Haar random unitary $U$, is close in total variation distance to both an $N\times N$ symmetric complex Gaussian matrix $\mathbf G$ with independent entries, and the symmetric product $GG^T/\sqrt{K}$ for $G$ an $N\times K$ matrix of iid standard complex Gaussians. We show however that the density-based instance generating method of [Aaronson and Arkhipov, Theory Comput. 9, 143 (2013), Lemma 5.8] used to efficiently implement a hiding procedure fails for Gaussian boson sampling with $K=cM$ if $c<1/2$. Instead we use approximate instance generating to implement the hiding for the usual classical hardness reduction.

Quantifying over Optimal MSO-Definable Sets on Graphs of Bounded Clique-Width

from arXiv: Data Structures and Algorithms

Authors: Tatsuya Gima

We introduce $\mathsf{AmCMSO}$, an extension of counting monadic second-order logic ($\mathsf{CMSO}$) with predicates that refer to minimum- and maximum-value satisfying assignments. We establish fixed-parameter tractable model-checking meta-theorems for $\mathsf{AmCMSO}_1$ on graphs of bounded clique-width and for $\mathsf{AmCMSO}_2$ on graphs of bounded treewidth. These meta-theorems yield fixed-parameter tractable algorithms for several bilevel graph optimization problems, including interdiction and preassignment problems for solution uniquification, as well as algorithms for maximizing the diversity of optimal solutions without parameterizing by the optimum value. In contrast, allowing an optimality predicate to depend on an external set variable makes model checking hard for every level of the polynomial hierarchy, even on trees of fixed depth.

Authors: Tatsuya Gima

We introduce $\mathsf{AmCMSO}$, an extension of counting monadic second-order logic ($\mathsf{CMSO}$) with predicates that refer to minimum- and maximum-value satisfying assignments. We establish fixed-parameter tractable model-checking meta-theorems for $\mathsf{AmCMSO}_1$ on graphs of bounded clique-width and for $\mathsf{AmCMSO}_2$ on graphs of bounded treewidth. These meta-theorems yield fixed-parameter tractable algorithms for several bilevel graph optimization problems, including interdiction and preassignment problems for solution uniquification, as well as algorithms for maximizing the diversity of optimal solutions without parameterizing by the optimum value. In contrast, allowing an optimality predicate to depend on an external set variable makes model checking hard for every level of the polynomial hierarchy, even on trees of fixed depth.

The Complexity of Boolean Connectivity Problem of $k$-Horn Formulas

from arXiv: Data Structures and Algorithms

Authors: Takashi Horiyama, Shoon Mineyoshi, Yuto Okura, Kazuhisa Seto, Junichi Teruyama

The Boolean connectivity problem asks whether the set of satisfying assignments of a given Boolean formula forms a connected subgraph in the $n$-dimensional hypercube. This problem is known to be $\mathsf{coNP}$-complete, even when restricted to $k$-Horn formulas for $k \geq 3$, as shown by Makino, Tamaki, and Yamamoto. In this paper, we further investigate the computational complexity of {\sc Conn $k$-Horn}, the Boolean connectivity problem for $k$-Horn formulas. We provide algorithmic and hardness results for {\sc Conn $k$-Horn}. On the algorithmic side, we first present an exact exponential-time algorithm for arbitrary $k$ without any structural restrictions. Our algorithm builds on the deterministic PPZ algorithm proposed by Paturi, Pudlák, and Zane. It runs in $O^*(2^{(1 - 1/2k)n})$ time and polynomial space, achieving an exponential improvement over the previously known algorithm for the Boolean connectivity problem of $k$-CNF formulas, shown by Makino, Tamaki, and Yamamoto. We next give two polynomial-time algorithms for arbitrary $k$ under the following two restrictions: (i) each variable appears at most twice, and (ii) each clause has length exactly $k$ and each variable appears at most $k$ times. On the hardness side, we prove that {\sc Conn $3$-Horn} remains $\mathsf{coNP}$-complete even when each variable appears exactly three times.

Authors: Takashi Horiyama, Shoon Mineyoshi, Yuto Okura, Kazuhisa Seto, Junichi Teruyama

The Boolean connectivity problem asks whether the set of satisfying assignments of a given Boolean formula forms a connected subgraph in the $n$-dimensional hypercube. This problem is known to be $\mathsf{coNP}$-complete, even when restricted to $k$-Horn formulas for $k \geq 3$, as shown by Makino, Tamaki, and Yamamoto. In this paper, we further investigate the computational complexity of {\sc Conn $k$-Horn}, the Boolean connectivity problem for $k$-Horn formulas. We provide algorithmic and hardness results for {\sc Conn $k$-Horn}. On the algorithmic side, we first present an exact exponential-time algorithm for arbitrary $k$ without any structural restrictions. Our algorithm builds on the deterministic PPZ algorithm proposed by Paturi, Pudlák, and Zane. It runs in $O^*(2^{(1 - 1/2k)n})$ time and polynomial space, achieving an exponential improvement over the previously known algorithm for the Boolean connectivity problem of $k$-CNF formulas, shown by Makino, Tamaki, and Yamamoto. We next give two polynomial-time algorithms for arbitrary $k$ under the following two restrictions: (i) each variable appears at most twice, and (ii) each clause has length exactly $k$ and each variable appears at most $k$ times. On the hardness side, we prove that {\sc Conn $3$-Horn} remains $\mathsf{coNP}$-complete even when each variable appears exactly three times.

Fast Algorithms for Stoquastic Spin Systems

from arXiv: Data Structures and Algorithms

Authors: Ryan L. Mann

We establish a general framework for developing fast sampling and counting algorithms for stoquastic spin systems at high temperature. Our framework is based on a rapidly mixing Markov chain for polymer models and a subcritical percolation process for sampling individual polymers. We apply our framework to obtain fast algorithms for approximating the partition function and sampling from the thermal distribution of (1) general stoquastic spin systems, (2) ferromagnetic Heisenberg models, and (3) antiferromagnetic Heisenberg models on bipartite graphs. For the Heisenberg models, we obtain an improved bound on the inverse temperature by using their respective cycle and loop representations.

Authors: Ryan L. Mann

We establish a general framework for developing fast sampling and counting algorithms for stoquastic spin systems at high temperature. Our framework is based on a rapidly mixing Markov chain for polymer models and a subcritical percolation process for sampling individual polymers. We apply our framework to obtain fast algorithms for approximating the partition function and sampling from the thermal distribution of (1) general stoquastic spin systems, (2) ferromagnetic Heisenberg models, and (3) antiferromagnetic Heisenberg models on bipartite graphs. For the Heisenberg models, we obtain an improved bound on the inverse temperature by using their respective cycle and loop representations.

Differentially Private Continual Release with Relative Error

from arXiv: Data Structures and Algorithms

Authors: Bo Li, Wei Wang, Peng Ye

This work investigates several fundamental tasks, including $\mathsf{MaxSum}$, $\mathsf{MinSum}$, $\mathsf{MaxSelect}$, and $\mathsf{MinSelect}$, in the continual release model under differential privacy. Previous research has demonstrated that any algorithm for these tasks must admit a large purely additive error. We show that the error can be substantially reduced if a relative error term is allowed, provided that the input stream is generated non-adaptively. However, when input data records can be selected adaptively, we prove that a large error is inevitable for the task of selecting an attribute with a small cumulative sum, whereas small error bounds remain achievable for other tasks. This reveals a significant separation between non-adaptive and adaptive streams. We also complement our algorithms with nearly matching lower bounds.

Authors: Bo Li, Wei Wang, Peng Ye

This work investigates several fundamental tasks, including $\mathsf{MaxSum}$, $\mathsf{MinSum}$, $\mathsf{MaxSelect}$, and $\mathsf{MinSelect}$, in the continual release model under differential privacy. Previous research has demonstrated that any algorithm for these tasks must admit a large purely additive error. We show that the error can be substantially reduced if a relative error term is allowed, provided that the input stream is generated non-adaptively. However, when input data records can be selected adaptively, we prove that a large error is inevitable for the task of selecting an attribute with a small cumulative sum, whereas small error bounds remain achievable for other tasks. This reveals a significant separation between non-adaptive and adaptive streams. We also complement our algorithms with nearly matching lower bounds.

Parameterized Complexity of Temporal Agony

from arXiv: Data Structures and Algorithms

Authors: Tom-Lukas Breitkopf, Vincent Froese, Anton Herrmann, Pascal Kunz

Real-world networks are often organized in several layers forming a hierarchy which determines the interaction between the individual components. In order to discover such hierarchies in temporal networks, Tatti [ECML PKDD 2018] introduced the temporal agony problem Seg-Agony. Here, the goal is to assign each vertex a certain rank (from 1 to $k$) such that arcs only point from lower ranks to higher ranks. Backward arcs are penalized depending on the difference between the corresponding ranks. Since arcs may change over time, each vertex is allowed to change its rank $\ell\ge 1$ times in order to minimize the overall penalty $α$ (called temporal agony). We study the parameterized complexity of Seg-Agony with a special focus on the number $k$ of possible ranks for which we identify the precise complexity border. We show that the problem is polynomial-time solvable for $k=2$, NP-hard for $k=3$ and $\ell=1$ but polynomial-time solvable for constant $α$, and NP-hard for $k=4$ and $\ell=1$ even for $α=0$. We further show a polynomial-time algorithm for a constant number $n$ of vertices and fixed-parameter tractability for the combined parameter $n+\ell$.

Authors: Tom-Lukas Breitkopf, Vincent Froese, Anton Herrmann, Pascal Kunz

Real-world networks are often organized in several layers forming a hierarchy which determines the interaction between the individual components. In order to discover such hierarchies in temporal networks, Tatti [ECML PKDD 2018] introduced the temporal agony problem Seg-Agony. Here, the goal is to assign each vertex a certain rank (from 1 to $k$) such that arcs only point from lower ranks to higher ranks. Backward arcs are penalized depending on the difference between the corresponding ranks. Since arcs may change over time, each vertex is allowed to change its rank $\ell\ge 1$ times in order to minimize the overall penalty $α$ (called temporal agony). We study the parameterized complexity of Seg-Agony with a special focus on the number $k$ of possible ranks for which we identify the precise complexity border. We show that the problem is polynomial-time solvable for $k=2$, NP-hard for $k=3$ and $\ell=1$ but polynomial-time solvable for constant $α$, and NP-hard for $k=4$ and $\ell=1$ even for $α=0$. We further show a polynomial-time algorithm for a constant number $n$ of vertices and fixed-parameter tractability for the combined parameter $n+\ell$.

A Canonical m-Atomic Decomposition of Bipartite Graphs via a Grid Model

from arXiv: Data Structures and Algorithms

Authors: Béla Jónás

We study finite, connected, simple bipartite graphs in a grid model, in which a graph is drawn as a rectangular array and its structure is read off from empty subrectangles, called holes. In this model we attach to every brick a numerical invariant, its characteristic m, the difference between the number of rows and the largest proper independent set. A brick is excessive if m > 0. Our main results concern this invariant. We determine the characteristic of a disconnected excessive brick from those of its components, showing that m = min_i min{m_i, imb(W_i)} while the imbalance is additive; and we prove that an m-excessive brick is m-extendable, that is, every matching of size m extends to a maximum matching. Since Plummer's notion of n-extendability is defined only for graphs carrying a perfect matching, and our proof nowhere uses balance, the characteristic extends that notion canonically to unbalanced bipartite graphs. Using the characteristic we partition bipartite graphs into eleven structural classes. The underlying decomposition into atomic blocks is the classical decomposition into elementary components, and the description of the maximum proper independent sets by ideals of the block poset is likewise classical; the paper states precisely which results are classical and are not claimed here. What the grid model adds is a single geometric framework in which holes, characteristics and the block triangular form are read off from one picture.

Authors: Béla Jónás

We study finite, connected, simple bipartite graphs in a grid model, in which a graph is drawn as a rectangular array and its structure is read off from empty subrectangles, called holes. In this model we attach to every brick a numerical invariant, its characteristic m, the difference between the number of rows and the largest proper independent set. A brick is excessive if m > 0. Our main results concern this invariant. We determine the characteristic of a disconnected excessive brick from those of its components, showing that m = min_i min{m_i, imb(W_i)} while the imbalance is additive; and we prove that an m-excessive brick is m-extendable, that is, every matching of size m extends to a maximum matching. Since Plummer's notion of n-extendability is defined only for graphs carrying a perfect matching, and our proof nowhere uses balance, the characteristic extends that notion canonically to unbalanced bipartite graphs. Using the characteristic we partition bipartite graphs into eleven structural classes. The underlying decomposition into atomic blocks is the classical decomposition into elementary components, and the description of the maximum proper independent sets by ideals of the block poset is likewise classical; the paper states precisely which results are classical and are not claimed here. What the grid model adds is a single geometric framework in which holes, characteristics and the block triangular form are read off from one picture.

The Greedy Superstring Algorithm Achieves Ratio 2 for Strings of Length 6 Already

from arXiv: Data Structures and Algorithms

Authors: Nikolai Chukhin, Alexander S. Kulikov, Ivan Mihajlin, Alexander Smal

In the Shortest Common Superstring (SCS) problem, one is given a set of strings and asked to find a shortest string containing every input string as a substring. The greedy superstring conjecture states that the natural greedy algorithm, which repeatedly merges a pair of strings with maximum overlap, has approximation ratio $2$. The greedy algorithm runs in linear time and is arguably the simplest approximation algorithm for SCS. If the conjecture holds, it would also surpass the approximation guarantees of the best known algorithms. The conjecture has remained open for 40 years. Even the approximation ratio $ρ_k$ for instances whose strings all have length $k$ is unknown; for every $k \ge 3$, we have $2 - 1/k \le ρ_k \le \min\{(k+1)/2, 3.396\}$. We prove that strings of length 6 already suffice to achieve approximation ratio $2$: $ρ_k \ge 2$ for every $k \ge 6$. We also prove that $ρ_3 = 9/5$, completely characterizing the worst-case behavior of the greedy algorithm for strings of length 3.

Authors: Nikolai Chukhin, Alexander S. Kulikov, Ivan Mihajlin, Alexander Smal

In the Shortest Common Superstring (SCS) problem, one is given a set of strings and asked to find a shortest string containing every input string as a substring. The greedy superstring conjecture states that the natural greedy algorithm, which repeatedly merges a pair of strings with maximum overlap, has approximation ratio $2$. The greedy algorithm runs in linear time and is arguably the simplest approximation algorithm for SCS. If the conjecture holds, it would also surpass the approximation guarantees of the best known algorithms. The conjecture has remained open for 40 years. Even the approximation ratio $ρ_k$ for instances whose strings all have length $k$ is unknown; for every $k \ge 3$, we have $2 - 1/k \le ρ_k \le \min\{(k+1)/2, 3.396\}$. We prove that strings of length 6 already suffice to achieve approximation ratio $2$: $ρ_k \ge 2$ for every $k \ge 6$. We also prove that $ρ_3 = 9/5$, completely characterizing the worst-case behavior of the greedy algorithm for strings of length 3.

New Complexity Results for Fair Repetitive Scheduling

from arXiv: Data Structures and Algorithms

Authors: Moran Koren, Michael L. Pinedo, Dvir Shabtay

We revisit the problem of finding fair solutions to repetitive scheduling problems with a single machine. In this problem, we are given a set of $n$ clients and a planning horizon consisting of $q$ periods (days). Each day, every client submits a single job that must be processed by the machine. The objective is to construct a set of $q$ schedules, one for each day, such that the quality of service (QoS) received by each client meets a predefined threshold. The QoS measure may be any standard scheduling criterion, such as the total waiting time or total completion time of a client's jobs over the entire planning horizon. This problem has been studied in the literature, with previous works providing complexity classifications and approximation algorithms for various QoS measures. Nevertheless, several important questions remain open. In this paper, we resolve three of these questions and identify several additional directions for future research.

Authors: Moran Koren, Michael L. Pinedo, Dvir Shabtay

We revisit the problem of finding fair solutions to repetitive scheduling problems with a single machine. In this problem, we are given a set of $n$ clients and a planning horizon consisting of $q$ periods (days). Each day, every client submits a single job that must be processed by the machine. The objective is to construct a set of $q$ schedules, one for each day, such that the quality of service (QoS) received by each client meets a predefined threshold. The QoS measure may be any standard scheduling criterion, such as the total waiting time or total completion time of a client's jobs over the entire planning horizon. This problem has been studied in the literature, with previous works providing complexity classifications and approximation algorithms for various QoS measures. Nevertheless, several important questions remain open. In this paper, we resolve three of these questions and identify several additional directions for future research.

Palette Sparsification for General Uniform Hypergraphs

from arXiv: Data Structures and Algorithms

Authors: Ruizhe Shi

We prove a palette sparsification theorem for general $r$-uniform hypergraphs. For all sufficiently large $n$, every $r\ge 3$, and every $α\ge 7.1$, we show that an $n$-vertex $r$-uniform hypergraph of maximum degree $Δ$ is w.h.p. colorable from independently sampled lists of size $O(\sqrt{\log n})$ drawn from an ambient palette of size $\lceil αΔ^{1/(r-1)}\rceil$. The $\sqrt{\log n}$ dependence is asymptotically tight.

Authors: Ruizhe Shi

We prove a palette sparsification theorem for general $r$-uniform hypergraphs. For all sufficiently large $n$, every $r\ge 3$, and every $α\ge 7.1$, we show that an $n$-vertex $r$-uniform hypergraph of maximum degree $Δ$ is w.h.p. colorable from independently sampled lists of size $O(\sqrt{\log n})$ drawn from an ambient palette of size $\lceil αΔ^{1/(r-1)}\rceil$. The $\sqrt{\log n}$ dependence is asymptotically tight.

A simple and practical $o(\sqrt{n})$-time algorithm for shortest paths in power law graphs

from arXiv: Data Structures and Algorithms

Authors: Jiaqi Mao

Computing shortest paths in large graphs is, and remains, a fundamental and practically motivated problem. While many algorithms were proposed to calculate shortest path between pairs of vertices efficiently, many of them (index-based methods) require substantial preprocessing, while others (traversal-based methods) have higher time complexity. In this paper, we propose and analyze Pruned Bidirectional Search (PBS), a simple sublinear approximation algorithm for power-law graphs with parameter $β\in[2,3)$: our algorithm does not require any preprocessing, yet exhibits performance comparable to light index-based algorithms (of linear or sublinear index size): that is, PBS runs in time $O(n^{(1-1/\log\log n)/2})$ and, with high probability, returns a path with length within $\frac{41}{32}$ of the shortest path. Moreover, if one does allow a $n^{Θ(2-1/\log\log n)}$-time preprocessing step, its query time improves to $n^{Θ(1/\log\log n})$. We complement our theoretical results by experiments on both real-world and synthetic power-law graphs, which show that PBS is typically $1.84\times$-$7.76\times$ times faster than existing alternatives, while achieving an approximation ratio at most 1.05.

Authors: Jiaqi Mao

Computing shortest paths in large graphs is, and remains, a fundamental and practically motivated problem. While many algorithms were proposed to calculate shortest path between pairs of vertices efficiently, many of them (index-based methods) require substantial preprocessing, while others (traversal-based methods) have higher time complexity. In this paper, we propose and analyze Pruned Bidirectional Search (PBS), a simple sublinear approximation algorithm for power-law graphs with parameter $β\in[2,3)$: our algorithm does not require any preprocessing, yet exhibits performance comparable to light index-based algorithms (of linear or sublinear index size): that is, PBS runs in time $O(n^{(1-1/\log\log n)/2})$ and, with high probability, returns a path with length within $\frac{41}{32}$ of the shortest path. Moreover, if one does allow a $n^{Θ(2-1/\log\log n)}$-time preprocessing step, its query time improves to $n^{Θ(1/\log\log n})$. We complement our theoretical results by experiments on both real-world and synthetic power-law graphs, which show that PBS is typically $1.84\times$-$7.76\times$ times faster than existing alternatives, while achieving an approximation ratio at most 1.05.

Breaking the $2^n$ Barrier for Counting Linear Extensions with a Short Elementary Algorithm

from arXiv: Data Structures and Algorithms

Authors: Keigo Oka

A linear extension of a finite partially ordered set is a total ordering that respects the partial order. We give a deterministic exact algorithm that counts the linear extensions of an arbitrary $n$-element poset in time $O^*(1.89^n)$, where $O^*(\cdot)$ suppresses polynomial factors. This breaks the $2^n$ barrier for the general problem and resolves a question explicitly posed by Koivisto at Dagstuhl 2013. The proof refines an argument of Kozma for two-dimensional posets. A chain partition handles the case in which the poset is sufficiently far from an antichain. Otherwise, fix a maximum antichain (a largest set of pairwise incomparable elements). For each of its elements that has a comparable element above it outside the antichain, we record only which such element appears first. A decoding lemma enumerates the resulting patterns from their multiplicities. Once a pattern is fixed, each antichain element has a release condition and at most one deadline, so the dynamic program stores only the number of released elements in each deadline class. A stars-and-bars count bounds the total number of states.

Authors: Keigo Oka

A linear extension of a finite partially ordered set is a total ordering that respects the partial order. We give a deterministic exact algorithm that counts the linear extensions of an arbitrary $n$-element poset in time $O^*(1.89^n)$, where $O^*(\cdot)$ suppresses polynomial factors. This breaks the $2^n$ barrier for the general problem and resolves a question explicitly posed by Koivisto at Dagstuhl 2013. The proof refines an argument of Kozma for two-dimensional posets. A chain partition handles the case in which the poset is sufficiently far from an antichain. Otherwise, fix a maximum antichain (a largest set of pairwise incomparable elements). For each of its elements that has a comparable element above it outside the antichain, we record only which such element appears first. A decoding lemma enumerates the resulting patterns from their multiplicities. Once a pattern is fixed, each antichain element has a release condition and at most one deadline, so the dynamic program stores only the number of released elements in each deadline class. A stars-and-bars count bounds the total number of states.

A note on efficient k-limited broadcast domination in graphs

from arXiv: Data Structures and Algorithms

Authors: Bharadwaj, A. Senthil Thilak

An efficient $k$-limited dominating broadcast, or $k$-ELDB, is a $k$-limited broadcast in which every vertex is dominated exactly once. This notion brings together efficient domination and limited broadcast domination in a common framework. For a graph $G$, we write $mcr(G)$ for the smallest integer $k$ for which $G$ admits a $k$-ELDB. For an admissible value $k\ge mcr(G)$, we denote by $γ_{ebk}(G)$ the minimum cost of a $k$-ELDB on $G$, and is called the $k$-efficient broadcast domination number of $G$. In this paper, we study these parameters from an algorithmic perspective with complexity analysis. We develop a dynamic programming algorithm for trees which, for fixed $k$, computes $γ_{ebk}(T)$ and thereby obtains a polynomial-time procedure for determining $mcr(T) $. In contrast, we prove that, for every fixed integer $k\ge 1$, deciding whether a graph admits a $k$-ELDB is NP-complete for arbitrary graphs. These results place efficient limited broadcast domination in a natural complexity framework, with trees forming a tractable class and arbitrary graphs remaining computationally hard.

Authors: Bharadwaj, A. Senthil Thilak

An efficient $k$-limited dominating broadcast, or $k$-ELDB, is a $k$-limited broadcast in which every vertex is dominated exactly once. This notion brings together efficient domination and limited broadcast domination in a common framework. For a graph $G$, we write $mcr(G)$ for the smallest integer $k$ for which $G$ admits a $k$-ELDB. For an admissible value $k\ge mcr(G)$, we denote by $γ_{ebk}(G)$ the minimum cost of a $k$-ELDB on $G$, and is called the $k$-efficient broadcast domination number of $G$. In this paper, we study these parameters from an algorithmic perspective with complexity analysis. We develop a dynamic programming algorithm for trees which, for fixed $k$, computes $γ_{ebk}(T)$ and thereby obtains a polynomial-time procedure for determining $mcr(T) $. In contrast, we prove that, for every fixed integer $k\ge 1$, deciding whether a graph admits a $k$-ELDB is NP-complete for arbitrary graphs. These results place efficient limited broadcast domination in a natural complexity framework, with trees forming a tractable class and arbitrary graphs remaining computationally hard.

Thursday, August 20

Better than gold

from Scott Aaronson
What’s about the only thing more badass than a 17-year-old winning a gold medal at the International Olympiad in Informatics (IOI)? That 17-year-old intentionally forfeiting his gold medal by wearing an Israeli flag while the medal was announced, defying the IOI’s boycott of Israel (for background on this boycott, see my post from 2024). Kol […]

What’s about the only thing more badass than a 17-year-old winning a gold medal at the International Olympiad in Informatics (IOI)?

That 17-year-old intentionally forfeiting his gold medal by wearing an Israeli flag while the medal was announced, defying the IOI’s boycott of Israel (for background on this boycott, see my post from 2024).

Kol HaKavod (mad respect) to Yotam Budnik, who incredibly, has also won a Gold Medal (which he was allowed to keep, apparently) at the International Math Olympiad. And congratulations to the entire Israeli team, which (incredibly) would apparently have had a higher overall score than the US team, had it been allowed to compete as an official team at all.

By Scott

PhD/MS at Tennessee Tech University (apply by October 1, 2026)

from CCI: jobs
A fully-funded PhD position and MS positions with RA/TA support are available under the supervision of Prof. Prantar Ghosh at Tennessee Tech University starting Jan 2027 (Spring 2027 semester). Research will focus broadly on graph algorithms. A good mathematical background and prior experience in Theoretical CS is required. Please email CV and a brief description […]

A fully-funded PhD position and MS positions with RA/TA support are available under the supervision of Prof. Prantar Ghosh at Tennessee Tech University starting Jan 2027 (Spring 2027 semester). Research will focus broadly on graph algorithms. A good mathematical background and prior experience in Theoretical CS is required. Please email CV and a brief description of background to the email below.

Website: https://sites.google.com/view/prantarg/home
Email: pghosh@tntech.edu

By shacharlovett

Quantum Speedups Require Structure or Depth

from arXiv: Computational Complexity

Authors: Guy Blanc, Jordan Docter, Carmen Strassle, Li-Yang Tan

One of the most basic conjectures in quantum complexity theory states that every $t$-query quantum algorithm can be simulated on most inputs by a $\mathrm{poly}(t)$-query classical algorithm. If true, this would provide broad justification for the need for structure in quantum speedups. We settle this conjecture for parallel quantum algorithms, showing that every $t$-query $d$-round quantum algorithm can be simulated on most inputs with $t^{O(d^2)}$ classical queries. This suggests that for unstructured problems, superpolynomial speedups would require quantum circuits of superconstant depth, and exponential speedups would further require polynomial depth. In contrast, most known speedups for structured problems are achieved by highly parallel, low-depth algorithms. Our techniques also carry new implications for the status of $\mathsf{BPP}$ vs. $\mathsf{BQP}$ relative to a random oracle, a similarly longstanding problem.

Authors: Guy Blanc, Jordan Docter, Carmen Strassle, Li-Yang Tan

One of the most basic conjectures in quantum complexity theory states that every $t$-query quantum algorithm can be simulated on most inputs by a $\mathrm{poly}(t)$-query classical algorithm. If true, this would provide broad justification for the need for structure in quantum speedups. We settle this conjecture for parallel quantum algorithms, showing that every $t$-query $d$-round quantum algorithm can be simulated on most inputs with $t^{O(d^2)}$ classical queries. This suggests that for unstructured problems, superpolynomial speedups would require quantum circuits of superconstant depth, and exponential speedups would further require polynomial depth. In contrast, most known speedups for structured problems are achieved by highly parallel, low-depth algorithms. Our techniques also carry new implications for the status of $\mathsf{BPP}$ vs. $\mathsf{BQP}$ relative to a random oracle, a similarly longstanding problem.

Structure and Complexity of 2-Nilpotent Mal'cev Algebras

from arXiv: Computational Complexity

Authors: Patrick Wynne

We investigate the structure of central extensions for algebras in a congruence modular variety. We use a multisorted algebraic object called a clonoid to understand the term clone of such a central extension. We develop the difference clonoid of such a central extension and use it to show that the number of $2$-step nilpotent algebras on a fixed finite set is finite if and only if the set is of squarefree order. The subpower membership problem for a finite algebraic structure $\mathbb{A}$ is the problem of deciding on input $a_1,\dots,a_k, b \in A^n$, whether $b$ is in the subalgebra of $\mathbb{A}^n$ generated by $a_1, \dots, a_k$. We show that for a large class of nilpotent Mal'cev algebras the subpower membership problem is solvable in polynomial time, in particular for $2$-step nilpotent Mal'cev algebras of squarefree order.

Authors: Patrick Wynne

We investigate the structure of central extensions for algebras in a congruence modular variety. We use a multisorted algebraic object called a clonoid to understand the term clone of such a central extension. We develop the difference clonoid of such a central extension and use it to show that the number of $2$-step nilpotent algebras on a fixed finite set is finite if and only if the set is of squarefree order. The subpower membership problem for a finite algebraic structure $\mathbb{A}$ is the problem of deciding on input $a_1,\dots,a_k, b \in A^n$, whether $b$ is in the subalgebra of $\mathbb{A}^n$ generated by $a_1, \dots, a_k$. We show that for a large class of nilpotent Mal'cev algebras the subpower membership problem is solvable in polynomial time, in particular for $2$-step nilpotent Mal'cev algebras of squarefree order.

Lower Bounds for Domination-Type Problems Parameterized by Rank-Width

from arXiv: Computational Complexity

Authors: Chenghua Liu, Boning Meng

For graphs of rank-width \(w\), the algorithms of Bui-Xuan, Telle, and Vatshelle (\emph{Theor. Comput. Sci.}, 2013) for fixed finite/cofinite \((σ,ρ)\)-problems and of Bergougnoux and Kanté (\emph{SIAM J. Discrete Math.}, 2021) for Connected Dominating Set run in \(2^{O(w^2)}n^{O(1)}\) time. Bergougnoux, Korhonen, and Nederlof (STACS 2023) proved a matching lower bound under the Exponential Time Hypothesis (ETH) for \emph{Weighted} Dominating Set, but left the unweighted problem open. We prove that, unless ETH fails, Dominating Set admits no \(2^{o(w^2)}n^{O(1)}\)-time algorithm, even on split graphs and, separately, on bipartite graphs of diameter at most four, and even with a rank-decomposition or witnessing vertex order supplied. The proof replaces the earlier weights by a two-guard gadget and uses a low-rank equality gadget to carry \(k^2\) assignment bits through cuts of rank \(O(k)\). The construction also gives the same lower bound for Independent, Connected, and Total Dominating Set on restricted graph classes and applies to a broad family of \((σ,ρ)\)-set problems. This family includes cases in which \(σ\) is neither finite nor cofinite and contains the entire nontrivial cofinite--cofinite minimization regime. Every solution within the target budget has target size and corresponds bijectively to a satisfying assignment. Under the counting Exponential Time Hypothesis (\(\#\mathrm{ETH}\)), the same bounds therefore hold for counting solutions of size at most or exactly the target. Together with the known algorithms, our results show that the quadratic dependence on the rank-width \(w\) is optimal up to constant factors in the exponent for the classical problems above and throughout the covered finite/cofinite regime.

Authors: Chenghua Liu, Boning Meng

For graphs of rank-width \(w\), the algorithms of Bui-Xuan, Telle, and Vatshelle (\emph{Theor. Comput. Sci.}, 2013) for fixed finite/cofinite \((σ,ρ)\)-problems and of Bergougnoux and Kanté (\emph{SIAM J. Discrete Math.}, 2021) for Connected Dominating Set run in \(2^{O(w^2)}n^{O(1)}\) time. Bergougnoux, Korhonen, and Nederlof (STACS 2023) proved a matching lower bound under the Exponential Time Hypothesis (ETH) for \emph{Weighted} Dominating Set, but left the unweighted problem open. We prove that, unless ETH fails, Dominating Set admits no \(2^{o(w^2)}n^{O(1)}\)-time algorithm, even on split graphs and, separately, on bipartite graphs of diameter at most four, and even with a rank-decomposition or witnessing vertex order supplied. The proof replaces the earlier weights by a two-guard gadget and uses a low-rank equality gadget to carry \(k^2\) assignment bits through cuts of rank \(O(k)\). The construction also gives the same lower bound for Independent, Connected, and Total Dominating Set on restricted graph classes and applies to a broad family of \((σ,ρ)\)-set problems. This family includes cases in which \(σ\) is neither finite nor cofinite and contains the entire nontrivial cofinite--cofinite minimization regime. Every solution within the target budget has target size and corresponds bijectively to a satisfying assignment. Under the counting Exponential Time Hypothesis (\(\#\mathrm{ETH}\)), the same bounds therefore hold for counting solutions of size at most or exactly the target. Together with the known algorithms, our results show that the quadratic dependence on the rank-width \(w\) is optimal up to constant factors in the exponent for the classical problems above and throughout the covered finite/cofinite regime.

Quantum Mixedness Testing with Pauli Measurements

from arXiv: Computational Complexity

Authors: Jayadev Acharya, Abhilash Dharmavarapu, Yuhan Liu, Nengkun Yu

We consider a fundamental problem of \emph{mixedness testing}: Given $n$ copies of an $N$-qubit state $ρ$, determine whether $ρ= \mathbb{I}_d/d$ or $\|ρ-\mathbb{I}_d/d\|_1 \geq \varepsilon$ with high probability, where $d = 2^N$. In particular, we focus on performing this task in the practical setting of single-qubit measurements, where measurements are prepared independently on each qubit. We provide a nearly complete picture of single-qubit mixedness tesing by showing $n = \widetildeΘ\left(\sqrt{10}^N/\varepsilon^2\right)$. To establish our lower bound, we introduce a new measurement-dependent lower bound framework for adaptive single-copy state certification. For the upper bound, we present a randomized Pauli basis measurement protocol, which relies on a new primitive for computationally efficient uniformity testing of correlation-concentrated distributions on the Boolean hypercube.

Authors: Jayadev Acharya, Abhilash Dharmavarapu, Yuhan Liu, Nengkun Yu

We consider a fundamental problem of \emph{mixedness testing}: Given $n$ copies of an $N$-qubit state $ρ$, determine whether $ρ= \mathbb{I}_d/d$ or $\|ρ-\mathbb{I}_d/d\|_1 \geq \varepsilon$ with high probability, where $d = 2^N$. In particular, we focus on performing this task in the practical setting of single-qubit measurements, where measurements are prepared independently on each qubit. We provide a nearly complete picture of single-qubit mixedness tesing by showing $n = \widetildeΘ\left(\sqrt{10}^N/\varepsilon^2\right)$. To establish our lower bound, we introduce a new measurement-dependent lower bound framework for adaptive single-copy state certification. For the upper bound, we present a randomized Pauli basis measurement protocol, which relies on a new primitive for computationally efficient uniformity testing of correlation-concentrated distributions on the Boolean hypercube.

On the quantum communication complexity of total functions

from arXiv: Computational Complexity

Authors: Dmytro Gavinsky

We present a total function with a polylogarithmic two-message quantum protocol, whereas every randomised protocol, even with arbitrarily many rounds, requires polynomial communication.

Authors: Dmytro Gavinsky

We present a total function with a polylogarithmic two-message quantum protocol, whereas every randomised protocol, even with arbitrarily many rounds, requires polynomial communication.

Hardness of Forcing Unique Perfect Matchings in Bipartite Graphs of Maximum Degree 3

from arXiv: Computational Complexity

Authors: Ryoma Aoshima, Takashi Horiyama, Atsuki Nagao, Fumiya Sakamoto, Hibiki Sato, Kazuhisa Seto, Karin Umebayashi

In a graph $G$, a set of edges $F$ is called a \emph{forcing set} if there exists a unique perfect matching $M$ such that $F \subseteq M$. Similarly, a set of edges $A$ is called an \emph{anti-forcing set} if the graph with edge set $ E(G)\setminus A$ has a unique perfect matching. It is known that, given a bipartite graph $G$ of maximum degree~$3$ and a perfect matching $M$, the problem of deciding whether there exists a forcing set of size at most $k$ for $M$ is NP-complete. Moreover, given a bipartite graph $G$ of maximum degree~$4$ and a perfect matching $M$, the problem of deciding whether there exists an anti-forcing set of size at most $k$ for $M$ is NP-complete. Furthermore, given a bipartite graph of maximum degree~$5$, the problem of deciding whether there exists a perfect matching $M$ that can be made unique by a forcing set of size at most $k$ is also NP-complete. In contrast, the computational complexity of deciding whether there exists a perfect matching $M$ that can be made unique by an anti-forcing set of size at most $k$ is not known, even for general graphs. In this paper, we show that all of these problems remain NP-complete even when restricted to bipartite graphs of maximum degree~$3$.

Authors: Ryoma Aoshima, Takashi Horiyama, Atsuki Nagao, Fumiya Sakamoto, Hibiki Sato, Kazuhisa Seto, Karin Umebayashi

In a graph $G$, a set of edges $F$ is called a \emph{forcing set} if there exists a unique perfect matching $M$ such that $F \subseteq M$. Similarly, a set of edges $A$ is called an \emph{anti-forcing set} if the graph with edge set $ E(G)\setminus A$ has a unique perfect matching. It is known that, given a bipartite graph $G$ of maximum degree~$3$ and a perfect matching $M$, the problem of deciding whether there exists a forcing set of size at most $k$ for $M$ is NP-complete. Moreover, given a bipartite graph $G$ of maximum degree~$4$ and a perfect matching $M$, the problem of deciding whether there exists an anti-forcing set of size at most $k$ for $M$ is NP-complete. Furthermore, given a bipartite graph of maximum degree~$5$, the problem of deciding whether there exists a perfect matching $M$ that can be made unique by a forcing set of size at most $k$ is also NP-complete. In contrast, the computational complexity of deciding whether there exists a perfect matching $M$ that can be made unique by an anti-forcing set of size at most $k$ is not known, even for general graphs. In this paper, we show that all of these problems remain NP-complete even when restricted to bipartite graphs of maximum degree~$3$.

Good Stabilizer Codes from Shallow Clifford Circuits with Random Matchings

from arXiv: Computational Complexity

Authors: Emile Anand, Elia Gorokhovsky, Jennifer Hritz, Jingtong Sun

Encoding quantum information with low circuit overhead is a fundamental challenge in fault-tolerant quantum computation. Random circuits provide a natural mechanism for rapidly spreading logical information through simple gates applied in parallel. Brown and Fawzi showed that random Clifford circuits on two-qubit Clifford gates provide such encoders that achieve the quantum Gilbert-Varshamov rate-distance tradeoff with depth $O(\log^3 n)$. We show that the same asymptotic tradeoff is attained in optimal $O(\log n)$ depth under a gate distribution with a more restricted support. For every fixed $δ>0$ and sufficiently large $n$, if $\frac kn < 1 - H(\frac{d}{n}) - \frac{d}{n}\log_2 3 - δ$, we can construct random circuits of depth $O(\log n)$ which define, with high probability, an $[n,k]$ stabilizer code of distance at least $d+1$, which matches the $Ω(\log n)$ light-cone lower bound for linear distance encoders. Our ensemble employs a random matching circuit architecture consisting of $T$ independent permutation-invariant layers. In each layer, the qubits are paired up by a uniformly random perfect matching, and a random independent two-qubit Clifford gate is applied to each pair. The gate distribution need not be uniform over, or even have full support on, the two-qubit Clifford group; rather, we allow for very general distributions on Clifford gates satisfying three regularity conditions. In particular, the construction can be implemented using $n/2$ CNOT gates on randomly matched pairs in each layer, with parallel one-qubit Clifford twirls. These regularity conditions allow us to reduce the second-moment dynamics of our random circuits to a reversible Markov chain on binary support strings. We establish logarithmic hitting-time bounds for this Markov chain and comparisons of its stationary distribution to prove the coding properties of the circuits.

Authors: Emile Anand, Elia Gorokhovsky, Jennifer Hritz, Jingtong Sun

Encoding quantum information with low circuit overhead is a fundamental challenge in fault-tolerant quantum computation. Random circuits provide a natural mechanism for rapidly spreading logical information through simple gates applied in parallel. Brown and Fawzi showed that random Clifford circuits on two-qubit Clifford gates provide such encoders that achieve the quantum Gilbert-Varshamov rate-distance tradeoff with depth $O(\log^3 n)$. We show that the same asymptotic tradeoff is attained in optimal $O(\log n)$ depth under a gate distribution with a more restricted support. For every fixed $δ>0$ and sufficiently large $n$, if $\frac kn < 1 - H(\frac{d}{n}) - \frac{d}{n}\log_2 3 - δ$, we can construct random circuits of depth $O(\log n)$ which define, with high probability, an $[n,k]$ stabilizer code of distance at least $d+1$, which matches the $Ω(\log n)$ light-cone lower bound for linear distance encoders. Our ensemble employs a random matching circuit architecture consisting of $T$ independent permutation-invariant layers. In each layer, the qubits are paired up by a uniformly random perfect matching, and a random independent two-qubit Clifford gate is applied to each pair. The gate distribution need not be uniform over, or even have full support on, the two-qubit Clifford group; rather, we allow for very general distributions on Clifford gates satisfying three regularity conditions. In particular, the construction can be implemented using $n/2$ CNOT gates on randomly matched pairs in each layer, with parallel one-qubit Clifford twirls. These regularity conditions allow us to reduce the second-moment dynamics of our random circuits to a reversible Markov chain on binary support strings. We establish logarithmic hitting-time bounds for this Markov chain and comparisons of its stationary distribution to prove the coding properties of the circuits.

Formal Verification of Romanov's Triplet Logic: A Verified Filter for Sliding-window 3-CNF with Application to Structured Formulas

from arXiv: Computational Complexity

Authors: Dmitry V. Alexandrov

We present the first mechanised formalisation of Romanov's Triplet Logic (TLS) in the Rocq proof assistant. TLS is a triplet-based combinatorial framework for reasoning about compatible paths through layered triplet structures, called Compact Triplets Structures (CTS), and their intersection via Romanov's Effective Procedure, which we refer to as Simple Vertex Intersection (SVI). Originally motivated by Boolean satisfiability, TLS constitutes a self-contained mathematical theory whose formal properties had not been previously established. We formalise the core of TLS in Rocq, including Compact Triplets Formulas (CTF), CTS, hyperstructures, clearing, and SVI. For the well-formed sliding-window fragment we verify a clause-by-clause CNF-to-CTF translation, the clearing procedure, and aligned intersection, and we prove explicit polynomial-time bounds for the filter stages. Our main contribution is a precise correctness boundary: the existence of a joint satisfying set implies non-emptiness of SVI, but the converse does not hold in general; for aligned structures we recover a complete bi-implication, extended to systems of structures. We also formalise soundness of grouped-window translation and exhibit a formal counterexample to its completeness. We introduce VFR, an extracted OCaml prototype that provides a verified decision procedure for the sliding-window fragment and a sound one-sided filter for general 3-CNF, with a Python runtime and reproducible Docker packaging. Benchmarks on random and structured instances confirm the predicted behaviour, and the complete toolchain is available as a curated Zenodo artifact. The Rocq development comprises more than 23,000 lines of code across seventeen files, with 427 proved lemmas and theorems and zero admitted goals.

Authors: Dmitry V. Alexandrov

We present the first mechanised formalisation of Romanov's Triplet Logic (TLS) in the Rocq proof assistant. TLS is a triplet-based combinatorial framework for reasoning about compatible paths through layered triplet structures, called Compact Triplets Structures (CTS), and their intersection via Romanov's Effective Procedure, which we refer to as Simple Vertex Intersection (SVI). Originally motivated by Boolean satisfiability, TLS constitutes a self-contained mathematical theory whose formal properties had not been previously established. We formalise the core of TLS in Rocq, including Compact Triplets Formulas (CTF), CTS, hyperstructures, clearing, and SVI. For the well-formed sliding-window fragment we verify a clause-by-clause CNF-to-CTF translation, the clearing procedure, and aligned intersection, and we prove explicit polynomial-time bounds for the filter stages. Our main contribution is a precise correctness boundary: the existence of a joint satisfying set implies non-emptiness of SVI, but the converse does not hold in general; for aligned structures we recover a complete bi-implication, extended to systems of structures. We also formalise soundness of grouped-window translation and exhibit a formal counterexample to its completeness. We introduce VFR, an extracted OCaml prototype that provides a verified decision procedure for the sliding-window fragment and a sound one-sided filter for general 3-CNF, with a Python runtime and reproducible Docker packaging. Benchmarks on random and structured instances confirm the predicted behaviour, and the complete toolchain is available as a curated Zenodo artifact. The Rocq development comprises more than 23,000 lines of code across seventeen files, with 427 proved lemmas and theorems and zero admitted goals.

The Limits of Black-Box Reductions for All-Pairs Triangle Detection

from arXiv: Data Structures and Algorithms

Authors: Nathan Sheffield, Virginia Vassilevska Williams, Zoe Xi

For any tripartite relation $R\subseteq \mathbb{Z}^3$, the $R$-Triangle problem asks, given an edge-weighted graph, whether it contains a triangle whose weights form a triple in $R$. The All-Edge $R$-Triangle problem asks to determine for every edge whether it is contained in such a triangle. It is known that $R$-Triangle and All-Edge $R$-Triangle are subcubically fine-grained equivalent for every $R$ [Vassilevska W.-Williams'10]. However, while it is conjectured that these problems are tightly equivalent, this reduction only shows that if $R$-Triangle has an $O(n^{3-ε})$-time algorithm for some $ε>0$, then All-Edge $R$-Triangle has an $O(n^{3-ε/3})$-time algorithm. This paper provides a strong unconditional barrier to a tight equivalence: the reduction of [Vassilevska W.-Williams'10] is optimal for black-box reductions that work for arbitrary $R$. We give further results about black-box reductions between a variety of $R$-triangle problems. Our positive results yield new reductions between several classes of triangle and matrix problems --- for instance, we demonstrate that an $O(n^{2.53})$-time algorithm for computing equality or dominance product would imply an improvement on known algorithms for computing boolean $(\min, +)$-product, giving the first conditional lower bound for dominance and equality product. Our negative results can be thought of as barriers against natural fine-grained proof techniques. Besides the result that a tighter equivalence between $R$-Triangle and All-Edge $R$-Triangle is not possible, we also show that no appropriately "black-box" reductions are capable of demonstrating a subcubic equivalence between triangle counting and binary integer matrix multiplication, or a tight equivalence between boolean matrix multiplication and listing $n^2$ triangles, and more, despite the fact that all of these equivalences are conjectured to hold.

Authors: Nathan Sheffield, Virginia Vassilevska Williams, Zoe Xi

For any tripartite relation $R\subseteq \mathbb{Z}^3$, the $R$-Triangle problem asks, given an edge-weighted graph, whether it contains a triangle whose weights form a triple in $R$. The All-Edge $R$-Triangle problem asks to determine for every edge whether it is contained in such a triangle. It is known that $R$-Triangle and All-Edge $R$-Triangle are subcubically fine-grained equivalent for every $R$ [Vassilevska W.-Williams'10]. However, while it is conjectured that these problems are tightly equivalent, this reduction only shows that if $R$-Triangle has an $O(n^{3-ε})$-time algorithm for some $ε>0$, then All-Edge $R$-Triangle has an $O(n^{3-ε/3})$-time algorithm. This paper provides a strong unconditional barrier to a tight equivalence: the reduction of [Vassilevska W.-Williams'10] is optimal for black-box reductions that work for arbitrary $R$. We give further results about black-box reductions between a variety of $R$-triangle problems. Our positive results yield new reductions between several classes of triangle and matrix problems --- for instance, we demonstrate that an $O(n^{2.53})$-time algorithm for computing equality or dominance product would imply an improvement on known algorithms for computing boolean $(\min, +)$-product, giving the first conditional lower bound for dominance and equality product. Our negative results can be thought of as barriers against natural fine-grained proof techniques. Besides the result that a tighter equivalence between $R$-Triangle and All-Edge $R$-Triangle is not possible, we also show that no appropriately "black-box" reductions are capable of demonstrating a subcubic equivalence between triangle counting and binary integer matrix multiplication, or a tight equivalence between boolean matrix multiplication and listing $n^2$ triangles, and more, despite the fact that all of these equivalences are conjectured to hold.

Computing All Optimal Partial $p$-Wasserstein Matchings on the Line

from arXiv: Data Structures and Algorithms

Authors: Sebastian Angrick, Jacobus Conradi, Mónika Csikós, Niko Hastrich, Danny Mittal, André Nusser, Krzystof Onak, Sharath Raghvendra

For $p \ge 1$, the $p$-Wasserstein distance measures the minimum cost of transporting probability mass between distributions, where moving unit mass between two points costs the $p$th power of their distance. For discrete distributions in one dimension, full transport is especially simple: after sorting, mass is matched in order along the line. By contrast, partial and unbalanced transport on the line remains much less understood. Recently, Chapel and Tavenard [ICLR'25] showed that, for $p=1$, all optimal partial transport plans between distributions supported on $n$ points, with uniform mass at each point, can be computed in $O(n\log n)$ time by exploiting the metric structure of the cost. For $p>1$, this structure no longer applies, and existing approaches require $Ω(n^2)$ time. Our main contribution is an FFT-based data structure for balanced-interval transport queries, which bypasses this quadratic bottleneck and yields an $O(p\,n\log^2 n)$-time algorithm for computing all optimal partial transports on the line for every finite $p\ge 1$. We also provide an open-source C++ implementation that outperforms the state-of-the-art baseline on a range of synthetic instances. Finally, we establish a conditional lower bound for $p=\infty$: any subquadratic-time algorithm for computing all optimal partial transport plan costs on the line would violate the $(\min,+)$-Convolution Hypothesis. This separates the problem from full optimal transport, which is solvable in $O(n\log n)$.

Authors: Sebastian Angrick, Jacobus Conradi, Mónika Csikós, Niko Hastrich, Danny Mittal, André Nusser, Krzystof Onak, Sharath Raghvendra

For $p \ge 1$, the $p$-Wasserstein distance measures the minimum cost of transporting probability mass between distributions, where moving unit mass between two points costs the $p$th power of their distance. For discrete distributions in one dimension, full transport is especially simple: after sorting, mass is matched in order along the line. By contrast, partial and unbalanced transport on the line remains much less understood. Recently, Chapel and Tavenard [ICLR'25] showed that, for $p=1$, all optimal partial transport plans between distributions supported on $n$ points, with uniform mass at each point, can be computed in $O(n\log n)$ time by exploiting the metric structure of the cost. For $p>1$, this structure no longer applies, and existing approaches require $Ω(n^2)$ time. Our main contribution is an FFT-based data structure for balanced-interval transport queries, which bypasses this quadratic bottleneck and yields an $O(p\,n\log^2 n)$-time algorithm for computing all optimal partial transports on the line for every finite $p\ge 1$. We also provide an open-source C++ implementation that outperforms the state-of-the-art baseline on a range of synthetic instances. Finally, we establish a conditional lower bound for $p=\infty$: any subquadratic-time algorithm for computing all optimal partial transport plan costs on the line would violate the $(\min,+)$-Convolution Hypothesis. This separates the problem from full optimal transport, which is solvable in $O(n\log n)$.

Cell-Probe Lower Bounds and Complexity-Preserving Reductions for Suffix Array Queries

from arXiv: Data Structures and Algorithms

Authors: Dominik Kempa, Tomasz Kociumaka

For a text $T$ of length $n$ over an alphabet of size $σ$, its suffix array lists the starting positions of the suffixes of $T$ in lexicographic order, and its inverse suffix array gives the lexicographic rank of the suffix starting at each position. Since the introduction of the FM-index and the compressed suffix array in 2000, both queries have been supported in $O((\log_σn)^ε)$ time using $O(n\logσ)$ bits, for any constant $ε>0$. Yet no nontrivial time-space lower bound for suffix-array queries was known. We give the first such lower bound. Specifically, we show that, in the cell-probe model with $Θ(\log n)$-bit words, every $S$-bit data structure answering suffix-array queries on binary strings of length at most $n$ has query time $Ω(\log\log n/\log((S/n)\log\log n))$. Consequently, every structure using $O(n(\log\log n)^{O(1)})$ bits requires $Ω(\log\log n/\log\log\log n)$ query time, while constant query time requires $Ω(n\log^εn)$ bits for some constant $ε>0$. In particular, no $O(n)$-bit suffix-array representation for binary texts supports constant-time queries, answering the 25-year-old question of Grossi and Vitter. We also give exact complexity-preserving equivalences between suffix-array access and simpler prefix queries on short strings. For every $2\leqσ\leq n$, suffix-array queries are equivalent to prefix-select queries, and inverse-suffix-array queries are equivalent to prefix-special-rank queries. The reductions in both directions preserve all four standard measures up to constant factors: space, query time, preprocessing time, and preprocessing space. Unlike previous reductions, they incur no additive $O(\log\log n)$ query-time term. Thus, the corresponding prefix-query problems capture suffix-array and inverse-suffix-array access without asymptotic loss in any of the four measures.

Authors: Dominik Kempa, Tomasz Kociumaka

For a text $T$ of length $n$ over an alphabet of size $σ$, its suffix array lists the starting positions of the suffixes of $T$ in lexicographic order, and its inverse suffix array gives the lexicographic rank of the suffix starting at each position. Since the introduction of the FM-index and the compressed suffix array in 2000, both queries have been supported in $O((\log_σn)^ε)$ time using $O(n\logσ)$ bits, for any constant $ε>0$. Yet no nontrivial time-space lower bound for suffix-array queries was known. We give the first such lower bound. Specifically, we show that, in the cell-probe model with $Θ(\log n)$-bit words, every $S$-bit data structure answering suffix-array queries on binary strings of length at most $n$ has query time $Ω(\log\log n/\log((S/n)\log\log n))$. Consequently, every structure using $O(n(\log\log n)^{O(1)})$ bits requires $Ω(\log\log n/\log\log\log n)$ query time, while constant query time requires $Ω(n\log^εn)$ bits for some constant $ε>0$. In particular, no $O(n)$-bit suffix-array representation for binary texts supports constant-time queries, answering the 25-year-old question of Grossi and Vitter. We also give exact complexity-preserving equivalences between suffix-array access and simpler prefix queries on short strings. For every $2\leqσ\leq n$, suffix-array queries are equivalent to prefix-select queries, and inverse-suffix-array queries are equivalent to prefix-special-rank queries. The reductions in both directions preserve all four standard measures up to constant factors: space, query time, preprocessing time, and preprocessing space. Unlike previous reductions, they incur no additive $O(\log\log n)$ query-time term. Thus, the corresponding prefix-query problems capture suffix-array and inverse-suffix-array access without asymptotic loss in any of the four measures.

Constant-Time Inverse Suffix Array Queries in Compact Space and Sublinear-Time Construction of Suffix Array Indexes

from arXiv: Data Structures and Algorithms

Authors: Dominik Kempa, Tomasz Kociumaka

For a text $T\in[0..σ)^n$ with $2\leqσ\leq n$, its suffix array orders the suffix starting positions lexicographically, while its inverse suffix array maps each position to its suffix's rank. Since compressed suffix arrays and FM-indexes appeared in 2000, a central goal has been to support both queries in $O(n\logσ)$ bits. Thankachan recently reduced inverse suffix array query time to $O(\log\log n/\log\logσ)$, but constant time remained open. We give the first inverse suffix array structure with optimal space and query time: $O(n\logσ)$ bits and $O(1)$ time. For binary texts, this unconditionally separates the two queries for deterministic structures, since every $O(n)$-bit suffix array structure in the cell-probe model with $Θ(\log n)$-bit cells has worst-case query time $Ω(\log\log n/\log\log\log n)$. Construction is a second challenge: linear time can take $Θ(\log_σ n)$ times as long as reading the input or writing a compact index. Previously, sublinear construction was known for only one such index supporting both queries. In the word RAM with $Θ(\log n)$-bit words, we deterministically construct the new structure and two suffix array families from the packed text in $O(n\min(1,\logσ/\sqrt{\log n}))$ time. For $B\geq2$, the first family uses $O(n\logσ(1+\log_B\log_σn))$ bits and has query time $O(B(1+\log_B\log_σn))$, whereas the second uses $O(Bn\logσ(1+\log_B\log_σn))$ bits and has query time $O(1+\log_B\log_σn)$. Each has peak preprocessing space bounded by its index size. For binary texts, the second family matches the deterministic cell-probe time-space lower bound whenever $B\geq(\log\log n)^{Ω(1)}$, and, outside the slowest-query regimes, improving the deterministic construction time to $o(n/\sqrt{\log n})$ would yield an equally fast Dictionary Matching algorithm.

Authors: Dominik Kempa, Tomasz Kociumaka

For a text $T\in[0..σ)^n$ with $2\leqσ\leq n$, its suffix array orders the suffix starting positions lexicographically, while its inverse suffix array maps each position to its suffix's rank. Since compressed suffix arrays and FM-indexes appeared in 2000, a central goal has been to support both queries in $O(n\logσ)$ bits. Thankachan recently reduced inverse suffix array query time to $O(\log\log n/\log\logσ)$, but constant time remained open. We give the first inverse suffix array structure with optimal space and query time: $O(n\logσ)$ bits and $O(1)$ time. For binary texts, this unconditionally separates the two queries for deterministic structures, since every $O(n)$-bit suffix array structure in the cell-probe model with $Θ(\log n)$-bit cells has worst-case query time $Ω(\log\log n/\log\log\log n)$. Construction is a second challenge: linear time can take $Θ(\log_σ n)$ times as long as reading the input or writing a compact index. Previously, sublinear construction was known for only one such index supporting both queries. In the word RAM with $Θ(\log n)$-bit words, we deterministically construct the new structure and two suffix array families from the packed text in $O(n\min(1,\logσ/\sqrt{\log n}))$ time. For $B\geq2$, the first family uses $O(n\logσ(1+\log_B\log_σn))$ bits and has query time $O(B(1+\log_B\log_σn))$, whereas the second uses $O(Bn\logσ(1+\log_B\log_σn))$ bits and has query time $O(1+\log_B\log_σn)$. Each has peak preprocessing space bounded by its index size. For binary texts, the second family matches the deterministic cell-probe time-space lower bound whenever $B\geq(\log\log n)^{Ω(1)}$, and, outside the slowest-query regimes, improving the deterministic construction time to $o(n/\sqrt{\log n})$ would yield an equally fast Dictionary Matching algorithm.

Space-Efficient Hierholzer for Undirected Graphs

from arXiv: Data Structures and Algorithms

Authors: Elena Grigorescu, Ziad Ismaili Alaoui, Tamio-Vesa Nakajima, Shayan Shirazi Mofrad, Sebastian Wild

We present a simple linear-time algorithm that outputs an Eulerian tour of an undirected multigraph with $n$ vertices and $m$ edges, if one exists, in $O(m)$ time and using $O(n)$ words of working memory. The input is given as read-only adjacency lists, and the output is written to an append-only stream in traversal order. Our algorithm first finds a sparse spanning circuit (a skeleton), then traverses the circuit step-by-step, repeatedly outputting further circuits rooted at the current vertex. This solves a problem left open by Ismaili Alaoui, Plump, and Wild (SOSA 2026): their space-efficient variant of Hierholzer's algorithm handles general directed multigraphs, but it is unclear how to generalize it to general undirected multigraphs. Our result completes the picture in the read-only model for space-efficient output of Eulerian tours.

Authors: Elena Grigorescu, Ziad Ismaili Alaoui, Tamio-Vesa Nakajima, Shayan Shirazi Mofrad, Sebastian Wild

We present a simple linear-time algorithm that outputs an Eulerian tour of an undirected multigraph with $n$ vertices and $m$ edges, if one exists, in $O(m)$ time and using $O(n)$ words of working memory. The input is given as read-only adjacency lists, and the output is written to an append-only stream in traversal order. Our algorithm first finds a sparse spanning circuit (a skeleton), then traverses the circuit step-by-step, repeatedly outputting further circuits rooted at the current vertex. This solves a problem left open by Ismaili Alaoui, Plump, and Wild (SOSA 2026): their space-efficient variant of Hierholzer's algorithm handles general directed multigraphs, but it is unclear how to generalize it to general undirected multigraphs. Our result completes the picture in the read-only model for space-efficient output of Eulerian tours.

Online Permutation Embedding: Optimal Stopping and Scaling Laws

from arXiv: Data Structures and Algorithms

Authors: Dylan J. Altschuler, Quentin Dubroff, Konstantin Tikhomirov

We study optimal online algorithms for embedding a permutation $π$ of $[k]$ into an iid stream of uniform $[0,1]$ random variables. This problem is a broad generalization of the classical online monotone subsequence selection problem, recovered in the special case $π=\mathrm{Id}_k$. Our first contribution is an efficiently solvable dynamic program for the optimal embedding time of any $k$-permutation $π$. This dynamic program also yields an explicit optimal online embedding algorithm. We then investigate the asymptotic scaling of the optimal embedding time for uniformly random target permutations, as well as the extremal problem of identifying the permutations with largest expected online embedding time. Our second main result shows that, to first order, random permutations are strictly faster to embed than monotone permutations, which in turn are strictly faster to embed than the extremal permutations. This separation stands in sharp contrast to prevailing conjectures and heuristics in the offline theory of permutation embeddings.

Authors: Dylan J. Altschuler, Quentin Dubroff, Konstantin Tikhomirov

We study optimal online algorithms for embedding a permutation $π$ of $[k]$ into an iid stream of uniform $[0,1]$ random variables. This problem is a broad generalization of the classical online monotone subsequence selection problem, recovered in the special case $π=\mathrm{Id}_k$. Our first contribution is an efficiently solvable dynamic program for the optimal embedding time of any $k$-permutation $π$. This dynamic program also yields an explicit optimal online embedding algorithm. We then investigate the asymptotic scaling of the optimal embedding time for uniformly random target permutations, as well as the extremal problem of identifying the permutations with largest expected online embedding time. Our second main result shows that, to first order, random permutations are strictly faster to embed than monotone permutations, which in turn are strictly faster to embed than the extremal permutations. This separation stands in sharp contrast to prevailing conjectures and heuristics in the offline theory of permutation embeddings.

Tight Energy Lower Bounds for Distributed Graph Algorithms

from arXiv: Data Structures and Algorithms

Authors: Fabien Dufoulon, Gopal Pandurangan, Peter Robinson

There has been a significant recent interest in designing distributed algorithms in the SLEEPING model that minimize the {energy (a.k.a awake) complexity, which measures the number of rounds a node is awake during the algorithm. A node spends non-trivial resources (messages, energy, etc.) only when it is awake and not while sleeping. Energy complexity has been studied for various fundamental problems with respect to minimizing the maximum (worst-case) or the average number of rounds a node is awake. It has been shown that the energy complexities of several fundamental problems such as leader election (LE), broadcast, Minimum Spanning Tree (MST), Maximal Independent Set (MIS) is exponentially smaller compared to their respective best-possible round complexities in the standard CONGEST model (where nodes can only send messages of small size). This raises a fundamental question of whether such significant energy gains are possible for many other fundamental problems. Our main contribution is a general and powerful technique for showing energy lower bounds using information theory. It gives almost a "plug-in" way to show energy lower bounds for various problems in the standard CONGEST model. Our information-theoretic technique allows us to leverage known lower bounds on communication complexity to obtain new, almost optimal (up to logarithmic factors) polynomial (in $n$) lower bounds on energy complexity --- for both worst-case and average-case --- for fundamental graph problems such as triangle enumeration, All-Pairs Shortest Paths (APSP), diameter computation, minimum weight cycle, Maximum Independent Set (MaxIS), Minimum Dominating Set (MinDS), Minimum Vertex Cover (MinVC). The energy lower bounds of these problems match their respective round lower bounds, implying that one cannot obtain any significant gains in energy complexity.

Authors: Fabien Dufoulon, Gopal Pandurangan, Peter Robinson

There has been a significant recent interest in designing distributed algorithms in the SLEEPING model that minimize the {energy (a.k.a awake) complexity, which measures the number of rounds a node is awake during the algorithm. A node spends non-trivial resources (messages, energy, etc.) only when it is awake and not while sleeping. Energy complexity has been studied for various fundamental problems with respect to minimizing the maximum (worst-case) or the average number of rounds a node is awake. It has been shown that the energy complexities of several fundamental problems such as leader election (LE), broadcast, Minimum Spanning Tree (MST), Maximal Independent Set (MIS) is exponentially smaller compared to their respective best-possible round complexities in the standard CONGEST model (where nodes can only send messages of small size). This raises a fundamental question of whether such significant energy gains are possible for many other fundamental problems. Our main contribution is a general and powerful technique for showing energy lower bounds using information theory. It gives almost a "plug-in" way to show energy lower bounds for various problems in the standard CONGEST model. Our information-theoretic technique allows us to leverage known lower bounds on communication complexity to obtain new, almost optimal (up to logarithmic factors) polynomial (in $n$) lower bounds on energy complexity --- for both worst-case and average-case --- for fundamental graph problems such as triangle enumeration, All-Pairs Shortest Paths (APSP), diameter computation, minimum weight cycle, Maximum Independent Set (MaxIS), Minimum Dominating Set (MinDS), Minimum Vertex Cover (MinVC). The energy lower bounds of these problems match their respective round lower bounds, implying that one cannot obtain any significant gains in energy complexity.

Minimizing the Makespan Approximately on Two Identical Parallel Machines with a Loading--Unloading Server

from arXiv: Data Structures and Algorithms

Authors: Keramat Hasani, Frank Werner

We study makespan minimisation on two identical parallel machines that share a single server for both loading and unloading. Each job must be loaded, processed without interruption on its assigned machine, and unloaded immediately after processing, with a common positive integer duration for all loading and unloading operations. We prove that the decision problem is NP-complete for every fixed server-operation duration and strongly NP-complete when this duration is part of the input. We then analyse ordinary list scheduling and the longest-processing-time rule in the non-unit setting. List scheduling has a tight supremum ratio of two. For the longest-processing-time rule, we obtain the exact worst-case ratio when all processing times are at least the server-operation duration, and derive new parameter-dependent lower and upper bounds for unrestricted instances. The results show that both processing-time granularity and blocking generated by short jobs shape the approximation behaviour of the common-server problem.

Authors: Keramat Hasani, Frank Werner

We study makespan minimisation on two identical parallel machines that share a single server for both loading and unloading. Each job must be loaded, processed without interruption on its assigned machine, and unloaded immediately after processing, with a common positive integer duration for all loading and unloading operations. We prove that the decision problem is NP-complete for every fixed server-operation duration and strongly NP-complete when this duration is part of the input. We then analyse ordinary list scheduling and the longest-processing-time rule in the non-unit setting. List scheduling has a tight supremum ratio of two. For the longest-processing-time rule, we obtain the exact worst-case ratio when all processing times are at least the server-operation duration, and derive new parameter-dependent lower and upper bounds for unrestricted instances. The results show that both processing-time granularity and blocking generated by short jobs shape the approximation behaviour of the common-server problem.