Theory of Computing Report

Authors: Zehua Lai, Lek-Heng Lim, Tianyun Tang

We show that linearly constrained linear optimization over a Stiefel or Grassmann manifold is NP-hard in general. We show that the same is true for unconstrained quadratic optimization over a Stiefel manifold. We will establish the nonexistence of FPTAS for these optimization problems over a Stiefel manifold. As an aside we extend our results to flag manifolds. Combined with earlier findings, this shows that manifold optimization is a difficult endeavor -- even the simplest problems like LP and unconstrained QP are already NP-hard on the most common manifolds.

Authors: Oswin Aichholzer, Joseph Dorfer

We provide a linear time algorithm to determine the flip distance between two plane spanning paths on a point set in convex position. At the same time, we show that the happy edge property does not hold in this setting. This has to be seen in contrast to several results for reconfiguration problems where the absence of the happy edge property implies algorithmic hardness of the flip distance problem. Further, we show that our algorithm can be adapted for (1) compatible flips (2) local flips and (3) flips for plane spanning paths in simple polygons.

Authors: Anders Aamand, Maryam Aliakbarpour, Justin Y. Chen, Shyam Narayanan, Sandeep Silwal

A hypothesis testing algorithm is replicable if, when run on two different samples from the same distribution, it produces the same output with high probability. This notion, defined by by Impagliazzo, Lei, Pitassi, and Sorell [STOC'22], can increase trust in testing procedures and is deeply related to algorithmic stability, generalization, and privacy. We build general tools to prove lower and upper bounds on the sample complexity of replicable testers, unifying and quantitatively improving upon existing results. We identify a set of canonical properties, and prove that any replicable testing algorithm can be modified to satisfy these properties without worsening accuracy or sample complexity. A canonical replicable algorithm computes a deterministic function of its input (i.e., a test statistic) and thresholds against a uniformly random value in $[0,1]$. It is invariant to the order in which the samples are received, and, if the testing problem is ``symmetric,'' then the algorithm is also invariant to the labeling of the domain elements, resolving an open question by Liu and Ye [NeurIPS'24]. We prove new lower bounds for uniformity, identity, and closeness testing by reducing to the case where the replicable algorithm satisfies these canonical properties. We systematize and improve upon a common strategy for replicable algorithm design based on test statistics with known expectation and bounded variance. Our framework allow testers which have been extensively analyzed in the non-replicable setting to be made replicable with minimal overhead. As direct applications of our framework, we obtain constant-factor optimal bounds for coin testing and closeness testing and get replicability for free in a large parameter regime for uniformity testing. We also give state-of-the-art bounds for replicable Gaussian mean testing, and, unlike prior work, our algorithm runs in polynomial time.

Authors: Jan Eube, Kelin Luo, Dorian Reineccius, Heiko Röglin, Melanie Schmidt

The connected $k$-median problem is a constrained clustering problem that combines distance-based $k$-clustering with connectivity information. The problem allows to input a metric space and an unweighted undirected connectivity graph that is completely unrelated to the metric space. The goal is to compute $k$ centers and corresponding clusters such that each cluster forms a connected subgraph of $G$, and such that the $k$-median cost is minimized. The problem has applications in very different fields like geodesy (particularly districting), social network analysis (especially community detection), or bioinformatics. We study a version with overlapping clusters where points can be part of multiple clusters which is natural for the use case of community detection. This problem variant is $\Omega(\log n)$-hard to approximate, and our main result is an $\mathcal{O}(k^2 \log n)$-approximation algorithm for the problem. We complement it with an $\Omega(n^{1-\epsilon})$-hardness result for the case of disjoint clusters without overlap with general connectivity graphs, as well as an exact algorithm in this setting if the connectivity graph is a tree.

Authors: Sariel Har-Peled

We prove an easy but very weak version of Chernoff inequality. Namely, that the probability that in $6M$ throws of a fair coin, one gets at most $M$ heads is $\leq 1/2^M$.

Authors: Lorenzo Carfagna, Carlo Tosoni

We study the problem of indexing and compressing tries using a BWT-based approach. Specifically, we consider a succinct and compressed representation of the XBWT of Ferragina et al.\ [FOCS '05, JACM '09] corresponding to the analogous of the FM-index [FOCS '00, JACM '05] for tries. This representation allows to efficiently count the number of nodes reached by a given string pattern. To analyze the space complexity of the above trie index, we propose a proof for the combinatorial problem of counting the number of tries with a given symbol distribution. We use this formula to define a worst-case entropy measure for tries, as well as a notion of k-th order empirical entropy. In particular, we show that the relationships between these two entropy measures are similar to those between the corresponding well-known measures for strings. We use these measures to prove that the XBWT of a trie can be encoded within a space bounded by our k-th order empirical entropy plus a o(n) term, with n being the number of nodes in the trie. Notably, as happens for strings, this space bound can be reached for every sufficiently small k simultaneously. Finally, we compare the space complexity of the above index with that of the r-index for tries proposed by Prezza [SODA '21] and we prove that in some cases the FM-index for tries is asymptotically smaller.

Authors: Tomasz Kociumaka, Ali Shahali

The tree edit distance is a natural dissimilarity measure between rooted ordered trees whose nodes are labeled over an alphabet $\Sigma$. It is defined as the minimum number of node edits (insertions, deletions, and relabelings) required to transform one tree into the other. In the weighted variant, the edits have associated costs (depending on the involved node labels) normalized so that each cost is at least one, and the goal is to minimize the total cost of edits. The unweighted tree edit distance between two trees of total size $n$ can be computed in $O(n^{2.6857})$ time; in contrast, determining the weighted tree edit distance is fine-grained equivalent to the All-Pairs Shortest Paths problem and requires $n^3/2^{\Omega(\sqrt{\log n})}$ time [Nogler et al.; STOC'25]. These super-quadratic running times are unattractive for large but very similar trees, which motivates the bounded version of the problem, where the runtime is parameterized by the computed distance $k$, potentially yielding faster algorithms for $k\ll n$. Previous best algorithms for the bounded unweighted setting run in $O(nk^2\log n)$ time [Akmal & Jin; ICALP'21] and $O(n + k^7\log k)$ time [Das et al.; STOC'23]. For the weighted variant, the only known running time has been $O(n + k^{15})$. We present an $O(n + k^6\log k)$-time algorithm for computing the bounded tree edit distance in both the weighted and unweighted settings. Our approach begins with an alternative $O(nk^2\log n)$-time algorithm that handles weights and is significantly easier to analyze than the existing counterpart. We then introduce a novel optimization that leverages periodic structures within the input trees. To utilize it, we modify the $O(k^5)$-size $O(n)$-time universal kernel, the central component of the prior $O(n + k^{O(1)})$-time algorithms, so that it produces instances containing these periodic structures.

Authors: Jens Schlöter

In the knapsack problem under explorable uncertainty, we are given a knapsack instance with uncertain item profits. Instead of having access to the precise profits, we are only given uncertainty intervals that are guaranteed to contain the corresponding profits. The actual item profit can be obtained via a query. The goal of the problem is to adaptively query item profits until the revealed information suffices to compute an optimal (or approximate) solution to the underlying knapsack instance. Since queries are costly, the objective is to minimize the number of queries. In the offline variant of this problem, we assume knowledge of the precise profits and the task is to compute a query set of minimum cardinality that a third party without access to the profits could use to identify an optimal (or approximate) knapsack solution. We show that this offline variant is complete for the second-level of the polynomial hierarchy, i.e., $\Sigma_2^p$-complete, and cannot be approximated within a non-trivial factor unless $\Sigma_2^p = \Delta_2^p$. Motivated by these strong hardness results, we consider a resource-augmented variant of the problem where the requirements on the query set computed by an algorithm are less strict than the requirements on the optimal solution we compare against. More precisely, a query set computed by the algorithm must reveal sufficient information to identify an approximate knapsack solution, while the optimal query set we compare against has to reveal sufficient information to identify an optimal solution. We show that this resource-augmented setting allows interesting non-trivial algorithmic results.

Authors: Itai Boneh, Egor Gorbachev, Tomasz Kociumaka

The edit distance $ed(X,Y)$ of two strings $X,Y\in \Sigma^*$ is the minimum number of character edits (insertions, deletions, and substitutions) needed to transform $X$ into $Y$. Its weighted counterpart $ed^w(X,Y)$ minimizes the total cost of edits, which are specified using a function $w$, normalized so that each edit costs at least one. The textbook dynamic-programming procedure, given strings $X,Y\in \Sigma^{\le n}$ and oracle access to $w$, computes $ed^w(X,Y)$ in $O(n^2)$ time. Nevertheless, one can achieve better running times if the computed distance, denoted $k$, is small: $O(n+k^2)$ for unit weights [Landau and Vishkin; JCSS'88] and $\tilde{O}(n+\sqrt{nk^3})$ for arbitrary weights [Cassis, Kociumaka, Wellnitz; FOCS'23]. In this paper, we study the dynamic version of the weighted edit distance problem, where the goal is to maintain $ed^w(X,Y)$ for strings $X,Y\in \Sigma^{\le n}$ that change over time, with each update specified as an edit in $X$ or $Y$. Very recently, Gorbachev and Kociumaka [STOC'25] showed that the unweighted distance $ed(X,Y)$ can be maintained in $\tilde{O}(k)$ time per update after $\tilde{O}(n+k^2)$-time preprocessing; here, $k$ denotes the current value of $ed(X,Y)$. Their algorithm generalizes to small integer weights, but the underlying approach is incompatible with large weights. Our main result is a dynamic algorithm that maintains $ed^w(X,Y)$ in $\tilde{O}(k^{3-\gamma})$ time per update after $\tilde{O}(nk^\gamma)$-time preprocessing. Here, $\gamma\in [0,1]$ is a real trade-off parameter and $k\ge 1$ is an integer threshold fixed at preprocessing time, with $\infty$ returned whenever $ed^w(X,Y)>k$. We complement our algorithm with conditional lower bounds showing fine-grained optimality of our trade-off for $\gamma \in [0.5,1)$ and justifying our choice to fix $k$.

Authors: Vaidehi Srinivas

We study the problem of conformal prediction in a novel online framework that directly optimizes efficiency. In our problem, we are given a target miscoverage rate $\alpha > 0$, and a time horizon $T$. On each day $t \le T$ an algorithm must output an interval $I_t \subseteq [0, 1]$, then a point $y_t \in [0, 1]$ is revealed. The goal of the algorithm is to achieve coverage, that is, $y_t \in I_t$ on (close to) a $(1 - \alpha)$-fraction of days, while maintaining efficiency, that is, minimizing the average volume (length) of the intervals played. This problem is an online analogue to the problem of constructing efficient confidence intervals. We study this problem over arbitrary and exchangeable (random order) input sequences. For exchangeable sequences, we show that it is possible to construct intervals that achieve coverage $(1 - \alpha) - o(1)$, while having length upper bounded by the best fixed interval that achieves coverage in hindsight. For arbitrary sequences however, we show that any algorithm that achieves a $\mu$-approximation in average length compared to the best fixed interval achieving coverage in hindsight, must make a multiplicative factor more mistakes than $\alpha T$, where the multiplicative factor depends on $\mu$ and the aspect ratio of the problem. Our main algorithmic result is a matching algorithm that can recover all Pareto-optimal settings of $\mu$ and number of mistakes. Furthermore, our algorithm is deterministic and therefore robust to an adaptive adversary. This gap between the exchangeable and arbitrary settings is in contrast to the classical online learning problem. In fact, we show that no single algorithm can simultaneously be Pareto-optimal for arbitrary sequences and optimal for exchangeable sequences. On the algorithmic side, we give an algorithm that achieves the near-optimal tradeoff between the two cases.

Authors: Yiping Liu, Hoai-An Nguyen, Junzhao Yang

We present a randomized linear-space solver for general linear systems $\mathbf{A} \mathbf{x} = \mathbf{b}$ with $\mathbf{A} \in \mathbb{Z}^{n \times n}$ and $\mathbf{b} \in \mathbb{Z}^n$, without any assumption on the condition number of $\mathbf{A}$. For matrices whose entries are bounded by $\mathrm{poly}(n)$, the solver returns a $(1+\epsilon)$-multiplicative entry-wise approximation to vector $\mathbf{x} \in \mathbb{Q}^{n}$ using $\widetilde{O}(n^2 \cdot \mathrm{nnz}(\mathbf{A}))$ bit operations and $O(n \log n)$ bits of working space (i.e., linear in the size of a vector), where $\mathrm{nnz}$ denotes the number of nonzero entries. Our solver works for right-hand vector $\mathbf{b}$ with entries up to $n^{O(n)}$. To our knowledge, this is the first linear-space linear system solver over the rationals that runs in $\widetilde{O}(n^2 \cdot \mathrm{nnz}(\mathbf{A}))$ time. We also present several applications of our solver to numerical linear algebra problems, for which we provide algorithms with efficient polynomial running time and near-linear space. In particular, we present results for linear regression, linear programming, eigenvalues and eigenvectors, and singular value decomposition.

Authors: Yotam Kenneth-Mordoch, Shay Sapir

This paper studies the adversarial-robustness of importance-sampling (aka sensitivity sampling); a useful algorithmic technique that samples elements with probabilities proportional to some measure of their importance. A streaming or online algorithm is called adversarially-robust if it succeeds with high probability on input streams that may change adaptively depending on previous algorithm outputs. Unfortunately, the dependence between stream elements breaks the analysis of most randomized algorithms, and in particular that of importance-sampling algorithms. Previously, Braverman et al. [NeurIPS 2021] suggested that streaming algorithms based on importance-sampling may be adversarially-robust; however, they proved it only for well-behaved inputs. We focus on the adversarial-robustness of online importance-sampling, a natural variant where sampling decisions are irrevocable and made as data arrives. Our main technical result shows that, given as input an adaptive stream of elements $x_1,\ldots,x_T\in \mathbb{R}_+$, online importance-sampling maintains a $(1\pm\epsilon)$-approximation of their sum while matching (up to lower order terms) the storage guarantees of the oblivious (non-adaptive) case. We then apply this result to develop adversarially-robust online algorithms for two fundamental problems: hypergraph cut sparsification and $\ell_p$ subspace embedding.

Authors: Dan Vanderkam

Finding all the words on a Boggle board is a classic computer programming problem. With a fast Boggle solver, local optimization techniques such as hillclimbing and simulated annealing can be used to find particularly high-scoring boards. The sheer number of possible Boggle boards has historically prevented an exhaustive search for the global optimum board. We apply Branch and Bound and a decision diagram-like data structure to perform the first such search. We find that the highest-scoring boards found via hillclimbing are, in fact, the global optima.

Authors: Liam Roditty, Plia Trabelsi

Let $G=(V,E)$ be an unweighted undirected graph with $n$ vertices and $m$ edges. Let $g$ be the girth of $G$, that is, the length of a shortest cycle in $G$. We present a randomized algorithm with a running time of $\tilde{O}\big(\ell \cdot n^{1 + \frac{1}{\ell - \varepsilon}}\big)$ that returns a cycle of length at most $ 2\ell \left\lceil \frac{g}{2} \right\rceil - 2 \left\lfloor \varepsilon \left\lceil \frac{g}{2} \right\rceil \right\rfloor, $ where $\ell \geq 2$ is an integer and $\varepsilon \in [0,1]$, for every graph with $g = polylog(n)$. Our algorithm generalizes an algorithm of Kadria \etal{} [SODA'22] that computes a cycle of length at most $4\left\lceil \frac{g}{2} \right\rceil - 2\left\lfloor \varepsilon \left\lceil \frac{g}{2} \right\rceil \right\rfloor $ in $\tilde{O}\big(n^{1 + \frac{1}{2 - \varepsilon}}\big)$ time. Kadria \etal{} presented also an algorithm that finds a cycle of length at most $ 2\ell \left\lceil \frac{g}{2} \right\rceil $ in $\tilde{O}\big(n^{1 + \frac{1}{\ell}}\big)$ time, where $\ell$ must be an integer. Our algorithm generalizes this algorithm, as well, by replacing the integer parameter $\ell$ in the running time exponent with a real-valued parameter $\ell - \varepsilon$, thereby offering greater flexibility in parameter selection and enabling a broader spectrum of combinations between running times and cycle lengths. We also show that for sparse graphs a better tradeoff is possible, by presenting an $\tilde{O}(\ell\cdot m^{1+1/(\ell-\varepsilon)})$ time randomized algorithm that returns a cycle of length at most $2\ell(\lfloor \frac{g-1}{2}\rfloor) - 2(\lfloor \varepsilon \lfloor \frac{g-1}{2}\rfloor \rfloor+1)$, where $\ell\geq 3$ is an integer and $\varepsilon\in [0,1)$, for every graph with $g=polylog(n)$. To obtain our algorithms we develop several techniques and introduce a formal definition of hybrid cycle detection algorithms. [...]

Scrolling through discourse about the evil vector, I stumbled across a group of people dismayed that the papers they were reviewing for NeurIPS didn’t include proper error bars. In fact, I learned that there’s a checklist that authors must fill out and attach to every NeurIPS submission. You can still learn things on social media.

The NeurIPS program chairs introduced the checklist in 2021. They argued that the community wanted “both more guidance around how to perform machine learning research responsibly and more flexibility in how they discuss this in their papers.” They came to this conclusion after listening at the “NeurIPS 2020 broader impacts workshop,” a fully remote workshop held during the cold, dark winter of the second wave of the covid pandemic. They argued that they would experiment with a checklist as a way to facilitate more responsible machine learning.

They called the checklist “experimental,” though there is no control group.1 They hoped that “future Program Chairs will continue to improve and evolve the checklist in subsequent years.” You don’t have to be a bureaucracy scholar to know that checklists “improve and evolve” by metastasizing in length and complexity. And that’s precisely what we’ve seen.

The NeurIPS paper checklist is now 3800 words long. This is twice as long as the original checklist, and has 3 times as many items to check off. It’s a lot of ridiculous infantilizing boilerplate. Item 1: “Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?” Come on, folks. You are required to check that you have read the code of ethics (another 2000 words here). You are asked to check whether you obtained the appropriate IRB approvals. Of course, this only applies if you are at a university. There’s a call out to the AI Safety dorks: “Do you have safeguards in place for responsible release of models with a high risk for misuse (e.g., pretrained language models)?” Come on, folks!

But I’m particularly fascinated by the weird obsession with statistics. I imagine Leo Breiman is chuckling up in heaven that one of the two cultures is trying to strangle the more successful one.2 In 2021, there was a single line about statistics:

2021: Did you report error bars (e.g., with respect to the random seed after running experiments multiple times)?

Honestly, not the worst question in the world. So much of machine learning and AI is based on randomized algorithms, and it’s good to check whether you have a stable result (i.e., training a neural net for classification) or a wildly variable result (i.e., using reinforcement learning to game a robotics simulator). But someone on the steering committee decided we needed a longer rule set and more statistics. The statistics creep began in 2023:

2023: If you ran experiments, did you report error bars (e.g., with respect to the random seed after running experiments multiple times), or other information about the statistical significance of your experiments?

And eventually, due to some unknown person’s lobbying, these were expanded further in 2024:

2024: “The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.). The assumptions made should be given (e.g., Normally distributed errors). It should be clear whether the error bar is the standard deviation or the standard error of the mean. It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). If error bars are reported in tables or plots, the authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.”

What does this have to do with anything? If I run my code ten times, why should you care if I properly account for normal approximations? Who does this help?

Anyway, I love that NeurIPS is proving my central thesis about statistics: Statistics is a bunch of arbitrary rules we use for approval. These arbitrary rules have now found their way into the machine learning publication machine. Whereas I understand why we require statistical tests when approving pharmaceuticals, no one has provided an explanation for why (or if) these statistical guidelines improve the quality of the thirty thousand NeurIPS submissions.

Indeed, I can’t figure out why people have become so obsessed with error bars in machine learning. I have been told that it’s because data sets are “small” now. For example, some of the “can LLM solve human tests” data sets have a few dozen questions. The AIME benchmark has 15. But what do frequentist error bars buy you here? This isn’t like Fisher’s friend who tastes tea. If a machine can solve a single one of these problems, it’s interesting! LLM answers are variable by design. Trying to gauge this variability with “Gaussian approximations to the standard errors of the mean” misses the forest for the trees. Indeed, if you only have 15 questions in a dataset, you don’t need statistics. Just look at the answers! We’re not grading the LLM on a curve here.

The obsession with statistics is particularly ironic because the advances in machine learning from the past 15 years have been entirely based on optimaxxing vibes. While program committees and responsible ethics boards fixate on procedure, the big ideas have come from “this feels right,” whether they be bigger convnets, ADAM optimizers, attention mechanisms, or anything in RL. Do you think recent trends in transformer architectures like using RMSNorm instead of Layernorm or SwiGLU instead of ReLU are undergirded by deep statistical grounding?3

What gives away the whole checklist charade here is bullet 4. The rules say that you must disclose the normal approximations in your error bars, but you don’t have to release code.

"While NeurIPS does not require releasing code, we do require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution.“

Why no code? It’s because a substantial fraction of NeurIPS papers come from private companies. The biggest models come from private companies. The conference exists to enrich Sam Altman. There’s no recruiting fair, no late-night parties, no signing bonuses based on Google Scholar profiles without the corporate commitment. So we can pat ourselves on the back and tell ourselves we’re being responsible researchers as we fill out our checklists and format our error bars. But let’s not kid ourselves about what we’re participating in.

Subscribe now

By Ben Recht

Authors: Vivien Ducros, Claudio Zandron

Membrane systems represent a computational model that operates in a distributed and parallel manner, inspired by the behavior of biological cells. These systems feature objects that transform within a nested membrane structure. This research concentrates on a specific type of these systems, based on cellular symport/antiport communication of chemicals. Results in the literature show that systems of this type that also allow cell division can solve PSPACE problems. In our study, we investigate systems that use membrane separation instead of cell division, for which only limited results are available. Notably, it has been shown that any problem solvable by such systems in polynomial time falls within the complexity class P^(#P). By implementing a system solving MIDSAT, a P^(#P)-complete problem, we demonstrate that the reverse inclusion is true as well, thus providing an exact characterization of the problem class solvable by P systems with symport/antiport and membrane separation. Moreover, our implementation uses rules of length at most three. With this limit, systems were known to be able to solve NP-complete problems, whereas limiting the rules by length two, they characterize P.

Authors: Taiga Hiroka, Min-Hsiu Hsieh, Tomoyuki Morimae

The existence of one-way functions (OWFs) forms the minimal assumption in classical cryptography. However, this is not necessarily the case in quantum cryptography. One-way puzzles (OWPuzzs), introduced by Khurana and Tomer, provide a natural quantum analogue of OWFs. The existence of OWPuzzs implies $PP\neq BQP$, while the converse remains open. In classical cryptography, the analogous problem-whether OWFs can be constructed from $P \neq NP$-has long been studied from the viewpoint of hardness of learning. Hardness of learning in various frameworks (including PAC learning) has been connected to OWFs or to $P \neq NP$. In contrast, no such characterization previously existed for OWPuzzs. In this paper, we establish the first complete characterization of OWPuzzs based on the hardness of a well-studied learning model: distribution learning. Specifically, we prove that OWPuzzs exist if and only if proper quantum distribution learning is hard on average. A natural question that follows is whether the worst-case hardness of proper quantum distribution learning can be derived from $PP \neq BQP$. If so, and a worst-case to average-case hardness reduction is achieved, it would imply OWPuzzs solely from $PP \neq BQP$. However, we show that this would be extremely difficult: if worst-case hardness is PP-hard (in a black-box reduction), then $SampBQP \neq SampBPP$ follows from the infiniteness of the polynomial hierarchy. Despite that, we show that $PP \neq BQP$ is equivalent to another standard notion of hardness of learning: agnostic. We prove that $PP \neq BQP$ if and only if agnostic quantum distribution learning with respect to KL divergence is hard. As a byproduct, we show that hardness of agnostic quantum distribution learning with respect to statistical distance against $PPT^{\Sigma_3^P}$ learners implies $SampBQP \neq SampBPP$.

Authors: Venkatesan Guruswami, Xuandi Ren, Kewen Wu

The Reconfiguration Inapproximability Hypothesis (RIH), recently established by Hirahara-Ohsaka (STOC'24) and Karthik-Manurangsi (ECCC'24), studies the hardness of reconfiguring one solution into another in constraint satisfaction problems (CSP) when restricted to approximate intermediate solutions. In this work, we make a tighter connection between RIH's soundness gap and that of probabilistically checkable proofs of proximity (PCPP). Consequently, we achieve an improved trade-off between soundness and query complexity in Gap CSP Reconfiguration. Our approach leverages a parallelization framework, which also appears in some recent parameterized inapproximability results.

Authors: Anna Brötzner, Bengt J. Nilsson, Christiane Schmidt

We consider the watchman route problem for multiple watchmen in staircase polygons, which are rectilinear $x$- and $y$-monotone polygons. For two watchmen, we propose an algorithm to find an optimal solution that takes quadratic time, improving on the cubic time of a trivial solution. For $m \geq 3$ watchmen, we explain where this approach fails, and present an approximation algorithm for the min-max criterion with only an additive error.

Authors: Haitao Wang

In this paper, we present a deterministic variant of Chan's randomized partition tree [Discret. Comput. Geom., 2012]. This result leads to numerous applications. In particular, for $d$-dimensional simplex range counting (for any constant $d \ge 2$), we construct a data structure using $O(n)$ space and $O(n^{1+\epsilon})$ preprocessing time, such that each query can be answered in $o(n^{1-1/d})$ time (specifically, $O(n^{1-1/d} / \log^{\Omega(1)} n)$ time), thereby breaking an $\Omega(n^{1-1/d})$ lower bound known for the semigroup setting. Notably, our approach does not rely on any bit-packing techniques. We also obtain deterministic improvements for several other classical problems, including simplex range stabbing counting and reporting, segment intersection detection, counting and reporting, ray-shooting among segments, and more. Similar to Chan's original randomized partition tree, we expect that additional applications will emerge in the future, especially in situations where deterministic results are preferred.

Authors: Benjamin Kraljusic, Zlatan Ajanovic, Nermin Covic, Bakir Lacevic

This work proposes a motion planning algorithm for robotic manipulators that combines sampling-based and search-based planning methods. The core contribution of the proposed approach is the usage of burs of free configuration space (C-space) as adaptive motion primitives within the graph search algorithm. Due to their feature to adaptively expand in free C-space, burs enable more efficient exploration of the configuration space compared to fixed-sized motion primitives, significantly reducing the time to find a valid path and the number of required expansions. The algorithm is implemented within the existing SMPL (Search-Based Motion Planning Library) library and evaluated through a series of different scenarios involving manipulators with varying number of degrees-of-freedom (DoF) and environment complexity. Results demonstrate that the bur-based approach outperforms fixed-primitive planning in complex scenarios, particularly for high DoF manipulators, while achieving comparable performance in simpler scenarios.

Authors: Erin W. Chambers, Guangyu Meng

Reeb graphs are a fundamental structure for analyzing the topological and geometric properties of scalar fields. Comparing Reeb graphs is crucial for advancing research in this domain, yet existing metrics are often computationally prohibitive or fail to capture essential topological features effectively. In this paper, we explore the application of the Gromov-Wasserstein distance, a versatile metric for comparing metric measure spaces, to Reeb graphs. We propose a framework integrating a symmetric variant of the Reeb radius for robust geometric comparison, and a novel probabilistic weighting scheme based on Persistence Images derived from extended persistence diagrams to effectively incorporate topological significance. A key contribution of this work is the rigorous theoretical proof of the stability of our proposed Reeb Gromov-Wasserstein distance with respect to perturbations in the underlying scalar fields. This ensures that small changes in the input data lead to small changes in the computed distance between Reeb graphs, a critical property for reliable analysis. We demonstrate the advantages of our approach, including its enhanced ability to capture topological features and its proven stability, through comparisons with other alternatives on several datasets, showcasing its practical utility and theoretical soundness.

Authors: Anders Aamand, Justin Y. Chen, Mina Dalirrooyfard, Slobodan Mitrović, Yuriy Nevmyvaka, Sandeep Silwal, Yinzhan Xu

We study differentially private algorithms for graph cut sparsification, a fundamental problem in algorithms, privacy, and machine learning. While significant progress has been made, the best-known private and efficient cut sparsifiers on $n$-node graphs approximate each cut within $\widetilde{O}(n^{1.5})$ additive error and $1+\gamma$ multiplicative error for any $\gamma > 0$ [Gupta, Roth, Ullman TCC'12]. In contrast, "inefficient" algorithms, i.e., those requiring exponential time, can achieve an $\widetilde{O}(n)$ additive error and $1+\gamma$ multiplicative error [Eli{\'a}{\v{s}}, Kapralov, Kulkarni, Lee SODA'20]. In this work, we break the $n^{1.5}$ additive error barrier for private and efficient cut sparsification. We present an $(\varepsilon,\delta)$-DP polynomial time algorithm that, given a non-negative weighted graph, outputs a private synthetic graph approximating all cuts with multiplicative error $1+\gamma$ and additive error $n^{1.25 + o(1)}$ (ignoring dependencies on $\varepsilon, \delta, \gamma$). At the heart of our approach lies a private algorithm for expander decomposition, a popular and powerful technique in (non-private) graph algorithms.

Authors: Mina Dalirrooyfard, Konstantin Makarychev, Slobodan Mitrović

We present a new Correlation Clustering algorithm for a dynamic setting where nodes are added one at a time. In this model, proposed by Cohen-Addad, Lattanzi, Maggiori, and Parotsidis (ICML 2024), the algorithm uses database queries to access the input graph and updates the clustering as each new node is added. Our algorithm has the amortized update time of $O_{\epsilon}(\log^{O(1)}(n))$. Its approximation factor is $20+\varepsilon$, which is a substantial improvement over the approximation factor of the algorithm by Cohen-Addad et al. We complement our theoretical findings by empirically evaluating the approximation guarantee of our algorithm. The results show that it outperforms the algorithm by Cohen-Addad et al.~in practice.

Authors: Steinar Laenen, Peter Macgregor, He Sun

In the kernel density estimation (KDE) problem, we are given a set $X$ of data points in $\mathbb{R}^d$, a kernel function $k: \mathbb{R}^d \times \mathbb{R}^d \rightarrow \mathbb{R}$, and a query point $\mathbf{q} \in \mathbb{R}^d$, and the objective is to quickly output an estimate of $\sum_{\mathbf{x} \in X} k(\mathbf{q}, \mathbf{x})$. In this paper, we consider $\textsf{KDE}$ in the dynamic setting, and introduce a data structure that efficiently maintains the estimates for a set of query points as data points are added to $X$ over time. Based on this, we design a dynamic data structure that maintains a sparse approximation of the fully connected similarity graph on $X$, and develop a fast dynamic spectral clustering algorithm. We further evaluate the effectiveness of our algorithms on both synthetic and real-world datasets.

Authors: Surender Baswana, Koustav Bhanja, Anupam Roy

We study (s,t)-cuts of second minimum capacity and present the following algorithmic and graph-theoretic results. 1. Vazirani and Yannakakis [ICALP 1992] designed the first algorithm for computing an (s,t)-cut of second minimum capacity using $O(n^2)$ maximum (s,t)-flow computations. For directed integer-weighted graphs, we significantly improve this bound by designing an algorithm that computes an $(s,t)$-cut of second minimum capacity using $O(\sqrt{n})$ maximum (s,t)-flow computations w.h.p. To achieve this result, a close relationship of independent interest is established between $(s,t)$-cuts of second minimum capacity and global mincuts in directed weighted graphs. 2. Minimum+1 (s,t)-cuts have been studied quite well recently [Baswana, Bhanja, and Pandey, ICALP 2022], which is a special case of second (s,t)-mincut. (a) For directed multi-graphs, we design an algorithm that, given any maximum (s,t)-flow, computes a minimum+1 (s,t)-cut, if it exists, in $O(m)$ time. (b) The existing structures for storing and characterizing all minimum+1 (s,t)-cuts occupy $O(mn)$ space. For undirected multi-graphs, we design a DAG occupying only $O(m)$ space that stores and characterizes all minimum+1 (s,t)-cuts. 3. The study of minimum+1 (s,t)-cuts often turns out to be useful in designing dual edge sensitivity oracles -- a compact data structure for efficiently reporting an (s,t)-mincut after insertion/failure of any given pair of query edges. It has been shown recently [Bhanja, ICALP 2025] that any dual edge sensitivity oracle for (s,t)-mincut in undirected multi-graphs must occupy ${\Omega}(n^2)$ space in the worst-case, irrespective of the query time. For simple graphs, we break this quadratic barrier while achieving a non-trivial query time.

Authors: Debasish Pattanayak, Ajay D. Kshemkalyani, Manish Kumar, Anisur Rahaman Molla, Gokarna Sharma

We study the dispersion problem in anonymous port-labeled graphs: $k \leq n$ mobile agents, each with a unique ID and initially located arbitrarily on the nodes of an $n$-node graph with maximum degree $\Delta$, must autonomously relocate so that no node hosts more than one agent. Dispersion serves as a fundamental task in distributed computing of mobile agents, and its complexity stems from key challenges in local coordination under anonymity and limited memory. The goal is to minimize both the time to achieve dispersion and the memory required per agent. It is known that any algorithm requires $\Omega(k)$ time in the worst case, and $\Omega(\log k)$ bits of memory per agent. A recent result [SPAA'25] gives an optimal $O(k)$-time algorithm in the synchronous setting and an $O(k \log k)$-time algorithm in the asynchronous setting, both using $O(\log(k+\Delta))$ bits. In this paper, we close the complexity gap in the asynchronous setting by presenting the first dispersion algorithm that runs in optimal $O(k)$ time using $O(\log(k+\Delta))$ bits of memory per agent. Our solution is based on a novel technique we develop in this paper that constructs a port-one tree in anonymous graphs, which may be of independent interest.

A new dean has taken my place, and I have returned to the professoriate at Illinois Tech, ending thirteen years in administration, six as dean and seven as department chair at Georgia Tech. I won't rule out more administrative roles in the future, but only if the right role presents itself.

I'll teach intro theory in the fall, my first course since 2018, and take a sabbatical in the spring, mostly at Oxford. I plan to focus on writing, hoping to get out another book or books and other projects. It will be hard to go back to traditional computational complexity research, the field has changed considerably. I plan to spend some time understanding how AI changes the way we think about computation. Particularly why we see many of the benefits of P = NP while cryptography remains secure.

Also for the first time in 13 years I don't have a "boss". Technically I report to the department chair, who until a few days ago reported to me. But tenure protects my job, I choose my own research agenda, and teaching and service assignments are more of a negotiation than a top-down decision. Freedom!

For the blog, I have held back talking about the inner workings of universities while I had administrative roles. I'll now be more open in giving my thoughts, at least in general terms.

The next chapter begins...

By Lance Fortnow

Annual meeting of the Israeli Mathematical Union and student talks day, July 6 and 7

The Annual meeting of the Israeli Mathematical Union will be held on Sunday, July 6th 2025 at Bar-Ilan University. The main speakers will be Elon Lindenstrauss, Amnon Shashua and  the 2025 Erdos Prize recipients Or Hershkovits and Eliran Subag. There will also be ten parallel sessions. The IMU student talks day 2025 will be held on Monday, July 7 at the same location. The Day will feature Plenary talks by the Wolf Prize laureate Noga Alon and Adi Shamir (see this post), and  the Nesiyahu prize recepient Pazit Haim-Kislev (see this post) and contributed talks by thirty one graduate students (program).

Joram’s Seminar: Hypercontractivity and Groups, July 9 and 10

The Joram Seminar new dates are July 9-10.
This year the topic will be “Hypercontractivity and Groups”, and the speakers are Noam Lifshitz and Guy Kindler (Hebrew University), Nathan Keller (Bar Ilan University) and Dor Minzer (MIT). For information on hypercontractivity see this post and this post.

Amitsur Memorial Symposum 2025, July 14

The symposium this year is in memoriam of Ilya (Eliyahu) Rips.

By Gil Kalai

Authors: Jefferson D. S. Silva, Adenilton J. da Silva

The synthesis of quantum operators involves decomposing general quantum gates into the gate set supported by a given quantum device. Multi-controlled gates are essential components in this process. In this work, we present improved decompositions of multi-controlled NOT gates with logarithmic depth using a single ancilla qubit, while also reducing the constant factors in the circuit depth compared to previous work. We optimize a previously proposed decomposition of multi-target, multi-controlled special unitary SU(2) gates by identifying the presence of a conditionally clean qubit. Additionally, we introduce the best-known decomposition of multi-controlled approximate unitary U(2) gates without using ancilla qubits. This approach significantly reduces the overall circuit depth and CNOT count while preserving an adjustable error parameter, yielding a more efficient and scalable solution for synthesizing large controlled-unitary gates. Our method is particularly suitable for both NISQ and fault-tolerant quantum architectures. All software developed in this project is freely available.

Authors: Deepu Benson, Balagopal Komarath, Nikhil Mande, Sai Soumya Nalli, Jayalal Sarma, Karteek Sreenivasaiah

In this paper, we study the query complexity of Boolean functions in the presence of uncertainty, motivated by parallel computation with an unlimited number of processors where inputs are allowed to be unknown. We allow each query to produce three results: zero, one, or unknown. The output could also be: zero, one, or unknown, with the constraint that we should output ''unknown'' only when we cannot determine the answer from the revealed input bits. Such an extension of a Boolean function is called its hazard-free extension. - We prove an analogue of Huang's celebrated sensitivity theorem [Annals of Mathematics, 2019] in our model of query complexity with uncertainty. - We show that the deterministic query complexity of the hazard-free extension of a Boolean function is at most quadratic in its randomized query complexity and quartic in its quantum query complexity, improving upon the best-known bounds in the Boolean world. - We exhibit an exponential gap between the smallest depth (size) of decision trees computing a Boolean function, and those computing its hazard-free extension. - We present general methods to convert decision trees for Boolean functions to those for their hazard-free counterparts, and show optimality of this construction. We also parameterize this result by the maximum number of unknown values in the input. - We show lower bounds on size complexity of decision trees for hazard-free extensions of Boolean functions in terms of the number of prime implicants and prime implicates of the underlying Boolean function.

Authors: Vanja Stojanović, Bor Pangeršič

The NP-complete mutual-visibility (MV) problem currently lacks empirical analysis on its practical behaviour despite theoretical studies. This paper addresses this gap by implementing and evaluating three distinct algorithms - a direct greedy heuristic, a hypergraph-based approximation, and a genetic algorithm - on diverse synthetic graph datasets, including those with analytically known $\mu(G)$ values and general graph models. Our results demonstrate that for smaller graphs, the algorithms consistently achieve MV set sizes aligning with theoretical bounds. However, for larger instances, achieved solution sizes notably diverge from theoretical limits; this, combined with the absence of tight bounds, complicates absolute quality assessment. Nevertheless, validation on known optimal graphs showed the Genetic Algorithm and other heuristics empirically performing best among tested methods.

Authors: Amritendu Dhar, Apratim Chakraborty, Vijay Natarajan

Morse-Cerf theory considers a one-parameter family of smooth functions defined on a manifold and studies the evolution of their critical points with the parameter. This paper presents an adaptation of Morse-Cerf theory to a family of piecewise-linear (PL) functions. The vertex diagram and Cerf diagram are introduced as representations of the evolution of critical points of the PL function. The characterization of a crossing in the vertex diagram based on the homology of the lower links of vertices leads to the definition of a topological descriptor for time-varying scalar fields. An algorithm for computing the Cerf diagram and a measure for comparing two Cerf diagrams are also described together with experimental results on time-varying scalar fields.

Authors: Jean Cardinal, Yelena Yuditsky

We consider the existence and construction of \textit{biclique covers} of graphs, consisting of coverings of their edge sets by complete bipartite graphs. The \textit{size} of such a cover is the sum of the sizes of the bicliques. Small-size biclique covers of graphs are ubiquitous in computational geometry, and have been shown to be useful compact representations of graphs. We give a brief survey of classical and recent results on biclique covers and their applications, and give new families of graphs having biclique covers of near-linear size. In particular, we show that semilinear graphs, whose edges are defined by linear relations in bounded dimensional space, always have biclique covers of size $O(n\polylog n)$. This generalizes many previously known results on special classes of graphs including interval graphs, permutation graphs, and graphs of bounded boxicity, but also new classes such as intersection graphs of L-shapes in the plane. It also directly implies the bounds for Zarankiewicz's problem derived by Basit, Chernikov, Starchenko, Tao, and Tran (\textit{Forum Math. Sigma}, 2021). We also consider capped graphs, also known as terrain-like graphs, defined as ordered graphs forbidding a certain ordered pattern on four vertices. Terrain-like graphs contain the induced subgraphs of terrain visibility graphs. We give an elementary proof that these graphs admit biclique partitions of size $O(n\log^3 n)$. This provides a simple combinatorial analogue of a classical result from Agarwal, Alon, Aronov, and Suri on polygon visibility graphs (\textit{Discrete Comput. Geom.} 1994). Finally, we prove that there exists families of unit disk graphs on $n$ vertices that do not admit biclique coverings of size $o(n^{4/3})$, showing that we are unlikely to improve on Szemer\'edi-Trotter type incidence bounds for higher-degree semialgebraic graphs.

Authors: Davide Bilò, Giodano Colli, Luca Forlizzi, Stefano Leucci

We study the minimum \emph{Monitoring Edge Geodetic Set} (\megset) problem introduced in [Foucaud et al., CALDAM'23]: given a graph $G$, we say that an edge is monitored by a pair $u,v$ of vertices if \emph{all} shortest paths between $u$ and $v$ traverse $e$; the goal of the problem consists in finding a subset $M$ of vertices of $G$ such that each edge of $G$ is monitored by at least one pair of vertices in $M$, and $|M|$ is minimized. In this paper, we prove that all polynomial-time approximation algorithms for the minimum \megset problem must have an approximation ratio of $\Omega(\log n)$, unless \p = \np. To the best of our knowledge, this is the first non-constant inapproximability result known for this problem. We also strengthen the known \np-hardness of the problem on $2$-apex graphs by showing that the same result holds for $1$-apex graphs. This leaves open the problem of determining whether the problem remains \np-hard on planar (i.e., $0$-apex) graphs. On the positive side, we design an algorithm that computes good approximate solutions for hereditary graph classes that admit efficiently computable balanced separators of truly sublinear size. This immediately results in polynomial-time approximation algorithms achieving an approximation ratio of $O(n^{\frac{1}{4}} \sqrt{\log n})$ on planar graphs, graphs with bounded genus, and $k$-apex graphs with $k=O(n^{\frac{1}{4}})$. On graphs with bounded treewidth, we obtain an approximation ratio of $O(\log^{3/2} n)$ for any constant $\varepsilon > 0$. This compares favorably with the best-known approximation algorithm for general graphs, which achieves an approximation ratio of $O(\sqrt{n \log n})$ via a simple reduction to the \textsc{Set Cover} problem.

Authors: Benjamin Bergougnoux, Lars Jaffke

We prove that Hamiltonian Path and Hamiltonian Cycle are NP-hard on graphs of linear mim-width 26, even when a linear order of the input graph with mim-width 26 is provided together with input. This fills a gap left by a broken proof of the para-NP-hardness of Hamiltonicity problems parameterized by mim-width.

Authors: Susanna Caroppo, Giordano Da Lozzo, Giuseppe Di Battista, Michael T. Goodrich, Martin Nöllenburg

We introduce a quantum dynamic programming framework that allows us to directly extend to the quantum realm a large body of classical dynamic programming algorithms. The corresponding quantum dynamic programming algorithms retain the same space complexity as their classical counterpart, while achieving a computational speedup. For a combinatorial (search or optimization) problem $\mathcal P$ and an instance $I$ of $\mathcal P$, such a speedup can be expressed in terms of the average degree $\delta$ of the dependency digraph $G_{\mathcal{P}}(I)$ of $I$, determined by a recursive formulation of $\mathcal P$. The nodes of this graph are the subproblems of $\mathcal P$ induced by $I$ and its arcs are directed from each subproblem to those on whose solution it relies. In particular, our framework allows us to solve the considered problems in $\tilde{O}(|V(G_{\mathcal{P}}(I))| \sqrt{\delta})$ time. As an example, we obtain a quantum version of the Bellman-Ford algorithm for computing shortest paths from a single source vertex to all the other vertices in a weighted $n$-vertex digraph with $m$ edges that runs in $\tilde{O}(n\sqrt{nm})$ time, which improves the best known classical upper bound when $m \in \Omega(n^{1.4})$.

Authors: Matthew Stephenson, Alex Newcombe, Eric Piette, Dennis Soemers

We present an efficient and generalised procedure to accurately identify the best performing algorithm for each sub-task in a multi-problem domain. Our approach treats this as a set of best arm identification problems for multi-armed bandits, where each bandit corresponds to a specific task and each arm corresponds to a specific algorithm or agent. We propose an optimistic selection process based on the Wilson score interval (Optimistic-WS) that ranks each arm across all bandits in terms of their potential regret reduction. We evaluate the performance of Optimistic-WS on two of the most popular general game domains, the General Video Game AI (GVGAI) framework and the Ludii general game playing system, with the goal of identifying the highest performing agent for each game within a limited number of trials. Compared to previous best arm identification algorithms for multi-armed bandits, our results demonstrate a substantial performance improvement in terms of average simple regret. This novel approach can be used to significantly improve the quality and accuracy of agent evaluation procedures for general game frameworks, as well as other multi-task domains with high algorithm runtimes.

Authors: Casper Moldrup Rysgaard, Sebastian Wild

Lazy search trees (Sandlund & Wild FOCS 2020, Sandlund & Zhang SODA 2022) are sorted dictionaries whose update and query performance smoothly interpolates between that of efficient priority queues and binary search trees - automatically, depending on actual use; no adjustments are necessary to the data structure to realize the cost savings. In this paper, we design lazy B-trees, a variant of lazy search trees suitable for external memory that generalizes the speedup of B-trees over binary search trees wrt. input/output operations to the same smooth interpolation regime. A key technical difficulty to overcome is the lack of a (fully satisfactory) external variant of biased search trees, on which lazy search trees crucially rely. We give a construction for a subset of performance guarantees sufficient to realize external-memory lazy search trees, which we deem of independent interest. As one special case, lazy B-trees can be used as an external-memory priority queue, in which case they are competitive with some tailor-made heaps; indeed, they offer faster decrease-key and insert operations than known data structures.

Authors: Nick Fischer, Melvin Kallmayer, Leo Wennmann

Evaluating a polynomial on a set of points is a fundamental task in computer algebra. In this work, we revisit a particular variant called trimmed multipoint evaluation: given an $n$-variate polynomial with bounded individual degree $d$ and total degree $D$, the goal is to evaluate it on a natural class of input points. This problem arises as a key subroutine in recent algorithmic results [Dinur; SODA '21], [Dell, Haak, Kallmayer, Wennmann; SODA '25]. It is known that trimmed multipoint evaluation can be solved in near-linear time [van der Hoeven, Schost; AAECC '13] by a clever yet somewhat involved algorithm. We give a simple recursive algorithm that avoids heavy computer-algebraic machinery, and can be readily understood by researchers without specialized background.

Kanazawa was this year’s host of Computational Geometry Week and the Symposium on Computational Geometry, and a great place to visit for lots of reasons. One of the lesser reasons is that it also hosts an interesting collection of geometric street art, some of which I photographed on my recent visit.

The first thing you see as you enter the city by the main entrance of its train station is Tsuzumimon, a massive ornamental wooden gate. The two pillars of the gate are made from wood beams in two layers that twist around each pillar in opposite directions. The lintel connecting the two pillars is a lattice of more wood, in a rounded form rather than the more traditional straight beam. The gate supports one end of an airy steel and glass space-frame dome, sheltering the plaza in front of the station from the frequent rain.

Tsuzumi are a certain type of Japanese hand drum, so Tsuzumimon means drum gate, because of the resemblance of the pillars to these drums. But instead, what it most reminds me of is a partition of space into skew lines that I ray-traced in 2010 and use as the header for my Mastodon account page.

A short way along the road to the fish market (worth multiple visits), one encounters this piece, “Corpus Minor #1” by Janne Kristian Virkkunen. Another conference participant told me he thought it resembled a shipping mine, but what it brings to mind to me is either an atomic nucleus or a morula (the complex of cells of a multi-cell organism at the stage of reproduction before they differentiate).

Here’s a more abstracted close-up look.

I’m pretty sure its underlying geometric structure comes from a tetrakis hexahedron, whose edges form the prominent ribs of the sculpture. This would allow it to be constructed by bolting together 24 identical triangular pieces, each containing smoothed-together patches from three of the 14 spherical bulges of the sculpture.

The part of Kanazawa between the station and the fish market is dominated by major boulevards filled with cars, and long waits for crosswalks. To make it somewhat less unfriendly to pedestrian traffic, the city has installed underpasses at several of the major crossings. It’s easy to miss the next piece, at the central hub of the underpass connecting to the fish market itself.

Also seen but not photographed: another large ornamental gate near the back entrance of the station, made of slanted concrete pillars and resembling a support structure for an elevated highway; a black stone monkey saddle in the basement level of the station, near a scale model of Tsuzumimon; a tangled tree of shiny stainless steel tubes across the street from my hotel (a block south of the station); a stylized sundial between the station and the fish market (not very effective in the rain); and many public fountains.

(Discuss on Mastodon)

By David Eppstein

Today marks the 2nd anniversary of this substack, and my elaborate blogging rule book compels me to write an annual reflection post. Whereas the first year was experimental and finding my footing, the second year has been decidedly more routine. That’s not a bad thing, as I love rituals. Wake up, brush my teeth, make two pour-over coffees, be harassed by the cat, blog.1 There’s a reassurance in these daily rituals themselves, where the process can be as rewarding as the product.

I’m only half joking about having a blogging rule book. I’ve never written it down, but some of the rules are

1. Spend the first hour of each working day blogging.

2. Aim for 1000 words. If I hit that number, publish.

3. If I don’t hit 1000 words today, try to finish the piece tomorrow.

4. Make equations with LaTeXit, 14 pt font.

5. Every equation halves your readership (This is a Stephen Hawking rule.)

6. Don’t overthink the titles.

7. A banner by Isaac Sparks goes at the top of each post, subscribe button at the bottom.

8. 14:00 GMT is international posting time. (This is a Brian Whitman rule.)

9. Aim for two posts a week. Don’t post more than four.

I have a different set of rules for class liveblogging. I invented my own set of rules for working through Meehl’s course. Maybe I should spend more time writing these rules down. I’m sure there are many more I haven’t even articulated to myself.

Whatever the case, I’ve got a process now and I’m sticking to it. The rules are oddly freeing. Rules give you a “freedom from choice,” paring down the degrees of freedom to one where you are able to create but are not overwhelmed by options. They are “constraints that deconstrain,” facilitating improvisation within the narrow boundaries of the ruleset.

Part of my obsession with bureaucracy is that I love rules, and yet bureaucratic rules so frequently lack the deconstraining property that lets people flourish. Making matters worse, bureaucratic processes stifle course correction because by their nature. They are necessarily ossified and onerous to change. That’s a topic for a longer conversation in another post.

In any event, while I don’t have a clear idea of the topics I’ll be covering in year three of the argmin substack, I do know the starting rule book I’ll be using. And I’m trying to think a bit about rule changes for the upcoming season.2

Part of these rule changes will be adapting to new goals for this season. One thing I haven’t been able to do is use my blogging time as “real writing” time. I’ve taken some mornings and tried to work on other writing projects during my allotted blogging time, and it hasn’t been helpful. That’s interesting in itself. This blog post writing is fundamentally different from the more archival writing, and the latter needs its own set of rules.

I should figure those rules out because I am in a stage where I should write a few more papers. You know, blog posts with DOIs. I don’t want to write too many papers, but some folks have suggested that it would be helpful to collect and collate some of the meandering thoughts here into tighter arguments. My blog posts are first drafts of thoughts, not finished ones. I don’t consider any of the arguments here to be definitive. I love that you all think out loud with me. Nonetheless, some of them are worth preserving in academic amber, and I need to do my scholarly duties of mailing pdfs to my friends. I’ve written two blog posts with DOIs this year (this one, that one), and I have three or four more I should try to finish. I also have a few more books in me that I want to write. I will have more news on that front coming very soon. Finding the right way to balance writing time is going to be an important part of argmin year three.

Another goal is finding the best balance for the multiple audiences who read this. Some posts get very technical, but there is a slice of the readership that enjoys those. I have tried to maintain a balance that doesn't alienate those who don’t want the math, while also engaging with those who do. I could split this blog into multiple newsletters, but that seems like a lot of unnecessary work, and I know everyone must have incredible substack subscription fatigue at this point. I could perhaps signal at the top of each post whether I’m going to get into the weeds. If you have any ideas on how to strike the right balance and send the right signals, please send me an email or leave a comment. Hopefully, you folks who agree to be spammed by me are fine with closing the posts that are too hypertechnical and selectively reading the ones that hook you.

Regardless, I love the feedback you send me, and I apologize if I miss any or don’t reply. I read them all and value them all. I look forward to more of them in year three.

Subscribe now

By Ben Recht

Authors: Igor Balla, Lianna Hambardzumyan, István Tomon

We prove that Boolean matrices with bounded $\gamma_2$-norm or bounded normalized trace norm must contain a linear-sized all-ones or all-zeros submatrix, verifying a conjecture of Hambardzumyan, Hatami, and Hatami. We also present further structural results about Boolean matrices of bounded $\gamma_2$-norm and discuss applications in communication complexity, operator theory, spectral graph theory, and extremal combinatorics. As a key application, we establish an inverse theorem for MaxCut. A celebrated result of Edwards states that every graph $G$ with $m$ edges has a cut of size at least $\frac{m}{2}+\frac{\sqrt{8m+1}-1}{8}$, with equality achieved by complete graphs with an odd number of vertices. To contrast this, we prove that if the MaxCut of $G$ is at most $\frac{m}{2}+O(\sqrt{m})$, then $G$ must contain a clique of size $\Omega(\sqrt{m})$.

Authors: Melissa Antonelli, Arnaud Durand, Juha Kontinen

In this paper, we provide a uniform framework for investigating small circuit classes and bounds through the lens of ordinary differential equations (ODEs). Following an approach recently introduced to capture the class of polynomial-time computable functions via ODE-based recursion schemas and later applied to the context of functions computed by unbounded fan-in circuits of constant depth (FAC^0), we study multiple relevant small circuit classes. In particular, we show that natural restrictions on linearity and derivation along functions with specific growth rate correspond to kinds of functions that can be proved to be in various classes, ranging from FAC^0 to FAC^1. This reveals an intriguing link between constraints over linear-length ODEs and circuit computation, providing new tools to tackle the complex challenge of establishing bounds for classes in the circuit hierarchies and possibly enhancing our understanding of the role of counters in this setting. Additionally, we establish several completeness results, in particular obtaining the first ODE-based characterizations for the classes of functions computable in constant depth with unbounded fan-in and Mod 2 gates (FACC[2]) and in logarithmic depth with bounded fan-in Boolean gates (FNC1).

Authors: Somnath Bhattacharjee, Mrinal Kumar, Shanthanu Rai, Varun Ramanathan, Ramprasad Saptharishi, Shubhangi Saraf

We show that the GCD of two univariate polynomials can be computed by (piece-wise) algebraic circuits of constant depth and polynomial size over any sufficiently large field, regardless of the characteristic. This extends a recent result of Andrews & Wigderson who showed such an upper bound over fields of zero or large characteristic. Our proofs are based on a recent work of Bhattacharjee, Kumar, Rai, Ramanathan, Saptharishi \& Saraf that shows closure of constant depth algebraic circuits under factorization. On our way to the proof, we show that any $n$-variate symmetric polynomial $P$ that has a small constant depth algebraic circuit can be written as the composition of a small constant depth algebraic circuit with elementary symmetric polynomials. This statement is a constant depth version of a result of Bl\"{a}ser & Jindal, who showed this for algebraic circuits of unbounded depth. As an application of our techniques, we also strengthen the closure results for factors of constant-depth circuits in the work of Bhattacharjee et al. over fields for small characteristic.

Authors: Somnath Bhattacharjee, Mrinal Kumar, Shanthanu S. Rai, Varun Ramanathan, Ramprasad Saptharishi, Shubhangi Saraf

We show that algebraic formulas and constant-depth circuits are closed under taking factors. In other words, we show that if a multivariate polynomial over a field of characteristic zero has a small constant-depth circuit or formula, then all its factors can be computed by small constant-depth circuits or formulas respectively. Our result turns out to be an elementary consequence of a fundamental and surprising result of Furstenberg from the 1960s, which gives a non-iterative description of the power series roots of a bivariate polynomial. Combined with standard structural ideas in algebraic complexity, we observe that this theorem yields the desired closure results. As applications, we get alternative (and perhaps simpler) proofs of various known results and strengthen the quantitative bounds in some of them. This includes a unified proof of known closure results for algebraic models (circuits, branching programs and VNP), an extension of the analysis of the Kabanets-Impagliazzo hitting set generator to formulas and constant-depth circuits, and a (significantly) simpler proof of correctness as well as stronger guarantees on the output in the subexponential time deterministic algorithm for factorization of constant-depth circuits from a recent work of Bhattacharjee, Kumar, Ramanathan, Saptharishi & Saraf.

Authors: Zach Hunter, Aleksa Milojević, Istvan Tomon, Benny Sudakov

The Zarankiewicz problem, a cornerstone problem in extremal graph theory, asks for the maximum number of edges in an $n$-vertex graph that does not contain the complete bipartite graph $K_{s,s}$. While the problem remains widely open in the case of general graphs, the past two decades have seen significant progress on this problem for various restricted graph classes -- particularly those arising from geometric settings -- leading to a deeper understanding of their structure. In this paper, we develop a new structural tool for addressing Zarankiewicz-type problems. More specifically, we show that for any positive integer $k$, every graph with average degree $d$ either contains an induced $C_4$-free subgraph with average degree at least $k$, or it contains a $d$-vertex subgraph with $\Omega_k(d^2)$ edges. As an application of this dichotomy, we propose a unified approach to a large number of Zarankiewicz-type problems in geometry, obtaining optimal bounds in each case.

Authors: Jing Huang, Hao Su, Kwok Wai Samuel Au

This paper introduces a new paradigm of optimal path planning, i.e., passage-traversing optimal path planning (PTOPP), that optimizes paths' traversed passages for specified optimization objectives. In particular, PTOPP is utilized to find the path with optimal accessible free space along its entire length, which represents a basic requirement for paths in robotics. As passages are places where free space shrinks and becomes constrained, the core idea is to leverage the path's passage traversal status to characterize its accessible free space comprehensively. To this end, a novel passage detection and free space decomposition method using proximity graphs is proposed, enabling fast detection of sparse but informative passages and environment decompositions. Based on this preprocessing, optimal path planning with accessible free space objectives or constraints is formulated as PTOPP problems compatible with sampling-based optimal planners. Then, sampling-based algorithms for PTOPP, including their dependent primitive procedures, are developed leveraging partitioned environments for fast passage traversal check. All these methods are implemented and thoroughly tested for effectiveness and efficiency validation. Compared to existing approaches, such as clearance-based methods, PTOPP demonstrates significant advantages in configurability, solution optimality, and efficiency, addressing prior limitations and incapabilities. It is believed to provide an efficient and versatile solution to accessible free space optimization over conventional avenues and more generally, to a broad class of path planning problems that can be formulated as PTOPP.

Authors: Crane He Chen, Vladimir G. Kim

We present a real-time deformation method for Escher tiles -- interlocking organic forms that seamlessly tessellate the plane following symmetry rules. We formulate the problem as determining a periodic displacement field. The goal is to deform Escher tiles without introducing gaps or overlaps. The resulting displacement field is obtained in closed form by an analytical solution. Our method processes tiles of 17 wallpaper groups across various representations such as images and meshes. Rather than treating tiles as mere boundaries, we consider them as textured shapes, ensuring that both the boundary and interior deform simultaneously. To enable fine-grained artistic input, our interactive tool features a user-controllable adaptive fall-off parameter, allowing precise adjustment of locality and supporting deformations with meaningful semantic control. We demonstrate the effectiveness of our method through various examples, including photo editing and shape sculpting, showing its use in applications such as fabrication and animation.

Authors: Javier Garcia, Jonas Friemel, Ramin Kosfeld, Michael Yannuzzi, Peter Kramer, Christian Rieck, Christian Scheffer, Arne Schmidt, Harm Kube, Dan Biediger, Sándor P. Fekete, Aaron T. Becker

We implement and evaluate different methods for the reconfiguration of a connected arrangement of tiles into a desired target shape, using a single active robot that can move along the tile structure. This robot can pick up, carry, or drop off one tile at a time, but it must maintain a single connected configuration at all times. Becker et al. (CCCG 2025) recently proposed an algorithm that uses histograms as canonical intermediate configurations, guaranteeing performance within a constant factor of the optimal solution if the start and target configuration are well-separated. We implement and evaluate this algorithm, both in a simulated and practical setting, using an inchworm type robot to compare it with two existing heuristic algorithms.