Theory of Computing Report

The Theory Group in the Department of Computing Science at University of Alberta invites applications for a one-year (with the possibility of extension) postdoctoral fellowship position. The successful applicant is expected to work closely with Mohammad Salavatipour and Zachary Friggstad and their students in the areas of approximation algorithms for combinatorial optimization problems.

Website: https://friggstad.github.io/pdf_advertisement_2026.pdf
Email: zacharyf@ualberta.ca

By shacharlovett

I applaud Jensen Huang and industry leaders for coming out in support of open large language models. The entire tech sector minus Anthropic has now signed on. Now that the movement has momentum, I urge the signatories to endorse something even more radical that would truly separate us in our economic competition with China: The USA should heavily invest in models not just with open weights, but with open source and open corpus.

Let me back up in case you missed it. Last Friday, Huang pasted a short letter on Twitter calling for American investment in “a strong, open ecosystem” around open source artificial intelligence. “Open source…created a shared foundation of knowledge on which generations of American engineers and entrepreneurs built their institutional sovereignty,” Huang predicts that a similar thing will happen with the embrace of open source AI.

Part of this letter was a plea to the Trump administration, which had been sending signals about banning open source software in a protectionist move to squash insurgent Chinese language machines. Seeing that this would benefit Anthropic and OpenAI and no one else, the CEOs of all of the big and small tech firms quickly signed on to Huang’s letter on Friday.

This is an amazing, positive development, and I want to air some points that Huang left out. I’ve been passionately calling for a deeper investment in open source language models on this blog for years. In fact, this post from last July makes a bunch of points about what I think is necessary for this to happen, and I don’t think any of it has changed.

You should go read that post, but let me summarize what I said for the present moment. What is needed to build a good language model is people, compute, and data. It’s not clear how much of each of these you need, but the answer seems to be a lot. We’ve always had the people, though the promise of impossible riches has lured many smart young minds away from more ethical paths. But now that we have the backing of the entire tech industry, I think this base is covered.

What about compute? Hyperscalers and their economic bedfellows always want you to believe that their massive datacenter buildout is a moat from us open source plebes. But the Chinese models have complicated this story and shown you can get by on the cheap. No one has precise estimates, but models from Chinese companies DeepSeek and Moonshot were arguably trained using under ten million dollars. Dozens of AI startup “NeoLabs” with few concrete ideas are currently being given 10x that by venture firms. Good VCs could make a small bet on the open ecosystem to juice their other investments. Compute for open models will require a massive industrial consortium, but it would cost each member of the consortium a minuscule fraction of their war chests. Let’s work together to build computing agreements for open source development.

Once these models are built out in the open, there is no doubt that they will only get dramatically more efficient. We’ve seen time and time again that machine learning is a field that innovates through “frictionless reproducibility.” Research, code, and data out in the open, evaluated by competitive benchmarking, rapidly improve machine learning systems. It also makes them more efficient. In last year’s post, I wrote about how high-quality ImageNet models went from something only trainable at Google to something you could build on a desktop in less than a year. These sorts of efficiency gains happened throughout the 2010s. The secrecy of labs in the 2020s has harmed the broader engineering field, even though the artifacts produced have been beyond impressive. Put everything out in the open, and we’ll figure out how to make it faster and more efficient. It’s guaranteed.

That brings us to the actual hard part. The data. As my friend and colleague Alyosha Efros loves to remind us, “It’s all about the data,” and language models are trained on unfathomable amounts of it. Discovery in lawsuits has revealed that companies trained these models on pirated libraries of books, academic papers, and copyrighted imagery. The models are trained on collaborative knowledge bases like Wikipedia, countless volunteer forums like Reddit, and all of the public code on GitHub. They are trained on the transcript of every video you post to YouTube. All of this collective work by human society gets slurried into proprietary software so a few zealots can get rich. This is a bad outcome!

The companies are all up front about this use. They have been found liable in court. They have admitted it in papers they have written. They claim this is all fair use because the training was transformative of the texts. Fine, if that’s the case, then it’s fair use to take the outputs of their models and build new ones. This is called “distillation.” Chatbot terms of service agreements do not negate my argument. That the Trump administration is flirting with banning distillation is a travesty.

But I want something bigger. The biggest step to making competitive open source models is allowing the broader community fair use access to the same material the companies used. This is the open corpus. If closed models can exist, then open models should be allowed a level playing field. This will require a long overdue rethinking of intellectual property and what we owe the people who create it.

I think all of these challenges are surmountable. We’re going to have to (a) get young people to care about open source instead of becoming impossibly rich. (b) get billionaires to collaborate in a non-winner-take-all fashion, and (c) have a long hard conversation about copyright law, intellectual property, and fair use standards. But we’ve thrived in an open ecosystem before ChatGPT. It hasn’t even been half a decade of closedness. With the blessing of the entire tech industry, it’s time to open things up again.

Subscribe now

The title of this post is a coinage of Kevin Kelly. His dedication also inspired me to write this post.

By Ben Recht

Authors: Papangkorn Apinyanon

We prove that the solution-search problem for the pencil puzzle Ice Walk is ASP-complete. Our reduction maps Hamiltonian cycles in an undirected maximum-degree-3 spanning subgraph of a rectangular grid graph bijectively to Ice Walk solutions.

Authors: Aparna Gupte, Seyoon Ragavan

We show that under a plausible number-theoretic conjecture, for any constant $s$ there exists an $s$-server private information retrieval (PIR) protocol that on an $n$-bit database requires communication $\exp(O((\log n)^{1/s} (\log \log n)^{1-1/s}))$. Previous constructions attaining the same communication required $2^{O(s)}$ servers. Our number-theoretic conjecture is implied by existing conjectures, namely the generalized repunit conjecture and Schinzel's hypothesis H (either one of these conjectures would suffice alone). Our result builds on the ``matching vector family + $S$-decoding polynomials'' framework pioneered by Efremenko (STOC 2009) and recently refined by Ghasemi, Kopparty, and Sudan (STOC 2025). The main ingredient is a framework for constructing $S$-decoding polynomials with only $k+1$ nonzero coefficients modulo special products of $k$ primes, resolving an open problem posed by Ghasemi and Kopparty (ITCS 2026). By the lower bound shown by Ghasemi and Kopparty, this is the minimum achievable sparsity. We also empirically validate our construction and make our result unconditional for all $s \leq 15$. We also apply our techniques to regimes where $s$ grows with $n$, showing under a stronger variant of our number-theoretic conjecture that the communication complexity of $s$-server matching-vector PIR can be superpolynomially reduced from the previous state of the art for any $s \leq \exp(o(\sqrt{\log \log n/\log \log \log n}))$. The main result for $s = O(1)$ and its proof were discovered in a GPT-5.5 Pro conversation prompted by the authors.

Authors: MingZe Sun, Haiyong Jiang, Bingchen Yang, Haoxuan Song, Yidi Li, Jun Xiao, Peter Wonka

Boundary representation (B-rep) is the standard format for computer-aided design (CAD). This article proposes a lightweight two-stage diffusion-based B-rep generation framework, TG-Diff, that achieves efficient, high-quality B-rep generation by decoupling topology and geometric modeling. In contrast to previous work that generates topology as a collection of vertices, edges, and surfaces together with their relationships, TG-Diff represents topology only as a collection of surfaces and their adjacency relationships. This surface-centric representation inherently alleviates the geometric and topological inconsistencies between separately generated surfaces, edges, and vertices, simplifying the generation process. Based on the surface-centric representation, we develop two independent diffusion models that generate surface adjacency relationships and surface latents, respectively. By using topology as guidance, the surface generation process becomes more stable, leading to stronger structural completeness in the generated B-rep models. The topology diffusion model adopts a Discrete Diffusion Model (D3PM) for efficient binary sampling, avoiding the slow inference of autoregressive methods. Surface latent generation employs a conditional latent diffusion model with a lightweight DiT architecture, where surface adjacency guides geometry generation while reducing computational cost. Finally, edges and vertices are derived from the decoded adjacent surfaces via post-processing to form a final watertight B-rep. Despite its compact computational footprint (82.18M parameters and 2.2 GFLOPs), TG-Diff excels in the validity metric while achieving superior performance on all COV, MMD, and JSD metrics across the DeepCAD and ABC datasets.

Authors: Anders Aamand, Mikkel Abrahamsen, Simon Bartlmae, Arindam Khan, Linda Kleist, Csaba D. Tóth

We consider the problem of online packing of convex polygons into a strip by translations. While online algorithms with a constant competitive ratio have been known for rectangles for decades [Baker and Schwarz, SICOMP 1983], the current best algorithm for convex polygons has competitive ratio $O(n^{\log_2 3-1}\log n) = O(n^{0.59})$, where $n$ is the number of polygons. This algorithm was described by Aamand, Abrahamsen, Beretta, and Kleist [SODA 2023], who also proved a lower bound of $Ω(\sqrt{\log n/\log\log n})$ on the competitive ratio of any algorithm. Their lower bound is obtained via a reduction from \emph{online sorting}, a problem introduced in the same paper, for which they established a lower bound on the competitive ratio. We introduce a new, natural online problem that we call online TSP scheduling. Here, points $x_1,\ldots,x_n$ arrive online from a metric space $(M,d)$, and upon arrival each $x_i$ must be assigned a visit time $p_i\in[0,\infty)$ satisfying $|p_i-p_j|\ge d(x_i,x_j)$ for all $j

Authors: Junye Ji

We formalize in Lean 4 the Kannan-Bachem Smith normal form algorithm for nonsingular square integer matrices. The program returns $S,U,U^{-1},V,V^{-1}$ and proves $UAV=S$, $U^{-1}SV^{-1}=A$, four inverse identities, the Smith divisibility conditions, and equality of $S$ with a canonical reference matrix. Stabilization terminates because each recursive pass strictly decreases the binary size of the active pivot; the outer algorithm recurses on the lower-right block. The computation also emits a flat trace of designated sign-magnitude arithmetic leaves. Branch conditions, quotients, Bezout data, and matrix entries are taken from the recorded primitive runs. Composite phases form their traces by concatenating the charge lists returned by the executed children. Verified self-delimiting codecs define the input and output sizes. Coefficient and work recurrences, closed by a kernel-checked polynomial-envelope calculus, give fixed polynomial bounds for both trace cost and the encoded length of the five output matrices. The theorem concerns these arithmetic primitives; structural operations and compiled Lean runtime are outside the model.

Authors: Bo Peng, Zhihao Gavin Tang

We study online metric facility location in the random-order model with arbitrary positive opening costs. A finite set of candidate facilities and their costs is known in advance, while an adversary fixes a multiset of demand points that arrives in a uniformly random order. This setting includes both prescribed candidate sites and the classical finite full-space node-cost model. For a known horizon, we give a deterministic $4.2674$-competitive algorithm, improving the previous factor $33$ for nonuniform opening costs. At rank $t$, the algorithm uses the positive normalized rank $q_t=t/n$, chooses a candidate minimizing $d(x,y)+λ_t f_y$, where $λ_t=\min\{1,q_t/μ\}$, and opens it when the current connection distance covers this penalized objective. The analysis uses a monotone one-round charge and an upper-envelope decomposition to control later points and the first point of each optimal cluster. With unit opening costs, the rule reduces exactly to a cutoff on the distance improvement attainable from a nearest candidate. A supplementary appendix gives the sharper analysis of the closely related zero-start rank cutoff and obtains a ratio below $3.2805$. We also prove a $3-o(1)$ lower bound for arbitrary randomized online algorithms. The lower bound already holds with uniform costs on a prescribed candidate set and transfers, without loss, to the finite full-space model with nonuniform opening costs. Together with the recent competitive ratio below $2.42$ for full-space uniform costs, this yields a strict separation between the full-space uniform- and nonuniform-cost models.

Authors: Bartłomiej Bosek, Wojciech Nadara, Michał Pilipczuk, Anna Zych-Pawlewicz

Let $\mathscr{C}$ be a class of graphs of bounded expansion and $r,k\in \mathbb{N}$ be fixed. We give a dynamic data structure that for a given dynamic graph $G$, updated by edge insertions and deletions subject to the promise that $G\in \mathscr{C}$ at all times, maintains the answer to the following two queries: (a) Does $G$ contain a distance-$r$ dominating set of size $k$? (b) Does $G$ contain a distance-$r$ independent set of size $k$? The data structure is randomized with error probability bounded by $\varepsilon$, for a parameter $\varepsilon>0$ fixed upon the initialization. The amortized update time is $\log^c n\cdot \log \frac{1}{\varepsilon}$, where $n$ is the vertex count of $G$ and $c$ is a constant that depends only on $r$, $k$, and $\mathscr{C}$. In the case of the first query, the data structure can also output a distance-$r$ dominating set of size $k$, if existent. We also prove that when $r=1$, our data structure for the dominating set query can be implemented even if we only assume that the maintained graph $G$ has degeneracy bounded by a constant $d$, yielding a simpler data structure with an improved amortized update time of $2^{k^{{\cal O}(d)}}\cdot \log^3 n\cdot \log \frac{1}{\varepsilon}$. Finally, we prove that in graphs of degeneracy at most $d$, one can maintain an ${\cal O}(d^2)$-approximation of the minimum size of a (distance-$1$) dominating set with amortized expected update time $d^{{\cal O}(1)}\cdot \log n$.

Authors: Justin Dallant

Given an $n\times n$ matrix $A$, a saddlepoint of $A$ is an entry that is the maximum in its row and the minimum in its column. It is a strict saddlepoint if no other entry in its row or column has the same value. Finding a non-strict saddlepoint requires $Θ(n^2)$ matrix queries in the worst case. In contrast, a strict saddlepoint can be found with only $O(n)$ queries. In 1991, Bienstock, Chung, Fredman, Schäffer, Shor, and Suri---and, independently, Byrne and Vaserstein---showed that one can find a strict saddlepoint (or certify that none exists) in $O(n\log n)$ time using $O(n)$ matrix queries. In 2024, Dallant, Haagensen, Jacob, Kozma, and Wild gave an $O(n\log^* n)$-time algorithm, followed shortly after by an optimal randomized algorithm running in $O(n)$ time with high probability. Whether $O(n)$ time could also be achieved deterministically was left open by these works. Here we resolve this question by presenting a simple deterministic algorithm that finds a strict saddlepoint, or reports that none exists, in optimal $O(n)$ time. Our algorithm combines elementary ingredients from previous approaches with linear-time selection from a collection of sorted lists.

Authors: Klaus Heeger, Danny Hermelin, Dvir Shabtay

We study the single-machine scheduling problem with controllable processing times to minimize the total weighted completion time, focusing on the setting where a job's processing time is a convex function of its allocated continuous resource. The computational complexity of this problem represents a long-standing open question, as it is currently neither known to be polynomial-time solvable nor NP-hard. While we do not fully resolve this complexity question, we provide several insights into the problem's approximability. On the positive side, we present a polynomial-time $e \le 2.719$-approximation algorithm, alongside a quasi-polynomial approximation scheme for instances where the largest parameter value is polynomially bounded by the instance size. On the negative side, we demonstrate that simple sorting rules, which are optimal for certain special cases in the literature, cannot guarantee a constant-factor approximation for the general case.

Authors: Katrin Casel, Archontia C. Giannopoulou, Aikaterini Niklanovits

We focus on two variants of graph partitioning problems, connected partition and dense partition. Formally, given a graph $G=(V,E)$ and a partition of its vertices $\mathcal P=\{P_1,\ldots, P_k\}$ we say that $\mathcal P$ is a connected partition of $G$ if each $P_i$ induces a connected graph in $G$. Many classical variants of this problem impose additional restrictions both on the number of parts as well as on the size of each part. Moreover, given a partition $\mathcal P=\{P_1,\ldots, P_k\}$ we define its density by $d(\mathcal P):=\sum_{i=1}^k |E(P_i)|/|V(P_i)|$. The problem Maximum Dense Graph Partition asks to construct a partition of maximum density. We study this problem both with and without fixed number of sets $k$. We prove the following results: 1. A polynomial time algorithm for Maximum Dense Graph Partition of thick forests, a subclass of chordal graphs, generalizing the previously known polynomial time algorithm on block graphs. 2. A generic dynamic programming algorithm to construct (if possible) a connected partition into $k$ sets of prescribed sizes on graphs with bounded treewidth. This yields algorithms for both variants of Dense Graph Partition and an efficient construction for the Győri-Lovász theorem. 3. The $\mathsf{NP}$-hardness of Maximum Dense Graph Partition to $k$ parts restricted to split graphs, indicating that thick trees are the boundary for the polynomial computability of this problem.

Authors: Lucas Gerin

HyperLogLog is a now classic probabilistic algorithm that provides an approximation of the number of distinct elements in a massive dataset, using only one pass over the data. In the original article, Flajolet, Fusy, Gandouet, Meunier (2007) provided a sharp analysis of the expectation and variance of the output, using explicit formulas analyzed using poissonization and Mellin transform. In this short article, we revisit the analysis of HyperLogLog with a more probabilistic viewpoint. This allows us to establish exponential deviation inequalities for the HyperLogLog estimator. The methods are elementary, but the estimates are non-asymptotic and totally explicit.

Authors: Retsef Levi, Georgia Perakis, Emily Zhang

This paper develops an approximation algorithm for the submodular joint replenishment problem (SJRP) under a broad family of decomposable submodular ordering cost functions. In the SJRP, a central planner coordinates orders to satisfy deterministic demand for multiple items over a finite discrete planning horizon while minimizing total holding and ordering costs, with the latter modeled as a submodular function of the subset of items ordered in each period. The ordering cost functions considered in this paper are defined based on a decomposition of the items into $k$ categories, where the cost is a function of weighted aggregate quantities within each category and allows for arbitrary interactions across categories through a joint cost function. The proposed algorithm rounds the solution to a linear programming relaxation by partitioning the fractional solution into nested regions according to marginal costs using a novel water-filling procedure, and then selecting one order from each region to obtain a feasible integral schedule. The resulting algorithm achieves an $O(k)$-approximation. When the number of categories $k$ is fixed, this yields the first constant-factor guarantee for this broad class of submodular ordering costs, significantly expanding the class of cost functions for which such guarantees are known.

Let's say there is a statement in math T that you wonder whether it's true or false.  You may even make a conjecture of which way it goes. Do you have a rooting interest?  I may think T is true, but if someone proves T or proves NOT(T) my main concerns are (1) can I understand the proof ? (2) is the proof interesting?

Paul Erdos posed the sum-product conjecture which was recently proven false (by humans!).  I blogged about it here.

I wondered whether Paul Erdos would be happy with how it turned out. So I did the obvious thing: I asked Google AI

       Would Erdos have liked the solution to the sum-product conjecture?

Here is what it said:

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

Paul Erdős would likely have had mixed feelings about the final resolution of the sum-product conjecture, but ultimately thrilled by the breakthroughs.

The original conjecture stated that for any finite set \(A\) of real numbers, either the sumset \(A+A\) or the product set \(AA\) must be large, meaning \(\max(\vert{}A+A\vert{}, \vert{}AA\vert{}) \approx \vert{}A\vert{}^{2-o(1)}\).

Here is how he would have reacted to the different aspects of the solution:

a) Shock and Disbelief at the Disproof: Erdős believed so strongly in his 1974 conjecture that he originally offered a \(\$500\) reward for its solution. He would likely be shocked to learn that it is actually false for real numbers.

BILL COMMENT: OFFERING $500 MIGHT BE BECAUSE HE THOUGHT IT WAS IMPORTANT, NOT THAT HE THOUGHT IT WAS TRUE. DID HE ALSO OFFER $500 TO SHOW IT'S FALSE?

b) Excitement Over the Methods: The disproof of the conjecture relies on sophisticated constructions using high-degree number fields. Erdős loved deep, elegant connections between combinatorics and number theory, and would have admired the clever ways algebraic integers were used to cheat both addition and multiplication.

c) Joy in the Breakthrough: Erdős famously loved to "solve problems" and advance mathematics above all else.  Because the disproof opens entirely new avenues in additive combinatorics and number theory, he would be thrilled with the mathematical progress it generated.

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

By gasarch

We show the following hardness results for monotone learning and approximation of monotone circuit size: 1. Under the Randomised Exponential-Time Hypothesis (rETH), it requires time $n^{\Omega(\log n)}$ to PAC-learn monotone formulas with $n$ input bits and size $s(n) = n$ by monotone circuits of size $n^{(\log n)^{1-\epsilon}}$, for every $\epsilon > 0$. 2. Under the Randomised Exponential-Time Hypothesis (rETH), for any $\delta > 0$, there is a polynomially bounded function $m$ such that $m^{1-\delta}$-multiplicatively approximating the minimum monotone circuit size of a monotone function consistent with a sequence of $m(n)$ labelled examples ${(x_i, b_i)}$ over $n$-bit inputs requires time $m^{\Omega(\log(m))}$. Our results are shown by a novel application of lifting arguments in proof and communication complexity to hardness of monotone learning, by building on the seminal result of Atserias and Müller on hardness of automating Resolution proofs.

Earlier this week I posted a list of arguments why smoothed analysis is a poor model to study the running time of the simplex method. (Hence why we introduced by-the-book analysis which has none of those problems.)

One thing I mentioned was that the standard Klee-Minty cube is stable under zero-preserving perturbations. Someone asked me for a proof. Since there is currently no written source for this lore, I will write a quick proof here.

Let's start with some traditional Klee-Minty cubes:

\[\begin{aligned} \operatorname{maximize} \quad &x_d \\ \operatorname{subject~to} \quad & 0 \leq x_1 \leq 1 \\ & 0.2 x_{j-1} \leq x_j \leq 1-0.2 x_{j-1} \qquad \forall j \in \{2,\dots,d\}. \end{aligned}\]

Assume the inequalities are ordered as shown: first we list both inequalities for \(j=2\) and then both inequalities for \(j=3\) and so on.

We shift the means slightly and then perturb all non-zero coefficients. This yields a linear program

\[\begin{aligned} \operatorname{maximize} \quad x_d \hphantom{\leq}& \\ \operatorname{subject~to} \quad 0.1 + \alpha_1 \leq& (1+\gamma_1) x_1 \\ & (1+\delta_1) x_1 \leq 0.9+\varepsilon_1 \\ 0.1 + \alpha_j + (0.2 + \beta_j) x_{j-1} \leq& (1+\gamma_j) x_j \\ & (1+\delta_j) x_j \leq (0.9+\varepsilon_j) - (0.2 + \eta_j) x_{j-1} \qquad \forall j \in \{2,\dots,d\}. \end{aligned}\]

Theorem. If \(\alpha,\beta,\gamma,\delta,\varepsilon,\eta \in [-0.05,0.05]^d\) then Bland's rule takes exponentially many pivot steps.

Proof. We go by induction. We prove that there are exactly \(2^d\) bases, and Bland's rule will visit all bases when it starts at the basis minimizing \(x_d\) and works to maximize \(x_d\). All basic feasible solutions \(x\) satisfy \(x \in [0,1]^d\). The Bland path is reversible: if we start at the basis maximizing \(x_d\) and we use Bland's rule to minimize \(x_d\) then the same bases are visited but in reverse order.

We can check the base case \(d=1\) easily. The starting basis consists of the constraint \(0.1 + \alpha_1 \leq (1+\gamma_1)x_1\) and the end basis consists of the constraint \((1+\delta_1)x_1 \leq 0.9 + \varepsilon_1\). The two basic feasible solutions \(\frac{0.1 + \alpha_1}{1+\gamma_1}\) and \(\frac{0.9+\varepsilon_1}{1+\delta_1}\) are easily verified to be in \([0,1]\).

When \(d \geq 2\), assume that the induction statement has been proven for \(d-1\). The starting basis for \(d\) consists of all lower-bounding constraints: \(0.1 + \alpha_1 \leq (1+\gamma_1)x_1\) and \(0.1 + \alpha_j + (0.2+\beta_j)x_{j-1}\leq(1+\gamma_j)x_j\) for all \(j \in \{2,\dots,d\}\).

Take the Bland path for \(d-1\), and append to every basis in it the constraint \(0.1 + \alpha_j + (0.2+\beta_j)x_{j-1} \leq (1+\gamma_j)x_j\). These bases are now bases for the KM-cube in \(d\) variables. The associated basic solutions are identical on coordinates \(1,\dots,d-1\) and have \(x_d = \frac{0.1 + \alpha_j + (0.2+\beta_j)x_{d-1}}{1+\gamma_j}\). The Bland path for \(d-1\) contains \(2^{d-1}\) bases and increases the value of \(x_{d-1}\) in every step. Since \(1+\gamma_d \in [0.95,1.05]\) and \(0.1 + \alpha_d \in [0.05,0.15]\) and \(0.2 + \beta_d \in [0.15,0.25]\) and \(x_{d-1} \in [0,1]\) we get \(x_d \in [0, 0.43]\).

When we consider the constraint \((1+\delta_d)x_d \leq (0.9+\varepsilon_d)-(0.2+\eta_d)x_{d-1}\), we see that the left-hand side is at most \(1.05 \cdot 0.43 \leq 0.46\) and the right-hand side is at least \(0.85-0.25 = 0.6\). That is all we needed to check in order to verify that the bases constructed so far are feasible.

Every step on our path so far is improving. Due to our chosen ordering of the inequalities, the constraint \(0.1 + \alpha_j + (0.2+\beta_j)x_{j-1} \leq (1+\gamma_j)x_j\) will not leave the basis until there is no other possible improving direction left. Hence our path so far is all part of the Bland path for our KM-cube in \(d\) variables.

At the end of our path so far, Bland's rule will pivot out the constraint \(0.1 + \alpha_j + (0.2+\beta_j)x_{j-1} \leq (1+\gamma_j)x_j\) and pivot in \((1+\delta_d)x_d \leq (0.9+\varepsilon_d)-(0.2+\eta_d)x_{d-1}\), since it is the only available improving move.

Now take again the Bland path for \(d-1\), but reverse its order and append to every basis in it the constraint \((1+\delta_d)x_d \leq (0.9+\varepsilon_d)-(0.2+\eta_d)x_{d-1}\). This yields \(2^{d-1}\) more bases for the \(d\)-variable KM-cube. Because we reversed the order, the Bland path is decreasing \(x_{d-1}\). Since \(0.2+\eta_d > 0\) and \(1+\delta_d > 0\), the path is thus increasing the value of \(x_d\). We have now constructed our full Bland path of \(2^d\) bases. It remains to show that these final \(2^{d-1}\) bases are feasible and in \([0,1]^d\). Note that \(1+\delta_d \in [0.95,1.05]\), \(0.9+\varepsilon_d \in [0.85,0.95]\) and \(0.2+\eta_d \in [0.15,0.25]\). Since \(x_{d-1} \in [0,1]\) we get \(x_d = \frac{0.9+\varepsilon_d - (0.2+\eta_d)x_{d-1}}{1+\delta_d} \in [0.57, 1]\). The only constraint that can lead to infeasiblity is \(0.1 + \alpha_j + (0.2+\beta_j)x_{j-1} \leq (1+\gamma_j)x_j\) but its left-hand side is at most \(0.4\) and its right-hand side is at least \(0.57\), hence the bases are all feasible. QED

Interpretation

This theorem directly shows us that Bland's rule has exponential complexity under both relative and zero-preserving smoothed analysis. When we rescale the inequalities by large numbers in the standard way, it follows directly that Dantzig's most-negative reduced cost rule has exponential complexity for relative smoothed analysis.

In my previous post I interpreted the above theorem by stating that zero-preserving smoothed analysis is a dead end. While I stand by that statement, I do want to give a second possible interpretation.

Namely, you can conclude that Bland's rule is just bad.^[1] More specifically: Bland's rule is purely combinatorial in nature. Perturbations are (stochastic) geometry. It is no wonder that Bland's pivoting decisions fail to benefit from perturbations. Dantzig's rule is also bad of course. In this case, specifically because it fails to be scale-invariant with respect to rescaling the inequalities. Dantzig thus similarly fails to be a geometrically-steered pivot rule.

When your pivot rule does incorporate the ambient geometry, you can do significantly better than zero-preserving smoothed analysis. In fact, in the by-the-book paper we bound the running time of a simplex method in a much weaker probabilistic model: only the right-hand side is perturbed.^[2] That is part of why we are so proud of the BTB paper: its both mathematically stronger and scientifically more robust than what we had before.

[1]	Every practitioner will agree.

[2]	We use the semi-random shadow vertex pivot rule, which generally prefers steeper edges over shallower edges. Hence it incorporates the ambient geometry. The analysis also needs some additional minor assumptions to make the definitions make sense: RHS perturbations alone lack scale.

We prove that every De Morgan formula with $n$ leaves has a pointwise $1/3$-approximating real polynomial of degree $O(\sqrt n)$ and coefficient $\ell_1$-norm $2^{O(\sqrt n)}$. The standard approximate-degree theorem for formulas gives the same degree bound, but only yields the weaker coefficient estimate $2^{O(\sqrt n\log n)}$. Our proof constructs, for every formula, a span program with witness size $O(\sqrt n)$ and, additionally, $O(1)$ entrywise-absolute operator norm for the available-vector matrix. A standard span-program-to-polynomial argument then gives the desired approximating polynomial while preserving coefficient weight. We also show that the coefficient bound is tight up to constants in the exponent: the De Morgan formula for inner product modulo $2$ already gives a matching $2^{\Omega(\sqrt n)}$ lower bound for formulas with at most $n$ leaves, even regardless of the degree of the approximating polynomial.

We show that under a plausible number-theoretic conjecture, for any constant $s$ there exists an $s$-server private information retrieval (PIR) protocol that on an $n$-bit database requires communication $\exp(O((\log n)^{1/s} (\log \log n)^{1-1/s}))$. Previous constructions attaining the same communication required $2^{O(s)}$ servers. Our number-theoretic conjecture is implied by existing conjectures, namely the generalized repunit conjecture and Schinzel's hypothesis H (either one of these conjectures would suffice alone). Our result builds on the ``matching vector family + $S$-decoding polynomials'' framework pioneered by Efremenko (STOC 2009) and recently refined by Ghasemi, Kopparty, and Sudan (STOC 2025). The main ingredient is a framework for constructing $S$-decoding polynomials with only $k+1$ nonzero coefficients modulo special products of $k$ primes, resolving an open problem posed by Ghasemi and Kopparty (ITCS 2026). By the lower bound shown by Ghasemi and Kopparty, this is the minimum achievable sparsity. We also empirically validate our construction and make our result unconditional for all $s \leq 15$. We also apply our techniques to regimes where $s$ grows with $n$, showing under a stronger variant of our number-theoretic conjecture that the communication complexity of $s$-server matching-vector PIR can be superpolynomially reduced from the previous state of the art for any $s \leq \exp(o(\sqrt{\log \log n/\log \log \log n}))$. The main result for $s = O(1)$ and its proof were discovered in a GPT-5.5 Pro conversation prompted by the authors.

We describe a method that lifts an arbitrary polynomial $f$ with sparsity $s$ to a polynomial that requires a read-once oblivious algebraic program of width $s$ for every variable order. To do so, we introduce a technique for constructing a gadget based on erasure codes over finite fields, where each variable in $f$ is substituted with a monomial that encodes a codeword into the exponents of the monomial. To the best of our knowledge, our construction represents the first use of error-correcting codes in the context of lifting. As an application, we consider factor complexity, which studies how much the complexity of a polynomial can increase under factorization. Our result allows us to lift any gap in sparsity to the same gap in width in a generic manner.

For a directed graph $G = (V, E)$, we say that a weight function $\rho \colon E \to [M]$ is *min-isolating* if the minimum-weight path from $u$ to $v$ is unique for each pair of vertices $u, v \in V$ such that $v$ is reachable from $u$. If we could efficiently construct a polynomially-bounded min-isolating weight function for any given digraph (or even just for *layered* digraphs), it would follow that NL = UL, thanks to work by Reinhardt and Allender (SICOMP 2000). Van Melkebeek and Prakriya constructed an explicit, deterministic, min-isolating weight function for layered digraphs (SICOMP 2019). Their weight function is *oblivious*, i.e., it is a single weight function that works for all width-$w$ length-$n$ layered digraphs simultaneously, assigning a weight to each possible edge in the digraph without needing to know which edges are actually present. However, they use weights of magnitude $M = 2^{\Theta(\log n \cdot \log w)}$ instead of the desired $M = \mathrm{poly}(wn)$. In this work, we prove that every deterministic, oblivious weight function that is min-isolating for width-$w$ length-$n$ layered digraphs must use weights of magnitude $2^{\Omega(\log w \cdot \log n)}$. This rules out one possible method of proving NL = UL. Our proof is based on a connection with coding theory. A *solid burst error* is a vector $e \in \mathbb{Z}_q^n$ such that the support of $e$ is an interval. Using spectral graph theory methods, we prove that every code $\mathcal{C} \subseteq \mathbb{Z}_q^n$ that can detect solid burst errors with Hamming weight up to $d$ must satisfy $|\mathcal{C}| \leq q^{n - \Omega(\log d)}$, which is optimal. The best prior bound, by Das (BEEI 2012), says $|\mathcal{C}| \leq q^n / (d + 1)$ assuming the code is linear.

Authors: Hrishikesh Belagali, Thomas Van Camp, R. Pradeep, Sourin Das, Namit Anand, Ryan LaRose

Recent experiments on quantum computers have challenged the limits of classical computation in chemistry, simulating ground states of strongly correlated molecules. Many of these experiments have utilized the unitary cluster Jastrow ansatz, a quantum circuit inspired by the unitary coupled cluster ansatz that can be tailored to current quantum hardware. Notably, the largest experiment in Sci. Adv. 11, 25 (2025) executed a quantum circuit with 77 qubits and 10,570 gates on an IBM quantum computer and performed classical post-processing with up to 6400 nodes on Fugaku to compute ground state energies better than Hartree-Fock. In this work, we present a polynomial time classical algorithm to compute the energy of any single-layer unitary cluster Jastrow circuit, independent of locality constraints for quantum hardware. Our algorithm can reproduce the largest experiment from Sci. Adv. 11, 25 (2025) in less than a minute on a laptop, and through circuit optimization enabled by fast simulation we achieve a lower ground state energy than the experiment.

Authors: Alexander S. Kulikov, Ivan Mihajlin

The Edge Coloring problem is notoriously hard: it is still unknown whether it can be solved in time $2^{o(n^2)}$ (let alone $2^{O(n)}$), where $n$ is the number of nodes of the input graph. Can one explain the lack of such upper bounds by deriving a lower bound $2^{Ω(n^2)}$ from a lower bound for SAT, $3$-SUM, or APSP? In this note, we provide a negative answer for this question: if there is a reduction showing that Edge Coloring cannot be solved faster than in $α^{n^2}$ (where $α>1$ is an explicit constant) under a hypothesis that known algorithms for one of the problems mentioned above are optimal, then the corresponding hypothesis is false.

Authors: Yanwen Luo, Yuan Luo

We propose the first algorithm to morph geometric graphs on hyperbolic surfaces. It is based on a generalization of Tutte's spring embedding theorem on essentially 3-vertex-connected graphs. We describe the algorithms in detail and show experiments with triangulations and graphs on a hyperbolic surface of genus two, the Bolza surface, and a hyperbolic surface of genus three, the Klein quartic.

Authors: Johannes Schmidt, Mohamed Maizia, Victor Lagerkvist, Johannes K. Fichte

The propositional abduction problem is a well-known form of non-monotonic reasoning where we are asked to find an explanation of a given manifestation. Recently, there has been an influx of results asking more refined questions about the solution space rather than only individual solutions. For example, we might be interested in finding two solutions that are sufficiently far from each other (diverse solutions) in the solution space. In this paper we consider a related representation question where we ask if a given set of explanations S can represent any other explanation (that is, whether their symmetric difference is smaller than a given k). We first study this problem from a classical complexity perspective and obtain a complete classification. While only a handful of cases are tractable, the increase in complexity compared to classical abduction is often smaller than expected. We then study the parameterized complexity for several parameters and obtain new tractable and hard cases. Interestingly, a full parameterized complexity classification would require resolving the parameterized complexity of the covering radius problem from coding theory. To the best of our knowledge, no useful relationship between coding theory and non-monotonic reasoning has previously been established, but such connections seemingly become important when asking more complex questions about solution spaces.

Authors: Suryajith Chillara, Kshitij Gajjar, Nithish Raja

We study shortest paths in directed graphs whose edge weights are of the form $$ \mathsf{wt}(e) = a_{e,1} λ_1 + a_{e,2} λ_2 + a_{e,3} λ_3 + \cdots + a_{e,d} λ_d + a_{e,d+1}.$$ Here, each $a_{e,i}\in\mathbb{R}$ is a fixed constant for each edge $e$, whereas each $λ_i\in\mathbb{R}$ is common across the entire graph. So, there could be different shortest paths in the graph for different values of the $λ_i$'s. This is called the Parametric Shortest Paths problem, and has been studied since the 1980s. For $d=1$, Carstensen (1983) showed that the number of shortest paths in $n$-vertex graphs is at most $n^{O(\log n)}$. She also proved a matching lower bound of $n^{Ω(\log n)}$, later refined by Mulmuley & Shah (2001). For $d=2$, Gajjar & Radhakrishnan (2019) showed an upper bound of $n^{O(\log^2 n)}$. Barth, Funke & Proissl (2022) generalized their result to prove an upper bound of $n^{O_d(\log^d n)}$ for all positive integers $d$. The lower bound did not undergo any improvement over the years. In this paper, we close this long line of research by showing an $n^{O(d\log n)}$ upper bound for all positive integers $d$, exponentially improving the previous upper bound. We observe that a matching lower bound of $n^{Ω(d\log n)}$ can be obtained from earlier works. We also show that our proof can be adapted to work for undirected graphs with positive edge weights. Furthermore, for directed graphs whose edge weights are univariate polynomials of degree at most $q$, we prove an upper bound of $n^{O(\log{n}+\log{q})}$. Finally, building upon work on the Point Location problem by Ezra, Har-Peled, Kaplan & Sharir (2020), we construct a Shortest Path Oracle which takes as input a point $\overline{x}\in \mathbb{R}^d$, and outputs a shortest path at $\overlineλ=\overline{x}$ in sublinear time (for a wide regime of $d$).

Authors: Patrizio Angelini, Sabine Cornelsen, Giordano Da Lozzo, Seok-Hee Hong, Ignaz Rutter

Orthogonal planar drawings constitute a classical and mainstream research topic in graph drawing due to their clarity and wide applicability. In an orthogonal planar drawing of a graph, each face is represented as an orthogonal polygon, that is, a polygon whose edges are either horizontal or vertical. Yet a planar graph admits such a representation if and only if its maximum degree is at most four. In this paper, we consider planar polyline drawings of graphs with unrestricted maximum degree. We focus on drawings that are ``close to orthogonal'', where closeness is measured by the number of faces that are not orthogonal polygons. We show that, even when the input graph is triconnected and thus has a unique planar embedding, the problem of testing whether there exists a planar polyline drawing with at most $h$ non-orthogonal faces is NP-complete. Motivated by this computational hardness, we study parameterized and approximation algorithms. In the fixed-embedding setting, we prove that the problem admits linear-time FPT algorithms parameterized by (i) the outerplanarity index and (ii) the natural parameter $h$. In addition, we provide an FPT algorithm parameterized by the treewidth and a polynomial-time approximation scheme. In the variable-embedding setting, we give an FPT algorithm parameterized by treewidth for biconnected graphs.

Authors: Arnold Filtser, Hung Le, Nikolas Mählmann, Marcin Pilipczuk, Michał Pilipczuk

Fat minors are the metric analog of graph minors that are tailored to the analysis of metric (edge-weighted) graphs and, more generally, metric spaces having a suitable notion of shortest paths. Despite a large interest in this notion, not much is known about the structure of metric graphs excluding a fixed fat minor. We prove that if a metric graph $G$ excludes a fixed graph $H$ as a $δ$-fat minor, for some $δ>0$, then $G$ enjoys the metric analog of flatness (aka uniform quasi-wideness) - a structural property from the field of Sparsity. In essence, our flatness result says that for any $α\geq β$ large enough compared to $δ$, in every large enough set $A$ in $G$ one can find a sizable subset $B$ that becomes $α$-scattered after removing a bounded number of balls of radius $β$. We call this property drill-flatness. Notably, the proof only relies on excluding shallow fat minors: every branch set has radius at most $2α$. As a corollary, we prove that metric graphs that exclude a fixed $δ$-fat minor have bounded $\varepsilon$-scatter dimension if we consider only $\varepsilon$-scatters at distances large enough compared to $δ$. By combining this with the results of Abbasi et al. [FOCS 2023], we infer that the $k$-Center problem on instances excluding $H$ as a $δ$-fat minor admits an approximation algorithm that finds a solution of cost at most $(1+\varepsilon)\cdot\mathsf{OPT}+{\cal O}(δ/\varepsilon^2)$ in time ${\cal O}_{H,\varepsilon}(n^{{\cal O}(1)})$. This is one of the first algorithmic results for general fat-minor-free metrics. We also study drill-flatness in hereditary classes of (unweighted) graphs, where we obtain a characterization equating drill-flatness with excluding shallow induced minors. This is an induced analog of the equivalence between flatness and nowhere denseness - one of central results of Sparsity.

Authors: Sanjeev Khanna, Aaron Putterman, Junkai Song

In the cut-query model, an algorithm is given access to a graph $G = (V, E)$ \emph{only} via cut queries. This model has seen significant attention in the undirected graph setting, with works establishing $O(n)$ cut query algorithms for computing the global minimum cut, $\widetilde{O}(n^{3/2})$ cut query algorithms for all pairs minimum cut, and many more. However, despite this vast array of progress in designing sub-quadratic query algorithms for computing properties of undirected graphs, there has been \emph{no} progress in designing such algorithms in directed graphs. Indeed, even for basic problems like whether a vertex $t$ is reachable from a vertex $s$, the cut query complexity is only known to be bounded in the interval $[Ω(n), O(n^2 / \log n)]$. In this work, we begin a systematic study of these basic problems in directed \emph{acyclic} graphs (DAGs). In this setting, we show that reachability from a single vertex and even topological sorting are both computable in $O(n \log^3 n)$ many cut queries. As a consequence, we also obtain an algorithm which, for any \emph{arbitrary} directed graph $G$, uses only $O(n \log^3 n)$ cut queries and determines whether $G$ contains a cycle.

Authors: Ismail H. Toroslu

Multi-object tracking in dense crowds requires solving a bipartite assignment problem between detections and trajectories at every video frame. The classical Hungarian algorithm solves this in $O(N^3)$ time, which becomes a bottleneck for large scenes with hundreds of people. We propose an \emph{incremental} assignment algorithm that exploits the block-sparse structure of crowd tracking cost matrices --- dense within each crowd cluster, near-zero between clusters. We compute the exact same optimal $N \times N$ assignment as the Hungarian algorithm, but via an incremental strategy: we add one person at a time, exploiting the fact that after step $n-1$ the dual potentials are \emph{exactly optimal} for the $(n-1)\times(n-1)$ subproblem --- a strictly stronger condition than the intermediate feasibility maintained by the Hungarian algorithm during its $N$ outer iterations. Each new step therefore requires only a single augmenting path search from a certified optimal starting point. This avoids repeated full-matrix scans while guaranteeing an identical globally optimal result. A diagonal-reordering invariant keeps the data structure compact and cache-friendly. On realistic crowd benchmarks with $N \in [200, 5000]$ people organised into dense clusters, our algorithm achieves \textbf{3.7--6.5$\times$ speedup} over the Hungarian baseline while producing provably optimal matchings identical to those of Hungarian. The speedup grows with $N$ and remains stable beyond $N=3000$, making the method especially attractive for large-scale crowd scenes such as stadium exits and mass public events.

Authors: Patthadon Tantiameorn, Grittin Nuntasombat, Jittat Fakcharoenphol

Sketch data structures are very useful for computing statistics on streaming data, including network traffic, server requests, and financial transactions. In recent work, FermatSketch was introduced as an underlying data structure used to monitor changes in network states. It is a linear data structure that maintains an associated array of counters and supports listing all key-counter pairs while using almost linear space. Because it is linear, it can be used to monitor changes between two streams with space proportional to the number of items that change. The data structure is based on a hash table, and all key-counter pairs can be successfully listed when there are slots in the table with exactly one key hashed to them. We show how to relax this requirement by using additional computational resources when listing the key-counter pairs, thereby improving space efficiency with only a small overhead when collecting statistics. We achieve this by storing, for each bucket, multiple linear combinations of the counters whose coefficients are generated from the keys. With this information, certain linear systems can be solved to obtain the key-counter pairs. A preliminary experiment shows a significant reduction of memory needed for the data structure. Our work can be viewed as a trade-off between space and time.

Authors: Cornelius Brand, Robert Ganian, Mathis Rocton

In spite of the fundamental role of neural networks in contemporary machine learning research, our understanding of the computational complexity of optimally training neural networks remains incomplete even when dealing with the simplest kinds of activation functions. Indeed, while there has been a number of very recent results that establish ever-tighter lower bounds for the problem under linear and ReLU activation functions, less progress has been made towards the identification of novel polynomial-time tractable network architectures. In this article we obtain novel algorithmic upper bounds for training linear- and ReLU-activated neural networks to optimality which push the boundaries of tractability for these problems beyond the previous state of the art. In particular, for ReLU networks we establish the polynomial-time tractability of all architectures where hidden neurons have an out-degree of $1$, improving upon the previous algorithm of Arora, Basu, Mianjy and Mukherjee. On the other hand, for networks with linear activation functions we identify the first non-trivial polynomial-time solvable class of networks by obtaining an algorithm that can optimally train network architectures satisfying a novel data throughput condition.

Authors: Joel Daniel Andersson, Anamay Chaturvedi, Monika Henzinger, Roodabeh Safavi

Differential privacy under Continual Observation (CO) quantifies the loss in privacy that occurs when outputs generated using a stream of sensitive input data are published in the online setting. In this paper, we consider a more stringent notion of privacy compared to prior work wherein an individual's participation may shift the entire stream by a time-step. We define a new notion of edit-neighboring streams that captures this scenario. Our findings are as follows. First, we prove that on a stream of length $T$, every additive-noise mechanism incurs error $\tildeΩ(\min\{T^{1/3}/\varepsilon^{2/3}, T\})$ when required to be $\varepsilon$-DP under CO for edit-neighboring streams. This includes state-of-the-art continual counters constructed via the factorization mechanism that in the standard neighboring setting incur only polylogarithmic additive error. Second, we construct the first mechanisms with polylogarithmic additive error for our more stringent notion of privacy. We show that we can recover the same additive error as in the standard notion of privacy albeit with worse constant coefficients for both arbitrary input streams and sparse streams. Third, we show that the notion of edit-neighboring streams inhabits a `sweet-spot' in terms of generality and additive error incurred. More precisely, we show that the even more general notion of prefix-sum neighboring streams---which arises naturally in reductions for problems under CO---must incur additive error scaling as $\tildeΩ(\min\{T^{1/3}/\varepsilon^{2/3}, T\})$ for any mechanism that is $\varepsilon$-DP under continual observation. Finally, we show empirically on synthetic data that when compared with prior work, our mechanism achieves a superior trade-off between the success probability of a simple distinguishing attack, and the additive error incurred by the respective mechanisms.

Authors: Kavya Ravichandran

As humans, we face many decisions that require us to choose between sticking to something and giving up. This thesis uses algorithmic tools to derive insights about such decision-making problems in theoretical models, studying both near-optimal methods and outcomes of social and behavioral influences. Along the way, this thesis sheds light on what we gain and what we lose as we move from a messy and complex real world setting to a very general abstract model by studying various points along this spectrum. In Part I, we study algorithms for sequential decision-making in the improving multi-armed bandits problem. We provide nearly matching upper and lower bounds in the general case. Then, we then ask what is possible if we have access to similar instances to the one we wish to deploy our algorithm on. To that end, we provide guarantees in the data-driven algorithm design framework, showing that a polynomial number of samples is sufficient for learning good algorithms from a class of algorithms. In Part II, we study algorithmic approaches for problems in social epistemology. We start by analyzing what role theoretical models can play in the study of social problems. We then study social and behavioral influences in decision-making requiring investment. First, we provide mathematical formalism in which to study the formation of pessimism traps, a phenomenon identified by philosophers in which agents are influenced by their predecessors to engage in less-ambitious goals. We develop financial interventions to sustainably shift communities out of these traps. The second problem we study is the influence of grit as a behavioral trait in ambitious decision-making. Overall, these works seek to theoretically model phenomena in social epistemology and provide a framework for intervening algorithmically.

The Miller Institute is accepting nominations for its Miller Research Postdoc Fellowships in the basic sciences. The program provides exceptional, curious researchers with the opportunity to conduct research at UC Berkeley. Candidates are selected based on academic achievement, scientific promise, and a strong passion for interdisciplinary discovery.

Website: https://miller.berkeley.edu/nominate-apply/miller-research-fellowship
Email: millerinstitute@berkeley.edu

By shacharlovett

ICM 2026 starts today in Philadelphia; ICM 2030 will be in Glasgow

I am now in Philadelphia after a two-day meeting in New York of the General Assembly of the IMU (International Mathematical Union). Among its many activities, the IMU organizes the ICM (International Congress of Mathematicians).

ICM 2026 starts tomorrow later today (Thursday, July 23) here in Philadelphia, and it was just announced that ICM 2030 will take place in Glasgow. I will try to (slowly) blog about ICM 2026, continuing the tradition of my posts on ICM 2018 and ICM 2022. Yesterday there was an impressive reception event and I had the opportunity to reconnect briefly with man old friends.

A lecture at Columbia University

Yesterday I gave a lecture at Columbia University to a group of brilliant students, followed by a lively discussion. I spoke about some old problems and results in discrete geometry and reflected on how our understanding of them has evolved over the years.

Two quantum items

Here is a draft of my recent paper, The Fully Depolarizing Noise Conjecture for Entangled Physical States: A Twenty-Year Perspective. As always, comments and corrections are most welcome.

Amit Hagar (a philosopher of science from Indiana University) has written an interesting paper entitled The NISQ Trap: Eight Years of Demonstrations the Hardware was Built to Lose. (There is a post about it and an interesting discussion on Shtetl-Optimized.) This joins an earlier paper of Amit’s from 2009, Active Fault-Tolerant Quantum Error Correction: The Curse of the Open System and his subsequent book on the subject.

A lecture for Furstenberg’s birthday

I gave a talk in Hebrew at an evening celebrating Hillel Furstenberg’s 90th birthday. The talk was about Furstenberg’s contributions to enumerative combinatorics and their recent applications to algebraic circuit complexity. Here are the slides, and here is the raw video of the event. (My lecture 2:13:00.)

AI and math news

Two significant items: The Jacobian conjecture has been disproved (Claude; see this enlightening blog post by Terry Tao); the double cover conjecture has been proved (OpenAI).

By Gil Kalai

Authors: Frederic Koehler, Pui Kuen Leung

Let $\mathbb{K}\in\{\mathbb{R},\mathbb{C},\mathbb{H}\}$, put $β=\dim_{\mathbb{R}}\mathbb{K}$, and let $G_n^{\mathbb{K}}$ be an $n\times n$ matrix with i.i.d. standard $\mathbb{K}$-Gaussian entries, namely a standard $\mathbb{K}$-Ginibre matrix. We prove that the normalized row-ordered permanent $W_n^{\mathbb{K}}=\operatorname{per}_{\mathbb{K}}G_n^{\mathbb{K}}/\sqrt{n!}$ has a radial density $p_n^{\mathbb{K}}$ satisfying $\|p_n^{\mathbb{K}}\|_\infty=p_n^{\mathbb{K}}(0)\lesssim_βn^{(β+2)/4}$ and $\sup_{z\in\mathbb{K}}\mathbb{P}(|W_n^{\mathbb{K}}-z|\leq\varepsilon)\lesssim_βn^{(β+2)/4}\varepsilon^β$. In particular, for $\mathbb{K}=\mathbb{C}$, this resolves the Permanent Anticoncentration Conjecture of Aaronson and Arkhipov. The proof compares the squared Gaussian permanent with the squared (Study) determinant in Laplace-transform order.

Authors: Todor Antić, Jiří Fiala, Jelena Glišić, Grzegorz Gutowski, Konstanty Junosza-Szaniawski, Jan Kratochvíl, Giuseppe Liotta, Morteza Saghafian, Maria Saumell, Krisztina Szilágyi, Pavel Valtr

Let $Γ$ be a straight-line crossing-free drawing of a tree $T$. A \emph{bad pair} in $Γ$ is a pair of non-adjacent vertices of $T$ whose Euclidean distance in $Γ$ is smaller than the length of the longest edge in the path connecting them in~$Γ$. When $Γ$ has no bad pairs, $Γ$ is a Euclidean Minimum Spanning Tree of its vertex set (or EMST-drawing for short). Deciding whether a tree of maximum degree at most six admits an EMST-drawing is known to be \NP-hard. In contrast, we characterize those caterpillars that admit an EMST-drawing. The characterization gives rise to a linear-time algorithm that decides if a caterpillar admits an EMST-drawing, and in the affirmative case, computes such a drawing. For caterpillars of maximum degree six, we further present a linear-time algorithm to compute a crossing-free straight-line drawing with the minimum number of bad pairs. For $n$-vertex trees with maximum vertex degree $Δ$, we prove the $Δ^2n\log n$ upper bound on the minimum number of bad pairs. In the special case of stars, we construct a drawing with the minimum number of bad pairs.

Authors: Saeed Odak, Jonathan Rollin, Torben Scheele

A graph is $k$-matching-planar if it admits a drawing in the plane such that, for every edge $e$, the edges crossing $e$ contain no matching of size greater than $k$. The class of $k$-matching-planar graphs generalizes other beyond-planar graph classes, such as $k$-planar and fan-planar graphs. In a $2$-layer drawing of a bipartite graph, the vertices of the two bipartition classes are placed on two parallel horizontal lines and edges are drawn as straight-line segments between them. We prove that every graph with a $2$-layer $k$-matching-planar drawing has pathwidth at most $2k+1$. Moreover, for every $k \geq 0$, we construct a graph with a $2$-layer $k$-matching-planar drawing whose pathwidth is $3\lfloor k/2\rfloor + 1$. On the algorithmic side, we consider the one-sided recognition problem where a fixed embedding of the vertices on one side is given. We show that this problem is NP-hard. On the other hand, we prove that the problem is fixed-parameter tractable with respect to $k$. Finally, we prove that the two-sided variant cannot be approximated within any constant factor in polynomial time unless $\operatorname{P}=\operatorname{NP}$.

Authors: Michael A. Bekos, Carla Binucci, Emilio Di Giacomo, Walter Didimo, Luca Grilli, Maria Eleni Pavlidi, Alessandra Tappini, Alexandra Weinberger

Linear layouts of graphs -- particularly \emph{stack} and \emph{queue} layouts -- are well-established types of representations in graph drawing, thanks to their connection with numerous theoretical and practical problems. In such layouts, all vertices are linearly ordered and the edges are partitioned into sets that avoid specific forbidden configurations: in a stack layout no two independent edges within the same set cross, whereas in a queue layout no two independent edges within the same set are nested. A central problem in this context is to determine, for a given graph $G$, its \emph{stack number} or \emph{queue number}, that is, the minimum number of sets into which the edges can be partitioned so that a corresponding stack or queue layout of $G$ exists. In this work, we introduce a relaxation of stack and queue layouts, which allows some forbidden patterns for the edges in the same set. Namely, for a given integer $k > 0$, a \emph{$k$-defective stack layout} (resp. a \emph{$k$-defective queue layout}) allows an edge to be in a crossing (resp. nesting) relationship with at most~$k$ edges within the same set. Our motivation is to extend the classes of graphs that admit linear layouts using a limited number of edge-partition sets, at the cost of allowing some defects. We study defective linear layouts both from a combinatorial and from an algorithmic perspective, providing an array of results across different graph classes and parameters.

Authors: Henrique Ennes, Clément Maria

The Solovay-Kitaev algorithm describes how to approximate, to arbitrary precision, a matrix in the special unitary group SU(d) using any fixed universal gate set. Although the algorithm scales as O(poly(log(1/$ε$))), where $ε$ is the maximum targeted approximation error, its running time depends exponentially on the qudit dimension d. This bad dependence can be traced to its explicit use of an $ε$_0-net of size 2 $Ω$(d^2) , which is queried O(poly(log(1/$ε$))) times throughout the execution. For this reason, the standard Solovay-Kitaev theorem is usually stated for fixed d, with the base net and its lookup cost absorbed into the constants. We study the algorithmic problem in the variabledimension regime and show how to avoid searching an exponentially large precomputed net for each target unitary. In particular, we introduce the notion of a good exponential basis and show that such a basis can replace the usual depth-zero net-search routine. This yields a modification of the algorithm in which the use of an explicit net is fully moved to a preprocessing step. For instruction sets that already contain, or allow the efficient construction of, a good exponential basis, the resulting online synthesis algorithm is polynomial in d and polylogarithmic in 1/$ε$. For arbitrary universal instruction sets, the exponential dependence on d^2 is not removed, but is isolated into a one-time additive preprocessing cost. Our technique uses differential-geometric methods to devise an integerized version of trotterization that replaces the depth-zero net query by a constructive local synthesis routine. The same framework also suggests possible extensions based on other discretized numerical integration schemes.

Authors: Nattawut Phetmak, Grittin Nuntasombat, Jittat Fakcharoenphol

We study an infinite variant of the coin-covering problem for periodic point sets in the plane. Given a point set of spacing $d$, we ask whether all of its points can be covered by pairwise non-overlapping unit disks. We consider the triangular lattice, the square lattice, and the honeycomb point set, and construct periodic motif patterns that certify several intervals of coverable spacings. For the triangular lattice, our constructions include single-family patterns with vertex, face, and off-lattice realizing centers, as well as multi-family patterns. For the honeycomb point set, additional native motifs fill gaps left by the triangular-lattice constructions. For the square lattice, we revisit the constructions of Alm et al., identify an unintended overlap in one motif realization, and give new patterns that recover part of the affected interval and establish an additional coverability interval.

Authors: Grittin Nuntasombat, Nattawut Phetmak, Jittat Fakcharoenphol

Given two sets of points in 3-dimensional space $R$ and $B$, we want to separate these two sets of points using a classifier based on linear constraints, while ensuring robustness against outliers. The problem was studied in $\mathbb{R}^2$ by Glazenburg et al. We follow their approach and present various algorithms for many types of classifiers under various definitions of outliers. Our algorithms rely mainly on the duality of points and planes in $\mathbb{R}^3$.

Authors: Songtao Mao

The low-degree method and its associated lower bounds are widely used to guide algorithm design and to provide evidence of computational hardness in average-case inference, high-dimensional statistics, random optimization, and related problems. This led to the low-degree conjecture, which predicts that when the low-degree advantage between a planted distribution and a uniform null distribution remains bounded, no efficient distinguisher can succeed after independent noise, provided that the planted distribution has permutation symmetry. Several works have produced counterexamples to variants of this conjecture or to versions for algorithms with higher time complexity, but the conjecture remained open in its standard binary, polynomial-time formulation. We disprove the polynomial-time low-degree conjecture by giving a family of examples in this setting. For every fixed integer $r\geq3$, we construct a permutation-invariant distribution $\mathbb{P}_n$ on simple graphs, with $\mathbb{Q}_n=G(n,1/2)$, such that every marginal of $\mathbb{P}_n$ on at most $D_n=Θ((\log n)^{r-1})$ edges is uniform. Therefore, the low-degree advantage is zero through degree $D_n$. Nevertheless, after every edge is independently resampled at a fixed positive rate, a deterministic rank test strongly distinguishes the resulting distribution from $\mathbb{Q}_n$ in polynomial time. The construction chooses a subspace of a Reed--Muller code whose nonzero polynomials have small absolute bias, selects points whose evaluation vectors have no short linear dependencies, and evaluates a random alternating bilinear form on pairs of these vectors. Our result shows that low-degree indistinguishability, a uniform null distribution, permutation invariance, and independent resampling do not by themselves imply polynomial-time hardness, and suggests that a valid general conjecture must impose an additional condition.

Authors: Jack Fitzsimons

Nikolov and Ullman asked whether k statistical queries on a universe of size T can be released under pure differential privacy with expected worst-coordinate error at the square-root rate suggested by known lower bounds. We prove their conjectured upper bound. For every database size n and privacy parameter $\varepsilon>0$, there is an $\varepsilon$-differentially private mechanism with expected error $O(\min\{1,\sqrt{\log(2T)\log(2k)/(\varepsilon n)}\})$. This matches the lower-bound dependence in the standard high-dimensional regimes where those bounds apply; the shifted logarithms and outer minimum make the upper bound valid without additional parameter assumptions. The construction starts from a selection-only private multiplicative weights transcript, then replaces its probability mass function by a distance-penalized likelihood envelope. To prove that the modification preserves accuracy, a likelihood-level Maurey argument upper-bounds each Hamming-ball maximum by a small family of auxiliary PMW laws. Renyi moment bounds control nearby balls, a direct mixture bound controls distant balls, and grouping radii at the privacy scale prevents an additional $1/\varepsilon$ factor in the error. The mechanism is information-theoretic. A companion Lean 4 development machine-checks the finite construction, pure privacy after deterministic decoding, and the displayed all-regimes upper bound.

Authors: Rajesh Jayaram, Honghao Lin, Vahab Mirrokni, David P. Woodruff

Multi-vector embeddings represent items by point clouds and compare query and document point clouds using Chamfer similarity, whereas single-vector embeddings use ordinary inner products. For singleton queries, Chamfer becomes maximum inner product similarity (MAX-IP). In our setting, MUVERA gives dimension $m^{O(1/\varepsilon^2)}$~\cite{dhulipala2024muvera}, whereas the previous lower bound $(\varepsilon^2m)^{Ω(1/\varepsilon)}$~\cite{jayaram2026expressive} left a gap between $1/\varepsilon$ and $1/\varepsilon^2$ in the exponent of $m$. We nearly close this gap. For every fixed $δ\in(0,1)$, there are constants $A_δ,c_δ>0$ such that, for all sufficiently small $\varepsilon>0$ and every $m\ge(1/\varepsilon)^{A_δ}$, there exist unit query vectors and document point clouds of at most $m$ unit vectors for which every single-vector approximation of all pairwise MAX-IP values to additive error $\varepsilon$ has dimension \[ D \ge m^{c_δ/\varepsilon^{2-2δ}}. \] This holds even for fully data-dependent representations chosen after seeing the dataset. It also applies to Chamfer because all queries are singletons. Since $δ$ can be arbitrarily small, the exponent approaches the $O(1/\varepsilon^2)$ dependence of the upper bound. The proof combines Sherstov's pattern matrix method with polynomial-size, constant-width DNF formulas computing functions of approximate degree $Ω(k^{1-δ})$. Uniform-width padding and a block encoding create an $Ω(\varepsilon)$ gap. A dummy coordinate then equalizes all false inputs, yielding a unit-sphere MAX-IP matrix that is an exact two-valued affine image of the DNF pattern matrix with gap at least $8\varepsilon$. This allows the approximate-rank bound to apply.

Authors: Kostas Lakis, Johannes Lengler, Adeline Pittet

We study distributed vertex colouring on Hyperbolic Random Graphs (HRGs), a geometric random graph model capturing key structural features of real-world networks. This provides a natural setting for analysing distributed algorithms beyond worst-case general graphs. We introduce Sequential Radial Colouring, a CONGEST algorithm using only efficient local computation. The algorithm achieves a near-optimal palette, colouring HRGs with $\frac{4}{3}χ$ colours and running in $O((\log\log n)^2)$ rounds a.a.s. We also give a variant that speeds this up to $O(\log\log n)$ rounds a.a.s., at the price of using $O(χ\log\log n)$ colours. Finally, for every constant $\varepsilon>0$, it runs in $O(1)$ rounds a.a.s. when $χ^{1+\varepsilon}$ colours are used. This greatly reduces the number of colours over the previous constant-round algorithm of Maus and Ruff (SODA 2026) by a factor of at least $n^{1/6}$. Our analysis contains a phase in which we consider a classical randomised colouring protocol on a (large) clique of the graph. We also delve deeper into this part of the analysis and improve upon previous results for colouring a clique $C$, bounding the number of rounds required as a function of the additive slack $s = |Ψ| - χ$, where $Ψ$ is the set of colours used. In particular, constant-round colouring is possible if and only if $s=|C|^{1+Ω(1)}$, while $s=|C|/\log |C|$ already gives the optimal $Θ(\log\log |C|)$ round complexity.

Authors: Diego Arroyuelo, Aidan Hogan, Gonzalo Navarro, Juan Reutter

We study how to evaluate basic graph patterns (BGPs) in a worst-case-optimal (wco) manner over {\em temporal} labeled graphs, where edges have an interval of temporal validity. We adopt a flexible query language in which users specify m quads of the form (subject, property, object, time), using constants or variables. The time component denotes the instant at which a particular edge is valid, and users may also include order relations between temporal constants or variables. The answer is the set of all valid variable assignments, including time. We describe an index structure that, for a temporal graph with N edges, requires O(N) space and can evaluate extended BGPs in wco time O(Q* m log N), where Q* represents the maximum number of solutions for query Q over any temporal graph with the same number of instants of edge validity. We use our index to adapt Leapfrog Triejoin to the temporal graph setting under any variable evaluation ordering. Our index further yields wco guarantees for related query types, including snapshot evaluation, version queries, and other temporal variants. Experiments on real-world datasets show that our approach answers realistic queries in milliseconds with low space overhead.

Authors: Sina Kalantarzadeh, Kanstantin Pashkovich

Prophet inequalities are a fundamental model for online decision-making under uncertainty. For matroid constraints, Kleinberg and Weinberg gave a tight $1/2$-approximation, but their algorithm uses adaptive thresholds that depend on the previously accepted elements. Specifically, the mechanism of Kleinberg and Weinberg accepts an arriving element if and only if it is feasible to add with respect to the matroid constraint and the value of the arriving element passes its threshold; but this threshold depends on the elements accepted so far and on the arriving element itself. Later, Feldman, Svensson, and Zenklusen showed that one can give a $1/4$-approximation for general matroids. Their algorithm is almost non-adaptive, i.e., it uses non-adaptive thresholds but changes the underlying matroid to another ``stricter'' matroid. Feldman, Svensson, and Zenklusen also showed that no constant approximation is possible in general matroids using non-adaptive thresholds if one does not change the underlying matroid. We give a new almost non-adaptive algorithm for matroid prophet inequalities that achieves a $1/2$ guarantee. We change the underlying matroid to a ``stricter'' new matroid that is a direct sum of several matroids. For each part of the new matroid, we precompute a single non-adaptive threshold. Once the elements start to arrive, we accept an arriving element as long as it is feasible with respect to the new ``stricter'' matroid and its value passes the precomputed threshold. In addition, we guarantee that our algorithm achieves the $1/2$ guarantee not simply with respect to the prophet's expected gain, but with respect to the stronger ex-ante relaxation value. Thus, we provide the first almost non-adaptive algorithm for the matroid prophet inequality that achieves the best-possible approximation guarantee of $1/2$.

Authors: Abhijeet Sahu, Harmit Singh, Soham Nandy, G. Ramakrishna

Spanning trees are fundamental structures in graph theory, essential for various applications such as network maintenance, routing adjustments, and many more. The dynamic nature of real-world networks requires efficient updates to these structures as the underlying graph evolves. Maintaining rooted spanning trees dynamically is particularly crucial for algorithms addressing 2-connected components and minimum-weighted spanning trees. In this paper, we address the challenge of maintaining a rooted spanning forest when a batch of edges are inserted or deleted. We present four novel fully dynamic parallel algorithms to update the spanning forest without reconstructing it from scratch. To the best of our knowledge, parallel algorithms for this problem remain largely unexplored. Our experiments on a diverse collection of real-world graphs using a GPU environment demonstrate a throughput of 2 million insertions and 1.4 million deletions per second, significantly outperforming state-of-the-art parallel static algorithms.