Theory of Computing Report

In this post, we study non-uniform agreement and weak validity under synchronous networks with general omission failures, where faulty parties may lose both incoming and outgoing messages. In this model, agreement is required only among non-faulty parties. Omission faulty parties may disagree and validity is weak: the output must be...

Authors: John M. Hitchcock, Adewale Sekoni, Hadi Shafei

This paper makes two primary contributions. First, we introduce the concept of counting martingales and use it to define counting measures, counting dimensions, and counting strong dimensions. Second, we apply these new tools to strengthen previous circuit lower bounds. Resource-bounded measure and dimension have traditionally focused on deterministic time and space bounds. We use counting complexity classes to develop resource-bounded counting measures and dimensions. Counting martingales are constructed using functions from the #P, SpanP, and GapP complexity classes. We show that counting martingales capture many martingale constructions in complexity theory. The resulting counting measures and dimensions are intermediate in power between the standard time-bounded and space-bounded notions, enabling finer-grained analysis where space-bounded measures are known, but time-bounded measures remain open. For example, we show that BPP has #P-dimension 0 and BQP has GapP-dimension 0. As our main application, we improve circuit-size lower bounds. Lutz (1992) strengthened Shannon's classic $(1-\epsilon)\frac{2^n}{n}$ lower bound (1949) to PSPACE-measure, showing that almost all problems require circuits of size $\frac{2^n}{n}\left(1+\frac{\alpha \log n}{n}\right)$, for any $\alpha < 1$. We extend this result to SpanP-measure, with a proof that uses a connection through the Minimum Circuit Size Problem (MCSP) to construct a counting martingale. Our results imply that the stronger lower bound holds within the third level of the exponential-time hierarchy, whereas previously, it was only known in ESPACE. We study the #P-dimension of classical circuit complexity classes and the GapP-dimension of quantum circuit complexity classes. We also show that if one-way functions exist, then #P-dimension is strictly more powerful than P-dimension.

Authors: Marius Huber, Patrick Schnider

The Dowker complex $\mathrm{D}_{R}(X,Y)$ is a simplicial complex capturing the topological interplay between two finite sets $X$ and $Y$ under some relation $R\subseteq X\times Y$. While its definition is asymmetric, the famous Dowker duality states that $\mathrm{D}_{R}(X,Y)$ and $\mathrm{D}_{R}(Y,X)$ have homotopy equivalent geometric realizations. We introduce the Dowker-Rips complex $\mathrm{DR}_{R}(X,Y)$, defined as the flagification of the Dowker complex or, equivalently, as the maximal simplicial complex whose $1$-skeleton coincides with that of $\mathrm{D}_{R}(X,Y)$. This is motivated by applications in topological data analysis, since as a flag complex, the Dowker-Rips complex is less expensive to compute than the Dowker complex. While the Dowker duality does not hold for Dowker-Rips complexes in general, we show that one still has that $\mathrm{H}_{i}(\mathrm{DR}_{R}(X,Y))\cong\mathrm{H}_{i}(\mathrm{DR}_{R}(Y,X))$ for $i=0,1$. We further show that this weakened duality extends to the setting of persistent homology, and quantify the ``failure" of the Dowker duality in homological dimensions higher than $1$ by means of interleavings. This makes the Dowker-Rips complex a less expensive, approximate version of the Dowker complex that is usable in topological data analysis. Indeed, we provide a Python implementation of the Dowker-Rips complex and, as an application, we show that it can be used as a drop-in replacement for the Dowker complex in a tumor microenvironment classification pipeline. In that pipeline, using the Dowker-Rips complex leads to increase in speed while retaining classification performance.

Authors: Guanqun Ma, David Lenz, Hanqi Guo, Tom Peterka, Bei Wang

Implicit continuous models, such as functional models and implicit neural networks, are an increasingly popular method for replacing discrete data representations with continuous, high-order, and differentiable surrogates. These models offer new perspectives on the storage, transfer, and analysis of scientific data. In this paper, we introduce the first framework to directly extract complex topological features -- contours, Jacobi sets, and ridge-valley graphs -- from a type of continuous implicit model known as multivariate functional approximation (MFA). MFA replaces discrete data with continuous piecewise smooth functions. Given an MFA model as the input, our approach enables direct extraction of complex topological features from the model, without reverting to a discrete representation of the model. Our work is easily generalizable to any continuous implicit model that supports the queries of function values and high-order derivatives. Our work establishes the building blocks for performing topological data analysis and visualization on implicit continuous models.

Authors: Steven van den Broek, Wouter Meulemans, Andreas Reimer, Bettina Speckmann

Chorematic diagrams are highly reduced schematic maps of geospatial data and processes. They can visually summarize complex situations using only a few simple shapes (choremes) placed upon a simplified base map. Due to the extreme reduction of data in chorematic diagrams, they tend to be produced manually; few automated solutions exist. In this paper we consider the algorithmic problem of summarizing classed region maps, such as choropleth or land use maps, using a chorematic diagram with a single disk choreme. It is infeasible to solve this problem exactly for large maps. Hence, we propose several point sampling strategies and use algorithms for classed point sets to efficiently find the best disk that represents one of the classes. We implemented our algorithm and experimentally compared sampling strategies and densities. The results show that with the right sampling strategy, high-quality results can be obtained already with moderately sized point sets and within seconds of computation time.

Authors: Szymon Snoeck, Noah Bergam, Nakul Verma

To what extent is it possible to visualize high-dimensional datasets in a two- or three-dimensional space? We reframe this question in terms of embedding $n$-vertex graphs (representing the neighborhood structure of the input points) into metric spaces of low doubling dimension $d$, in such a way that maintains the separation between neighbors and non-neighbors. This seemingly lax embedding requirement is surprisingly difficult to satisfy. Our investigation shows that an overwhelming fraction of graphs require $d = \Omega(\log n)$. Even when considering sparse regular graphs, the situation does not improve, as an overwhelming fraction of such graphs requires $d= \Omega(\log n / \log\log n)$. The landscape changes dramatically when embedding into normed spaces. In particular, all but a vanishing fraction of graphs demand $d=\Theta(n)$. Finally, we study the implications of these results for visualizing data with intrinsic cluster structure. We find that graphs produced from a planted partition model with $k$ clusters on $n$ points typically require $d=\Omega(\log n)$, even when the cluster structure is salient. These results challenge the aspiration that constant-dimensional visualizations can faithfully preserve neighborhood structure.

Authors: Arpon Basu, Pravesh K. Kothari, Yang P. Liu, Raghu Meka

In this paper, we revisit spectral sparsification for sums of arbitrary positive semidefinite (PSD) matrices. Concretely, for any collection of PSD matrices $\mathcal{A} = \{A_1, A_2, \ldots, A_r\} \subset \mathbb{R}^{n \times n}$, given any subset $T \subseteq [r]$, our goal is to find sparse weights $\mu \in \mathbb{R}_{\geq 0}^r$ such that $(1 - \epsilon) \sum_{i \in T} A_i \preceq \sum_{i \in T} \mu_i A_i \preceq (1 + \epsilon) \sum_{i \in T} A_i.$ This generalizes spectral sparsification of graphs which corresponds to $\mathcal{A}$ being the set of Laplacians of edges. It also captures sparsifying Cayley graphs by choosing a subset of generators. The former has been extensively studied with optimal sparsifiers known. The latter has received attention recently and was solved for a few special groups (e.g., $\mathbb{F}_2^n$). Prior work shows any sum of PSD matrices can be sparsified down to $O(n)$ elements. This bound however turns out to be too coarse and in particular yields no non-trivial bound for building Cayley sparsifiers for Cayley graphs. In this work, we develop a new, instance-specific (i.e., specific to a given collection $\mathcal{A}$) theory of PSD matrix sparsification based on a new parameter $N^*(\mathcal{A})$ which we call connectivity threshold that generalizes the threshold of the number of edges required to make a graph connected. Our main result gives a sparsifier that uses at most $O(\epsilon^{-2}N^*(\mathcal{A}) (\log n)(\log r))$ matrices and is constructible in randomized polynomial time. We also show that we need $N^*(\mathcal{A})$ elements to sparsify for any $\epsilon < 0.99$. As the main application of our framework, we prove that any Cayley graph can be sparsified to $O(\epsilon^{-2}\log^4 N)$ generators. Previously, a non-trivial bound on Cayley sparsifiers was known only in the case when the group is $\mathbb{F}_2^n$.

Authors: Jun-Ting Hsieh, Daniel Z. Lee, Sidhanth Mohanty, Aaron Putterman, Rachel Yun Zhang

A classic result in graph theory, due to Batson, Spielman, and Srivastava (STOC 2009) shows that every graph admits a $(1 \pm \varepsilon)$ cut (or spectral) sparsifier which preserves only $O(n / \varepsilon^2)$ reweighted edges. However, when applying this result to \emph{Cayley graphs}, the resulting sparsifier is no longer necessarily a Cayley graph -- it can be an arbitrary subset of edges. Thus, a recent line of inquiry, and one which has only seen minor progress, asks: for any group $G$, do all Cayley graphs over the group $G$ admit sparsifiers which preserve only $\mathrm{polylog}(|G|)/\varepsilon^2$ many re-weighted generators? As our primary contribution, we answer this question in the affirmative, presenting a proof of the existence of such Cayley graph spectral sparsifiers, along with an efficient algorithm for finding them. Our algorithm even extends to \emph{directed} Cayley graphs, if we instead ask only for cut sparsification instead of spectral sparsification. We additionally study the sparsification of linear equations over non-abelian groups. In contrast to the abelian case, we show that for non-abelian valued equations, super-polynomially many linear equations must be preserved in order to approximately preserve the number of satisfied equations for any input. Together with our Cayley graph sparsification result, this provides a formal separation between Cayley graph sparsification and sparsifying linear equations.

Authors: Yang Hu

In the online sorting problem, we have an array $A$ of $n$ cells, and receive a stream of $n$ items $x_1,\dots,x_n\in [0,1]$. When an item arrives, we need to immediately and irrevocably place it into an empty cell. The goal is to minimize the sum of absolute differences between adjacent items, which is called the \emph{cost} of the algorithm. It has been shown by Aamand, Abrahamsen, Beretta, and Kleist (SODA 2023) that when the stream $x_1,\dots,x_n$ is generated adversarially, the optimal cost bound for any deterministic algorithm is $\Theta(\sqrt{n})$. In this paper, we study the stochastic version of online sorting, where the input items $x_1,\dots,x_n$ are sampled uniformly at random. Despite the intuition that the stochastic version should yield much better cost bounds, the previous best algorithm for stochastic online sorting by Abrahamsen, Bercea, Beretta, Klausen and Kozma (ESA 2024) only achieves $\tilde{O}(n^{1/4})$ cost, which seems far from optimal. We show that stochastic online sorting indeed allows for much more efficient algorithms, by presenting an algorithm that achieves expected cost $\log n\cdot 2^{O(\log^* n)}$. We also prove a cost lower bound of $\Omega(\log n)$, thus show that our algorithm is nearly optimal.

Authors: Yotam Kenneth-Mordoch, Robert Krauthgamer

In the fully dynamic edge connectivity problem, the input is a simple graph $G$ undergoing edge insertions and deletions, and the goal is to maintain its edge connectivity, denoted $\lambda_G$. We present two simple randomized algorithms solving this problem. The first algorithm maintains the edge connectivity in worst-case update time $\tilde{O}(n)$ per edge update, matching the known bound but with simpler analysis. Our second algorithm achieves worst-case update time $\tilde{O}(n/\lambda_G)$ and worst-case query time $\tilde{O}(n^2/\lambda_G^2)$, which is the first algorithm with worst-case update and query time $o(n)$ for large edge connectivity, namely, $\lambda_G = \omega(\sqrt{n})$.

Authors: Daniel Brous, David Shmoys

In redistricting litigation, effective enforcement of the Voting Rights Act has often involved providing the court with districting plans that display a larger number of majority-minority districts than the current proposal (as was true, for example, in what followed Allen v. Milligan concerning the congressional districting plan for Alabama in 2023). Recent work by Cannon et al. proposed a heuristic algorithm for generating plans to optimize majority-minority districts, which they called short bursts; that algorithm relies on a sophisticated random walk over the space of all plans, transitioning in bursts, where the initial plan for each burst is the most successful plan from the previous burst. We propose a method based on integer programming, where we build upon another previous work, the stochastic hierarchical partitioning algorithm, which heuristically generates a robust set of potential districts (viewed as columns in a standard set partitioning formulation); that approach was designed to optimize a different notion of fairness across a statewide plan. We design a new column generation algorithm to find plans via integer programming that outperforms short bursts on multiple data sets in generating statewide plans with significantly more majority-minority districts. These results also rely on a new local re-optimization algorithm to iteratively improve on any baseline solution, as well as an algorithm to increase the compactness of districts in plans generated (without impacting the number of majority-minority districts).

Authors: Honghao Lin, Hoai-An Nguyen, William Swartworth, David P. Woodruff

We study $\ell_p$ sampling and frequency moment estimation in a single-pass insertion-only data stream. For $p \in (0,2)$, we present a nearly space-optimal approximate $\ell_p$ sampler that uses $\widetilde{O}(\log n \log(1/\delta))$ bits of space and for $p = 2$, we present a sampler with space complexity $\widetilde{O}(\log^2 n \log(1/\delta))$. This space complexity is optimal for $p \in (0, 2)$ and improves upon prior work by a $\log n$ factor. We further extend our construction to a continuous $\ell_p$ sampler, which outputs a valid sample index at every point during the stream. Leveraging these samplers, we design nearly unbiased estimators for $F_p$ in data streams that include forget operations, which reset individual element frequencies and introduce significant non-linear challenges. As a result, we obtain near-optimal algorithms for estimating $F_p$ for all $p$ in this model, originally proposed by Pavan, Chakraborty, Vinodchandran, and Meel [PODS'24], resolving all three open problems they posed. Furthermore, we generalize this model to what we call the suffix-prefix deletion model, and extend our techniques to estimate entropy as a corollary of our moment estimation algorithms. Finally, we show how to handle arbitrary coordinate-wise functions during the stream, for any $g \in \mathbb{G}$, where $\mathbb{G}$ includes all (linear or non-linear) contraction functions.

Authors: Hannes Ihalainen, Dieter Vandesande, André Schidler, Jeremias Berg, Bart Bogaerts, Matti Järvisalo

The implicit hitting set (IHS) approach offers a general framework for solving computationally hard combinatorial optimization problems declaratively. IHS iterates between a decision oracle used for extracting sources of inconsistency and an optimizer for computing so-called hitting sets (HSs) over the accumulated sources of inconsistency. While the decision oracle is language-specific, the optimizers is usually instantiated through integer programming. We explore alternative algorithmic techniques for hitting set optimization based on different ways of employing pseudo-Boolean (PB) reasoning as well as stochastic local search. We extensively evaluate the practical feasibility of the alternatives in particular in the context of pseudo-Boolean (0-1 IP) optimization as one of the most recent instantiations of IHS. Highlighting a trade-off between efficiency and reliability, while a commercial IP solver turns out to remain the most effective way to instantiate HS computations, it can cause correctness issues due to numerical instability; in fact, we show that exact HS computations instantiated via PB reasoning can be made competitive with a numerically exact IP solver. Furthermore, the use of PB reasoning as a basis for HS computations allows for obtaining certificates for the correctness of IHS computations, generally applicable to any IHS instantiation in which reasoning in the declarative language at hand can be captured in the PB-based proof format we employ.

Authors: Anne Driemel, Jan Höckendorff, Ioannis Psarros, Christian Sohler

A time series of complexity $m$ is a sequence of $m$ real valued measurements. The discrete Fr\'echet distance $d_{dF}(x,y)$ is a distance measure between two time series $x$ and $y$ of possibly different complexity. Given a set of $n$ time series represented as $m$-dimensional vectors over the reals, the $(k,\ell)$-median problem under discrete Fr\'echet distance aims to find a set $C$ of $k$ time series of complexity $\ell$ such that $$\sum_{x\in P} \min_{c\in C} d_{dF}(x,c)$$ is minimized. In this paper, we give the first near-linear time $(1+\varepsilon)$-approximation algorithm for this problem when $\ell$ and $\varepsilon$ are constants but $k$ can be as large as $\Omega(n)$. We obtain our result by introducing a new dimension reduction technique for discrete Fr\'echet distance and then adapt an algorithm of Cohen-Addad et al. (J. ACM 2021) to work on the dimension-reduced input. As a byproduct we also improve the best coreset construction for $(k,\ell)$-median under discrete Fr\'echet distance (Cohen-Addad et al., SODA 2025) and show that its size can be independent of the number of input time series \emph{ and } their complexity.

Authors: Mengxue Jia, Zhihua Allen-Zhao, You Zhao, Sanyang Liu

Multiview clustering (MC) aims to group samples using consistent and complementary information across various views. The subspace clustering, as a fundamental technique of MC, has attracted significant attention. In this paper, we propose a novel joint sparse self-representation learning model for MC, where a featured difference is the extraction of view-specific local information by introducing cardinality (i.e., $\ell_0$-norm) constraints instead of Graph-Laplacian regularization. Specifically, under each view, cardinality constraints directly restrict the samples used in the self-representation stage to extract reliable local and global structure information, while the low-rank constraint aids in revealing a global coherent structure in the consensus affinity matrix during merging. The attendant challenge is that Augmented Lagrange Method (ALM)-based alternating minimization algorithms cannot guarantee convergence when applied directly to our nonconvex, nonsmooth model, thus resulting in poor generalization ability. To address it, we develop an alternating quadratic penalty (AQP) method with global convergence, where two subproblems are iteratively solved by closed-form solutions. Empirical results on six standard datasets demonstrate the superiority of our model and AQP method, compared to eight state-of-the-art algorithms.

Authors: Qiming Cui, Michael Dinitz

We study the optimal solution to a general two-slope ski rental problem with a tail risk, i.e., the chance of the competitive ratio exceeding a value $\gamma$ is bounded by $\delta$. This extends the recent study of tail bounds for ski rental by [Dinitz et al. SODA 2024] to the two-slope version defined by [Lotker et al. IPL 2008]. In this version, even after "buying," we must still pay a rental cost at each time step, though it is lower after buying. This models many real-world "rent-or-buy" scenarios where a one-time investment decreases (but does not eliminate) the per-time cost. Despite this being a simple extension of the classical problem, we find that adding tail risk bounds creates a fundamentally different solution structure. For example, in our setting there is a possibility that we never buy in an optimal solution (which can also occur without tail bounds), but more strangely (and unlike the case without tail bounds or the classical case with tail bounds) we also show that the optimal solution might need to have nontrivial probabilities of buying even at finite points beyond the time corresponding to the buying cost. Moreover, in many regimes there does not exist a unique optimal solution. As our first contribution, we develop a series of structure theorems to characterize some features of optimal solutions. The complex structure of optimal solutions makes it more difficult to develop an algorithm to compute such a solution. As our second contribution, we utilize our structure theorems to design two algorithms: one based on a greedy algorithm combined with binary search that is fast but yields arbitrarily close to optimal solutions, and a slower algorithm based on linear programming which computes exact optimal solutions.

Authors: Lorenzo Beretta, Vincent Cohen-Addad, Rajesh Jayaram, Erik Waingarten

We give a reduction from $(1+\varepsilon)$-approximate Earth Mover's Distance (EMD) to $(1+\varepsilon)$-approximate Closest Pair (CP). As a consequence, we improve the fastest known approximation algorithm for high-dimensional EMD. Here, given $p\in [1, 2]$ and two sets of $n$ points $X,Y \subseteq (\mathbb R^d,\ell_p)$, their EMD is the minimum cost of a perfect matching between $X$ and $Y$, where the cost of matching two vectors is their $\ell_p$ distance. Further, CP is the basic problem of finding a pair of points realizing $\min_{x \in X, y\in Y} ||x-y||_p$. Our contribution is twofold: we show that if a $(1+\varepsilon)$-approximate CP can be computed in time $n^{2-\phi}$, then a $1+O(\varepsilon)$ approximation to EMD can be computed in time $n^{2-\Omega(\phi)}$; plugging in the fastest known algorithm for CP [Alman, Chan, Williams FOCS'16], we obtain a $(1+\varepsilon)$-approximation algorithm for EMD running in time $n^{2-\tilde{\Omega}(\varepsilon^{1/3})}$ for high-dimensional point sets, which improves over the prior fastest running time of $n^{2-\Omega(\varepsilon^2)}$ [Andoni, Zhang FOCS'23]. Our main technical contribution is a sublinear implementation of the Multiplicative Weights Update framework for EMD. Specifically, we demonstrate that the updates can be executed without ever explicitly computing or storing the weights; instead, we exploit the underlying geometric structure to perform the updates implicitly.

Authors: Matthew Fahrbach, Mehrdad Ghadiri

We prove that the classic approximation guarantee for the higher-order singular value decomposition (HOSVD) is tight by constructing a tensor for which HOSVD achieves an approximation ratio of $N/(1+\varepsilon)$, for any $\varepsilon > 0$. This matches the upper bound of De Lathauwer et al. (2000a) and shows that the approximation ratio of HOSVD cannot be improved. Using a more advanced construction, we also prove that the approximation guarantees for the ST-HOSVD algorithm of Vannieuwenhoven et al. (2012) and higher-order orthogonal iteration (HOOI) of De Lathauwer et al. (2000b) are tight by showing that they can achieve their worst-case approximation ratio of $N / (1 + \varepsilon)$, for any $\varepsilon > 0$.

Authors: Qiheng Lu, Nicholas D. Sidiropoulos, Aritra Konar

Dense subgraph mining is a fundamental technique in graph mining, commonly applied in fraud detection, community detection, product recommendation, and document summarization. In such applications, we are often interested in identifying communities, recommendations, or summaries that reflect different constituencies, styles or genres, and points of view. For this task, we introduce a new variant of the Densest $k$-Subgraph (D$k$S) problem that incorporates the attribute values of vertices. The proposed Vertex-Attribute-Constrained Densest $k$-Subgraph (VAC-D$k$S) problem retains the NP-hardness and inapproximability properties of the classical D$k$S. Nevertheless, we prove that a suitable continuous relaxation of VAC-D$k$S is tight and can be efficiently tackled using a projection-free Frank--Wolfe algorithm. We also present an insightful analysis of the optimization landscape of the relaxed problem. Extensive experimental results demonstrate the effectiveness of our proposed formulation and algorithm, and its ability to scale up to large graphs. We further elucidate the properties of VAC-D$k$S versus classical D$k$S in a political network mining application, where VAC-D$k$S identifies a balanced and more meaningful set of politicians representing different ideological camps, in contrast to the classical D$k$S solution which is unbalanced and rather mundane.

If you’re out there on the socials, everyone is worried that the GPT5 release shows we’re finally “hitting a wall” with LLM progress. My dear friend and Twitter addict Dimitris Papailiopoulos exclaimed:

“It is funny that we've accepted the diminishing returns of scaling laws as the only roadmap to intelligence. And by funny I mean sad.”

Shital Shah devastatingly replied to Dimitris with the pedagogical thought experiment:

“It's year 2018. You walk into Algorithms and Data Structures class. You tell students to just use whatever algorithm first comes to their mind, throw in a ton of compute and call it scaling. ‘That's a bitter lesson for you all’, you say, and leave the classroom.”

Shital’s tweet had me reeling for multiple reasons. It’s August, so I have been thinking about what I am going to teach this fall semester. I’m a bit worried I agreed more than disagreed with his assessment of the future of computer science pedagogy. To explain why, I first need to unpack the bitter lesson meme and how it has captured computer science.

In case you don’t know, “The Bitter Lesson” is the title of a short blog post by Turing Laureate Richard Sutton from 2019. The bitter lesson is one of those researcher magic mirrors. People see whatever they want to see. Like much of Sutton’s writing, it’s vague and nontechnical, allowing for many interpretations. Shital motivated me to go back and stare in that mirror, actually reading it for the first time in years.

Sutton begins:

“The biggest lesson that can be read from 70 years of AI research is that general methods that leverage computation are ultimately the most effective, and by a large margin. “

What does it mean to leverage computation? He never says. What he does say is “The ultimate reason for this is Moore's law,...” which is an interesting lesson for us in 2025 since we’re well past Moore’s Law actually delivering. Moore’s Law used to mean that if you had an algorithm that needed 2x your current computing, you just had to wait two years, and that computing would appear magically at the Apple Store. Today, we’re in the interesting phase where spending on AI infrastructure has to grow exponentially to keep up with the expectations set by Moore’s Law. Given that we’re in such a competitive bubble driving up NVIDIA stock prices, the costs probably have to more than double every two years. That’s a different sort of bitter lesson that, like with all speculative bubbles, we’ll have to deal with eventually.

Sutton continues:

“Most AI research has been conducted as if the computation available to the agent were constant (in which case leveraging human knowledge would be one of the only ways to improve performance)”

This passage reveals a salient perspective of old school AI researchers that most people miss when reading the essay. I’ve been engaged in machine learning research for over twenty years. I never thought this way. No one I ever talked to at N(eur)IPS ever thought this way. However, when I was in grad school, “AI” researchers did think this way. I always thought those people were weird (yes, I’m talking about Marvin Minsky and his acolytes).

Indeed, that Sutton’s Lesson was Bitter suggests he wasn’t a fan of computer science. The only intellectual through line in computer science is a faster computer is always a better computer. Every course in computer science, except for HCI and good old fashioned AI, is obsessed with computation being a variable that grows. “Scaling is all you need” is the motto of computer science.

This motto doesn’t mean you use crappy algorithms, but it is why computing researchers spend so much time thinking about scaling. Except in very special resource constrained cases, the goal is always to build algorithms that minimize computation time when presented with larger tasks.

Leaving this particular quirk of thinking aside, the heart of Sutton’s argument is the next passage:

“Seeking an improvement that makes a difference in the shorter term, researchers seek to leverage their human knowledge of the domain, but the only thing that matters in the long run is the leveraging of computation. These two need not run counter to each other, but in practice they tend to. Time spent on one is time not spent on the other.”

I’m not sure how you leverage computation without leveraging human knowledge. Certainly, if you look at the language people use in machine learning, it’s loaded with all sorts of speculations about human knowledge. The field still loves anthropomorphically loaded words like intelligence, learning, critic, teacher, student, curriculum, etc. The best evidence that hyperscaling AI researchers aren’t thinking seriously about leveraging computation is their love for reinforcement learning. Every theoretical and practical result in reinforcement learning shows that it doesn’t leverage computation. People like reinforcement learning because of the ethos, not because it scales well.

I could write another thousand words about the confusing examples of parlor games and supervised learning that Sutton presents as evidence of what taught him his lesson. I’d be happy to do this in another post if people are interested. However, I want to come back to the points raised by Shital and Dimitris.

The Bitter Lesson has been used to motivate the scale at all costs mentality behind AI companies. It’s undeniable that scale has been a dominant trend and that computational search is powerful. Devoting effort to scale isn’t the worst thing in the world. I am guilty of devoting a lot of time to this in the 2010s.

It’s only been 6 years since Sutton’s essay, and I’m sure we’ll continue to hyperscale until everyone runs out of money. Maybe we’re in the MMT era of computing and we can keep building bigger data centers and pursuing worse algorithms because that’s what the market rewards. Everyone in computer science has bought into the pact of evaporating oceans for better coding assistants. But scaling is all you need until you hit diminishing returns. Overindexing on the bitter lesson is a commitment to nihilism. I’m not sure this is a sustainable path for industry. It’s assuredly not the way to sustain a field.

Subscribe now

By Ben Recht

Today’s post, by Diptangshu Sen and Juba Ziani, is about strategic classification: the interesting setting where incentives and rational agents enter the learning process. Read on to learn more!

---

A gentle introduction to Strategic Classification

Machine learning systems are ubiquitous in many aspects of our lives. In recent years, they have been increasingly used to assist and sometimes even entirely replace human decision-making. AI tools have found large-scale use in many high-stakes settings that impact human lives long-term, like loan applications, university admissions, and criminal justice to name a few.

These systems may be complicated, but at their core, they usually function in the following way. First, a machine learning algorithm takes an agent’s features as input — for example, an individual’s financial history if they are going up for a mortgage. Then, the algorithm maps these features to an output in the form of either i) a score (e.g., credit scores in the United States) or ii) a decision (e.g., whether an individual is approved for a loan). In the second case, we talk about a positive classification outcome if the applicant gets the loan, and a negative classification outcome if they do not. Typically, much of these AI tools make the (implicit or explicit) assumption that the input data is independently and identically (i.i.d.) distributed. The i.i.d. assumption is central to guarantees like unbiasedness and generalization that these tools often claim to provide.

Unfortunately, real life is not this clean. Even absent human behavior, typical datasets do not satisfy the i.i.d. assumption: datasets are often inherently biased, incomplete, and unbalanced due to uneven data collection and sampling biases; data points may be correlated; labels and annotations (especially when done by humans) may be inconsistent; test and deployment data might be from a different distribution from the training data; datasets are not static and may evolve over time; etc. While the previous list is non-exhaustive, it aims to give the reader a sense of the variety and the complexity of reasons why typical assumptions in machine learning may fail.

The focus of this blog is, however, to tie this failure to human behavior. In particular, when faced with high-stakes decisions that can inform their lives or careers in the long term, humans tend to be strategic. By strategic, we mean that an individual may not face the classifier at face value and accept whatever decisions comes out of it. Instead, they may try to influence and steer the decision-making tool towards a positive scoring or classification outcome. In particular, individuals may try to modify their features in order to improve their outcomes — e.g., opening new credit card accounts to lower credit usage, which would improve their credit score (in fact, a quick internet search yields dozens of websites giving individuals financial advice on how to improve their credit score at minimal cost and effort). Change in features induces a distribution shift in the input data faced by the classifier, meaning it may be making decisions on data that significantly differs from its training data, leading to inaccuracies, loss of efficiency, and potential societal harms. The area of research that aims to understand how strategic human behavior affects classification outcomes was pioneered by Hardt et al. (2016) and coined Strategic Classification.

Beyond Traditional Strategic Classification

The current blog aims to study recent developments in strategic classification that aim to take it one step closer to reality, and focuses on our recent work Efthymiou et al. (2025). This mandates some context: what is the current state of strategic classification, and what are the current gaps with reality? We identify two main gaps below that our work aims to address.

Gaming vs Improvement. The initial view of Hardt et al. (2016) was that humans systematically try to game the system, i.e., humans try to “lie” about their features in order to trick the classifier into making wrong decisions (in their favor). This can, for example, be seen as a student cheating on a problem set or an individual artificially inflating their credit score by opening dummy credit card accounts. However, agents may modify their features in ways that are, in fact, valuable: a student may decide to invest more effort reviewing the material or engaging with a course to improve their grade; a loan applicant may start paying their bills consistently and on time to increase their credit score. In the space of strategic classification, it is important to distinguish what is gaming the classifier and what is investing in legitimate improvements to pass the classifier.

This distinction between gaming vs improvement has been studied in the literature (Miller et al. (2020), Shavit et al. (2020), Kleinberg and Raghavan (2020), Bechavod et al. (2021)). One aspect that all these works have in common is the way they model this important distinction: i.e., via a causal graph. Causality provides a natural framework to understand the causes behind changes in features. For example, a student may have improved their performance in class, but this may either be because they studied harder or because they cheated on homeworks. Causality allows us to present such potentially unobserved actions (cheating vs studying) as causal roots of the observed features (improved performance) faced by a classifier. Our recent work adopts such a causal framework.

Our work proposes a slightly different distinction than gaming vs improvement, instead focusing on desirable and undesirable effort. While these concepts are closely connected (gaming can often be seen as undesirable), the concepts do not exactly map one-to-one. Even some forms of improvement might be considered undesirable by a learner; for a concrete example, see our experimental case study which focuses on lowering the risk of cardiovascular disease (CVD)—there, we take a common view in the medical field that while both pharmaceutical and lifestyle interventions can both significantly lower one’s risk of CVD, lifestyle interventions, largely free of side effects, are preferred as a first line of prevention.

Incomplete Information. Recently, there has been some interest in studying the problem of strategic classification when agents have imperfect or incomplete information about the classifier (Ghalme et al. (2021), Bechavod et al. (2022), Cohen et al. (2024), Ebrahimi et al. (2024)). This is highly relevant in practice — in most real-life settings, the deployed classifier is unknown or only partially known to agents for a multitude of reasons. This may be because of privacy reasons that prevent model or training data transparency; high model complexity (think neural nets or large language models); or the model being proprietary. Think for example of credit scoring rules; it is generally understood which features are important (length of credit history; number of credit accounts; history of repayment of loans or credit; borrowing history; credit utilization; etc.), but it is not fully understood i) how each of these features are rated and ii) how they are put together into a single numerical score.

Another major source of uncertainty, that has not been studied in the context of strategic classification to the best of our knowledge, arises from agents not fully knowing the causal relationship between features. Going back to our running case study, an individual may know that reducing their alcohol consumption would lower their risk of CVD, but may not know the exact strength of this causal relationship. In fact, there is still a lot of debate on whether obesity is a cause of CVD or a symptom of related metabolic conditions, and what the specific causal path between obesity and CVD is. This can in turn impede their ability to understand how the effort they invest translates into a change in features, and to choose a reliable course of action to improve their outcomes. To the best of our knowledge, our paper Efthymiou et al. (2025) is the first to propose a framework that can model agents with uncertainty about both the deployed classifier and the underlying causal graph.

Our Work (Efthymiou et al. (2025))

Problem Setting

Model. Each agent in our model is represented by a feature vector where is the dimension of the feature space . All features in are embedded on a causal graph which is assumed to be weighted, directed and acyclic. Each node of the graph represents a feature in , while each edge weight captures the degree to which effort investment in the out-node affects the value of the in-node (Figure 1).

Now, the principal or learner deploys a linear classifier which works as follows: for any agent with features , the classifier computes a score and classifies the agent a `PASS’ if (where is a pre-determined exogenous threshold). If however, an agent FAILS, the classifier informs her the gap by which she failed to help the agent take corrective action.

The agent’s decision problem is the following: Given , how does she modify her features in order to obtain a positive classification outcome? There are two aspects that make this decision non-trivial:

1. Since features are not independent, modifying one may directly or indirectly modify another feature. We measure the importance of a feature by its ability to affect other features. Intuitively, modifying an “important” feature appears to be more beneficial because it creates a cascading effect by simultaneously improving many features. We capture this phenomenon using a contribution matrix . The contribution matrix is very useful because it helps to map any effort vector to change in feature vector via a linear transformation, i.e., . We also show that can be computed efficiently using the adjacency matrix of the causal graph.
2. The other aspect is that investing any effort incurs cost. Additionally, there may be cost-heterogeneity across features, i.e., it may cost more to invest unit effort into some features compared to others. For instance, in the earlier loan example, paying off existing debts in a timely manner requires consistent effort on the part of the agent over a long period, while opening new credit card accounts often only requires a few clicks. In our work, we primarily use weighted -norm costs () for agents:

.

The agent’s goal is, therefore, to find the optimal effort vector that minimizes her cost while reliably ensuring a positive classification outcome.

Desirable vs Undesirable Effort Profiles. We have already motivated why all effort profiles are not the same — in the sense that some may be more desirable than others. The principal (entity who owns/deploys the classifier) naturally has incentives to design classifiers the induce desirable effort from agents. The principal, in our setting, gets to decide which types of efforts or which features they deem desirable; our framework makes no assumption about how the principal makes this decision, and takes the sets of desirable and undesirable features as an input.

We adopt one of the examples in (Kleinberg and Raghavan 2020) to illustrate this point. Consider a course where students are evaluated based on two metrics (in our context, features): their understanding of the course material and performance on tests/assignments. The professor’s goal is to incentivize students to invest more effort in the former (studying) rather than just the latter (rote-learning or cheating). There is a clear distinction between desirable and undesirable features from the professor’s (principal’s) perspective.

Formally, we model this as a partition of the set of features into the set of desirable features and the set of undesirable features . Subsequently, for a given , an effort profile can be deemed -desirable if and only if the magnitude of effort invested in desirable features is at least a fraction of the total magnitude of effort, i.e.,

where refers to the effort vector restricted only to coordinates in . This framework provides the principal a structured way to reason about desirability of agent effort profiles, and generalizes the distinction of gaming vs improvement from previous work. The concept of desirability can be further refined by giving different weights to different desirable vs undesirable features at no cost to the generality of our results.

Main Results

Uncertainty or lack of information plays a key role in determining how agents best respond to the classifier. This, in turn, directly influences how the principal should design the classifier if the final goal is to induce desirable effort from agents. To the best of our knowledge, our work is the first to bring uncertainty to the study of incentivizing desirable effort in causal strategic classification problems. In particular, we try to answer two key questions under complete and incomplete information settings:

1. How does a strategic agent choose their optimal effort profile?
2. What are the properties of the design space of “desirable” classifiers ?

There are two main sources of uncertainty in our setting: the principal’s classifier and the feature causal graph. We model uncertainty as agents having Gaussian priors over the classifier weights and the edge weights of the causal graph (while graph topology is assumed common knowledge). This model captures a significant spectrum of uncertainty, including complete information, partially incomplete information (uncertainty lies in either the classifier or the causal graph but not both), and total incomplete information (with uncertainty over both the classifier and the causal graph).

Complete Information. In this case, every agent has complete information about the classifier and the causal graph . This leads to the following optimization problem for the agent to choose her effort vector :

Recall that is the change in the agent’s feature vector when she invests effort . We provide a complete characterization of for all -norm cost functions with . Importantly, the cost function does have a major influence on the structure of the optimal effort profile. While it is sufficient for the agent to invest all effort in exactly one feature for weighted -norm costs, any other -norm cost with requires effort investment along all features with non-trivial importance. We build on these results to present our main theorem in the complete information setting, which fully characterizes the design space of -desirable classifiers for the principal for all -norm costs with :

Theorem 1. For any and a -norm cost function (where , the agent’s best response is always a -desirable effort profile if and only if:

1. when ; and
2. when ,

with and representing the set of desirable and undesirable features respectively.

This is a strong result in the sense that it provides the principal with necessary and sufficient conditions to find desirable classifiers for a broad class of agent cost functions. At this point, it is important to highlight the differences of our results with those of (Kleinberg and Raghavan 2020). For their main result, they show that given any effort profile, it is possible to check whether there exists a classifier that can induce that profile. Further, if such a classifier exists, then there must also exist a linear classifier which induces the same profile. This result relies on agents having linear cost functions, as is the case in (Kleinberg and Raghavan 2020). Our paper Efthymiou et al. (2025) further demonstrates that the picture changes when agent cost functions come from a slightly more general class (for example, all -norms with ). In particular, we show that agent best responses can now belong in the interior of the effort polytope (instead of just at corner points) which makes the principal’s task of finding a desirable classifier more challenging. Further, we introduce a general concept of desirability of effort profiles which enables us to identify conditions on the entire space of desirable classifiers that always induce such effort profiles, parametrized by .

Despite the closed-form characterization of the design space of “good” classifiers as provided in Theorem 1, this space is, quite unfortunately, non-convex in the general case. This is grim because it essentially implies that searching for desirable classifiers while also optimizing for accuracy is likely to be difficult. We show heuristic ways to circumvent this issue in the full version of our paper Efthymiou et al. (2025).

Incomplete Information. The incomplete information setting comes with a fresh set of challenges. First of all, unlike the complete information setting, it is no longer guaranteed that an agent can always pass the classifier with sufficient effort. The agent’s goal is, therefore, to choose an effort profile which passes the classifier with high probability. The introduction of probabilistic constraints makes the agent’s optimization problem significantly more involved. And if agents cannot best respond reliably, the question of finding classifiers that can induce them to behave desirably is even harder. We will briefly touch upon our main results in this setting.

While the agent’s optimization problem is non-convex (and likely to be hard) under total incomplete information, we show that there are some settings with partial uncertainty where the problem is still convex and can be solved efficiently. In special cases, the optimal effort profile also has a nice structure: the agent is found to prioritize effort investment in features with high mean importance (as expected) and actively avoid investing effort into features for which she has a high degree of uncertainty (high variance in importance). This enables us to characterize conditions on the classifier which can induce desirable agent behavior under uniform uncertainty across features. Perhaps more interestingly, this observation also generalizes to much broader settings with incomplete information which we demonstrate with numerical experiments using data from a medical study looking at cardio-vascular disease risk in adults.

Case Study. Our experimental study focuses on a setting where the principal is trying to reduce a population’s risk of cardiovascular disease (CVD). To do so, we identify relevant features and build a causal graph based on the recent medical study by Hasani et al. (2024). We exclude immutable features such as age, gender and ethnicity, focusing instead on eight modifiable features: alcohol consumption, diet, physical activity, smoking, diabetes mellitus (DM), hyperlipidemia (HPL), hypertension (HPT), and obesity. Among these, we designate as desirable the features corresponding to lifestyle interventions—namely, alcohol, diet, physical activity, and smoking over those corresponding to medical conditions or interventions (DM, HPL, HPT, and obesity).

This is a carefully chosen example because it highlights how our framework can model scenarios beyond just gaming and improvement. Observe that in this example, neither lifestyle interventions nor medical interventions can be classified as “gaming” behavior. However, lifestyle interventions are clearly more desirable because medical interventions are often associated with long-term unfavorable side effects. In our experiments, we focus exclusively on the incomplete information setting, exploring how different kinds of classifiers can induce hugely varying levels of desirable effort from strategic agents and quantifying the achievable limits of desirable behavior as a function of uncertainty. These experiments provide key insights on how a principal can incentivize desirable effort from agents, even under general settings of incomplete information. For more details, we refer the reader to our paper Efthymiou et al. (2025).

References

1. Yahav Bechavod, Katrina Ligett, Steven Wu, and Juba Ziani. Gaming helps! learning from strategic interactions in natural dynamics. In International Conference on Artificial Intelligence and Statistics, pages 1234–1242. PMLR, 2021.
2. Yahav Bechavod, Chara Podimata, Steven Wu, and Juba Ziani. Information discrepancy in strategic learning. In International Conference on Machine Learning, pages 1691–1715. PMLR, 2022.
3. Lee Cohen, Saeed Sharifi-Malvajerdi, Kevin Stangl, Ali Vakilian, and Juba Ziani. Bayesian strategic classification. arXiv preprint arXiv:2402.08758, 2024.
4. Raman Ebrahimi, Kristen Vaccaro, and Parinaz Naghizadeh. The double-edged sword of behavioral responses in strategic classification: Theory and user studies. arXiv preprint arXiv:2410.18066, 2024.
5. Valia Efthymiou, Chara Podimata, Diptangshu Sen, and Juba Ziani. Incentivizing desirable effort profiles in strategic classification: The role of causality and uncertainty. arXiv preprint arXiv:2502.06749, 2025.
6. Ganesh Ghalme, Vineet Nair, Itay Eilat, Inbal Talgam-Cohen, and Nir Rosenfeld. Strategic classification in the dark. In International Conference on Machine Learning, pages 3672– PMLR, 2021.
7. Moritz Hardt, Nimrod Megiddo, Christos Papadimitriou, and Mary Wootters. Strategic classification. In Proceedings of the 2016 ACM conference on innovations in theoretical computer science, pages 111–122, 2016.
8. Wan Shakira Rodzlan Hasani, Kamarul Imran Musa, Xin Wee Chen, and Kueh Yee Cheng. Constructing causal pathways for premature cardiovascular disease mortality using directed acyclic graphs with integrating evidence synthesis and expert knowledge. Scientific Reports, 14(1):28849, 2024.
9. Jon Kleinberg and Manish Raghavan. How do classifiers induce agents to invest effort strategically? ACM Transactions on Economics and Computation (TEAC), 8(4):1–23, 2020.
10. John Miller, Smitha Milli, and Moritz Hardt. Strategic classification is causal modeling in disguise. In International Conference on Machine Learning, pages 6917–6926. PMLR, 2020.
11. Yonadav Shavit, Benjamin Edelman, and Brian Axelrod. Causal strategic linear regression. In International Conference on Machine Learning, pages 8676–8686. PMLR, 2020.

By Diptangshu Sen

Authors: Dan Johnson, Michael Levet, Petr Vojtěchovský, Brett Widholm

In this paper, we investigate the computational complexity of isomorphism testing for finite groups and quasigroups, given by their multiplication tables. We crucially take advantage of their various decompositions to show the following: - We first consider the class $\mathcal{C}$ of groups that admit direct product decompositions, where each indecompsable factor is $O(1)$-generated, and either perfect or centerless. We show any group in $\mathcal{C}$ is identified by the $O(1)$-dimensional count-free Weisfeiler--Leman (WL) algorithm with $O(\log \log n)$ rounds, and the $O(1)$-dimensional counting WL algorithm with $O(1)$ rounds. Consequently, the isomorphism problem for $\mathcal{C}$ is in $\textsf{L}$. The previous upper bound for this class was $\textsf{TC}^{1}$, using $O(\log n)$ rounds of the $O(1)$-dimensional counting WL (Grochow and Levet, FCT 2023). - We next consider more generally, the class of groups where each indecomposable factor is $O(1)$-generated. We exhibit an $\textsf{AC}^{3}$ canonical labeling procedure for this class. Here, we accomplish this by showing that in the multiplication table model, the direct product decomposition can be computed in $\textsf{AC}^{3}$, parallelizing the work of Kayal and Nezhmetdinov (ICALP 2009). - Isomorphism testing between a central quasigroup $G$ and an arbitrary quasigroup $H$ is in $\textsf{NC}$. Here, we take advantage of the fact that central quasigroups admit an affine decomposition in terms of an underlying Abelian group. Only the trivial bound of $n^{\log(n)+O(1)}$-time was previously known for isomorphism testing of central quasigroups.

Authors: Theresa Pollinger, Masado Ishii, Jens Domke

Structured adaptive mesh refinement (AMR), commonly implemented via quadtrees and octrees, underpins a wide range of applications including databases, computer graphics, physics simulations, and machine learning. However, octrees enforce isotropic refinement in regions of interest, which can be especially inefficient for problems that are intrinsically anisotropic--much resolution is spent where little information is gained. This paper presents omnitrees as an anisotropic generalization of octrees and related data structures. Omnitrees allow to refine only the locally most important dimensions, providing tree structures that are less deep than bintrees and less wide than octrees. As a result, the convergence of the AMR schemes can be increased by up to a factor of the dimensionality d for very anisotropic problems, quickly offsetting their modest increase in storage overhead. We validate this finding on the problem of binary shape representation across 4,166 three-dimensional objects: Omnitrees increase the mean convergence rate by 1.5x, require less storage to achieve equivalent error bounds, and maximize the information density of the stored function faster than octrees. These advantages are projected to be even stronger for higher-dimensional problems. We provide a first validation by introducing a time-dependent rotation to create four-dimensional representations, and discuss the properties of their 4-d octree and omnitree approximations. Overall, omnitree discretizations can make existing AMR approaches more efficient, and open up new possibilities for high-dimensional applications.

Authors: Tyler Chen, Ethan N. Epperly, Raphael A. Meyer, Christopher Musco, Akash Rao

We study the problem of computing a rank-$k$ approximation of a matrix using randomized block Krylov iteration. Prior work has shown that, for block size $b = 1$ or $b = k$, a $(1 + \varepsilon)$-factor approximation to the best rank-$k$ approximation can be obtained after $\tilde O(k/\sqrt{\varepsilon})$ matrix-vector products with the target matrix. On the other hand, when $b$ is between $1$ and $k$, the best known bound on the number of matrix-vector products scales with $b(k-b)$, which could be as large as $O(k^2)$. Nevertheless, in practice, the performance of block Krylov methods is often optimized by choosing a block size $1 \ll b \ll k$. We resolve this theory-practice gap by proving that randomized block Krylov iteration produces a $(1 + \varepsilon)$-factor approximate rank-$k$ approximation using $\tilde O(k/\sqrt{\varepsilon})$ matrix-vector products for any block size $1\le b\le k$. Our analysis relies on new bounds for the minimum singular value of a random block Krylov matrix, which may be of independent interest. Similar bounds are central to recent breakthroughs on faster algorithms for sparse linear systems [Peng & Vempala, SODA 2021; Nie, STOC 2022].

Authors: Akash Pareek, Supratim Shit

Clustering is a fundamental technique in data analysis, with the $k$-means being one of the widely studied objectives due to its simplicity and broad applicability. In many practical scenarios, data points come with associated weights that reflect their importance, frequency, or confidence. Given a weighted point set $P \subset R^d$, where each point $p \in P$ has a positive weight $w_p$, the goal is to compute a set of $k$ centers $C = \{ c_1, c_2, \ldots, c_k \} \subset R^d$ that minimizes the weighted clustering cost: $\Delta_w(P,C) = \sum_{p \in P} w_p \cdot d(p,C)^2$, where $d(p,C)$ denotes the Euclidean distance from $p$ to its nearest center in $C$. Although most existing coreset-based algorithms for $k$-means extend naturally to the weighted setting and provide a PTAS, no prior work has offered a simple, coreset-free PTAS designed specifically for the weighted $k$-means problem. In this paper, we present a simple PTAS for weighted $k$-means that does not rely on coresets. Building upon the framework of Jaiswal, Kumar, and Sen (2012) for the unweighted case, we extend the result to the weighted setting by using the weighted $D^2$-sampling technique. Our algorithm runs in time $n d \cdot 2^{O\left(\frac{k^2}{\epsilon}\right)}$ and outputs a set of $k$ centers whose total clustering cost is within a $(1 + \epsilon)$-factor of the optimal cost. As a key application of the weighted $k$-means, we obtain a PTAS for the sensor coverage problem, which can also be viewed as a continuous locational optimization problem. For this problem, the best-known result prior to our work was an $O(\log k)$-approximation by Deshpande (2014), whereas our algorithm guarantees a $(1 + \epsilon)$-approximation to the optimal coverage cost even before applying refinement steps like Lloyd desent.

Authors: Zichun Ye, Runqi Wang, Xutong Liu, Shuai Li

The combinatorial multi-armed bandit (CMAB) is a cornerstone of sequential decision-making framework, dominated by two algorithmic families: UCB-based and adversarial methods such as follow the regularized leader (FTRL) and online mirror descent (OMD). However, prominent UCB-based approaches like CUCB suffer from additional regret factor $\log T$ that is detrimental over long horizons, while adversarial methods such as EXP3.M and HYBRID impose significant computational overhead. To resolve this trade-off, we introduce the Combinatorial Minimax Optimal Strategy in the Stochastic setting (CMOSS). CMOSS is a computationally efficient algorithm that achieves an instance-independent regret of $O\big( (\log k)^2\sqrt{kmT}\big )$ under semi-bandit feedback, where $m$ is the number of arms and $k$ is the maximum cardinality of a feasible action. Crucially, this result eliminates the dependency on $\log T$ and matches the established $\Omega\big( \sqrt{kmT}\big)$ lower bound up to $O\big((\log k)^2\big)$. We then extend our analysis to show that CMOSS is also applicable to cascading feedback. Experiments on synthetic and real-world datasets validate that CMOSS consistently outperforms benchmark algorithms in both regret and runtime efficiency.

Authors: Jesse Beisegel, Nina Chiarelli, Ekkehard Köhler, Matjaž Krnc, Martin Milanič, Nevena Pivač, Robert Scheffler, Martin Strehler

Edge-weighted graphs play an important role in the theory of Robinsonian matrices and similarity theory, particularly via the concept of level graphs, that is, graphs obtained from an edge-weighted graph by removing all sufficiently light edges. This suggest a natural way of associating to any class $\mathcal{G}$ of unweighted graphs a corresponding class of edge-weighted graphs, namely by requiring that all level graphs belong to $\mathcal{G}$. We show that weighted graphs for which all level graphs are split, threshold, or chain graphs can be recognized in linear time using special edge elimination orderings. We obtain these results by introducing the notion of degree sandwich monotone graph classes. A graph class $\mathcal{G}$ is sandwich monotone if every edge set which may be removed from a graph in $\mathcal{G}$ without leaving the class also contains a single edge that can be safely removed. Furthermore, if we require the safe edge to fulfill a certain degree property, then $\mathcal{G}$ is called degree sandwich monotone. We present necessary and sufficient conditions for the existence of a linear-time recognition algorithm for any weighted graph class whose corresponding unweighted class is degree sandwich monotone and contains all edgeless graphs.

Authors: Romain Bourneuf, Tim Planken

The block-cut tree decomposes a connected graph along its cutvertices, displaying its 2-connected components. The Tutte-decomposition extends this idea to 2-separators in 2-connected graphs, yielding a canonical tree-decomposition that decomposes the graph into its triconnected components. In 1973, Hopcroft and Tarjan introduced a linear-time algorithm to compute the Tutte-decomposition. Cunningham and Edmonds later established a structural characterization of the Tutte-decomposition via totally-nested 2-separations. We present a conceptually simple algorithm based on this characterization, which computes the Tutte-decomposition in linear time. Our algorithm first computes all totally-nested 2-separations and then builds the Tutte-decomposition from them. Along the way, we derive new structural results on the structure of totally-nested 2-separations in 2-connected graphs using a novel notion of stability, which may be of independent interest.

Authors: Chris Camaño, Raphael A. Meyer, Kevin Shu

We study the problem of approximating an unknown function $f:\mathbb{R}\to\mathbb{R}$ by a degree-$d$ polynomial using as few function evaluations as possible, where error is measured with respect to a probability distribution $\mu$. Existing randomized algorithms achieve near-optimal sample complexities to recover a $ (1+\varepsilon) $-optimal polynomial but produce biased estimates of the best polynomial approximation, which is undesirable. We propose a simple debiasing method based on a connection between polynomial regression and random matrix theory. Our method involves evaluating $f(\lambda_1),\ldots,f(\lambda_{d+1})$ where $\lambda_1,\ldots,\lambda_{d+1}$ are the eigenvalues of a suitably designed random complex matrix tailored to the distribution $\mu$. Our estimator is unbiased, has near-optimal sample complexity, and experimentally outperforms iid leverage score sampling. Additionally, our techniques enable us to debias existing methods for approximating a periodic function with a truncated Fourier series with near-optimal sample complexity.

NICK: I read and enjoyed your blog post on Tom L (see here). I then spent 40 minutes down a rabbithole listening to his music on YouTube.

By gasarch

We prove that for a natural distribution over random satisfiable 3--CNF formulas with $\Theta(n)$ clauses, every $\mathsf{AC}^0$ circuit family of constant depth $d$ and polynomial size $n^k$ fails to decide satisfiability with probability at least $2/3$ under the standard random restriction method with parameter $p = n^{-1/(2d)}$. The proof follows the classical Håstad switching-lemma framework with explicit parameterization: we choose optimal restriction parameters, argue a collapse to small decision trees, and derive a contradiction with correctness on the induced sub-instances. This explicit bound, stated for satisfiable instances at constant clause density, provides a clear benchmark within the $\mathsf{AC}^0$ lower-bound program.

September 22-23, 2025 University of Warwick, UK https://sites.google.com/view/algorithmscomplexitywarwick2/home Registration deadline: September 10, 2025 The Workshop Algorithms & Complexity @ Warwick will be held on 22-23 September at the University of Warwick. The aim of the event is to highlight several recent exciting advances in the field of Algorithms and Complexity and to facilitate interactions within … Continue reading Workshop Algorithms & Complexity @ Warwick

By shacharlovett

We initiate the study of complexity classes ${A^B}$ where ${A}$ and ${B}$ are both ${TFNP}$ subclasses. For example, we consider complexity classes of the form ${PPP^{PPP}}$, ${PPAD^{PPA}}$, and ${PPA^{PLS}}$. We define complete problems for such classes, and show that they belong in ${TFNP}$. These definitions require some care, since unlike a class like ${PPA^{NP}}$, where the ${NP}$ oracle defines a function, in ${PPA^{PPP}}$, the oracle is for a search problem with many possible solutions. Intuitively, the definitions we introduce quantify over all possible instantiations of the ${PPP}$ oracle. With these notions in place, we then show that several ${TFNP}$ subclasses are self-low. In particular, ${PPA^{PPA}} = {PPA}$, ${PLS^{PLS}} = {PLS}$, and ${LOSSY^{LOSSY}} = {LOSSY}$. These ideas introduce a novel approach for classifying computational problems within ${TFNP}$, such as the problem of deterministically generating large primes.

Quantum computational pseudorandomness has emerged as a fundamental notion that spans connections to complexity theory, cryptography and fundamental physics. However, all known constructions of efficient quantum-secure pseudorandom objects rely on complexity theoretic assumptions. In this work, we establish the first unconditionally secure efficient pseudorandom constructions against shallow-depth quantum circuit classes. We prove that: - Any quantum state $2$-design yields unconditional pseudorandomness against both $QNC^0$ circuits with arbitrarily many ancillae and $AC^0\circ QNC^0$ circuits with nearly linear ancillae. - Random phased subspace states, where the phases are picked using a $4$-wise independent function, are unconditionally pseudoentangled against the above circuit classes. - Any unitary $2$-design yields unconditionally secure parallel-query pseudorandom unitaries against geometrically local $QNC^0$ adversaries, even with limited $AC^0$ postprocessing. Our indistinguishability results for $2$-designs stand in stark contrast to the standard setting of quantum pseudorandomness against $BQP$ circuits, wherein they can be distinguishable from Haar random ensembles using more than two copies or queries. Our work demonstrates that quantum computational pseudorandomness can be achieved unconditionally for natural classes of restricted adversaries, opening new directions in quantum complexity theory.

A problem $\mathcal{P}$ is considered downward self-reducible, if there exists an efficient algorithm for $\mathcal{P}$ that is allowed to make queries to only strictly smaller instances of $\mathcal{P}$. Downward self-reducibility has been well studied in the case of decision problems, and it is well known that any downward self-reducible problem must lie in ${PSPACE}$. Harsha, Mitropolsky and Rosen [ITCS, 2023] initiated the study of downward self reductions in the case of search problems. They showed the following interesting collapse: if a problem is in ${TFNP}$ and also downward self-reducible, then it must be in ${PLS}$. Moreover, if the problem admits a unique solution then it must be in ${UEOPL}$. We demonstrate that this represents just the tip of a much more general phenomenon, which holds for even harder search problems that lie higher up in the total function polynomial hierarchy (${TF\Sigma_i^P}$). In fact, even if we allow our downward self-reduction to be much more powerful, such a collapse will still occur. We show that any problem in ${TF\Sigma_i^P}$ which admits a randomized downward self-reduction with access to a ${\Sigma_{i-1}^P}$ oracle must be in ${PLS}^{{\Sigma_{i-1}^P}}$. If the problem has essentially unique solutions then it lies in ${UEOPL}^{{\Sigma_{i-1}^P}}$. As one (out of many) application of our framework, we get new upper bounds for the problems $\mathrm{Range Avoidance}$ and $\mathrm{Linear Ordering Principle}$ and show that they are both in ${UEOPL}^{{NP}}$.

In the Maxmin E$k$-SAT Reconfiguration problem, we are given a satisfiable $k$-CNF formula $\varphi$ where each clause contains exactly $k$ literals, along with a pair of its satisfying assignments. The objective is transform one satisfying assignment into the other by repeatedly flipping the value of a single variable, while maximizing the minimum fraction of satisfied clauses of $\varphi$ throughout the transformation. In this paper, we demonstrate that the optimal approximation factor for Maxmin E$k$-SAT Reconfiguration is $1 - \Theta\left(\frac{1}{k}\right)$. On the algorithmic side, we develop a deterministic $\left(1-\frac{1}{k-1}-\frac{1}{k}\right)$-factor approximation algorithm for every $k \geq 3$. On the hardness side, we show that it is PSPACE-hard to approximate this problem within a factor of $1-\frac{1}{10k}$ for every sufficiently large $k$. Note that an “NP analogue” of Maxmin E$k$-SAT Reconfiguration is Max E$k$-SAT, whose approximation threshold is $1-\frac{1}{2^k}$ shown by Håstad (JACM 2001). To the best of our knowledge, this is the first reconfiguration problem whose approximation threshold is (asymptotically) worse than that of its NP analogue. To prove the hardness result, we introduce a new “non-monotone” test, which is specially tailored to reconfiguration problems, despite not being helpful in the PCP regime.

This paper makes two primary contributions. First, we introduce the concept of counting martingales and use it to define counting measures, counting dimensions, and counting strong dimensions. Second, we apply these new tools to strengthen previous circuit lower bounds. Resource-bounded measure and dimension have traditionally focused on deterministic time and space bounds. We use counting complexity classes to develop resource-bounded counting measures and dimensions. Counting martingales are constructed using functions from the #P, SpanP, and GapP complexity classes. We show that counting martingales capture many martingale constructions in complexity theory. The resulting counting measures and dimensions are intermediate in power between the standard time-bounded and space-bounded notions, enabling finer-grained analysis where space-bounded measures are known, but time-bounded measures remain open. For example, we show that BPP has #P-dimension 0 and BQP has GapP-dimension 0, whereas the P-dimensions of these classes remain open. As our main application, we improve circuit-size lower bounds. Lutz (1992) strengthened Shannon's classic $(1-\epsilon)\frac{2^n}{n}$ lower bound (1949) to $\pspace$-measure, showing that almost all problems require circuits of size $\frac{2^n}{n}\left(1+\frac{\alpha \log n}{n}\right)$, for any $\alpha < 1$. We extend this result to SpanP-measure, with a proof that uses a connection through the Minimum Circuit Size Problem (MCSP) to construct a counting martingale. Our results imply that the stronger lower bound holds within the third level of the exponential-time hierarchy, whereas previously, it was only known in ESPACE. Under a derandomization hypothesis, this lower bound holds within the second level of the exponential-time hierarchy, specifically in the class $E^{NP}$. We study the #P-dimension of classical circuit complexity classes and the GapP-dimension of quantum circuit complexity classes. We also show that if one-way functions exist, then #P-dimension is strictly more powerful than P-dimension.

We prove that for the bit pigeonhole principle with any number of pigeons and $n$ holes, any depth $D$ proof in resolution over parities must have size $\exp(\Omega(n^3/D^2))$. Our proof uses the random walk with restarts approach of Alekseev and Itsykson [STOC '25], along with ideas from recent simulation theorems for randomized parity decision trees.

The Forrelation problem is a central problem that demonstrates an exponential separation between quantum and classical capabilities. In this problem, given query access to $n$-bit Boolean functions $f$ and $g$, the goal is to estimate the Forrelation function $\mathrm{forr}(f,g)$, which measures the correlation between $g$ and the Fourier transform of $f$. In this work we provide a new linear algebraic perspective on the Forrelation problem, as opposed to prior analytic approaches. We establish a connection between the Forrelation problem and bent Boolean functions and through this connection, analyze an extremal version of the Forrelation problem where the goal is to distinguish between extremal instances of Forrelation, namely $(f,g)$ with $\mathrm{forr}(f,g)=1$ and $\mathrm{forr}(f,g)=-1$. We show that this problem can be solved with one quantum query and success probability one, yet requires $\tilde{\Omega}\left(2^{n/4}\right)$ classical randomized queries, even for algorithms with a one-third failure probability, highlighting the remarkable power of one exact quantum query. We also study a restricted variant of this problem where the inputs $f,g$ are computable by small classical circuits and show classical hardness under cryptographic assumptions.

Since 2018, blockchain research has seen a surge in DAG-based BFT protocols aimed at higher throughput. These protocols can be traced back to Hashgraph, 2018 and Aleph, 2019, theoretical work of All You Need is DAG, 2021 and systems papers Narwhal and Bullshark. In this post, we highlight 5 aspects...

Authors: Federica Di Stefano, Quentin Manière, Magdalena Ortiz, Mantas Šimkus

Reasoning with minimal models has always been at the core of many knowledge representation techniques, but we still have only a limited understanding of this problem in Description Logics (DLs). Minimization of some selected predicates, letting the remaining predicates vary or be fixed, as proposed in circumscription, has been explored and exhibits high complexity. The case of `pure' minimal models, where the extension of all predicates must be minimal, has remained largely uncharted. We address this problem in popular DLs and obtain surprisingly negative results: concept satisfiability in minimal models is undecidable already for $\mathcal{EL}$. This undecidability also extends to a very restricted fragment of tuple-generating dependencies. To regain decidability, we impose acyclicity conditions on the TBox that bring the worst-case complexity below double exponential time and allow us to establish a connection with the recently studied pointwise circumscription; we also derive results in data complexity. We conclude with a brief excursion to the DL-Lite family, where a positive result was known for DL-Lite$_{\text{core}}$, but our investigation establishes ExpSpace-hardness already for its extension DL-Lite$_{\text{horn}}$.

Authors: Hsin-Yuan Huang, Soonwon Choi, Jarrod R. McClean, John Preskill

The quest to identify quantum advantages lies at the heart of quantum technology. While quantum devices promise extraordinary capabilities, from exponential computational speedups to unprecedented measurement precision, distinguishing genuine advantages from mere illusions remains a formidable challenge. In this endeavor, quantum theorists are like prophets attempting to foretell the future, yet the boundary between visionary insight and unfounded fantasy is perilously thin. In this perspective, we examine our mathematical tools for navigating the vast world of quantum advantages across computation, learning, sensing, and communication. We explore five keystone properties: predictability, typicality, robustness, verifiability, and usefulness that define an ideal quantum advantage, and envision what new quantum advantages could arise in a future with ubiquitous quantum technology. We prove that some quantum advantages are inherently unpredictable using classical resources alone, suggesting a landscape far richer than what we can currently foresee. While mathematical rigor remains our indispensable guide, the ultimate power of quantum technologies may emerge from advantages we cannot yet conceive.

Authors: Mohammad Ferry Husnil Arif, Muhammad Imran

The semidirect discrete logarithm problem (SDLP) in finite groups was proposed as a foundation for post-quantum cryptographic protocols, based on the belief that its non-abelian structure would resist quantum attacks. However, recent results have shown that SDLP in finite groups admits efficient quantum algorithms, undermining its quantum resistance. This raises a fundamental question: does the SDLP offer any computational advantages over the standard discrete logarithm problem (DLP) against classical adversaries? In this work, we investigate the classical hardness of SDLP across different finite group platforms. We establish that the group-case SDLP can be reformulated as a generalized discrete logarithm problem, enabling adaptation of classical algorithms to study its complexity. We present a concrete adaptation of the Baby-Step Giant-Step algorithm for SDLP, achieving time and space complexity $O(\sqrt{r})$ where $r$ is the period of the underlying cycle structure. Through theoretical analysis and experimental validation in SageMath, we demonstrate that the classical hardness of SDLP is highly platform-dependent and does not uniformly exceed that of standard DLP. In finite fields $\mathbb{F}_p^*$, both problems exhibit comparable complexity. Surprisingly, in elliptic curves $E(\mathbb{F}_p)$, the SDLP becomes trivial due to the bounded automorphism group, while in elementary abelian groups $\mathbb{F}_p^n$, the SDLP can be harder than DLP, with complexity varying based on the eigenvalue structure of the automorphism. Our findings reveal that the non-abelian structure of semidirect products does not inherently guarantee increased classical hardness, suggesting that the search for classically hard problems for cryptographic applications requires more careful consideration of the underlying algebraic structures.

Authors: Sefat Rahman, Tushar M. Athawale, Paul Rosen

Reeb graphs are an important tool for abstracting and representing the topological structure of a function defined on a manifold. We have identified three properties for faithfully representing Reeb graphs in a visualization. Namely, they should be constrained to the boundary, compact, and aligned with the function gradient. Existing algorithms for drawing Reeb graphs are agnostic to or violate these properties. In this paper, we introduce an algorithm to generate Reeb graph visualizations, called \textit{GASP}, that is cognizant of these properties, thereby producing visualizations that are more representative of the underlying data. To demonstrate the improvements, the resulting Reeb graphs are evaluated both qualitatively and quantitatively against the geometric barycenter algorithm, using its implementation available in the Topology ToolKit (TTK), a widely adopted tool for calculating and visualizing Reeb graphs.

Authors: Lei Shangyu, Fan Wei, Ren Hui

This paper proposes improvements to the physically-based surface triangulation method, bubble meshing. The method simulates physical bubbles to automatically generate mesh vertices, resulting in high-quality Delaunay triangles. Despite its flexibility in local mesh size control and the advantage of local re-meshing, bubble meshing is constrained by high computational costs and slow convergence on complex surfaces. The proposed approach employs conformal mapping to simplify surface bubble packing by flattening the surface onto a plane. Surface triangulation is induced from the planar mesh, avoiding direct bubble movement on the surface. Optimizing bubble quantity control and separating it from the relaxation process accelerates convergence, cutting computation time by over 70%. The enhanced method enables efficient triangulation of disk topology surfaces, supports local size control, curvature adaptation, and re-meshing of discrete surfaces. Keywords: Adaptive triangulation, Surface remeshing, Bubble meshing, Conformal parameterization, Algorithm efficiency

Authors: Serge Gaspers, Zixu He, Simon Mackenzie

We prove that computing the deterministic communication complexity D(f) of a Boolean function is NP-hard, even when protocols are limited to a constant number of alternations, resolving a question first posed by Yao (1979). Our reduction builds and expands on a suite of structural "interlacing" lemmas introduced by Mackenzie and Saffidine (arXiv:2411.19003); these lemmas can be reused as black boxes in future lower-bound constructions. The instances produced by our reduction admit optimal protocols that use only constant alternations, so NP-hardness holds under stronger restrictions than those considered in concurrent and independent work by Hirahara, Ilango, and Loff (arXiv:2507.10426), whose proof requires unbounded alternations. Because the gadgets in our construction are self-similar, they can be recursively embedded. We sketch how this yields, under the Exponential-Time Hypothesis, an additive inapproximability gap that grows without bound, and we outline a route toward NP-hardness of approximating D(f) within a fixed constant additive error. Full details of the ETH-based inapproximability results will appear in a future version. Beyond settling the complexity of deterministic communication complexity itself, the modular framework we develop opens the door to a wider class of reductions and, we believe, will prove useful in tackling other long-standing questions in communication complexity.

Authors: Jingyang Zhao, Mingyu Xiao

The Capacitated Arc Routing Problem (CARP), introduced by Golden and Wong in 1981, is an important arc routing problem in Operations Research, which generalizes the famous Capacitated Vehicle Routing Problem (CVRP). When every customer has a unit demand, the best known approximation ratio for CARP, given by Jansen in 1993, remains $\frac{5}{2}-\frac{1.5}{k}$, where $k$ denotes the vehicle capacity. Based on recent progress in approximating CVRP, we improve this result by proposing a $(\frac{5}{2}-\Theta(\frac{1}{\sqrt{k}}))$-approximation algorithm, which to the best of our knowledge constitutes the first improvement over Jansen's bound.

Authors: Dibyayan Chakraborty, Oscar Defrain, Florent Foucaud, Mathieu Mari, Prafullkumar Tale

We investigate the parameterized complexity of the Isometric Path Partition problem when parameterized by the treewidth ($\mathrm{tw}$) of the input graph, arguably one of the most widely studied parameters. Courcelle's theorem shows that graph problems that are expressible as MSO formulas of constant size admit FPT algorithms parameterized by the treewidth of the input graph. This encompasses many natural graph problems. However, many metric-based graph problems, where the solution is defined using some metric-based property of the graph (often the distance) are not expressible as MSO formulas of constant size. These types of problems, Isometric Path Partition being one of them, require individual attention and often draw the boundary for the success story of parameterization by treewidth. In this paper, we prove that Isometric Path Partition is $W[1]$-hard when parameterized by treewidth (in fact, even pathwidth), answering the question by Dumas et al. [SIDMA, 2024], Fernau et al. [CIAC, 2023], and confirming the aforementioned tendency. We complement this hardness result by designing a tailored dynamic programming algorithm running in $n^{O(\mathrm{tw})}$ time. This dynamic programming approach also results in an algorithm running in time $\textrm{diam}^{O(\mathrm{tw}^2)} \cdot n^{O(1)}$, where $\textrm{diam}$ is the diameter of the graph. Note that the dependency on treewidth is unusually high, as most problems admit algorithms running in time $2^{O(\mathrm{tw})}\cdot n^{O(1)}$ or $2^{O(\mathrm{tw} \log (\mathrm{tw}))}\cdot n^{O(1)}$. However, we rule out the possibility of a significantly faster algorithm by proving that Isometric Path Partition does not admit an algorithm running in time $\textrm{diam}^{o(\mathrm{tw}^2/(\log^3(\mathrm{tw})))} \cdot n^{O(1)}$, unless the Randomized-ETH fails.

Authors: Joyentanuj Das, Suranjan De, He Sun

Graph clustering is an important algorithmic technique for analysing massive graphs, and has been widely applied in many research fields of data science. While the objective of most graph clustering algorithms is to find a vertex set of low conductance, a sequence of recent studies highlights the importance of the inter-connection between vertex sets when analysing real-world datasets. Following this line of research, in this work we study bipartite-like clusters and present efficient and online sparsification algorithms that find such clusters in both undirected graphs and directed ones. We conduct experimental studies on both synthetic and real-world datasets, and show that our algorithms significantly speedup the running time of existing clustering algorithms while preserving their effectiveness.

Authors: Fangjian Shen, Yicheng Zheng, Wushao Wen, Hankz Hankui Zhuo

In this paper, we present fixed-parameter tractability algorithms for both the undirected and directed versions of the Spanning Tree Isomorphism Problem, parameterized by the size $k$ of a redundant set. A redundant set is a collection of edges whose removal transforms the graph into a spanning tree. For the undirected version, our algorithm achieves a time complexity of $O(n^2 \log n \cdot 2^{k \log k})$. For the directed version, we propose a more efficient algorithm with a time complexity of $O(n^2 \cdot 2^{4k-3})$, where $n$ is the number of vertices.