Theory of Computing Report

Lance has posted about his, and around 160 others, being laid off from IIT here.

Hence I looked into what is happening at IIT to see if there is a lesson for us all.

I) I wondered why IIT had declining enrollment. I wondered which of the two was the issue (and of course there are other reasons). 

--The enrollment cliff

--International students have declined in number. Why? (1) Having getting student visas, (2)  They think they are not welcome here (3) Schools in their home country getting better. Note that I am just guessing.

Rather than speculate I asked ChatGPT for the data on both enrollment and on international enrollment from 2015 to 2025. Here is the data: here.

a) 2015 had an enrollment of 7792. It went down in 2020 (COVID?) but then came up again and it was 8838 in 2024.  In all the years for which there is data international students were about half of the students.

b) 2024: 8838 students, of which 4596-International (52%), 4242-Americans

   2025: 7502 students, of which 2141-International (42%), 5361-Americans

So it looks like the enrollment cliff was not a problem since more Americans came, but the decline in international students is a problem.

I think that international students pay more, so their decline creates more of a financial pinch.

----------------------------------

II) I wondered if other schools had massive layoffs so  I asked Google what other schools had laid off more than 30 professors in the last two years. It had an issue with that since schools combine faculty and staff.  Even so, the main fact is that (a) it is happening at other schools, and (b) 160 is more than usual. 

--------------------------------------

III) Challenges facing Universities

a) The enrollment cliff. This will be a real problem for small schools.  For big schools it may be an opportunity to have smaller classes.  This issue cannot be stopped.

b) Less international students means less money. This may change since this or a later administration may change the rules. However, changing the rules might not help much since other countries have fine schools and international students may feel they are not welcome here.

c) Grants are drying up. Again, this may change.

d) AI and cheating. This may make us rethink the entire point of education.

e) Does college exist to create an educated public who can make decisions and vote intelligently, or are colleges vocational? It's getting harder to do both.

f) Fads: The hot topics in CS now are Quantum, ML, and Quantum ML. What will they be in 10 year? How do we adjust? Do other fields have this problem?

g) Tuition keeps going up. The business model may be broken..

h) A while back online education seemed like it might be an alternative for some students (MOOCS were hot). That hasn't happened yet but it might.

i) This is a far bigger subject than the points above. Maybe Lance can write a book on the topic now that he has some free time.

By gasarch

We give a randomized algorithmic version of the Balog--Szemer\'edi--Gowers theorem for sets of integers. Let $A\subseteq[N]$ have size $n:=|A|\geq2$, let $1\leq K\leq n$, and suppose that its additive energy satisfies $E(A)\geq n^3/K$. Reiher and Schoen proved existentially that, for every fixed $\epsilon \in (0,1/2)$, there is a subset $A'\subseteq A$ satisfying $|A'|\geq(1-\epsilon)n/\sqrt K$ and $|A'-A'|\leq O_{\epsilon}(K^4)|A'|$; the size scale $n/\sqrt K$ is essentially optimal. We give an algorithmic counterpart: with probability at least $1-n^{-10}$, our algorithm runs in time $nKN^{o(1)}$ and returns a subset $A'\subseteq A$ satisfying $|A'|\geq cn/\sqrt K$ and $|A'-A'|\leq CK^4|A'|$, where $c,C>0$ are absolute constants. Thus the output attains the essentially optimal subset-size scale and the best-known $K^4$ dependence for the normalized difference set.

The line--versus--point test asks the following local-to-global question. Suppose a function $f\colon\mathbb{F}_q^m\to\mathbb{F}_q$ is, on average over a random affine line $L$, correlated with some degree-$d$ polynomial on $L$. Must $f$ then be globally correlated with a single multivariate polynomial of degree at most $d$? Beyond being a natural combinatorial question, this test and its variants have played a central role in the construction of PCPs. Generally, one is most interested in the soundness of the test: the smallest expected local agreement from which one can still deduce nontrivial global agreement. We revisit the line--versus--point test and prove the following cubic threshold. If \[ \Pr_{L,,x\in L}\bigl[P_L(x)=f(x)\bigr]\ge C\left(\frac{d}{q}\right)^{1/3}, \] then there is a polynomial $Q\in\mathbb{F}_q[X_1,\ldots,X_m]$ of total degree at most $d$ such that \[ \Pr_{x\in\mathbb{F}_q^m}[Q(x)=f(x)]\ge c\cdot \Pr_{L,,x\in L}\bigl[P_L(x)=f(x)\bigr], \] for absolute constants $C,c>0$ and over every finite field $\mathbb{F}_q$. The prior state of the art, due to [HKSS24], had an inexplicit exponent in their soundness, which we estimate to be $\Omega\left((d/q)^{1/48}\right)$ in the $m>2$ case and $\Omega\left((d/q)^{1/7}\right)$ in the $m=2$ case. We believe our proof is comparatively direct and isolates the combinatorial and algebraic mechanisms responsible for the improved soundness.

A secret-sharing scheme allows a dealer to distribute a secret $s$ among $n$ parties such that only predefined “authorized” sets of parties can reconstruct the secret, and all other “unauthorized” sets learn nothing about $s$. Families of authorized sets are called access structures, and a scheme is called linear if its sharing map is linear in the secret and the dealer’s randomness. We show that every $n$-party access structure can be realized by a linear secret-sharing scheme for one-bit secrets with maximal share size of $2^{\lceil n/2\rceil-1}+1$ bits. A counting lower bound for monotone span programs shows that almost all access structures require linear share size $2^{n/2-o(n)}$, which makes our upper bound tight. Our scheme is considerably simpler than previous schemes that obtained share size $2^{cn+o(n)}$ with $1/2\leq c<1$. We also present a variant of this linear construction that is tailored for monotone k-DNFs access structures (also known as $k$-upslices). Then, by combining it with a non-linear scheme of Applebaum et al. (STOC 2020), we derive a scheme for all access structures with share size $2^{0.496n+o(n)}$. This improves the previous upper bound of $2^{0.585n+o(n)}$ by Applebaum and Nir (CRYPTO 2021), and establishes a separation between the worst-case non-linear and linear exponents. Plugging the quadratic construction of Beimel, Othman, and Peter (CRYPTO 2021) into this framework yields quadratic schemes of share size $2^{0.4995n+o(n)}$, separating the quadratic and linear exponents. The linear scheme for upslices and its proof were discovered in conversations prompted by the author with GPT-5.6 Sol and Claude Fable 5.

We prove a general upper bound for scaling windows of sparse monotone covering problems. From that, we deduce that for every fixed value $k\geq 3$, the window of random $k$-SAT is $O(n/\log n)$, improving the Friedgut-Bourgain bound of $O(n/\log\log n)$. We also show that random signed Not-All-Equal-$k$-SAT and hypergraph non-two-colourability (Property B) have windows of the same order. Our upper bound for scaling windows of sparse monotone covering problems follows from a general strategy combining the strengthening of Bourgain's sharp threshold theorem by Keevash, Lifshitz, Long, and Minzer with a local-to-random replacement principle. This provides a systematic method for proving scaling-window bounds, addressing a question of Perkins.

We give a quantitative combinatorial characterization of size-oblivious one-sided testability in the dense graph model, resolving a question of Alon, Fischer, Newman, and Shapira. For hereditary graph properties, we prove that one-sided testability is quantitatively equivalent to the existence of suitable hypergraph containers, a central and widely used tool in modern combinatorics. Combining this equivalence with the Alon--Shapira notion of semi-hereditariness yields a quantitative characterization of arbitrary graph properties. The correspondence is effective in both directions and provides explicit translations between tester complexity and container parameters. Our proof is regularity-free and extends uniformly to every fixed finite relational signature of bounded arity, including digraphs, coloured graphs, and hypergraphs. As applications, we obtain quantitative closure results for partition properties and testers for properties defined by the existence of a linearly large induced substructure.

A Boolean-weighted graph is a finite graph whose edges carry DNF formulas over a common variable set. This paper studies two isomorphism problems on such graphs, distinguished by whether the per-edge condition requires the matched edge labels to be syntactically DNF-isomorphic (BWG-ISO) or syntactically DNF non-isomorphic (BWG-NI), each over a vertex bijection that preserves edges. The two sit at opposite ends of one phenomenon: imposing local syntactic DNF-isomorphism on every edge does not raise complexity above graph isomorphism, whereas replacing it by local non-isomorphism makes the problem NP-hard, the jump being driven by the search over host isomorphisms rather than by the complexity of the labels. For the isomorphism requirement, BWG-ISO $\equiv_m^p$ GI: although syntactic DNF isomorphism is itself GI-complete (Ausiello, Cristiano, and Laura 2012), attaching such a label to every edge leaves the global problem exactly at GI. For the non-isomorphism requirement, the per-edge test is a graph-non-isomorphism query, placing BWG-NI in $NP^{GI}$; the paper shows it is GI-hard and GNI-hard and not coNP-hard unless PH $= \Sigma_2^P$, and proves it is NP-hard. The hardness already holds when labels are restricted to monotone DNFs, equivalently $\{0,1\}$-matrices, so it stems from the interaction with host automorphisms, not from rich Boolean structure. This NP-hardness is unconditional; the hardest NP set known to $\le_m^p$-reduce to FI is GI (Agrawal and Thierauf 2000). BWG-NI is thereby a natural inhabitant of $NP^{GI}$: with the NP-hardness, $NP^{GI}$ membership places it outside $P^{GI}$, $coNP^{GI}$, and $Low_2$ unless PH $= \Sigma_2^P$, making it a natural candidate to separate $NP^{GI}$ from $P^{GI}$ when the hierarchy is infinite. The second-level collapse that would be forced by its $\Sigma_2^P$-completeness is one level below the third-level collapse Agrawal and Thierauf obtain for the formula isomorphism problem FI, reflecting that BWG-NI, unlike the coNP-hard FI, lies in $NP^{GI}$. The counting problem #BWG-NI is #P-hard.

 

When the papacy becomes vacant, a new pope is elected through a procedure known as the conclave. Cardinal-electors from around the world gather in the Sistine Chapel and vote in successive rounds. In each round, every elector casts one ballot for a candidate. If some candidate receives at least two-thirds of the votes, the conclave ends and that candidate is elected pope; otherwise, the ballots are burned and another round is held. 

 

The most recent papal conclave took place from May 7 to May 8, 2025, in the Sistine Chapel. It ended on the second day of voting when the College of Cardinals elected Cardinal Robert Francis Prevost as the 267th pope, who chose the name Pope Leo XIV. Pope Leo XIV has a B. S. degree in mathematics. 

There is a well-known movie about the conclave. Conclave (2024), directed by Edward Berger, is a political thriller detailing the election of a new Pope following the unexpected death of the previous pontiff. The film focuses on Cardinal Lawrence, played by Ralph Fiennes, as he manages the secretive process and uncovers factional infighting and personal scandals among the leading candidates. The movie is based on Robert Harris’s 2016 novel.

The Conclave process

The conclave process for cardinals is described as follows: In round one each cardinal votes uniformly at random for one of the cardinals.

This occurs again in each of the following rounds, but in round the probabilities to vote for cardinal are weighted according to the number of votes for this cardinal in round . The process depends on a real positive parameter α.

Let be the number of votes cardinal received  in round . The probability to vote for cardinal in round is proportional to taken to the power α.

Test your intuition:  What is the expected number of steps until a pope is elected

1.  When α = 1
2.  When α < 1
3.  When α > 1

Remarks:  1) The case α = 1 was study already by Wright and Fisher and by Kingman. The general model is introduced and studied recently by Benjamini, Cai, Chen, Gong, and Li.  Their model was inspired by a discussion with Francesco Maria Saettone after the passing of Pope Francis.

2) Robert Alicki told me the following amazing coincidence related to the newly elected pope: Robert and his wife Maria became grandparents of Leon Robert. After their daughter Monika registered baby LR in the office, in the morning, cardinal Robert became pope Leon in the afternoon. Pope Leon studied mathematics like LR’s father and has his birthday on the same day as Monika. What are the odds of these coincidences and what can you learn from them?

3) Here is an earlier post about cardinals from 2012.

(source of picture.)

By Gil Kalai

• A permutation generation algorithm in the work of 13th-century Kabbalist Abraham Abulafia (\(\mathbb{M}\), via). The resulting permutation sequence is the one you get by reversing suffixes whose lengths form the sequence \((((2, 3)^2, 2, 4)^3, 2, 5)^4, \dots\) but that’s not the generation rule. Instead the rule is: to generate the permutations of \(1, 2, 3,\dots, n,\) form its \(n\) cyclically rotated permutations (starting with \(1, 2, 3,\dots, n,\)) and for each one in order, recursively generate the permutations of its length-\((n-1)\) suffix.

  The link claims that this is the first method for systematically listing permutations (long before the discovery of the Steinhaus–Johnson–Trotter algorithm for generating a different ordering, by 17th-century bell ringers). However, I’m not entirely convinced: it’s not the same as an enumeration algorithm, but factorials and lists of permutations were known long before to the Jain mathematicians, to scholars of the Talmudic period, and to medieval Arab grammarians and mathematicians (see Wikipedia on the history of the factorial). They may not have described their rules for generating lists of permutations, but they did generate those lists, presumably by following some rule. Priority arguments aside, though, I still think it’s interesting.

• Complexity Class of the Week: \(\mathsf{L}_2^P\) (\(\mathbb{M}\)). This is a complexity class characterized by polynomial-time reductions to finding the minimum element of a comparator circuit that computes a total order, or finding a violation of total ordering for the circuit. It has interesting relations both to other complexity classes (e.g. \(\mathsf{NP}\subset\mathsf{P/poly}\) collapses \(\mathsf{PH}\) to \(\mathsf{L}_2^P\)) and to circuit complexity (it requires circuits of size \(\ge n^k\) for all fixed \(k\)).

• Terry Tao on recent problematic behavior in mathematics research (\(\mathbb{M}\)): AI companies generate a solution to a well-known problem, take the publicity for their solution, but don’t take the effort to digest and explain the solution in a way that makes sense to human mathematicians.

• Transliteration of unicode text from one script to another through its Locale Data Markup Language is Turing-complete (\(\mathbb{M}\), via). The proof is via Post tag systems. The widely-used ICU library guards against this by imposing a small limit on the number of times a unit can be rewritten, so there is no denial-of-service vulnerability in practice, but this limit is not in the spec.

• Leslie Lamport’s dictum “State the problem before describing the solution” (\(\mathbb{M}\)).

• Big spike in monthly submissions to arXiv Combinatorics (\(\mathbb{M}\)).

• Q&A from the slop trenches (\(\mathbb{M}\), via). Two human machine-learning researchers on their recent experiences refereeing LLM-generated slop with bad references, and then getting their reject recommendations overridden as accept for oral presentation with an unenforceable request to fix the slop.

• Asymptotically attaining the Moore bound (\(\mathbb{M}\)), Wouter Cames van Batenburg and Samuel Korsky, on the largest graphs with maximum degree \(d\) and diameter \(k\), for fixed \(k\) in the limit as \(d\) grows.

• The mathematical beauty of hyperbezier curves (\(\mathbb{M}\)), on a curve family with the same control points as cubic Bézier curves but with smoother curvature variation and a larger range of parameters for which the curvature is monotonic.

• The only reason you’ll ever need not to write with AI (\(\mathbb{M}\)): because it could expose you to charges of plagiarism.

• Illinois Tech lays off roughly 160 tenured faculty members including Lance Fortnow (\(\mathbb{M}\)).

• A stroll through the pentagram zoo (\(\mathbb{M}\)). Richard Evan Schwartz explains the mathematics behind some of his mathematical artworks, based on the pentagram map, a dynamical system that repeatedly replaces the vertices of a polygon by the crossing points of its diagonals.

• Slides for my two talks at CCCG’26 are now online (\(\mathbb{M}\)):

  • “Minimum-weight Steiner triangulation of convex polygons requires interior Steiner points”

  • “Tangent spheres and integer distances”

• Liquids can shatter (\(\mathbb{M}\)).

By David Eppstein

Authors: Radu Curticapean, Daniel Neuen, Amir Nikabadi, Tim Seppelt, Ben Young

Two graphs $G$ and $H$ are homomorphism indistinguishable over a graph class $\mathcal{F}$ if they admit the same number of homomorphisms from every graph in $\mathcal{F}$. A wide range of relaxations of graph isomorphism arise this way: isomorphism itself over the class of all graphs [Lovász, Acta Math. Hung. 1967], equivalence under the $k$-dimensional Weisfeiler-Leman algorithm over the graphs of treewidth $\leq k$ [Dvořák, J. Graph Theory 2010], and quantum isomorphism over planar graphs [Mančinska-Roberson, FOCS 2020]. Since the class $\mathcal{F}$ is typically infinite, it is not clear a priori whether homomorphism indistinguishability over $\mathcal{F}$ is decidable; for planar graphs it is undecidable. Every class for which decidability was previously known is sparse. We give the first decidability results for dense graph classes: We introduce the dense Weisfeiler-Leman algorithm that decides homomorphism indistinguishability over the class of graphs of cliquewidth $\leq k$, the dense counterpart of treewidth. This relation was not previously known to be decidable. The algorithm colors $k$-tuples of vertex subsets rather than $k$-tuples of vertices. Beyond the class of all graphs of cliquewidth $\leq k$, we prove a general meta-theorem: homomorphism indistinguishability over every $\mathsf{CMSO}_1$-definable graph class of bounded cliquewidth is decidable, in randomized exponential time. For classes of bounded linear cliquewidth the bound improves to $\mathsf{PSPACE}$, and we show this is tight by exhibiting such a class for which the problem is $\mathsf{PSPACE}$-complete. These are the first general algorithms for homomorphism indistinguishability over dense graph classes.

Authors: Huanyi Zhou

The $(\min,+)$ convolution is a central problem in fine-grained complexity, and whether it admits a truly subquadratic algorithm remains open. We study it through tropical polynomials, where $(\min,+)$ convolution is exactly polynomial multiplication. We introduce tropical decomposition width, a parameter measuring how finely a tropical polynomial can be decomposed into low-degree factors. We prove modular convexity theorems showing that bounded tropical decomposition width forces strong convexity on arithmetic subpolynomials. This yields deterministic algorithms for computing $a\otimes b$ in $O(n\max(\operatorname{tdw}(a),\operatorname{tdw}(b))^2)$ time when the width is given, and in $O(ne^{\min(\operatorname{tdw}(a),\operatorname{tdw}(b))(1+o(1))})$ time otherwise, without requiring a decomposition. For Multiple-Sequence $(\min,+)$ Convolution, we give a randomized algorithm running in $O(kn^2\sqrt{\min(k,n)}\log^{1.5}(kn))$ time for $k$ sequences of length at most $n$, improving the natural $O(k^2n^2)$ bound. We also obtain conditional lower bounds, a faster single-entry algorithm, and new upper bounds for Multiple-Choice Knapsack. Finally, bounded-decomposition-width classes admit interpolation algebras of finite generating rank, whereas distinguishing all tropical polynomials of degree at most $n$ requires rank exactly $\lfloor n/2\rfloor+1$. We further show that tropical decomposition width cannot decrease under any flat $\mathbb T$-algebra extension. These results connect efficient tropical multiplication with structural rigidity.

Authors: Kimberly Fluet, Lane A. Hemaspaandra, Christopher M. Homan

This article provides an assignment designed to let undergraduate students who have completed an undergraduate CS1/CS2 sequence try to themselves, in groups, prove Fortune's Theorem. (Fortune's Theorem states that if the complement of the Boolean satisfiability problem polynomial-time reduces to a sparse set, then the Boolean satisfiability problem is polynomial-time computable. The assignment does not assume that students have previously seen the Boolean satisfiability problem, polynomial-time reductions, or sparse sets. Rather, it teaches those within the assignment. Note: Reworded into the technical vocabulary of complexity theory, Fortune's Theorem states that no sparse set is coNP-hard unless P=NP. Fortune's Theorem was a major advance in the understanding of the relationship between hardness and density.) We provide both the assignment handout (as the main body of this report plus Appendix A) and a solution to the assignment (as Appendix B, which would of course not be made available to the students until after they had handed in the assignment). The assignment handout, though the instructor can change this, is framed as having the students starting the assignment in teams in class for a whole class session, and then finishing it in those same teams as a take-home assignment, and handing it in before the next class session. We have found that student groups often succeed, partially or completely, in this challenge. This can mean a lot to the students: they see that they were able to make an advance that, when it was first obtained, appeared in what was arguably at the time the top journal venue for complexity theory research. This can give them confidence that they have substantial problem-solving skills (which basically means research skills) when they truly apply themselves to a given challenge.

Authors: Maichi Zhang, Naoyuki Kamiyama, Kanae Yoshiwatari

Multi-Agent Path Finding for Large Agents (LA-MAPF) is a geometric variant of MAPF in which agents are modeled as disks and conflicts are determined by physical overlap in the underlying Euclidean workspace. The goal of LA-MAPF is to decide whether there exists a sequence of conflict-free transitions from a start configuration to a goal configuration. Agafonov and Yakovlev proved that LA-MAPF is NP-hard. In this paper, we strengthen their result by proving that LA-MAPF is PSPACE-complete via a polynomial-time reduction from Restricted Sliding Tokens.

Authors: Phokion Kolaitis, Rik Sengupta

Multi-layer transformers form the critical component of essentially all large language models (LLMs) in use today. Because of their ubiquity and computational capability, there is a rapidly growing body of work that aims to precisely calibrate the expressive power of transformers as language recognizers by comparing them against standard models of computation studied for decades by the theoretical computer science community. In this endeavor, circuit complexity has by and large emerged as the "correct" branch of computational complexity to analyze the expressive power of transformers; the reason is that parameterizing transformers by the various resources they use, such as attention and precision, leads to direct comparisons with different classes of circuits parameterized by resources such as type of gates, size, and depth. Here, we present an overview of selected results that delineate the expressive power of transformers using concepts and methods from circuit complexity.

Authors: Daqing Wan

We prove that, for every constant $ρ>1$, the Euclidean shortest vector problem is NP-hard to approximate within any constant factor $ρ$ under a deterministic polynomial-time many-one reduction. This extends our previous deterministic NP-hardness result from $ρ<\sqrt 2$ to arbitrary constants and gives a deterministic version of Khot's randomized arbitrary-constant theorem. Our proof also gives deterministic counterparts of the two classical dimension-dependent regimes of Haviv and Regev: $2^{(\log n)^{1-\varepsilon}}$ under quasipolynomial-time reductions and $n^{c/\log\log n}$ under subexponential-time reductions.

Authors: Jonah Bondar, Stephen Vavasis

Dadush et al.\ (2024) recently developed a scaling-invariant layered least squares algorithm for linear programming whose complexity depends on the optimal condition measure $\barχ_A^*$. Their work builds on Vavasis and Ye's (1996) algorithm whose running time depends only on the constraint matrix $A$ through the condition number $\barχ_A$. The optimal condition measure $\barχ_A^*$ is defined as the minimum $\barχ_{AD}$ achievable over all positive diagonal column rescalings $D$. Dadush et al.\ (2024) also introduced the optimal circuit imbalance measure $κ_W^*$, which serves as a lower bound for $\barχ^*_A$. Instances with artificially large optimal circuit imbalance measures $κ_W^*$ can be easily constructed; however, finding naturally occurring examples where this optimal scaling-invariant measure grows exponentially is of independent interest. In this paper, we show that the Ben-Tal Nemirovski (BN) linear programming approximation of the unit disk provides such an example. By explicitly constructing circuits in the kernel of the BN formulation, we prove that the optimal circuit imbalance measure $κ_W^*$ grows exponentially in the number of approximation steps. Since $κ_W^*$ lower bounds $\barχ_A^*$, our result demonstrates that the BN approximation yields an exponentially ill-conditioned family of constraint matrices.

Authors: Chaya Keller, Shakhar Smorodinsky

A set in $\mathbb{R}^d$ is $s$-convex if it is the union of at most $s$ convex sets. A family $F$ satisfies the $(p,q)$ property if among any $p$ sets in $F$, some $q$ intersect. Let $\mathrm{HD}_d^{(s)}(p,q)$ be the minimum number of points needed to pierce a finite family of $s$-convex sets that satisfies the $(p,q)$-property. Alon and Kalai (1995) proved that $\mathrm{HD}_d^{(s)}(p,q)$ exists for any $p \geq q \geq d+1$ and any $s \geq 1$, but the quantitative bounds they obtained are very loose. We present several improved upper and lower bounds, for a general $d$ and for $s$-intervals of the line (i.e., $\mathrm{HD}_1^{(s)}(p,q)$). In particular, we prove the following: (i) For every $d\ge2$, $s \geq 1$ and $δ>0$, if $p>q$ and $q\ge C_d\log(e sp)$, then $\mathrm{HD}_d^{(s)}(p,q) \le p-q+1 + O_{d,δ}((s \cdot \tfrac{p}{q} \cdot \log \tfrac{esp}{q})^{ρ_d+δ}),$ where $ρ_d2$. (iii) For any fixed $s$, there are an integer $κ_s\in\{s,\ldots,2s\}$ and constants $C_s,p_s>0$ such that, whenever $p\ge p_s$ and $q\ge C_s\log(ep)$, $ \mathrm{HD}_1^{(s)}(p,q)\in\{p-q+κ_s,\;p-q+κ_s+1\}. $ Interestingly, this two-value concentration result holds, although the exact value of the threshold remains unknown. (iv) For any $s \geq 1$, $\mathrm{HD}_3^{(s)}(p,4) \geq sp^{2-o(1)}$. Already for families of convex sets, this significantly improves the best known lower bound on $\mathrm{HD}_d^{(1)}(p,d+1)$, for all $d \geq 3$.

Authors: Georgy Noarov, Aaron Roth

We study online probabilistic forecasting of binary outcomes chosen by an adaptive adversary. Given an online learning algorithm for a weak hypothesis class $H$, we would like to efficiently obtain two incomparable guarantees that existing online boosting techniques provide separately. Online gradient boosting competes in Brier score with the best predictor induced by the span of $H$ on every sequence, but promises nothing when the span does not contain an accurate predictor. Online weak-to-strong boosting drives classification error to zero under a weak-learning condition, but promises little when that condition fails. We give a simple defensive forecasting algorithm, the Defensive Booster, that obtains both guarantees. On every adaptive sequence, its Brier score is competitive with the best prediction induced by the span of $H$ at the same rate as online gradient boosting; simultaneously, whenever the realized transcript satisfies the smooth weak-learning condition, its Brier score and randomized classification error satisfy the same rate guarantee as online classification boosting. This is achieved by operationalizing the "dual view" of boosting: When the algorithm's randomized classification error is persistently high, its mistake weights form a smooth reweighting on which every weak hypothesis has low edge, yielding an ex-post hard-core certificate that the weak-learning condition fails. We also develop a strongly adaptive variant, which satisfies both guarantees on every time interval. The Defensive Booster is very efficient: it accesses just one weak-class learner, whereas the prior online boosting methods we compare against maintain large weak-learner ensembles. Experiments on synthetic and real data streams demonstrate its strong predictive performance (sometimes substantially improving over all prior baselines) coupled with orders-of-magnitude faster runtime.

Authors: Hung Le, Huy Pham, Cuong Than, Tuan Tran

In this short note, we show that $H$-minor-free graphs have a tree cover with $3$ trees and constant stretch for any fixed graph $H$. The number of trees matches the recent lower bound by Chen, Tan, and Xu who showed that a toroidal grid requires at least $3$ trees for constant stretch. Our result is obtained by establishing a connection between tree covers and Assouad--Nagata dimension and then invoking the recent dimension bound for minor-free metrics by Liu.

Authors: Omar Montasser

We revisit the problem of learning predictors robust to adversarial examples at test-time. We prove that VC classes are adversarially robustly learnable with sample complexity linear in the VC dimension $d$, providing an exponential improvement over the previous upper bound of Montasser, Hanneke, and Srebro (2019). Remarkably, this result is achieved with a simple improper algorithm that combines the classic heuristic bagging (bootstrap aggregation) of Breiman (1996) with robust empirical risk minimization (RERM). Our algorithm computes RERMs on $O(d^\star)$ independent bootstrap samples and outputs their majority vote, where $d^\star$ denotes the dual VC dimension. We complement this result with a lower bound showing that this is unavoidable: in general, any learner in this oracle model requires $Ω(d^\star)$ calls to an RERM oracle, even when given arbitrarily many training examples.

Authors: Ruizhe Zhang

Let $K\subset\mathbb{R}^n$ be an isotropic convex body. We prove that the hit-and-run walk, started from any $M$-warm distribution, reaches total-variation distance $\varepsilon$ from the uniform distribution on $K$ in $O\!\left(n^2ψ_n^{-2}\log^3(M/\varepsilon)\right)$ steps, where $ψ_n^{-1}$ is the Kannan-Lovász-Simonovits (KLS) constant. Up to logarithmic factors, this matches the best-known warm-start mixing time for the ball walk. Chen and Eldan [Discrete Comput. Geom. 2026] obtained the same $n^2ψ_n^{-2}$ dependence for hit-and-run, but with polynomial dependence on $M/\varepsilon$. Our result improves that polynomial dependence to a polylogarithmic one, fully resolving their open question about warm-start mixing of hit-and-run in isotropic convex bodies.

Authors: Paola Bonizzoni, Alessio Conte, Gianluca Della Vedova, Younan Gao, Roberto Grossi, Brian Riccardi

Compactly representing a variation graph is a core problem in computational pangenomics that is usually attacked with techniques that have been originated on texts and adapted to graphs. In this paper we propose a new framework that takes a topology-centric perspective instead. A variation graph is modeled as a directed acyclic graph (DAG) together with a set of distinguished paths, where each path is assigned a distinct color. Our compact representation is centered on pebbling the graph, i.e. placing colored pebbles on edges so that every predefined path can be univocally reconstructed from the pebbled edges. In particular, a saturated pebbling marks each chosen edge with every path (color) traversing it. We first propose a data structure to represent and query a variation graph with storage space depending on the size of the pebbling. The supported queries are: (i) path query, which recovers a path given its color, and (ii) edge query, which reports the colors of paths traversing a given edge. We then prove that the problem of finding a pebbling of minimum size is solvable in polynomial time. On the contrary, we prove that finding a saturated pebbling of minimum size is NP-hard, but can be reduced to the minimum-weight set cover problem, allowing us to leverage integer linear programming (ILP) solvers. We show how to exploit saturated pebblings to achieve faster queries times than minimum size pebbling. Our framework opens a new algorithmic viewpoint on developing more efficient variation graph representations rooted on the study of the topology of those graphs.

Authors: Lorenzo Carfagna, Giovanni Manzini

We consider systems of submatrix equations, that is, sets of equality constraints over square submatrices of the input. By generalising the recursive algorithm of Gawrychowski et al. [Universal reconstruction of a string, Theoretical Computer Science 2020] to two dimensions, we obtain a linear-time procedure that finds a solution for any such input system. As an immediate by-product, this yields an optimal-time algorithm for decompressing any two-dimensional macro scheme based on copy operations of sub-squares.

Authors: Peter Davies-Peck, Xusheng Zhang

The Lovász Local Lemma (LLL) is a probabilistic tool that has been shown to be of central importance in the study of distributed algorithms. For example, the constructive LLL is known to be complete for the class of locally-checkable labeling problems with $o(\log n)$ randomized complexities in the LOCAL model. One classic application of the LLL is in coloring graphs with some sparse structure, such as triangle-free graphs. Triangle-free coloring therefore serves as a benchmark problem for techniques for sublogarithmic randomized distributed algorithms. The state-of-the-art distributed triangle-free coloring algorithm of Pettie and Su [ICALP 2013, Information and Computation 2015] uses $\fracΔ{k}$ colors (where $k$ can be up to $(\frac14 - \varepsilon)\ln Δ$) and consists of $O(k+\log^* n)$ applications of the distributed LLL. However, the distributed LLL is itself a difficult problem; despite significant study, the fastest algorithms known require $O(\log_Δn)$ or $O(\fracΔ{\logΔ})+\log^{O(1)}\log n$ rounds. In this work, we adapt the Pettie-Su's algorithm so that the resulting LLL instances can be solved in $\log^{O(1)}\log n$ rounds, by employing the 'resilience' definition of Davies [SODA 2023]. This gives an $O(k)+ \log^{O(1)}\log n$ complexity (since the LLL is not needed when $k= \log^{ω(1)}\log n$), essentially causing the LLL steps to no longer be the bottleneck of the algorithm. As a corollary we obtain the first $\log^{O(1)}\log n$-round algorithms for coloring triangle-free graphs with $o(Δ)$ colors. The same framework also yields a companion girth-$5$ algorithm, using $(1+\varepsilon)Δ/\ln Δ$ colors in $O(k)+ \log^{O(1)}\log n$ rounds, matching the best known existential upper bound for the number of colors.

Authors: Adam Y. Shavit

In restricted assignment - makespan minimization where each job has one size and a set of allowed machines - the configuration LP is the tightest studied relaxation, and its integrality gap is open in general. On two-weight graph balancing - each job allowed on at most two machines, sizes from two values - the value is known, both bounds due to Jansen, Land, and Maack (2016): their Table 1 instance attains 3/2, and their Corollary 11 bound of 2 - s/b for sizes s < b meets it at {1,2}. We ask how small such an instance - a witness - can be. We give I*, a six-job witness: the complete graph on four machines, unit jobs on a Hamiltonian cycle, weight-2 jobs on the complementary perfect matching, with integral optimum 3 against relaxation value 2. That is one job fewer than the smallest previously in print, and we prove it minimum and unique at its size. No instance of the class with at most five jobs reaches gap 3/2, on any number of machines; at six jobs, again on any number of machines, I* is the only witness, up to relabeling machines and adding machines no job can use. At seven jobs uniqueness fails: exactly thirteen witnesses, classified - the Jansen-Land-Maack instance among them - and at eight jobs exactly 154. Three machines never suffice, at any size: four are necessary for the gap. Results of this shape are in print for the same relaxation in one-dimensional cutting stock, where the extremal non-round-up instances have been enumerated and classified for small demand; the Discussion sets out the relation. Recognizing witnesses at relaxation value 2 - where all of ours live - is coNP-complete, so no min-max characterization exists unless NP = coNP. Every feasibility decision behind the exhaustive claims was made twice, in floating point and in exact rational arithmetic, with full agreement, and the pipeline must rediscover I* before its negatives are believed.

Authors: Shimon Kogan, Merav Parter

A $d$-shortcut of a directed graph $G=(V,E)$ is a subset of edges drawn from the transitive closure $TC(G)$ whose addition reduces the graph diameter to at most $d$. In the special case $d=1$, computing a $1$-shortcut is \emph{equivalent} to computing the transitive closure. For larger values of $d$, a lower bound of [Hesse, SODA 2003] shows that $n^δ$-shortcuts, for small constants $δ>0$, may still contain a large fraction of the edges of $TC(G)$, suggesting that shortcut construction may remain as hard as transitive closure even in this regime. Consequently, since $\widetilde{O}(d)$-depth parallel reachability algorithms rely on computing $d$-shortcuts, achieving $\widetilde{O}(1)$ depth by this approach has so far required computing the full transitive closure. Assuming $ω=2$, the PS-AE-Triangle hypothesis of [Abboud, Bringmann, Fischer, and Künnemann, SODA 2024] yields a conditional $T^{4/3-o(1)}$ time barrier for computing transitive closure when $T\leq n^{3/2}$, where $T=|TC(G)|$. In this work, we bypass the transitive-closure barrier for $\widetilde{O}(1)$-depth parallel reachability. We introduce randomized $d$-shortcut constructions that already circumvent this barrier for $d=3$ and, more generally, for every even $d\geq4$ up to $O(\log n)$. Our approach yields a randomized $\widetilde{O}(1)$-depth parallel reachability algorithm with total work $\widetilde{O}(T^{ω/2})$, which becomes $\widetilde{O}(T)$ when $ω=2$, falling below this conditional $T^{4/3-o(1)}$ barrier throughout that regime. Under the current bound of $ω$, this gives $\widetilde{O}(T^{1.186})$ work, improving on the current $T^{1.3459+o(1)}$ sequential-time bound for transitive closure due to Abboud et al. Thus, although $\widetilde{O}(1)$-shortcuts might be almost as dense as the full transitive closure, they can nevertheless be computed substantially faster.

Authors: Dibyayan Chakraborty, Sandip Das, Sk Samim Islam, Ritam Manna Mitra, Saumya Sen

Given a simple, undirected, and unweighted graph $G$, and an integer $R$, the objective of the \textsc{Minimum Eccentricity Shortest Path (MESP)} is to decide whether there exists an \emph{isometric path} $P$ in $G$ such that the distance from every vertex in the graph to its nearest vertex in $P$ is at most $R$. In this paper, we prove that MESP admits an $O(n^4)$-time algorithm on $K_{2,3}$-minor-free graphs. Our algorithm has a cubic running time when the inputs are restricted to a cactus.

Authors: Aranya Kumar Bal, Sourav Chakraborty, Arijit Ghosh, Rudrayan Kundu

We consider estimation of non-integer frequency moments $F_k$ and related Bernstein-type statistics in the Delphic set stream model under a bounded-frequency assumption: every universe element appears at most $τ$ times. The main challenge of this model is to keep space low while also keeping update time low, which is not trivial because the sets can be exponential in size compared to their representations. Our core insight is that by sampling the stream at different rates and observing the resulting distinct-counts, we can 'probe' the frequency distribution and numerically integrate these probes to reconstruct a broad class of statistics. Building on that, we crucially observe that the distinct-count of a randomly sampled substream, viewed as a function of the sampling rate, is a single analytic object whose evaluations determine a broad class of statistics via a complementary Laplace-type integral. Algorithmically we exploit this by: 1. estimating those evaluations using only standard $F_0$ (distinct-count) algorithms on sampled substreams and 2. recovering target statistics by controlled numerical integration on a judiciously chosen grid. For $F_k$ with $k\in (0,1)$ we obtain the first one-pass streaming algorithms for Delphic set streams whose space and per-set update time are $\mathrm{poly}(\log|Ω|,\log m,\varepsilon^{-1},\log(1/δ))$ in the practically relevant regime $τ=\mathrm{polylog}(|Ω|,m)$; in general the bounds are polynomial in $τ$ and $\varepsilon^{-1}$ and logarithmic in $δ^{-1}$. We also give a complexity-theoretic barrier explaining why lower bounds for removing the bounded-frequency assumption appear difficult: ruling out polylogarithmic algorithms for unrestricted Delphic $F_k$ would imply a linear-space threshold-counting separation.

Authors: Pradeesha Ashok, Sobyasachi Chatterjee, Soumi Nandi, Saket Saurabh, Priyanshu Tiwari

The problem of computing \emph{diverse} solutions has recently emerged as an important area of study, motivated by applications in fairness, robustness, and security. Instead of returning a single feasible or optimal solution, the goal is to output a \emph{collection} of meaningfully different solutions, often measured by symmetric differences. Diverse variants have been studied using sparsification, network-flow reductions, and algebraic techniques. We investigate the fixed-parameter tractability of diverse variants of an implicit set-system problem. Given parameters $k$ and $r$ and a threshold $b$, the task is to compute $r$ feasible solutions, each of size at most $k$, whose diversity under a specified objective is at least $b$. Our main contribution is an oracle-based meta-theorem. We identify a broad class of objectives, called \emph{consistently diverse}, that includes several standard measures. Assuming an \emph{exact empty-extension oracle} given a forbidden set ${\sf Forb}$, which returns a feasible solution of a prescribed size avoiding ${\sf Forb}$ or reports that none exists, we obtain a fixed-parameter tractable algorithm parameterized by $k+r$. The algorithm makes at most $(2kr)^{kr} \cdot r$ oracle calls, and in each call the oracle parameter satisfies $s+|{\sf Forb}| \leq k+2kr$. Our framework unifies and strengthens previous oracle-based approaches. Compared with Kumabe's framework (ESA 2025), which gives a doubly exponential bound on the number of oracle calls, our approach achieves the single exponential bound $2^{O(kr\log(kr))}$ and directly constructs the desired tuple of solutions. We recover fixed-parameter tractable algorithms for all problems covered by that framework, with improved oracle complexity, and obtain strong bounds for diverse variants of classical graph and matroid problems.

Authors: Dante Bencivenga, Homa Habashi, Philipp Woelfel

We study the fundamental problem of implementing $m$ linearizable LL/SC objects with constant expected step complexity in a system of $n$ processes, using bounded base objects commonly available in hardware. Assuming that each process may have at most $τ$ outstanding LL operations, the best known deterministic algorithm requires $Ω(n^2τ+ m)$ base objects (CAS and registers) [Blelloch and Wei, DISC 2020]. Previously, no comparable randomized algorithm was known. By employing randomization and FADD in addition to CAS and registers, we obtain a space bound of $O(nτ+m)$ against the weak adaptive adversary. For $m=O(1)$ this matches a lower bound for algorithms using CAS and registers [Aghazadeh and Woelfel, PODC 2015]. In addition, our object can be employed by quiescently history-independent (QHI) algorithms: Whenever no operation on the object is pending and no process has an outstanding LL operation, its internal memory state is uniquely determined by the values of the $m$ LL/SC objects. An important application is a QHI dynamic hashing algorithm presented at STOC 2025, which uses $Θ(m)$ hardware LL/SC objects to maintain a hash table of size $m$ [Attiya, Bender, Farach-Colton, Oshman, and Schiller, STOC 2025]. But LL/SC is not available in hardware, and prior to our work no wait-free or efficiently lock-free software implementation of LL/SC with similar properties was known. Our work demonstrates that one can actually implement the hashing algorithm on available hardware, without an asymptotic increase in step and space complexity, under the reasonable assumption that $m=Ω(n)$.

Authors: Sam Hiken, Yael Kirkpatrick, Jakob Nogler, Virginia Vassilevska Williams

The sensitivity setting is a restricted setting for dynamic algorithms, particularly practical for scenarios where extensive preprocessing is feasible but responses to real-time modifications must be near-instantaneous before the data structure is eventually rebuilt. For graph problems, a sensitivity data structure is constructed with a preprocessing time P so that the following queries can be answered quickly, preferably in $O(1)$ time: given an edge $e$, return the answer to the problem on either $G \setminus e$ (decremental) or $G \cup e$ (incremental). In this paper, we almost entirely settle the decremental setting for the diameter and eccentricities problems in a variety of approximation regimes by matching P to the static runtime while supporting $O(1)$-time queries, thereby improving upon all previous results for a single failure [Bilò, Cohen, Friedrich, Schirneck, MFCS 2021; Bilò, Choudhary, Cohen, Friedrich, Krogmann, Schirneck, ICALP 2021]. More precisely: (1) We provide a tight reduction demonstrating that any exact distance sensitivity oracle can be used to efficiently solve decremental exact diameter and all-node eccentricities; (2) For the approximate setting, we match the runtime of all known static diameter algorithms across all sparsity settings, up to an additional $1+o(1)$ factor in approximation. Conversely, for the previously unexplored incremental setting of these problems: (3) We develop new lower bounds, demonstrating that no incremental algorithm can efficiently approximate diameter, radius, or eccentricity beyond a $5/3$ factor in undirected graphs or a $2$ factor in directed graphs; (4) We introduce two new instructive techniques and demonstrate how to utilize them to construct several new algorithms. Most notably, we develop incremental single-node eccentricity approximations for both directed and undirected graphs that match our new lower bounds.

Authors: Brian Bushnell

Cardinality estimation - counting the number of distinct elements in a data stream - requires a tradeoff between memory and accuracy. ExaLogLog recently established the state of the art for this tradeoff by combining wide registers with a Fisher-information-optimal maximum likelihood (ML) estimator, achieving the best known memory-variance product (MVP) among HyperLogLog variants. Here we present Arithmetic Variable LogLog (AVLL), which surpasses ExaLogLog at every memory point tested using arithmetic encoding and eliminating uncommon states to consume 64-bit words completely with 11 registers each, yielding a 5.5x register-count advantage. Its four-component blended estimator, HLDLC, exploits this density advantage to surpass ExaLogLog's ML accuracy without iterative solving. At 1 KB, AVLL achieves 1.63% width-weighted mean absolute error compared to ExaLogLog's 1.71% - a 4.7% improvement. The corresponding empirical MVP is 3.4, surpassing ExaLogLog's practical MVP of 3.78 and its theoretical optimum of 3.67. This holds at every tested size from 0.25 to 4 KB. AVLL inherits DynamicLogLog's early exit mechanism, which filters most elements before any register is touched. With thousands of simultaneous sketches per thread, AVLL is 2.7-4.5x faster than ExaLogLog due to the reduced memory bandwidth from early exits. Like DynamicLogLog, AVLL stores relative NLZ values with a shared offset, so its memory scales as O(B + log log C) rather than O(B x log log C) - decoupling maximum representable cardinality from register width. These results hold under both high-complexity (all-unique) and low-complexity (nonuniformly high duplication rate) data distributions, with zero accuracy degradation from duplication. AVLL is implemented as a single self-contained Java class with all correction formulas embedded, available in the BBTools suite at https://bbmap.org.

Authors: Rajarshi Bhattacharjee, Ethan N. Epperly, Cameron Musco, Aaron Tian

We describe a simple rejection-sampling-based algorithm to perform length-squared sampling on an $n \times n$ positive-semidefinite (psd) matrix: that is, to sample a column with probability proportional to its squared $\ell_2$-norm. The algorithm runs in just $O(n)$ expected time, which is significantly sublinear in the input matrix size. The runtime is optimal, even when the input is assumed to be diagonal. Our result has several applications. Length-squared sampling is used by a number of sublinear time algorithms for matrix problems, like low-rank approximation and eigenvalue approximation. Often, it is assumed that the algorithm is given access to the matrix column norms, and thus can perform length-squared sampling efficiently. Our result shows that, at least for psd matrices, we can remove this assumption. We also discuss an application to an asymptotically optimal algorithm for estimating the Frobenius norm of a psd matrix to relative error. Finally, we show that our sampling algorithm yields a very simple sublinear time algorithm for the robust psd low-rank approximation problem introduced by Bakshi et al. (FOCS, 2020), which nearly matches the more complex method developed there.

Authors: Antonios Hmadi

Let $v_1,\ldots,v_T\in B_2^m$ be fixed in advance and revealed sequentially, and assume that $\|v_t\|_\infty\leqslant d^{-1/2}$ for some $d\geqslant 1$ and every $1\leqslant t\leqslant T$. There are absolute constants $L,C,c>0$ and a randomized online signing such that $$\mathbb{P}\left\{\max_{k\leqslant T}\left\|\sum_{t=1}^k\varepsilon_t v_t\right\|_\infty>6L\right\} \leqslant CT\exp\left(-\frac{cd}{\ln^2(ed)}\right).$$ Consequently, constant prefix discrepancy holds with probability at least $1-\varepsilon$ once $d$ is at least $C\ln\frac{3T}{\varepsilon}\left[\ln\left(e+\ln\frac{3T}{\varepsilon}\right)\right]^2$. In particular, every fixed sequence of vectors $a_t\in[-1,1]^m$ with at most $d$ nonzero coordinates admits an online signing with prefix discrepancy $O(\sqrt d)$ and failure probability at most $CT\exp[-cd/\ln^2(ed)]$. We also prove a nonuniform version in which the failure probability depends on the individual parameters $d_t=\|v_t\|_\infty^{-2}$, and a lower bound showing that a universal constant prefix discrepancy is impossible when $d=o(\ln T)$. We identify the corresponding $\ln^2 d$ barrier for the compact-potential method and extend the argument to general symmetric target bodies admitting a quadratic smoothness estimate.

Through a personal connection, my paternal grandfather was told to go on a plane to escape the start of World War II in Italy. He was told to go just like that, without bringing anything, and so he flew to Spain with his family: his wife and daughter. He was an academic himself and was arranged to have a position in an Italian institute. And so my father was born in Madrid in 1946. After that, he lived in Paris, where he attended French school, Venice, and Athens, before finally moving to Rome. My grandfather died when my father was very young and was buried in the Lido cemetery in Venice. Unfortunately, his tomb is apparently no longer.

Traveling continued to be a main feature of my father’s life. He went to Soviet Russia. He rode a yak in Tibet. He went to India. He went to Syria before the start of the recent civil war. He went to Africa. He went to Iceland and countless other places. For a period, he did back-and-forth between New York and Rome, traveling, I think, at least once a month, where he was organizing various exhibitions. He was twice a fellow at the Getty foundation. During his lifetime, he was fluent in four languages: Italian, French, Greek, and English.

He was the humanities scholar par excellence, a living encyclopedia who could talk about anything and wrote about everything: from the Columbus expedition to a guide of Rome to avant-garde movements.  Online, you can find a list of his more well-known publications, which give a sense of his breadth. He could enter a museum or a Church and talk about any painting, see any statue and tell you the story behind. I particularly remember his jokes, which always had a philosophical bent. He was also involved with exhibitions on fractals and modern logics, whose proceedings naturally piqued my interests more than others.  I feel sorry that all this knowledge now must be gone forever. Here he is delivering one of his last lectures, just few months before passing away:

He was always with a book in his hands, always writing. Something which seems to have transmitted to me. At a later stage of my life, I’ve also become interested in history and started devouring books to tile the vast unknown with which I had emerged from school, at times following his suggestions.

Sadly, I really didn’t have a relationship with him, which I think was a major loss for me and perhaps also for him.

Here is us on the Dolomites in 2009. You’ll see how he’s stepping back to lower his height to match mine, a habit he had acquired.

Here he is in Boston with my wife, a few years earlier:

My father also loved good dining. Its one of the things he really did not compromise about. Here he is enjoying a meal by Lake Trasimeno with my mom, whom he was married to since 1970. They got married in the church of the artists, opened just for them thanks to a church friend. He insisted on having the ritual performed in Latin, just to give you a sense of the man.

He was about 2 m tall (6.5 ft) and weighed about 100 kg (200 lbs) and gave the impression of a mountain of energy. I always envied his ability to process lots of food and still function, as well as withstand extreme temperatures, all wearing a suit.

He continued to travel and enjoy fine dining, study and write until the end, despite mobility issues. In the end, he wasn’t in the best of health. Still, it seems he could have lived a little longer. Instead, he met a doctor who was the type of person I described earlier in this blog as a liable person. The doctor didn’t care about his condition, just noticed that it required hospitalization according to the protocol. They didn’t care if my father’s body could withstand that. It couldn’t, and unfortunately I was not there when he passed away.

However, I went to visit him in Rome just a few months before he did. I hadn’t been back in maybe 15 years. Here is us at our last encounter, with my sister.

Ciao Papi

By Manu

Authors: Vaneet Aggarwal

We study nonnegative submodular maximization subject to a general matroid when the offline algorithm is given an arbitrary controlled value oracle. Our main result is an adversarial resilience theorem for the Spiteful Greedy Swap Poisson Process (SGS-Poisson): without modifying its Poisson intensity, single-element exchange rule, or spiteful drop step, the algorithm retains limiting approximation factors $1/e$ for non-monotone objectives and $1-1/e$ for monotone objectives. More precisely, under every controlled oracle $\widehat f$ satisfying $|\widehat f(S)-f(S)|\le ξ$ for every set $S$, our implementation returns a feasible set with expected value at least $(1/e-\varepsilon)\OPT-O(kξ)$ and $(1-1/e-\varepsilon)\OPT-O(kξ)$, respectively, using $\widetilde O(nk^2\varepsilon^{-2})$ oracle calls. As a consequence, the offline-to-online reduction yields full-bandit CMAB algorithms for general matroid-constrained submodular rewards with exact limiting approximation-regret factors $1/e$ and $1-1/e$ and $\widetilde O(n^{1/5}k^{4/5}T^{4/5})$ regret.

Authors: Stuart Hadfield

Evaluating expectation values is a critical task for variational quantum eigensolvers, and for parameterized quantum circuits and other quantum algorithms more generally. We consider the well-studied case of the Quantum Approximate Optimization Algorithm (QAOA) for the MaxCut problem. Recent work of Wang et al. [arXiv:2511.20212] showed this task to be NP-hard in general for any QAOA depth $p\geq 2$, complementing past results showing efficiently computable formulas for $p=1$ with arbitrary problem graphs. We sharpen this dichotomy showing that for $p\geq 2$ exact or exponentially precise cost expectation value evaluation is #P-hard under deterministic polynomial-time Turing reductions. Hardness at $p\geq 2$ is shown to remain even for evaluating single pairwise correlators $\langle Z\otimes Z\rangle $, as well as for highly restricted sets of algorithm parameters. Our proof refines the NP-hardness construction of Wang et al. that recovers the maximum cut value from the largest exponent of a QAOA Laurent polynomial, utilizing a distinct and simpler construction that extracts a value proportional to the total number of maximum cuts, in addition to the optimal cut value. Thus we show that the QAOA expectation value hardness transition from $p=1$ to $p=2$ is not only from tractability to optimization hardness, but to that of counting optimal solutions. As an application we show our results imply analogous hardness results for computing gradients and Hessians of QAOA circuits.

Authors: Saptarshi Biswas, James I. Lathrop, Rana D. Parshad

The computability of real numbers and functions using Turing Machines has been a central area of theoretical computer science since the mid-20th century. In the late 20th century, it was shown that chemical reactions can serve as a basis for computation using the Chemical Reaction Network (CRN) model. Recent advances in computing real numbers using Deterministic Chemical Reaction Networks (DCRNs) have identified numerous classes of DCRN-computable real numbers. In parallel, the works of R. Landauer and C. H. Bennett, spanning the 1960s to the early 2000s, showed that reversible computing offers significant advantages over irreversible methods, particularly in energy efficiency, motivating extensive research on reversible computation. In this work, we investigate the computability of real numbers using Reversible Chemical Reaction Networks (RevCRNs). The paper has two primary contributions: (1) establishing relationships among CRN-computable real number classes including Lyapunov CRN ($\mathbb{R}_{LCRN}$), Real-Time CRN ($\mathbb{R}_{RTCRN}$), rational numbers ($\mathbb{Q}$), and RevCRNs ($\mathbb{R}_{RevCRN}$), with key results: (i) $\mathbb{Q}$ is a strict subset of $\mathbb{R}_{RevCRN}$; (ii) the set of positive algebraic numbers ($ALG$), $\mathbb{R}_{LCRN}$, and real numbers computable by 1-species RevCRN ($\mathbb{R}_{RevCRN}^{1s}$) are equal; (iii) $\mathbb{R}_{RTCRN}$ and $\mathbb{R}_{RevCRN}$ exhibit non-empty overlap; and (iv) the set of real numbers computable by detailed-balanced RevCRNs ($\mathbb{R}^{DetBal}_{RevCRN}$) is a subset of $ALG$; and (2) exploring the existence of a hierarchy within $\mathbb{R}_{RevCRN}$. Finally, we leave open the exact relationship between $\mathbb{R}_{RevCRN}$ and $\mathbb{R}_{RTCRN}$ while conjecturing a general hierarchy of RevCRN-computable reals.

Authors: Yuval Filmus, Anqi Li, Dor Minzer

A classical theorem due to Friedgut, Kalai and Naor asserts that if a function $f\colon \{0,1\}^n\to\{-1,1\}$ close to a degree $1$ function, then either $f$ or $-f$ is close to either the all $1$ function, or to $(-1)^{x_i}$ for some $i\in [n]$. We prove a version of their theorem for the Grassmann scheme over $\mathbb{F}_2$. More precisely, we prove if a function $f\colon \genfrac{[}{]}{0pt}{}{\mathbb{F}_2^n}{\ell}\to\{0,1\}$ is close to a degree $1$ function, then either $f$ or $1-f$ must be close to a function of the form $g(L) = \sum_{x\in\mathcal{X}}1_{x\in L}+\sum_{W\in\mathcal{W}}1_{L\subseteq W}$, where $\mathcal{X}\subseteq\mathbb{F}_2^n$ is a set of points and $\mathcal{W}$ is a set of hyperplanes in $\mathbb{F}_2^n$.

Authors: Tanner Finken, Jixian Li, Bei Wang, Hanqi Guo, Joshua A. Levine

Topological analysis of scalar fields yields structures such as the Morse-Smale complex (MSC) that summarize salient features across multiple scales. Existing MSC extraction algorithms typically assume an explicit representation of the input field, such as a discretely sampled mesh. However, recent advances in visualization have popularized implicit field representations, for which these assumptions no longer hold. In this work, we address the problem of extracting an MSC from an implicitly defined 2D scalar field. We present a method for constructing a triangulated piecewise-linear (PL) mesh that aims to preserve the critical points of an underlying implicit scalar field. Our central insight is that if all edges are monotonic with respect to the underlying field, then the resulting PL approximation is topologically consistent with respect to critical points. Based on this insight, we introduce a refinement procedure that mitigates monotonicity violations. Requiring only pointwise evaluations and modest mesh refinement, the approach produces PL meshes that are correct with regards to critical points in our experiments. Finally, we demonstrate that additional targeted refinement improves the geometric fidelity of MSC separatrices.

Authors: John Rick Manzanares, Jay-Anne Bulauan

We introduce Probabilistic Ball Mapper, a formulation of Ball Mapper in which each data point is assigned a probability distribution supported only on the metric balls that contain it. This assignment defines both a partition subordinate to the Ball Mapper cover and a Markov kernel from the finite data space to the cover. We study two assignment schemes: a uniform-on-support rule and a localized radial-basis rule that incorporates distance to landmarks while preserving the underlying cover. Pushing the empirical data distribution through the kernel produces a probability distribution over vertices. Drawing twice, conditionally and independently, from each pointwise distribution produces a soft-overlap matrix. This matrix is symmetric, nonnegative, positive semidefinite, and has the vertex distribution as both marginals. It therefore provides a mass-normalized refinement of classical Ball Mapper overlap rather than another unnormalized edge count. For graphs constructed on a common cover, the vertex and overlap distributions can be compared directly. For independently fitted covers, we formulate Wasserstein and fused Gromov--Wasserstein-type discrepancies that account for vertex mass, landmark geometry when a common ambient metric is available, and intrinsic graph relations. For a fixed cover, we derive explicit perturbation bounds controlled by the sensitivity of the assignment rule, the magnitude of the data perturbation, and the data mass near cover boundaries. When the cover is recomputed, landmark motion creates an additional source of variation, for which we state a transport-based stability principle rather than an unconditional theorem. The resulting framework turns Ball Mapper into a probability-valued representation suitable for quantitative comparison while retaining its geometric interpretability and computational simplicity.

Authors: Bogumil Kaminski, Pawel Pralat, Maria Sadza

This paper investigates a multi-robot search-and-visit problem involving $n$ robots starting at the origin and $k$ unknown treasures hidden on the unit circle $\mathcal{C}$. The robots move independently anywhere in the plane with a maximum speed of 1 and instantly share discovery information. The goal is to determine an algorithm that minimizes the total time needed for all robots to individually visit every treasure. To establish the foundational limits of this task, we first solve an auxiliary optimal routing problem for a single robot on $\mathcal{C}$ that possesses complete prior knowledge of the treasure locations. The exact analysis of this auxiliary problem yields explicit upper and lower bounds for the original search problem.

Authors: Andrew McGregor

We present a slightly simplified analysis of the asymmetric palette sparsification result by Assadi and Yazdanyar [TheoretiCS, 2026]. The motivation is mainly pedagogical; our approach avoids hypergeometric concentration bounds and extra constant factors in the palette size.

Authors: Anubhav Dhar, Anita Dürr, Ahmed Ghazy, Jakob Greilhuber, Karol Węgrzycki

Minimizing the weighted completion times ($P \mid \mid Σw_j C_j$) and weighted number of tardy jobs ($P \mid \mid Σw_j U_j$) on multiple identical machines are two classical NP-hard scheduling problems. As shown by Lenté et al. (2014), both problems can be solved in time ${O}^{\star}(3^n)$. In this paper, we improve these bounds to ${O}(2.755^n)$ and ${O}^{\star}(2^n)$, respectively. Our algorithm for $P \mid \mid Σw_j C_j$ exploits the meet-in-the-middle paradigm and an efficient data structure answering linear programming queries. Additionally, when the number of machines is at most $6$, we show that the running time for $P \mid \mid Σw_j C_j$ can further be improved. Both scheduling problems are generalizations of the classical Bin Packing problem, which can be solved in ${O}^{\star}(2^n)$ time. Improving this running time is an important open question. We show that, when assuming the Asymptotic Rank Conjecture (ARC), Bin Packing can be solved in time ${O}((2-\varepsilon)^n)$ for some $\varepsilon >0$. Our algorithm makes use of two main ingredients: the recent ${O}((2-\varepsilon)^n)$-time algorithm of Nederlof et al. [SICOMP'23] for Bin Packing when the number of bins is a fixed constant, and the ${O}((2-\varepsilon)^n)$-time algorithm of Björklund et al. [SODA'25] for special instances of the $3$-way Partitioning problem when assuming ARC.

Authors: Bo Peng, Zhihao Gavin Tang

We study edge-weighted oblivious bipartite matching. The weight of every potential edge is known, but its existence is revealed only when the edge is probed, and a successful probe between two free vertices must be accepted immediately. We give an explicit randomized algorithm with certified competitive ratio $0.698$, improving the previous best guarantee of $0.659$ (Huang, Sun, Wu, and Zhao, FOCS 2025). The result is computer-assisted and verified by a reproducible exact-integer computation. The same algorithm has a $0.698$-competitive online implementation for the vertex-weighted random-arrival model, improving the previous $0.696$ unweighted guarantee of Mahdian and Yan (STOC 2011) and the $0.686$ vertex-weighted guarantee of Peng and Tang (EC 2025). Our algorithm, Harmonic Ranking, is a role-symmetric generalization of \textsc{Ranking}. It assigns an independent random rank $x_z$ to each vertex and probes a potential edge $uv$ in decreasing order of \[ w_{uv}\frac{h(x_u)h(x_v)}{h(x_u)+h(x_v)}. \] This harmonic priority arises from a budget-balanced gain split and a mutual-proposal interpretation. The analysis lifts two cutoff curves into indicators, reducing the exponential-size factor-revealing problem to a polynomial-size directed minimum-cut instance. A maximum-flow computation with rounded-down integer capacities gives a rigorous certificate. Independently, we observe that the finite-grid unweighted relaxation of our factor-revealing program coincides exactly with a Mahdian--Yan program.

Authors: Adam Karczmarz, Paweł Pilarski

We study the maximum flow problem in directed networks with real capacities in the parallel setting. For a network with $n$ vertices and $m$ arcs, we show that a randomized parallel implementation of a variant of the strongly polynomial max-flow algorithm of Dadush, Orlin, Sidford, and Végh [SODA 2026] runs in $\tilde{O}(mn)$ work and $\tilde{O}(m)$ depth. This improves upon the previously described tradeoffs between work and depth for strongly polynomial parallel maximum flow algorithms: earlier $\tilde{O}(n^3)$-work algorithms have $\tilde{O}(n^2)$ depth [Shiloach and Vishkin, J. Algorithms 1982; Goldberg and Tarjan, J. ACM 1988], while the known $\tilde{O}(m)$-depth approach uses $\tilde{O}(mn^3)$ work [Orlin, Oper. Res. 1993].

Authors: Keramat Hasani, Frank Werner

This paper investigates a parallel machine scheduling problem featuring a single common server responsible for both loading and unloading operations. Each job consists of a unit-time loading operation, non-preemptive processing on one of \(m\) identical machines, and a unit-time unloading operation executed by the same server. The objective is to minimize the makespan. Unlike classical loading-only common-server models, our setting requires the server to handle an unloading operation immediately after a job's processing phase concludes. We prove that the corresponding decision problem is strongly NP-complete when the number of machines is given as part of the input. Furthermore, we analyse the worst-case performance of the List Scheduling (LS) and Longest Processing Time (LPT) heuristics. For three machines, we establish that Algorithm LS achieves an approximation ratio of at most \(5/2\). For an arbitrary fixed \(m \ge 3\), we show that the general LS bound approaches \(4-3/m\) as the number of jobs grows, whereas for Algorithm LPT, we prove the finite-instance ratio $3-\frac{2}{m}+\frac{(m-1)(m-2)}{mn}.$ Thus, for each fixed \(m\), the LPT bound approaches \(3-2/m\) as the number of jobs grows.

Authors: Tao Jiang, Minbo Gao, Shaowei Cai

Sign-nonsingularity asks whether every real matrix with prescribed entry signs is nonsingular. Polynomial-time algorithms recognize square sign-nonsingular patterns through their connection with even directed cycles, but recognition does not itself produce an exact numerical witness in the negative case. We give a deterministic polynomial-time algorithm that, for any square sign pattern $A$, either reports that $A$ is sign-nonsingular or outputs $B\in\mathbb{Z}^{n\times n}$ and $z\in\mathbb{Z}^n\setminus\{0\}$ such that $\operatorname{sgn}(B)=A$ and $Bz=0$. After normalizing a perfect matching, an even directed cycle yields two determinant terms of opposite signs. Making either term dominant produces endpoint realizations with opposite determinant signs. Changing their magnitudes one coordinate at a time exposes an affine sign-changing step, whose zero is rational; clearing its denominator gives the integer witness. Entries of $B$ have $O(n^2\log n)$ bits, and entries of $z$ have $O(n^3\log n)$ bits. The result settles Conjecture 14.12.4 in the Handbook of Satisfiability.

Authors: Nader H. Bshouty

We give a lower bound for randomized non-adaptive group testing when the goal is to find any $\ell$ defective items but the total number $d$ of defectives is unknown. Bshouty and Haddad-Zaknoon proved an upper bound of $O(\ell\log^2 n)$ tests and a lower bound of $$Ω\!\left(\frac{\ell\log^2 n}{\log \ell+\log\log n}\right).$$ We prove the matching lower bound. More generally, we show that every randomized non-adaptive algorithm that succeeds with constant probability for every defective set must use $$Ω\!\left(\ell\log^2(n/\ell)\right)$$ tests. The proof is as follows. At a fixed value of $d$, finding $\ell$ defectives requires about $\ell\log(n/d)$ bits of information. On the other hand, one fixed group test is informative only when its size is tuned to the scale of $d$; across all logarithmic scales of $d$, a single test contributes only $O(1)$ bits. Summing over all scales gives the lower bound. We also record the matching upper bound $$O\!\left(\ell\log^2(n/\ell)\right),$$ obtained by running the known-$d$ algorithm in parallel over dyadic guesses for $d$. Thus the randomized non-adaptive complexity of unknown-$d$ partial detection is $Θ\!\left(\ell\log^2(n/\ell)\right)$ for constant success probability.

Authors: Xavier Coiteux-Roy, Maxime Flin, Carlos de Gois, Marc-Olivier Renou, Jukka Suomela, Isadora Veeren

We prove that any distributed quantum algorithm that finds a $3$-coloring with probability $1$ in a cycle of anonymous identical computers has to be global, that is, it needs $Ω(n)$ communication rounds. It follows that quantum computation and communication does not help with this problem. All prior lower bounds on quantum advantage in distributed graph algorithms use arguments related to physical causality. However, it is known that such arguments cannot rule out fast quantum advantage for $3$-coloring cycles. In particular, any causality-based argument would rule out the existence of finitely dependent coloring, but Holroyd and Liggett (2016) showed that such colorings do exist. Hence to tackle this problem, we need a ``genuinely quantum'' lower-bound technique that can distinguish between (1) distributions that do not violate physical causality vs. (2) distributions that can be realized with a quantum strategy. We present the first such lower-bound technique in this context. First, we show that $1$-round quantum algorithms cannot break symmetry with probability $1$. Second, we present a wishful teleportation strategy that can be used to turn $T$-round quantum 3-coloring algorithms into $1$-round quantum algorithms breaking symmetry, while preserving success probability $1$. Put together, the lower bound follows.