Theory of Computing Report

 The New Pope is Pope Leo XIV (pre-Pope name is Robert  Prevost). 

1) Pope names are one of the few places we still use Roman Numerals. I saw an article that was probably satirical that Americans prefer Roman Numerals (the numbers Jesus used) over Arabic Numerals. Also note that Pope Francis did not have a Roman Numeral- that is because he is the first Pope Francis. They could call him Pope Francis I now, rather than later, to avoid having to rewrite things. (John Paul I took the name John Paul I.)

2) Over the years I have  read the following and had the following thoughts (Spoiler- I was wrong on all of them)

a) The last non-Italian Pope was Pope Adrian VI who was Pope from Jan 9 1522 to Sept 14 1523. His Wikipedia entry: here. He was 80 years old when he became Pope and died of  a heart attack.

BILL THOUGHT: We will never see a non-Italian Pope again.

REALITY: John Paul II from Poland was Pope from 1978 until 2005. His Wikipedia page is here

MORE REALITY: Since then we've had Pope Benedict XVI (Germany), Pope Francis I (Argentina),and Pope Leo  XIV (America). I now wonder if we will ever have an Italian Pope again but I make no predictions. 

b) There will never be an American Pope because people think that America already has too much power and if there ever was an American Pope then people would think it was engineered by the CIA.

BILL THOUGHT: That sounded correct to me. Not that the election would be engineered by the CIA, but that people would think that. 

REALITY: Pope Leo XIV is American. Some MAGA people are calling Pope Leo a Woke Marxist Pope (see here). Not the type the CIA would install. 

QUESTION: How much power does the Pope really have? I ask non-rhetorically as always. 

c) The shortest Pope Reign was Pope Urban VII (1590) who reigned for 13 days. The tenth shortest was Pope Benedict V (964) who reigned for 33 days. I originally thought the short reigns were from assassinations, but I looked it up and there were two that may have been murdered, but the rest died of natural causes. Having looked it up I wrote it up here.

BILL THOUGHT: The 10th shortest reign was 33 days. With better health care and less skullduggery in the Papacy that won't happen again.

REALITY: Pope John-Paul I in 1978 died of a heart attack after being Pope for 33 days. 

d) The last Pope to resign was Pope Gregory XII in 1415 (his Wikipedia page is here). He resigned to heal a  schism in the church (its more complicated than that, see his Wikipedia page).

BILL THOUGHT: We will never see a Pope resign again.

REALITY: Pope Benedict XVI resigned (see here for the Wikipedia page on the resignation) in 2013. He said it was for health reasons.

BILL THOUGHT: Now that Pope Benedict has resigned it will be easier for later popes who feel they are not healthy enough for the job to resign. But I make no predictions. 

3) Pope Leo XIV has a degree in Mathematics. I emailed the following to my Ramsey Theory class which is an excerpt from his Wikipedia Page with one incorrect sentence. See if you can spot it. I will tell you what it is, and what the real line is, later. 

Prevost earned a Bachelor of Science (BS) degree in mathematics from Villanova University, an Augustinian college, in 1977. His Undergraduate Thesis was on Rado's Theorem for Nonlinear Equations.  He obtained a Master of Divinity (MDiv) from Catholic Theological Union in Chicago in 1982, also serving as a physics and math teacher at St. Rita of Cascia High School in Chicago during his studies. He earned a Licentiate of Canon Law in 1984, followed by a Doctor of Canon Law degree in 1987 from the Pontifical University of Saint Thomas Aquinas in Rome. His doctoral thesis was titled The Role of the Local Prior in the Order of Saint Augustine. Villanova University awarded him an honorary Doctor of Humanities degree in 2014

4) He is not the first Pope who knew some mathematics. In a general sense people used to be more well-rounded before fields got so specialized. So in that sense I am sure that some prior Popes knew some math. But more concretely Pope Sylvester II was, according to the article When the Pope was a Mathematician Europe's leading mathematician, (at the time a modest distinction) reigning as Pope Sylvester from  997 to1003. His Wikipedia page is here.

5) Since Pope Leo XIV was a mathematician, as Pope he won't only know about sin but also about cos.

6) The name Leo struck me since one of my TAs is named Leo. I asked him, if he became Pope, would he change his name. He said 

Hmm, after careful consideration, I think I would take another name. I like being Leo, but I think I would want to try out a different name. I looked up Papal names, and I would probably pick something cool like Boniface, Honorius, or Valentine. But I would do the name change after the semester ends so as not to screw up the payroll office. 

7) Popes did not always change their names. For a long article on that see here. For a short version here are some points:

a) The first Pope to change his name was born Mercurious, a Pagan God Name, and changed it to be Pope John II. That was in 533. 

b) The name-change did not become standard for a while. Before the year 1000 only 3 Popes changed their names, all to John. The other two had given name Peter and felt they should not take the name Peter since Peter was the first Pope and an apostle. Kind of like having a jersey number retired by a sports team.

c) After the year 1000 some changed,some didn't, but the last one to not change was Pope Marcellus II in 1555. His reign was 22 days, though I doubt that is related to not changing his name. 

8) Math question: What is the average length of a Papacy and what is the average length of a presidency (of America)?

The first Pope was Peter, began in 30AD.

The 266th Pope was Francis whose reign ended in 2025.

SO we have 266 Popes in 1995 years, so the average reign is 7.5 years.

The first president was George Washington whose presidency began in 1789.

The 46th president was Joe Biden and it ended in 2025.

SO we have 46 presidents (we ignore the Grover C thing) in 236 years, so the avg reign is 5.1 years.

The 7.5 and 5.1 are more different than they look since the length of presidents is usually 4 or 8 years,while the length of a Papal reign has had a min  of 13 days and a max of 31 years (Pope Pius IX).

I'l be curious what the standard deviation and deviance are for both Papal Reigns and Presidents. I suspect that it's much bigger for Papal reigns, and not just because the presidency is at most 8 years (with one exception-FDR was president for 12 years). 

9) There was betting and betting markets on the next Pope. This raises the question of how often someone NOT on the short list (so probably not bet on much) becomes Pope. Lets look at the last few:

Pope Leo XIV- not on the short list

Pope Francis- not on the short list

Pope Benedict XVI- a favorite

Pope John Paul II- not on the short list

Pope John Paul I- I don't know and I will stop here.

Upshot: it may be foolish to bet on the next Pope. Even more so than betting on the Vice Prez nominee which I commented on here.

10) Art imitates life: Some of the cardinals at the conclave watched the movie Conclave to get an idea of what a conclave is like. I suspect the real conclave was much less dramatic than the movie Conclave. 

13) The Wikipedia entry for Pope Leo XIV does not say his undergraduate thesis was on 

Rado's Theorem for Nonlinear Equations. 

It was on 

The Canonical Polynomial Hales-Jewitt Theorem.

By gasarch

Authors: Nicholas DeJesse, Spencer Lyudovyk, Dhruv Pai, Michael Reidy

In this paper, we examine Lin's "On NP versus coNP and Frege Systems" [Lin25]. Lin claims to prove that $\text{NP} \neq \text{coNP}$ by constructing a language $L_d$ such that $L_d \in \text{NP}$ but $L_d \notin \text{coNP}$. We present a flaw in Lin's construction of $D$ (a nondeterministic Turing machine that supposedly recognizes $L_d$ in polynomial time). We also provide a proof that $L_d \not\in \text{NP}$. In doing so, we demonstrate that Lin's claim that $\text{NP} \neq \text{coNP}$ is not established by his paper. In addition, we note that a number of further results that Lin claims are not validly established by his paper.

Authors: Jonathan E. Dullerud, Sariel Har-Peled

We present a data-structure for orthogonal range searching for random points in the plane. The new data-structure uses (in expectation) $O\bigl(n \log n ( \log \log n)^2 \bigr)$ space, and answers emptiness queries in constant time. As a building block, we construct a data-structure of expected linear size, that can answer predecessor/rank queries, in constant time, for random numbers sampled uniformly from $[0,1]$. While the basic idea we use is known [Dev89], we believe our results are still interesting.

Authors: Haikuan Zhu, Hongbo Li, Hsueh-Ti Derek Liu, Wenping Wang, Jing Hua, Zichun Zhong

This paper introduces a method to synthesize a 3D tensor field within a constrained geometric domain represented as a tetrahedral mesh. Whereas previous techniques optimize for isotropic fields, we focus on anisotropic tensor fields that are smooth and aligned with the domain boundary or user guidance. The key ingredient of our method is a novel computational design framework, built on top of the symmetric orthogonally decomposable (odeco) tensor representation, to optimize the stretching ratios and orientations for each tensor in the domain. In contrast to past techniques designed only for isotropic tensors, we demonstrate the efficacy of our approach in generating smooth volumetric tensor fields with high anisotropy and shape conformity, especially for the domain with complex shapes. We apply these anisotropic tensor fields to various applications, such as anisotropic meshing, structural mechanics, and fabrication.

Authors: Idan Attias, Xing Gao, Lev Reyzin

Learning-augmented algorithms are a prominent recent development in beyond worst-case analysis. In this framework, a problem instance is provided with a prediction (``advice'') from a machine-learning oracle, which provides partial information about an optimal solution, and the goal is to design algorithms that leverage this advice to improve worst-case performance. We study the classic Boolean satisfiability (SAT) decision and optimization problems within this framework using two forms of advice. ``Subset advice" provides a random $\epsilon$ fraction of the variables from an optimal assignment, whereas ``label advice" provides noisy predictions for all variables in an optimal assignment. For the decision problem $k$-SAT, by using the subset advice we accelerate the exponential running time of the PPSZ family of algorithms due to Paturi, Pudlak, Saks and Zane, which currently represent the state of the art in the worst case. We accelerate the running time by a multiplicative factor of $2^{-c}$ in the base of the exponent, where $c$ is a function of $\epsilon$ and $k$. For the optimization problem, we show how to incorporate subset advice in a black-box fashion with any $\alpha$-approximation algorithm, improving the approximation ratio to $\alpha + (1 - \alpha)\epsilon$. Specifically, we achieve approximations of $0.94 + \Omega(\epsilon)$ for MAX-$2$-SAT, $7/8 + \Omega(\epsilon)$ for MAX-$3$-SAT, and $0.79 + \Omega(\epsilon)$ for MAX-SAT. Moreover, for label advice, we obtain near-optimal approximation for instances with large average degree, thereby generalizing recent results on MAX-CUT and MAX-$2$-LIN.

Authors: Rom Pinchasi, Neta Singer, Lukas Vogl, Jiaye Wei

We study the Second Price Matching problem, introduced by Azar, Birnbaum, Karlin, and Nguyen in 2009. In this problem, a bipartite graph (bidders and goods) is given, and the profit of a matching is the number of matches containing a second unmatched bidder. Maximizing profit is known to be APX-hard and the current best approximation guarantee is $1/2$. APX-hardness even holds when all degrees are bounded by a constant. In this paper, we investigate the approximability of the problem under regular degree constraints. Our main result is an improved approximation guarantee of $9/10$ for Second Price Matching in $(3,2)$-regular graphs and an exact polynomial-time algorithm for $(d,2)$-regular graphs if $d\geq 4$. Our algorithm and its analysis are based on structural results in non-bipartite matching, in particular the Tutte-Berge formula coupled with novel combinatorial augmentation methods. We also introduce a variant of Second Price Matching where all goods have to be matched, which models the setting of expiring goods. We prove that this problem is hard to approximate within a factor better than $(1-1/e)$ and show that the problem can be approximated to a tight $(1-1/e)$ factor by maximizing a submodular function subject to a matroid constraint. We then show that our algorithm also solves this problem exactly on regular degree constrained graphs as above.

Authors: Alex Crane, Sorelle A. Friedler, Mihir Patel, Blair D. Sullivan

Graph modification problems with the goal of optimizing some measure of a given node's network position have a rich history in the algorithms literature. Less commonly explored are modification problems with the goal of equalizing positions, though this class of problems is well-motivated from the perspective of equalizing social capital, i.e., algorithmic fairness. In this work, we study how to add edges to make the closeness centralities of a given pair of nodes more equal. We formalize two versions of this problem: Closeness Ratio Improvement, which aims to maximize the ratio of closeness centralities between two specified nodes, and Closeness Gap Minimization, which aims to minimize the absolute difference of centralities. We show that both problems are $\textsf{NP}$-hard, and for Closeness Ratio Improvement we present a quasilinear-time $\frac{6}{11}$-approximation, complemented by a bicriteria inapproximability bound. In contrast, we show that Closeness Gap Minimization admits no multiplicative approximation unless $\textsf{P} = \textsf{NP}$. We conclude with a discussion of open directions for this style of problem, including several natural generalizations.

Authors: Martin Bullinger, René Romen, Alexander Schlenga

We study coalition formation in the framework of fractional hedonic games (FHGs). The objective is to maximize social welfare in an online model where agents arrive one by one and must be assigned to coalitions immediately and irrevocably. For general online FHGs, it is known that computing maximal matchings achieves the optimal competitive ratio, which is, however, unbounded for unbounded agent valuations. We achieve a constant competitive ratio in two related settings while carving out further connections to matchings. If algorithms can dissolve coalitions, then the optimal competitive ratio of $\frac{1}{6+4\sqrt{2}}$ is achieved by a matching-based algorithm. Moreover, we perform a tight analysis for the online matching setting under random arrival with an unknown number of agents. This entails a randomized $\frac 16$-competitive algorithm for FHGs, while no algorithm can be better than $\frac 13$-competitive.

Authors: Simon Märtens, Uwe Naumann

This paper addresses the efficient computation of Jacobian matrices for programs composed of sequential differentiable subprograms. By representing the overall Jacobian as a chain product of the Jacobians of these subprograms, we reduce the problem to optimizing the sequence of matrix multiplications, known as the Jacobian Matrix Chain Product problem. Solutions to this problem yield "optimal bracketings", which induce a precedence-constraint scheduling problem. We investigate the inherent parallelism in the solutions and develop a new dynamic programming algorithm as a heuristic that incorporates the scheduling. To assess its performance, we benchmark it against the global optimum, which is computed via a branch-and-bound algorithm.

Authors: Romain Bourneuf, Julien Cocquet, Chaoliang Tang, Stéphan Thomassé

As shown by Robertson and Seymour, deciding whether the complete graph $K_t$ is a minor of an input graph $G$ is a fixed parameter tractable problem when parameterized by $t$. From the approximation viewpoint, the gap to fill is quite large, as there is no PTAS for finding the largest complete minor unless $P = NP$, whereas a polytime $O(\sqrt n)$-approximation algorithm was given by Alon, Lingas and Wahl\'en. We investigate the complexity of finding $K_t$ as interval minor in ordered graphs (i.e. graphs with a linear order on the vertices, in which intervals are contracted to form minors). Our main result is a polytime $f(t)$-approximation algorithm, where $f$ is triply exponential in $t$ but independent of $n$. The algorithm is based on delayed decompositions and shows that ordered graphs without a $K_t$ interval minor can be constructed via a bounded number of three operations: closure under substitutions, edge union, and concatenation of a stable set. As a byproduct, graphs avoiding $K_t$ as an interval minor have bounded chromatic number.

Authors: Johanna Elena Schmitz, Jens Zentgraf, Sven Rahmann

Cuckoo filters are space-efficient approximate set membership data structures with a controllable false positive rate (FPR) and zero false negatives, similar to Bloom filters. In contrast to Bloom filters, Cuckoo filters store multi-bit fingerprints of keys in a hash table using variants of Cuckoo hashing, allowing each fingerprint to be stored at a small number of possible locations. Existing Cuckoo filters use fingerprints of $(k+3)$ bits per key and an additional space overhead factor of at least $1.05$ to achieve an FPR of $2^{-k}$. For $k=10$, this amounts to $1.365\, kn$ bits to store $n$ keys, which is better than $1.443\, kn$ bits for Bloom filters. The $+3$ for the fingerprint size is required to balance out the multiplied FPR caused by looking for the fingerprint at several locations. In the original Cuckoo filter, the number of hash table buckets is restricted to a power of 2, which may lead to much larger space overheads, up to $2.1\, (1+3/k)\, kn$ bits. We present two improvements of Cuckoo filters. First, we remove the restriction that the number of buckets must be a power of 2 by using a different placement strategy. Second, we reduce the space overhead factor of Cuckoo filters to $1.06 \, (1+2/k)$ by using overlapping windows instead of disjoint buckets to maintain the load threshold of the hash table, while reducing the number of alternative slots where any fingerprint may be found. A detailed evaluation demonstrates that the alternative memory layout based on overlapping windows decreases the size of Cuckoo filters not only in theory, but also in practice. A comparison with other state-of-the art filter types, Prefix filters and Vector Quotient filters (VQFs), shows that the reduced space overhead makes windowed Cuckoo filters the smallest filters supporting online insertions, with similarly fast queries, but longer insertion times.

Authors: Lorenzo Beretta

We study the problem of learning junta distributions on $\{0, 1\}^n$, where a distribution is a $k$-junta if its probability mass function depends on a subset of at most $k$ variables. We make two main contributions: - We show that learning $k$-junta distributions is \emph{computationally} equivalent to learning $k$-parity functions with noise (LPN), a landmark problem in computational learning theory. - We design an algorithm for learning junta distributions whose statistical complexity is optimal, up to polylogarithmic factors. Computationally, our algorithm matches the complexity of previous (non-sample-optimal) algorithms. Combined, our two contributions imply that our algorithm cannot be significantly improved, statistically or computationally, barring a breakthrough for LPN.

Authors: Umang Bhaskar, Vishwa Prakash HV, Aditi Sethia, Rakshitha

Equitability is a well-studied fairness notion in fair division, where an allocation is equitable if all agents receive equal utility from their allocation. For indivisible items, an exactly equitable allocation may not exist, and a natural relaxation is EQ1, which stipulates that any inequitability should be resolved by the removal of a single item. In this paper, we study equitability in the context of randomized allocations. Specifically, we aim to achieve equitability in expectation (ex ante EQ) and require that each deterministic outcome in the support satisfies ex post EQ1. Such an allocation is commonly known as a `Best of Both Worlds' allocation, and has been studied, e.g., for envy-freeness and MMS. We characterize the existence of such allocations using a geometric condition on linear combinations of EQ1 allocations, and use this to give comprehensive results on both existence and computation. For two agents, we show that ex ante EQ and ex post EQ1 allocations always exist and can be computed in polynomial time. For three or more agents, however, such allocations may not exist. We prove that deciding existence of such allocations is strongly NP-complete in general, and weakly NP-complete even for three agents. We also present a pseudo-polynomial time algorithm for a constant number of agents. We show that when agents have binary valuations, best of both worlds allocations that additionally satisfy welfare guarantees exist and are efficiently computable.

Authors: Parviz Afereidoon

This paper introduces persiansort, new stable sorting algorithm inspired by Persian rug. Persiansort does not have the weaknesses of mergesort under scenarios involving nearly sorted and partially sorted data, also utilizing less auxiliary memory than mergesort and take advantage of runs. Initial experimental showed, this method is flexible, powerful and works better than mergesort in almost all types of data. Persiansort offers several advantages over merge methods, make it a potential replacement.

Authors: Orr Fischer, Merav Parter

Resilient computation in all-to-all-communication models has attracted tremendous attention over the years. Most of these works assume the classical faulty model which restricts the total number of corrupted edges (or vertices) by some integer fault parameter $f$. A recent work by [Bodwin, Haeupler and Parter, SODA 2024] introduced a stronger notion of fault-tolerance, in the context of graph sparsification, which restricts the degree of the failing edge set $F$, rather than its cardinality. For a subset of faulty edges $F$, the faulty-degree $\mathrm{deg}(F)$ is the largest number of faults in $F$ incident to any given node. In this work, we study the communication aspects of this faulty model which allows us to handle almost linearly more edge faults (possibly quadratic), with no extra cost. Our end results are general compilers that take any Congested Clique algorithm and simulate it, in a round by round manner, in the presence of a $\alpha$-Byzantine mobile adversary that controls a $\alpha$-fraction of the edges incident to each node in the fully connected network. For every round $i$, the mobile adversary is allowed to select a distinct set of corrupted edges $F_i$ under the restriction that $\mathrm{deg}(F_i)\leq \alpha n$. In the non-adaptive setting, the $F_i$ sets are selected at the beginning of the simulation, while in the adaptive setting, these edges can be chosen based on the entire history of the protocol up to round $i$. We show general compilers for the non-adaptive, adaptive, and deterministic settings. A key component of our algorithms is a new resilient routing scheme which may be of independent interest. Our approach is based on a combination of techniques, including error-correcting-code, locally decodable codes, cover-free families, and sparse recovery sketches.

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

July 30, 2025 Lyon, France (colocated with COLT 2025) https://fopt-workshop.github.io/ Submission deadline: May 19, 2025 This COLT 2025 workshop seeks to explore the theoretical and practical aspects of the post-training of LLMs, across a diversity of domains and abstractions. The workshop aims to bring together experts from diverse fields including theoretical reinforcement learning, optimization, statistical … Continue reading Workshop on Foundations of Post-training

By shacharlovett

The University of Latvia is looking to hire a tenured professor in mathematical foundations of data science and artificial intelligence.The tenured professor is expected to demonstrate high quality intensive research. The position provides for motivational remuneration and support in the creation of a research group.

Website: https://www.lu.lv/en/about-us/vacancies/tenured-professorship-position-in-the-area-of-mathematical-foundations-of-data-science-and-artificial-intelligence-09/04/2025-18/05/2025/
Email: andris.ambainis@lu.lv

By shacharlovett

The University of Latvia is looking to hire a tenured professor in mathematical foundations of data science and artificial intelligence.The tenured professor is expected to demonstrate high quality intensive research. The position provides for motivational remuneration and support in the creation of a research group.

Website: https://www.lu.lv/en/about-us/vacancies/tenured-professorship-position-in-the-area-of-mathematical-foundations-of-data-science-and-artificial-intelligence-09/04/2025-18/05/2025/
Email: andris.ambainis@lu.lv

By shacharlovett

The bonanza of property testing results continues this month, with seven new papers on the arXiv! And with range, too: from regular languages to quantum states, with detours through distribution testing, Boolean functions, and relative error property testing. Oh, and yes, also, (quantum) magic!

The Trichotomy of Regular Property Testing (arXiv), by Gabriel Bathie, Nathanaël Fijalkow, and Corto Mascle. In property testing of regular languages, initiated by Alon, Krivelevich, Newman, and Szegedy in 2001, one has to decide whether an input word belongs to the target language \(L\), or is at distance at least \(\varepsilon\) from every \(x \in L\) (where the distance is typically Hamming or the (easier) edit distance). Surprisingly, it was shown that every regular language could be tested with \(\tilde{O}(1/\varepsilon)\) queries, independent of the input size. But is that tight? And is that \(\tilde{O}\) necessary> Many years of work later, the main result of this paper is settling the question, showing that for testing under the Hamming distance there are only three options: either a language is trivial (0 queries needed!), or easy (\(\Theta(1/\varepsilon)\) necessary and sufficient), or just plain hard \(\Theta(\log(1/\varepsilon)/\varepsilon)\) queries necessary and sufficient). Nothing else!

A Mysterious Connection Between Tolerant Junta Testing and Agnostically Learning Conjunctions (arXiv), by Xi Chen, Shyamal Patel, and Rocco Servedio. (1) Take two well-studied, notoriously challenging and seemingly unrelated problems about Boolean functions: agnostic learning conjunctions (that is, learning conjunctions with noise), and tolerantly testing juntas. (2) Unearth a new connection between the two tasks. (3) Write a very entertaining, illuminating introduction about this. (4) Oh, also, provide a new \(\tilde{O})(2^{n^{1/3}})\)-time agnostic learning algorithm for conjunctions, improving the previous best known result after 18 years; use it to obtain a \(\tilde{O})(2^{k^{1/3}})\)-query tolerant tester for juntas using this new connection, thus showing a polynomial separation between adaptive and non-adaptive algorithms for this task. (5) You get this paper.

Distribution Testing Meets Sum Estimation (arXiv), by Pinki Pradhan and Sampriti Roy. In the sum estimation problem, there is a set of \(n\) elements, each with a non-negative weight, and the goal is to estimate the total weight \(W\) while minimizing the number of weight queried. Under a model which allows both weighted and uniform sampling, this is known to be achievable with \(O(n^{1/3})\) queries (Beretta and Tětek). This paper considers the task under two additional assumptions: first, the weights are non-increasing, and second, the algorithm is allowed conditional weighted and uniform sampling (i.e., the same two types of sampling, but conditioned on any subset \(S\) of its choosing). In this setting, the authors show how to estimate the total weight to \(1\pm\varepsilon\) with only \(O((\log n)\text{poly}(1/\varepsilon))\) queries.

Efficient witnessing and testing of magic in mixed quantum states (arXiv), by Tobias Haug, and Poetri Sonya Tarabunga. Magic is real, and it’s quantifiable: roughly speaking, it quantifies the amount or “non-stabilizerness” of a state. I won’t pretend to fully understand what this means, but this paper shows that one can test the magic of low-entropy \(n\)-qubit states (i.e., distinguish between low magic states and high-magic states) with only polynomially (in \(n\)) many copies of the state.

Mildly-Interacting Fermionic Unitaries are Efficiently Learnable (arXiv), by Vishnu Iyer. More quantum property testing! In this paper, the author shows how to test whether an \(n\)-mode fermionic unitary has Gaussian dimension at least \(k\) (or is \(\varepsilon\)-far from it in Frobenius norm) in time \(\text{poly}(n, 1/\varepsilon)\). (This is then used as a building block to efficiently learn such unitaries.)

Testing Juntas and Junta Subclasses with Relative Error (arXiv), by Xi Chen, William Pires, Toniann Pitassi, and Rocco Servedio. In this relatively (!) new model of property testing, which we covered last October, the notion of farness between two Boolean functions is relative to their number of satisfying assignments. Testing with relative error is at least as hard as in the standard setting, and could be strictly harder: this paper shows that, for the case of testing juntas, this is not the case. Even with relative error testing, \(\tilde{O}(k/\varepsilon)\) queries are necessary and sufficient for junta testing! Using ideas from “standard testing” (specifically, from the “testing by implicit learning” framework), their results further extend to testing a large number of subclasses of juntas.

Relative-error testing of conjunctions and decision lists (arXiv), by Xi Chen, William Pires, Toniann Pitassi, and Rocco Servedio. Same team, same model — more results! After testing juntas in the relative error model, the authors continue their systematic exploration of the testing questions, this time focusing on testing decision lists and conjunctions. They are able to obtain a \(\tilde{O}(1/\varepsilon)\)-tester with two-sided error for the former, and an \(O(1/\varepsilon)\)-tester with one-sided error for the latter: both matching the best-known query complexity in the standard model.

By Clement Canonne

In the last post, I quoted Donald Knuth crediting George Forsythe with coining the term computer science. Forsythe, the founder and first department chair of Stanford University's Computer Science Department, first proposed this disciplinary naming in a lecture at Brown University in 1962.

Brown was an early mover in computer science, and having established its University Computing Laboratory, the Applied Math department partnered with IBM to sponsor a lecture series on “Applications of Digital Computers.” The series included a lecture on AI by Herb Simon and a lecture on using computers to solve open number theory problems by DH Lehmer. Forsythe, interestingly, was the only talk that did not focus on an application area. Instead, he lectured on “Educational Implications of the Computer Revolution.”

Forsythe’s lecture argued for the establishment of new academic departments. Though he credits the influence of Fein on his thinking, his presentation is more eloquent and polished. Forsythe was well-versed in the ins and outs of academic lobbying. Given the ultraconservatism of academia, you can’t start a department without a revolution. Forsythe’s lecture thus sets the stage with a sentence that could begin any introspective essay about computers after 1950:

“Those of us who work with automatic digital computers suffer from a certain megalomania. We consider that we are not merely working in an area of great importance, we insist that we are instruments of a revolution, the Computer Revolution… In 1945, the fastest generally available computer was a person with a desk calculator, averaging a multiplication about every 10 seconds. In 1962, anyone with the money can obtain a computer capable of multiplying in 0.000025 second. This acceleration by a factor of about half a million, or between 5 and 6 orders of magnitude.”

Scaling laws, everyone! With the benefit of hindsight, we know this exponential trend would continue for decades, though at a somewhat slower rate. Forsythe’s growth was over a factor of six every two years. With our Moore’s Law-esque doubling every two years, we have only been able to eke out 14 orders of magnitude in floating point operation speed since then.

Forsythe then lists some of the potentially revolutionary applications of computers: language translation, medical diagnosis, OCR, and speech-to-text. And assuredly, we’ve made progress in all of these fronts. He also asserts, "One key property of computers is the automation of routine decision-making.” However, he doesn’t pontificate about the loftier goals of AI that were bandied around at the time by MIT faculty.

Forsythe didn’t need to speculate about science fiction. The applications he listed were impressive and wide-reaching enough to argue that we needed to educate people about how to use computers, how to advance computing technology, and how to understand the potential impacts of computers on society. He estimated that there were around 5000 computers in the US in 1962, and hence, like Fein, he notes the demand for training professionals. Moreover, Forsythe sees how everyone will need to understand how to use computers:

“The student of social sciences now needs as much technical background in computing as does his brother in physical science. In fact, research in social science is one of the biggest generators of massive files of data. Dealing with them gracefully may require considerably more computer skill than dealing with scientific problems.”

Given the revolution and need for education, Forsythe argued that universities needed to step up. Every university should have a computing center, and that center should serve the entire campus. It would be equally valuable to the students planning to work in the computer industry as those who would not. “Our students of engineering, business, and science should learn how easy it can be to use automatic computers for their homework.” Sometimes you have to be careful about what you wish for.

Forsythe thus describes his visions for a curriculum. He gave the syllabus for his introductory programming class. The initial offering at Stanford had 140 students.1 The topic list included Boolean circuits, assembly language, the BALGOL programming language, and elementary algorithms in numerical analysis. The class also leaned heavily on labs, with all students sharing time on a Burroughs 220. Each student wrote five programs, and they were autograded. The assignments included solving polynomial equations and sorting numbers. In addition to this practical training, Forsythe also covered history and sociology of the field, as he argued, “The vast majority of university students must realize the intellectual and sociological implications of a computer world. They must contemplate what computers mean for man’s thinking, for his employment, and for his social organization.”

Beyond the coursework, there was the question of the research discipline. This is what Forsythe calls “computer science,” though he notes, “It is known also as communication science or synnoetics.” I’m sorry, but I must start using the term synnoetics. Too good. And even better, synnoetics also sprang from the imagination of Louis Fein.

Forsythe’s version of synnoetics includes the topics of Programming, Numerical Analysis, Automata Theory, Data Processing, Business Games, Adaptive Systems, Information Theory, Information Retrieval, Recursive Function Theory, and Computer Linguistics. He envisioned faculty having joint appointments with departments of mathematics, physics, psychology, philosophy, medicine, business, engineering, and law. “One of the significant roles of computer science should be to provide an academic clubhouse where interdisciplinary stimulation can counteract the well-known effects of specialization.”

Sadly, this cross-cutting, interdisciplinary vision didn’t pan out. I wonder about this a lot. Why is it that academics perpetually advocate for fewer boundaries and more multidisciplinary playgrounds, yet end up with narrow definitions of technical depth with ossified disciplinary boundaries? Those faculty who moved into the new synnoetics departments ended up hiring more faculty like them, imprinting the discipline with the predilections of the first movers. This is why optimization research remains core at the University of Wisconsin, and numerical analysis remains part of CS at UC Berkeley. The signal processing, information theory, and control faculty stayed in their engineering departments. As did the computational researchers in physics, medicine, and law. Because of departmental jockeying for resources, boundaries were raised and purviews were narrowed.

My favorite part of Forsythe’s vision is its expansiveness in viewing the university as an agile place for training, inquiry, and knowledge discovery. I don’t know what the future holds for the academy, and it’s easy to be pessimistic and cynical. But if you want a positive case for our future, Forsythe’s 63-year-old lecture isn’t the worst place to start.

Subscribe now

By Ben Recht

Authors: Laura Mančinska, Pieter Spaas, Taro Spirig

In complexity theory, gap-preserving reductions play a crucial role in studying hardness of approximation and in analyzing the relative complexity of multiprover interactive proof systems. In the quantum setting, multiprover interactive proof systems with entangled provers correspond to gapped promise problems for nonlocal games, and the recent result MIP$^*$=RE (Ji et al., arXiv:2001.04383) shows that these are in general undecidable. However, the relative complexity of problems within MIP$^*$ is still not well-understood, as establishing gap-preserving reductions in the quantum setting presents new challenges. In this paper, we introduce a framework to study such reductions and use it to establish MIP$^*$-completeness of the gapped promise problem for the natural class of independent set games. In such a game, the goal is to determine whether a given graph contains an independent set of a specified size. We construct families of independent set games with constant question size for which the gapped promise problem is undecidable. In contrast, the same problem is decidable in polynomial time in the classical setting. To carry out our reduction, we establish a new stability theorem, which could be of independent interest, allowing us to perturb families of almost PVMs to genuine PVMs.

Authors: Andrew D. Laack

Oblique decision trees have attracted attention due to their potential for improved classification performance over traditional axis-aligned decision trees. However, methods that rely on exhaustive search to find oblique splits face computational challenges. As a result, they have not been widely explored. We introduce a novel algorithm, Classification and Regression Tree - Exhaustive Linear Combinations (CART-ELC), for inducing oblique decision trees that performs an exhaustive search on a restricted set of hyperplanes. We then investigate the algorithm's computational complexity and its predictive capabilities. Our results demonstrate that CART-ELC consistently achieves competitive performance on small datasets, often yielding statistically significant improvements in classification accuracy relative to existing decision tree induction algorithms, while frequently producing shallower, simpler, and thus more interpretable trees.

Authors: Fabrizio Boninsegna

This paper extends $\texttt{InfTDA}$, a mechanism proposed in (Boninsegna, Silvestri, PETS 2025) for mobility datasets with origin and destination trips, in a general setting. The algorithm presented in this paper works for any dataset of $d$ categorical features and produces a differentially private synthetic dataset that answers all hierarchical queries, a special case of marginals, each with bounded maximum absolute error. The algorithm builds upon the TopDown mechanism developed for the 2020 US Census.

Authors: Matthias Bentert, Pål Grønås Drange, Erlend Haugen

In this paper, we introduce Bicluster Editing with Vertex Splitting, a variant of the Bicluster Editing problem, which aims to transform a given graph into a bicluster graph using a minimum number of operations. In Bicluster Editing, the allowed operations are the insertion and deletion of edges. In Bicluster Editing with Vertex Splitting we additionally allow overlapping clusters, which we model by allowing vertex splits. We prove that Bicluster Editing with Vertex Splitting is NP-complete. On the positive side, we show that it admits a polynomial kernel with respect to the number k of allowed edit operations and present an algorithm running in O(k^{11k} + n + m) time, where n and m denote the number of vertices and edges in the input graph, respectively.

Authors: Xiaoyu Chen, Hongyang Liu, Yitong Yin, Xinyuan Zhang

We introduce efficient parallel algorithms for sampling from the Gibbs distribution and estimating the partition function of Ising models. These algorithms achieve parallel efficiency, with polylogarithmic depth and polynomial total work, and are applicable to Ising models in the following regimes: (1) Ferromagnetic Ising models with external fields; (2) Ising models with interaction matrix $J$ of operator norm $\|J\|_2<1$. Our parallel Gibbs sampling approaches are based on localization schemes, which have proven highly effective in establishing rapid mixing of Gibbs sampling. In this work, we employ two such localization schemes to obtain efficient parallel Ising samplers: the \emph{field dynamics} induced by \emph{negative-field localization}, and \emph{restricted Gaussian dynamics} induced by \emph{stochastic localization}. This shows that localization schemes are powerful tools, not only for achieving rapid mixing but also for the efficient parallelization of Gibbs sampling.

Authors: Hadley Black, Arya Mazumdar, Barna Saha

We consider the basic problem of learning an unknown partition of $n$ elements into at most $k$ sets using simple queries that reveal information about a small subset of elements. Our starting point is the well-studied pairwise same-set queries which ask if a pair of elements belong to the same class. It is known that non-adaptive algorithms require $\Theta(n^2)$ queries, while adaptive algorithms require $\Theta(nk)$ queries, and the best known algorithm uses $k-1$ rounds. This problem has been studied extensively over the last two decades in multiple communities due to its fundamental nature and relevance to clustering, active learning, and crowd sourcing. In many applications, it is of high interest to reduce adaptivity while minimizing query complexity. We give a complete characterization of the deterministic query complexity of this problem as a function of the number of rounds, $r$, interpolating between the non-adaptive and adaptive settings: for any constant $r$, the query complexity is $\Theta(n^{1+\frac{1}{2^r-1}}k^{1-\frac{1}{2^r-1}})$. Our algorithm only needs $O(\log \log n)$ rounds to attain the optimal $O(nk)$ query complexity. Next, we consider two generalizations of pairwise queries to subsets $S$ of size at most $s$: (1) weak subset queries which return the number of classes intersected by $S$, and (2) strong subset queries which return the entire partition restricted on $S$. Once again in crowd sourcing applications, queries on large sets may be prohibitive. For non-adaptive algorithms, we show $\Omega(n^2/s^2)$ strong queries are needed. Perhaps surprisingly, we show that there is a non-adaptive algorithm using weak queries that matches this bound up to log-factors for all $s \leq \sqrt{n}$. More generally, we obtain nearly matching upper and lower bounds for algorithms using subset queries in terms of both the number of rounds, $r$, and the query size bound, $s$.

Authors: David Eppstein, Ofek Gila, Michael T. Goodrich, Ryuto Kitagawa

In this paper, we introduce zip-tries, which are simple, dynamic, memory-efficient data structures for strings. Zip-tries support search and update operations for $k$-length strings in $\mathcal{O}(k+\log n)$ time in the standard RAM model or in $\mathcal{O}(k/\alpha+\log n)$ time in the word RAM model, where $\alpha$ is the length of the longest string that can fit in a memory word, and $n$ is the number of strings in the trie. Importantly, we show how zip-tries can achieve this while only requiring $\mathcal{O}(\log{\log{n}} + \log{\log{\frac{k}{\alpha}}})$ bits of metadata per node w.h.p., which is an exponential improvement over previous results for long strings. Despite being considerably simpler and more memory efficient, we show how zip-tries perform competitively with state-of-the-art data structures on large datasets of long strings. Furthermore, we provide a simple, general framework for parallelizing string comparison operations in linked data structures, which we apply to zip-tries to obtain parallel zip-tries. Parallel zip-tries are able to achieve good search and update performance in parallel, performing such operations in $\mathcal{O}(\log{n})$ span. We also apply our techniques to an existing external-memory string data structure, the string B-tree, obtaining a parallel string B-tree which performs search operations using $\mathcal{O}(\log_B{n})$ I/O span and $\mathcal{O}(\frac{k}{\alpha B} + \log_B{n})$ I/O work in the parallel external memory (PEM) model. The parallel string B-tree can perform prefix searches using only $\mathcal{O}(\frac{\log{n}}{\log{\log{n}}})$ span under the practical PRAM model. For the case of long strings that share short common prefixes, we provide LCP-aware variants of all our algorithms that should be quite efficient in practice, which we justify empirically.

Authors: Clément L. Canonne, Kenny Chen, Julián Mestre

We study online algorithms with predictions using distributional advice, a type of prediction that arises when leveraging expert knowledge or historical data. To demonstrate the usefulness and versatility of this framework, we focus on two fundamental problems: first, the prophet inequality problem, for which we provide an algorithm achieving $\max\{\frac{1}{2}-\eta-o(1),\frac{1}{e}\}$-competitive ratio, where $\eta$ quantifies the quality of the prediction. Second, we turn to the online metric matching problem under random arrivals, for which our main positive result is an algorithm achieving the optimal cost under perfect advice, while smoothly defaulting to competitive ratios comparable to advice-free algorithms as the prediction's quality degrades.

Authors: Jiayao Wang, Qilong Shi, Xiyan Liang, Han Wang, Wenjun Li, Ziling Wei, Weizhe Zhang, Shuhui Chen

Finding persistent sparse (PS) flow is critical to early warning of many threats. Previous works have predominantly focused on either heavy or persistent flows, with limited attention given to PS flows. Although some recent studies pay attention to PS flows, they struggle to establish an objective criterion due to insufficient data-driven observations, resulting in reduced accuracy. In this paper, we define a new criterion "anomaly boundary" to distinguish PS flows from regular flows. Specifically, a flow whose persistence exceeds a threshold will be protected, while a protected flow with a density lower than a threshold is reported as a PS flow. We then introduce PSSketch, a high-precision layered sketch to find PS flows. PSSketch employs variable-length bitwise counters, where the first layer tracks the frequency and persistence of all flows, and the second layer protects potential PS flows and records overflow counts from the first layer. Some optimizations have also been implemented to reduce memory consumption further and improve accuracy. The experiments show that PSSketch reduces memory consumption by an order of magnitude compared to the strawman solution combined with existing work. Compared with SOTA solutions for finding PS flows, it outperforms up to 2.94x in F1 score and reduces ARE by 1-2 orders of magnitude. Meanwhile, PSSketch achieves a higher throughput than these solutions.

I’ve now been blogging for nearly twenty years—through five presidential administrations, my own moves from Waterloo to MIT to UT Austin, my work on algebrization and BosonSampling and BQP vs. PH and quantum money and shadow tomography, the publication of Quantum Computing Since Democritus, my courtship and marriage and the birth of my two kids, a global pandemic, the rise of super-powerful AI and the terrifying downfall of the liberal world order.

Yet all that time, through more than a thousand blog posts on quantum computing, complexity theory, philosophy, the state of the world, and everything else, I chased a form of recognition for my blogging that remained elusive.

Until now.

This week I received the following email:

I emailed regarding your blog Shtetl-Optimized Blog which was selected by FeedSpot as one of the Top 50 Quantum Computing Blogs on the web.

https://bloggers.feedspot.com/quantum_computing_blogs

We recommend adding your website link and other social media handles to get more visibility in our list, get better ranking and get discovered by brands for collaboration.

We’ve also created a badge for you to highlight this recognition. You can proudly display it on your website or share it with your followers on social media.

We’d be thankful if you can help us spread the word by briefly mentioning Top 50 Quantum Computing Blogs in any of your upcoming posts.

Please let me know if you can do the needful.

You read that correctly: Shtetl-Optimized is now officially one of the top 50 quantum computing blogs on the web. You can click the link to find the other 49.

---

Maybe it’s not unrelated to this new notoriety that, over the past few months, I’ve gotten a massively higher-than-usual volume of emailed solutions to the P vs. NP problem, as well as the other Clay Millennium Problems (sometimes all seven problems at once), as well as quantum gravity and life, the universe, and everything. I now get at least six or seven confident such emails per day.

While I don’t spend much time on this flood of scientific breakthroughs (how could I?), I’d like to note one detail that’s new. Many of the emails now include transcripts where ChatGPT fills in the details of the emailer’s theories for them—unironically, as though that ought to clinch the case. Who said generative AI wasn’t poised to change the world? Indeed, I’ll probably need to start relying on LLMs myself to keep up with the flood of fan mail, hate mail, crank mail, and advice-seeking mail.

Anyway, thanks for reading everyone! I look forward to another twenty years of Shtetl-Optimized, if my own health and the health of the world cooperate.

By Scott

TU Graz has an opening for a full professorship. We are looking for an internationally recognized researcher working in an area of Computational Discrete Mathematics with connections to Theoretical Computer Science. Topics include
discrete and combinatorial optimization, graph algorithms, algorithmic graph theory, complexity theory, theory of algorithms, or constraint satisfaction.

Website: https://jobs.tugraz.at/en/jobs/dec7b342-9f50-f780-b335-67c226f4d322
Email: j.wallner@tugraz.at

By shacharlovett

I reviewed a paper recently and I had to agree not to use AI in any aspect of the reviewing process. So I didn't but it felt strange, like I wouldn't be able to use a calculator to check calculations in a paper. Large language models aren't perfect but they've gotten very good and while we shouldn't trust them to find issues in a paper, they are certainly worth listening to. What we shouldn't do is have AI just write the review with little or no human oversight, and the journal wanted me to check the box probably to ensure I wouldn't just do that, though I'm sure some do and check the box anyway.

I've been playing with OpenAI's o3 model and color me impressed especially when it comes to complexity. It solves all my old homework problems and cuts through purported P v NP proofs like butter. I've tried it on some of my favorite open problems where it doesn't make new progress but it doesn't create fake proofs and does a good job giving the state of the art, some of which I didn't even know about beforehand.

We now have AI at the level of new graduate students. We should treat them as such. Sometimes we give grad students papers to review for conferences but we need to look over what they say afterwards, the same way we should treat these new AI systems. Just because o3 can't find a bug doesn't mean there isn't one. The analogy isn't perfect, we give students papers to review so they can learn the state of the art and become better critical thinkers, in addition to getting help in our reviews. 

We do have a privacy issue. Most papers under review are not for public consumption and if uploaded into a large-language model they could become training data and be revealed if someone asks a relevant question. Ideally we should use a system that doesn't train on our inputs if we use AI for reviewing but both the probability of leakage and amount of damage is low, so I wouldn't worry too much about it.

If you are an author, have AI review your paper before you submit it. Make sure you ask AI to give you a critical review and make suggestions. Maybe in the future we'd required all submitted papers to be AI-certified. It would make the conference reviewers jobs less onerous.

For now, humans alone or AI alone is just not the best way to do conference reviews. For now when you do a review, working with an AI system as an assistant will lead to a stronger review. I suspect in the future, perhaps not that far, AI alone might do a better job. We're not there yet, but we're further than you'd probably expect.

By Lance Fortnow

Authors: Naman Mishra, K S Sreeramji

Given two points $p, q \in \mathbb R^d$, we say that $p$ dominates $q$ and write $p \succ q$ if each coordinate of $p$ is larger than the corresponding coordinate of $q$. That is, if $p = (p^{(1)}, p^{(2)}, \ldots, p^{(d)})$ and $q = (q^{(1)}, q^{(2)}, \ldots, q^{(d)})$, $p \succ q$ if and only if $p^{(i)} > q^{(i)}$ for all $1 \le i \le d$. For example, $p$ and $q$ could represent various ratings for $2$ restaurants, based on different metrics like taste, affordability, ratings on different platforms, et cetera. $p \succ q$ then means that the first restaurant outperformed the second on each metric. Given a list of restaurants and their rating, we solve the problem of determining, for each restaurant, the closest restaurant to it that dominates it. We improve upon the algorithm under some assumptions towards the end.

Authors: Lorenzo Beretta, Nathaniel Harms, Caleb Koch

We prove tight upper and lower bounds of $\Theta\left(\tfrac{1}{\epsilon}\left( \sqrt{2^k \log\binom{n}{k} } + \log\binom{n}{k} \right)\right)$ on the number of samples required for distribution-free $k$-junta testing. This is the first tight bound for testing a natural class of Boolean functions in the distribution-free sample-based model. Our bounds also hold for the feature selection problem, showing that a junta tester must learn the set of relevant variables. For tolerant junta testing, we prove a sample lower bound of $\Omega(2^{(1-o(1)) k} + \log\binom{n}{k})$ showing that, unlike standard testing, there is no large gap between tolerant testing and learning.

Authors: Sujoy Bhore, Lazar Milenkovic

Lightness, sparsity, and hop-diameter are the fundamental parameters of geometric spanners. Arya et al. [STOC'95] showed in their seminal work that there exists a construction of Euclidean $(1+\varepsilon)$-spanners with hop-diameter $O(\log n)$ and lightness $O(\log n)$. They also gave a general tradeoff of hop-diameter $k$ and sparsity $O(\alpha_k(n))$, where $\alpha_k$ is a very slowly growing inverse of an Ackermann-style function. The former combination of logarithmic hop-diameter and lightness is optimal due to the lower bound by Dinitz et al. [FOCS'08]. Later, Elkin and Solomon [STOC'13] generalized the light spanner construction to doubling metrics and extended the tradeoff for more values of hop-diameter $k$. In a recent line of work [SoCG'22, SoCG'23], Le et al. proved that the aforementioned tradeoff between the hop-diameter and sparsity is tight for every choice of hop-diameter $k$. A fundamental question remains: What is the optimal tradeoff between the hop-diameter and lightness for every value of $k$? In this paper, we present a general framework for constructing light spanners with small hop-diameter. Our framework is based on tree covers. In particular, we show that if a metric admits a tree cover with $\gamma$ trees, stretch $t$, and lightness $L$, then it also admits a $t$-spanner with hop-diameter $k$ and lightness $O(kn^{2/k}\cdot \gamma L)$. Further, we note that the tradeoff for trees is tight due to a construction in uniform line metric, which is perhaps the simplest tree metric. As a direct consequence of this framework, we obtain a tight tradeoff between lightness and hop-diameter for doubling metrics in the entire regime of $k$.

Authors: Yann Bourreau, Ananth Narayanan, Alexandre Nolin

In a rendezvous task, a set of mobile agents dispersed in a network have to gather at an arbitrary common site. We consider the rendezvous problem on the infinite labeled line, with $2$ initially asleep agents, without communication, and a synchronous notion of time. Nodes are labeled with unique positive integers. The initial distance between the two agents is denoted by $D$. Time is divided into rounds. We count time from when an agent first wakes up, and denote by $\tau$ the delay between the agents' wake up times. If awake in a given round $T$, an agent has three options: stay at its current node $v$, take port $0$, or take port $1$. If it decides to stay, the agent is still at node $v$ in round $T+1$. Otherwise, it is at one of the two neighbors of $v$ on the line, based on the port it chose. The agents achieve rendezvous in $T$ rounds if they are at the same node in round $T$. We aim for a deterministic algorithm for this task. The problem was recently considered by Miller and Pelc [DISC 2023]. With $\ell_{\max}$ the largest label of the two starting nodes, they showed that no algorithm can guarantee rendezvous in $o(D \log^* \ell_{\max})$ rounds. The lower bound follows from a connection with the LOCAL model of distributed computing, and holds even if the agents are guaranteed simultaneous wake-up ($\tau = 0$) and are given $D$ as advice. Miller and Pelc also gave an algorithm of optimal matching complexity $O(D \log^* \ell_{\max})$ when $D$ is known to the agents, but only obtained the higher bound of $O(D^2 (\log^* \ell_{\max})^3)$ when $D$ is unknown. We improve this second complexity to a tight $O(D \log^* \ell_{\max})$. In fact, our algorithm achieves rendezvous in $O(D \log^* \ell_{\min})$ rounds, where $\ell_{\min}$ is the smallest label within distance $O(D)$ of the two starting positions.

Authors: Nicola Cotumaccio

In the String Matching in Labeled Graphs (SMLG) problem, we need to determine whether a pattern string appears on a given labeled graph or a given automaton. Under the Orthogonal Vectors hypothesis, the SMLG problem cannot be solved in subquadratic time [ICALP 2019]. In typical bioinformatics applications, pattern matching algorithms should be both fast and space-efficient, so we need to determine useful classes of graphs on which the SLMG problem can be solved efficiently. In this paper, we improve on a recent result [STACS 2024] that shows how to solve the SMLG problem in linear time on the compressed representation of Wheeler generalized automata, a class of string-labeled automata that extend de Bruijn graphs. More precisely, we show how to remove the assumption that the automata contain no $ \epsilon $-transitions (namely, edges labeled with the empty string), while retaining the same time and space bounds. This is a significant improvement because $ \epsilon $-transitions add considerable expressive power (making it possible to jump to multiple states for free) and capture the complexity of regular expressions (through Thompson's construction for converting a regular expression into an equivalent automaton). We prove that, to enable $ \epsilon $-transitions, we only need to store two additional bitvectors that can be constructed in linear time.

Authors: Ferenc Bencs, Guus Regts

We prove that for any graph $G$ the (complex) zeros of its chromatic polynomial, $\chi_G(x)$, lie inside the disk centered at $0$ of radius $4.25 \Delta(G)$, where $\Delta(G)$ denote the maximum degree of $G$. This improves on a recent result of Jenssen, Patel and the second author, who proved a bound of $5.94\Delta(G)$. We moreover show that for graphs of sufficiently large girth we can replace $4.25$ by $3.60$ and for claw-free graphs we can replace $4.25$ by $3.81$. Our proofs build on the ideas developed by Jenssen, Patel and the second author, adding some new ideas. A key novel ingredient for claw-free graphs is to use a representation of the coefficients of the chromatic polynomial in terms of the number of certain partial acyclic orientations.

Authors: Elizabeth Munch, Elena Xinyi Wang, Carola Wenk

The kinetic data structure (KDS) framework is a powerful tool for maintaining various geometric configurations of continuously moving objects. In this work, we introduce the kinetic hourglass, a novel KDS implementation designed to compute the bottleneck distance for geometric matching problems. We detail the events and updates required for handling general graphs, accompanied by a complexity analysis. Furthermore, we demonstrate the utility of the kinetic hourglass by applying it to compute the bottleneck distance between two persistent homology transforms (PHTs) derived from shapes in $\mathbb{R}^2$, which are topological summaries obtained by computing persistent homology from every direction in $\mathbb{S}^1$.

Authors: Faisal N. Abu-Khzam, Lucas Isenmann, Zeina Merchad

The BiCluster Editing problem aims at editing a given bipartite graph into a disjoint union of bicliques via a minimum number of edge deletion or addition operations. As a graph-based model for data clustering, the problem aims at a partition of the input dataset, which cannot always obtain meaningful clusters when some data elements are expected to belong to more than one cluster each. To address this limitation, we introduce the Bicluster Editing with Vertex Splitting problem (BCEVS) which consists of finding a minimum sequence of edge editions and vertex splittings such that the result graph is a disjoint union of bicliques. The vertex splitting operation consists of replacing a vertex $v$ with two vertices whose union of neighborhoods is the neighborhood of $v$. We also introduce the problem of Bicluster Editing with One-Sided Vertex Splitting (BCEOVS) where we restrict the splitting operations to the first set of the bipartition (often corresponding to data elements in the input raw data). We prove the two problems are NP-complete even when restricted to bipartite planar graphs of maximum degree three. Moreover, assuming the Exponential Time Hypothesis holds, there is no $2^{o(n)}n^{O(1)}$-time (resp. $2^{o(\sqrt{n})}n^{O(1)}$-time) algorithm for BCEVS and BCEOVS on bipartite (resp. planar) graphs with maximum degree three where $n$ is the number of vertices of the graph. Furthermore we prove both problems are APX-hard and solvable in polynomial time on trees. On the other hand, we prove that BCEOVS is fixed parameter tractable with respect to solution size and admits a polynomial size kernel.

Authors: Miguel Ferreira, Nirav Atre, Justine Sherry, Michael Dinitz, João Luís Sobrinho

Millions of flows are routed concurrently through a modern data-center. These networks are often built as Clos topologies, and flow demands are constrained only by the link capacities at the ingress and egress points. The minimum congestion routing problem seeks to route a set of flows through a data center while minimizing the maximum flow demand on any link. This is easily achieved by splitting flow demands along all available paths. However, arbitrary flow splitting is unrealistic. Instead, network operators rely on heuristics for routing unsplittable flows, the best of which results in a worst-case congestion of $2$ (twice the uniform link capacities). But is $2$ the lowest possible congestion? If not, can an efficient routing algorithm attain congestion below $2$? Guided by these questions, we investigate the minimum congestion routing problem in Clos networks with unsplittable flows. First, we show that for some sets of flows the minimum congestion is at least $\nicefrac{3}{2}$, and that it is $NP$-hard to approximate a minimum congestion routing by a factor less than $\nicefrac{3}{2}$. Second, addressing the motivating questions directly, we present a polynomial-time algorithm that guarantees a congestion of at most $\nicefrac{9}{5}$ for any set of flows, while also providing a $\nicefrac{9}{5}$ approximation of a minimum congestion routing. Last, shifting to the online setting, we demonstrate that no online algorithm (even randomized) can approximate a minimum congestion routing by a factor less than $2$, providing a strict separation between the online and the offline setting.

Monday’s post inspired some fun discussion in the comments and IRL. At the risk of too much academic navel gazing for one week, let me surface a few of those interesting bits and pieces today.

Academic disciplinary history gets reinvented with each cohort of PhD students. Most people don’t want to be disciplinary historians, so for most scholars “history” ends up being the hodgepodge of inspiring apocryphal tales told in intro classes and related work sections. However, if your discipline matters, it’s vital to seriously engage with its intellectual roots. No academic department arises from the well of intellectual purity. Many have far less noble origins than even computer science. The fathers of statistics all cut their teeth in departments of eugenics. That’s not even being hyperbolic: Ronald Fisher was the chair of the Department of Eugenics at UCL.

In that spirit of grappling, let’s talk a bit more about the history of computer science departments and their construction of a pure intellectual endeavor. Shreeharsh Kelkar shared an excellently spicy post he wrote a decade ago about Alan Turing’s influence. You should go read his post for all of the historical tidbits. When you read the papers and personal letters from the early computer pioneers in the United States, you almost never see Turing’s name mentioned before 1960. Shreeharsh’s post examines how Turing was canonized by the discipline to carve out a sense of intellectual purity in a very applied, service-oriented field.

Sheeharsh points to an excellent article by Thomas Haigh in CACM. Haigh asks, “Must theoretical breakthroughs precede and guide practical ones?” I might ask a similar question: Can science be a post-hoc rationalization of technology? This might be the best way to make sense of the “science” in “computer science.” And for those who think I’m just being mean to my colleagues, look at the history of the steam engine and thermodynamics to see how this phenomenon is not confined to the interplay between the science and technology of computers.

With its embrace of theory, computer science carefully carved out an identity as a pure intellectual exercise closer to mathematics than to business. Don Knuth seems to be one of the central figures in creating this identity. Knuth credits George Forsythe for envisioning a purer academic version of computer science. Forsythe was instrumental in establishing Stanford’s CS department in 1965, and university politics demands that all departments tell a story about their pure, ivory intellectual purity. So you’ll find Forsythe quotes like:

“The learning of mathematics and computer science together has pedagogical advantages, for the basic concepts of each reinforce the learning of the other. The question "What can be automated?" is one of the most inspiring philosophical and practical questions of contemporary civilization.”1

Once you tell this story, everyone in the department wants to believe it. No one wants to fess up to being part of a mercenary training program. And by the mid-1980s, with the theoretical, algorithmic backbones built upon the beatified Turing, some computer scientists even thought that any appeals to industry were misguided cynicism.

Along such lines, Max Raginsky pointed me to notes of Edsger Dijkstra, whose memorial website hosts handwritten screeds grumbling about, among other topics, computer science’s servility to industry. I’ll admit, they are very fun to read. Dijkstra would have been a great blogger. Related to this post, check out 1995’s “Why American Computing Science seems incurable,” where he describes how “how anti-intellectualism, amathematicism, and ‘industrial acceptance’ poison computing science.” Woven into the ranting, he makes some compelling points about software’s complexity and inscrutability. Another gem is 1999’s anti-industry screed “How they try to corrupt us.” I raise Dijkstra here not only because hand-written rants from the 90s are fun to read. At the time when personal computers had become ubiquitous and everyone was getting access to the internet, there were faculty in computer science departments who strongly believed that university computer science should be separable from industry.

Those days are over, of course. Trends that Dijkstra lamented, like justifying your research by arguing that some company was using it, are now requirements for CS job talks. Many of my colleagues spend most of their time at their startups or are employed 80% of the time as vice presidents of companies. Some unashamedly run their labs as startup incubators. You could side with Dijkstra and say this is an abomination and spells the end of academic purity. But the record shows the boundary between university and industrial computer science has always been nebulous. Perhaps we should just be arguing about the degree.

What should be the role of computer science at the university? What should be the role of the university in society? In case you hadn’t noticed, the US is in a heated debate about these questions. A discipline as (relatively) new as computer science does provide an interesting case study for how this role can evolve and change in short periods. Thinking about what it should be for the next decade is an important political question, as computing companies control more influence over political systems, and computing technology inescapably molds how we interact and make decisions. We may have deluded ourselves into thinking that we can say “I teach computer science, and that is all,” but that option is neither viable nor veridical in our current environment.

Subscribe now

By Ben Recht

Authors: Amirhossein Akbar Tabatabai

This is a survey on propositional proof complexity aimed at introducing the basics of the field with a particular focus on a method known as feasible interpolation. This method is used to construct "hard theorems" for several proof systems for both classical and non-classical logics. Here, a "hard theorem" refers to a theorem in the logic whose shortest proofs are super-polynomially long in the length of the theorem itself. To make this survey more accessible, we only assume a basic familiarity with propositional, modal, and first-order logic, as well as a basic understanding of the key concepts in computational complexity, such as the definitions of the classes $\mathbf{NP}$ and $\mathbf{PSPACE}$. Any additional concepts will be introduced and explained as needed.

Authors: Poria Azadi

This article explores the emergence of autonomy and agency by connecting fundamental computational limits (decidability, completeness, computational irreducibility) with physical concepts. We introduce a formal model of a "minimal agent" operating within potentially Turing-complete environments. Using algorithmic information theory, we argue that the inherent undecidability and computational irreducibility of agent-environment interaction lead to unpredictability and novel information generation, enabling agency (effective goal-directed action). Computational irreducibility prevents full external prediction, creating necessary conditions for autonomous behavior. We relate this to computational sourcehood, where an agent is the irreducible origin of its behavior, though formalizing this concept remains challenging. Our central thesis, formally proven, is that genuine autonomy necessarily implies undecidability from an external perspective, distinguishing autonomous systems from predictable ones. We propose that agency arises when agent-environment coupling complexity allows mutual information between internal states and relevant environmental variables to increase, particularly where analytical solutions are absent and operational closure is needed for persistence. This framework links agency directly to the computational properties of interaction, offering implications for understanding consciousness, designing autonomous AI, and reconceptualizing free will in a deterministic yet computationally irreducible universe.

Authors: Vibhas Vats, Md. Alimoor Reza, David Crandall, Soon-heung Jung

Traditional multi-view stereo (MVS) methods primarily depend on photometric and geometric consistency constraints. In contrast, modern learning-based algorithms often rely on the plane sweep algorithm to infer 3D geometry, applying explicit geometric consistency (GC) checks only as a post-processing step, with no impact on the learning process itself. In this work, we introduce GC MVSNet plus plus, a novel approach that actively enforces geometric consistency of reference view depth maps across multiple source views (multi view) and at various scales (multi scale) during the learning phase (see Fig. 1). This integrated GC check significantly accelerates the learning process by directly penalizing geometrically inconsistent pixels, effectively halving the number of training iterations compared to other MVS methods. Furthermore, we introduce a densely connected cost regularization network with two distinct block designs simple and feature dense optimized to harness dense feature connections for enhanced regularization. Extensive experiments demonstrate that our approach achieves a new state of the art on the DTU and BlendedMVS datasets and secures second place on the Tanks and Temples benchmark. To our knowledge, GC MVSNet plus plus is the first method to enforce multi-view, multi-scale supervised geometric consistency during learning. Our code is available.

Authors: Garret Castro

Motivated by group-project distribution, we introduce and study stable matching under the constraint of applicants needing to share a location to be matched with the same institute, which we call the Location-Restricted Stable Matching problem (LRSM). We show that finding a feasible matching is NP-hard, making finding a feasible and stable matching automatically NP-hard. We then analyze the subproblem where all the projects have the same capacity, and the applicant population of each location is a multiple of the universal project capacity, which mimics more realistic constraints and makes finding a feasible matching in P. Even under these conditions, a stable matching (a matching without blocking pairs) may not exist, so we look for a matching that minimizes the number of blocking pairs. We find that the blocking pair minimization problem for this subproblem is inapproximable within $|A|^{1-\epsilon}$ for $|A|$ agents and provide an $|A|$-approximation algorithm to show this result is almost tight. We extend this result to show that the problem of minimizing the number of agents in blocking pairs is also inapproximable within $|A|^{1-\epsilon}$, and since there are only $|A|$ agents, this result is also almost tight.

Authors: Samin Aref, Boris Ng

Clique partitioning is a fundamental network clustering task, with applications in a wide range of computational sciences. It involves identifying an optimal partition of the nodes for a real-valued weighted graph according to the edge weights. An optimal partition is one that maximizes the sum of within-cluster edge weights over all possible node partitions. This paper introduces a novel approximation algorithm named Troika to solve this NP-hard problem in small to mid-sized networks for instances of theoretical and practical relevance. Troika uses a branch-and-cut scheme for branching on node triples to find a partition that is within a user-specified optimality gap tolerance. Troika offers advantages over alternative methods like integer programming solvers and heuristics for clique partitioning. Unlike existing heuristics, Troika returns solutions within a guaranteed proximity to global optimality. And our results indicate that Troika is faster than using the state-of-the-art integer programming solver Gurobi for most benchmark instances. Besides its advantages for solving the clique partitioning problem, we demonstrate the applications of Troika in community detection and portfolio analysis. Troika returns partitions with higher proximity to optimal compared to eight modularity-based community detection algorithms. When used on networks of correlations among stocks, Troika reveals the dynamic changes in the structure of portfolio networks including downturns from the 2008 financial crisis and the reaction to the COVID-19 pandemic. Our comprehensive results based on benchmarks from the literature and new real and random networks point to Troika as a reliable and accurate method for solving clique partitioning instances with up to 5000 edges on standard hardware.

Authors: Marco Franzreb, Martin Burtscher, Stephan Rudolph

I present a new GPU implementation of the wavelet tree data structure. It includes binary rank and select support structures that provide at least 10 times higher throughput of binary rank and select queries than the best publicly available CPU implementations at comparable storage overhead. My work also presents a new parallel tree construction algorithm that, when excluding the time to copy the data from the CPU to the GPU, outperforms the current state of the art. The GPU implementation, given enough parallelism, processes access, rank, and select queries at least 2x faster than the wavelet tree implementation contained in the widely used Succinct Data Structure Library (SDSL), including the time necessary to copy the queries from the CPU to the GPU and the results back to the CPU from the GPU.

Authors: Michał Pilipczuk, Giannos Stamoulis, Michał Włodarczyk

In the Disjoint Shortest Paths problem one is given a graph $G$ and a set $\mathcal{T}=\{(s_1,t_1),\dots,(s_k,t_k)\}$ of $k$ vertex pairs. The question is whether there exist vertex-disjoint paths $P_1,\dots,P_k$ in $G$ so that each $P_i$ is a shortest path between $s_i$ and $t_i$. While the problem is known to be W[1]-hard in general, we show that it is fixed-parameter tractable on planar graphs with positive edge weights. Specifically, we propose an algorithm for Planar Disjoint Shortest Paths with running time $2^{O(k\log k)}\cdot n^{O(1)}$. Notably, our parameter dependency is better than state-of-the-art $2^{O(k^2)}$ for the Planar Disjoint Paths problem, where the sought paths are not required to be shortest paths.