Theory of Computing Report

This is the fifth post of this type (I (2008); II(2011); III(2015); IV(2024)).

Between Boise and Tel Aviv

During the summer we spent two months in the lovely city of Boise, Idaho. We stayed with my son Hagai and his husband Felix, their one-and-a-half-year-old son Yonatan, and—one week after our arrival—their second son, Rafael, was born. I was visiting Boise State University and was hosted by Zach Teitler, whom I first met many years ago at Texas A&M.

Boise is a beautiful city with wonderful parks, and Mazi and I also devoted a week to visiting Yellowstone for the first time.

On the flight back with Hagai, Rafael, Mazi, and Yonatan

Ceasefire in Gaza

On September 29, 2025, US president Donald Trump put forward a 21-point plan for a ceasefire in Gaza, as part of a broader initiative toward peace in the Middle East. The plan was endorsed by many world leaders, including Arab and Muslim leaders, as well as by the Israeli government headed by Benjamin Netanyahu. On October 9, an agreement was reached between Israel and Hamas on a ceasefire, a partial withdrawal of Israeli forces, and the release of kidnapped Israelis. On October 13, all living kidnapped Israelis were released. By January 27, 2026, all bodies of Israelis were returned.

The end of this terrible war is certainly a source of relief and hope. Still, we are living in dangerous and tragic times, with much uncertainty.

My 70th Birthday

We landed back in Tel Aviv on October 1, the eve of Yom Kippur. The following day—somewhat to my surprise—was my 70th birthday. Two weeks later, on Simchat Torah (October 14), we gathered to celebrate the holiday, the birthday, the new family member, and the end of the war. Being 70 years old feels sort of strange. 

Nostalgia Corner and Congratulations to Benjy Weiss

“secretly jubilant” 

I recently found, in my sister’s home (where we both lived as children), a Jerusalem Post article from 1970 about the Israeli Mathematical Olympiad. In that competition I received a consolation prize, while my friend Ron Donagi received the first price. Here is a quote from the article: ” ‘The prize is much more than I expected,’ stated an apparently indifferent yet secretly jubilant Gil.”

The reporter, Mark Daniel Sacks, also expressed his wish for similar encouragement for “those of us who are interested in literature, poetry, philosophy, and art.” I fully agree!

A few months earlier, in the fall of 1969, I began attending Benjy Weiss’s year-long mathematics course for high-school students, together with 20–25 other students, including Yehuda Agnon, Michael Ben-Or, Rami Grossberg (see comment below), Ehud Lehrer, Uzi Segal , Yonatan Stern, and Mike Werman. The course was an eye-opener for all of us.

It has just been announced that our teacher, Benjy Weiss, has won the 2026 Israel Prize in Mathematics. Heartfelt congratulations, Benjy!

Problems, Problems 

Over the years I have devoted quite a few posts—here, on other blogs, and on MathOverflow—to open problems. In 2013, at the Erdős Centennial conference, I gave a lecture on old and new problems, mainly in combinatorics and geometry (here are the slides), where I presented twenty problems that are also listed in this post. Since then, there has been substantial progress, and in some cases full solutions, for roughly 30% of them.  

I gradually plan, somewhat in Erdős’ tradition, to upgrade my problem posts and lectures into papers.

So far, in 2015 I wrote a paper around Borsuk’s problem. (Some of the problems appeared in these posts.) In 2022, Imre Barany and I wrote a survey article on Helly-type problems, which was nicely accepted.  I am currently writing a paper about the diameter problem for graphs of polytopes. We devoted many posts—and Polymath 3—to this problem, and I plan to submit the paper to the new and splendid journal JOMP: the Journal of Open Math Problems.

Geometric Combinatorics

There are many open problems that I like—and quite a few that I myself posed—concerning the combinatorial theory of convex polytopes, face numbers of polytopes, and related cellular objects. This post from 2008 lists five elementary problems and since then one problem was solved. One outstanding problem in the field that I like is whether triangulated spheres are determined from their dual graphs. This is known for simplicial polytopes (see this post from 2009) and was recently proved for all shellable simplicial spheres by  Yirong Yang in her paper Reconstructing a Shellable Sphere from its Facet-Ridge Graph. 

Let me mention two problems from other areas of combinatorial geometry.

Two triangles are called almost disjoint if they are either disjoint or their intersection consists of one common vertex. Let f(n) denote the maximum number of pairwise almost disjoint triangles that can be found on some vertex set of n points in 3-space. How large can f(n) be? It is easy to see that f(n) is at most quadratic in and the best lower bound from 2002 by Karolyi and Solmyosi is .  There is a related work from 2017 by Solmyosi and Wong. 

In 1995, Nati Linial and I conjectured that the kissing number for lattice sphere packings in is subexponential in . The highest known kissing number behaves like . Our problem was related to the question of finding upper bounds for the density of sphere packings in high dimension. Recent celebrated work of Klartag shows an intriguing connection between kissing numbers and lower bounds on sphere-packing density.

Analysis of Boolean Functions and Probabilistic Combinatorics

In a draft paper from 2000 (which I mostly distributed privately), I listed 18 interesting phenomena and 23 problems around these phenomena related to Boolean functions and their Fourier expansion. Since then there were many developments in the analysis of Boolean functions. Here is a comprehensive list of open problems from 2014. One problem in the list was recently solved by GPT5. I myself posed quite a few problems in this area but let me mention today the still open Aaronson-Ambainis conjecture from 2008: for every function of degree at most , there exists a variable with influence at least , for some constant .  stands for the variance of . 

In probabilistic combinatorics, the “Kahn-Kalai conjecture” from our 2006 paper has been famously solved by Park and Pham and a second conjecture about graphs was settled – up to factor by Dubroff, Kahn, and Park. 

Jeff Kahn and I regarded the conjecture as outrageous—and likely false—but in that paper we formulated several specific conjectures (in the area of discrete isoperimetric inequalities) as part of a broader program for proving it. In spite of some substantial progress, these conjecture remain largely open, although a few have been refuted. One of those conjectures is presented in this MO post. In principle, the Kruskal-Katona theorem should suffice to settle this problem, but still we cannot solve it. 

Extremal Combinatorics

One question I asked—independently also posed by Karen Meagher—concerned the independence numbers of intersection graphs of triangulations. This conjecture is still open and it admits a lovely generalization for a large class of polytopes. Recently, Anton Molnar, Cosmin Pohoata, Michael Zheng, and Daniel G. Zhu raised the question of finding the chromatic number of the intersection graphs of triangulations—and solved it! They showed that the Kneser graph of triangulations of a convex n-gon has chromatic number . 

Computation Complexity and Number Theory

Around 2010, I formulated several conjectures relating computational complexity and number theory, which led to some very nice developments. Together with Mrinal Kumar and Ben Lee Volk, I plan to write a paper with further problems connecting algebraic circuit complexity and number theory.

Two Outrageous Conjectures

Here are two very outrageous conjectures that may well admit simple refutations.(Comments are welcome; the right thing to do would be to devote a separate post to each of then, stay tuned.)  

The first outrageous conjecture is presented in this slide from a 2024 lecture. 

See also this MO question and this one.

The second vague and outrageous conjecture (already mentioned earlier in this post) is about computational complexity and more precisely about Papadimitriou’s computational hierarchy for mathematical proofs. It asserts that theorems guaranteeing the existence  (for sure, not just with high probability) of combinatorial structures and whose proofs are based on the probabilistic method,  are accompanied by an efficient algorithm (possibly randomized) for finding this structures.  (In other words, the probabilistic method does not lead to a new Papadimitriou class beyond P.)

Quantum Information and Quantum Physics

It is likely that the proportion of posts dealing with quantum computing and quantum physics will increase. So far, they account for about 8% of all posts since I began blogging. My interest in this area has branched into several related directions.

The Argument Against Quantum Computing

The direction closest to my heart is the argument against quantum computing. I have invested considerable effort in explaining and discussing my theory for why quantum computers are inherently impossible—through papers, lectures, debates, and blog posts. I try not to oversell the case, and I think that ultimately, experiments are likely to provide the clearest way to decide the matter.

Correlated Errors 

A related but distinct issue concerns the modeling of correlated errors, which was central in my research between 2005 and 2012, and more generally the behavior (and modeling) of noisy quantum systems that do not exhibit quantum fault tolerance. Here too, experiments and simulations can provide significant insight, and my (admittedly bold) conjectures about error correlations could be tested directly.

Statistical Analysis of Experimental Data

Another topic is the statistical analysis of current experimental data. With my coauthors we devoted substantial effort to analyzing Google’s 2019 experiment, and I believe more can be done to clarify and explain the findings of our papers. Our long-going project is closely related to developing statistical tools for analyzing quantum measurements and modeling noise. A recent paper on this topic by another group is: How much can we learn from quantum random circuit sampling? by Manole et al.

Quantum Puzzles

I also plan a series of posts devoted to quantum puzzles related to quantum information and computation. The first post concerned Majorana zero modes. Whether Majorana zero modes can in fact be created remains a major mystery in physics, and I personally suspect the answer may be negative. (As with “quantum supremacy,” their realization has been claimed by several research groups.) Planned follow-up posts will address quantum cryptography and the time–energy uncertainty principle.

Free Will

I plan to return to the fascinating connections between quantum physics, computation, and free will. I wrote a paper on this topic in 2021, and we discussed it in this blog post. Since then, I participated in two conferences in Nazareth, in 2022 and 2024, devoted to free will (here are the videotaped lectures – in Hebrew). Following these conference and my paper, I have had many stimulating discussions with colleagues from a wide variety of disciplines. 

Is Quantum Computational Advantage Manifested by Nature? Has it been Achieved by Experiments?

This question lies at the heart of the matter and connects to all the topics above. In a recent lecture, Yosi Avron mentioned an argument—possibly going back to Feynman—that quantum physics in Nature already exhibits “quantum supremacy”: computing the magnetic moments of the proton or neutron from first principles is extraordinarily difficult and yields estimates far from experimental values, yet protons and neutrons “compute” their magnetic moments effortlessly. In the same lecture, delivered at a celebratory meeting for the 100th anniversary of quantum mechanics at the Open University in Ra’anana, Yosi also argued that no country can afford to lag behind in quantum computation, drawing an analogy with nuclear capabilities.

Computers, AI and Mathematics

Like many others, I plan to experiment with modern AI tools in the hope of using them for meaningful mathematical research. I am cautiously optimistic—perhaps naïve. Let’s see how it goes.

Pictures

  

 

 

 

 

 

Top row: Boise with Zach Teitler, Alexander Woo and Bruce Sagan’s classical book, and with local convex polytopes. Second row:  sightseeing near Boise. Third, fourth, and fifth rows: Yellowstone. Sixth row: Yonatan in Boise. Seventh row: Mazi and I with Ilan and Yoav in Tel Aviv. 

 

 

By Gil Kalai

This is a live blog of Lecture 2 of my graduate seminar “Feedback, Learning, and Adaptation.” A table of contents is here.

The analysis in the last post hinted that we can use calculus to analyze the local behavior of a homeostatic system around its setpoint. I wrote up the details in these lecture notes. As long as the first terms of the Taylor series provide a reasonable approximation of the equations that define the dynamical system, we can use linear algebra to reason about how a homeostatic system maintains its steady state.

The problem with this analysis by linear proxy is that we need to somehow account for the error in the approximation. Such bookkeeping tends to be much more annoying. Determining the region of state space under which a Taylor series is accurate always amounts to frustrating calculations. These calculations also tend to be highly tuned to the particulars of the differential structure of the model. If the model slightly changes, you have to start all over again and rederive new error bounds.

To get around this sort of linear proxy analysis. Lyapunov invented an alternative method, called his second method or his direct method (I got the direct and indirect methods confused yesterday). To avoid having to create a mnemonic for what direct and indirect mean, I’m going to switch to descriptive terms for Lyapunov’s two methods: the method of linearization and the method of potential functions.

The method of potential functions is inspired by physics. The goal is to define a notion of “energy” for any possible state, and then show that energy dissipates as the dynamics unravel into the future. Mathematically, the method seeks a function that maps states to positive scalars. This function should be large far from the fixed point. It should equal zero at the fixed point and only at the fixed point. And the function should decrease along the trajectories of the dynamical system. In other words, the function must take on a lower value at time t+1 than it held at time t. Such a function is called a potential function (also often called a Lyapunov function).

You can already see that this construction should verify convergence to the fixed point. If potential decreases at every time step but is always positive, it eventually has to get to zero. The only place where the potential is zero is the fixed point. Therefore, the system has to converge to the fixed point. You can make this as rigorous as you’d like, but I find the intuition here easier than thinking about linearizations.

Proofs using potential functions are easy. Finding potential functions is hard. It’s an interesting mathematical maneuver: we have a proof technique that always works as long as you produce a particular certificate (the potential function). We thus shift the burden of proof to finding and verifying that the certificate satisfies a list of desiderata. This turns proof into a constraint satisfaction problem, one that is amenable to computer search.

Let me give a simple case in linear systems that demonstrates how this logical transformation works. We’ll do much more interesting nonlinear cases in the next class.

Suppose we’d like to show all trajectories of a linear dynamical system

converge to zero. From your first class on controls, you know that you can just compute the eigenvalues of A and make sure their magnitudes are all less than one. But let’s find a potential function that also certifies convergence. I need a family of functions that are positive everywhere except at the origin, where they are equal to zero. One simple family would be the strongly convex quadratics,

where P is a positive definite matrix with all eigenvalues greater than zero. If I want to show that the potential decreases along trajectories, I need

for all x. This is equivalent to the matrix inequality

I have reduced stability analysis to solving a system of linear matrix inequalities. The set of Lyapunov functions of this form is convex. And you can use techniques from convex optimization to search for the potential function.

Now, as written so far, this seems to have turned an annoying linear algebra problem (computing eigenvalues) into an annoying convex optimization problem (semidefinite programming). Fair! But the potential function method is far more extensible. For example, suppose the system were uncertain and could evolve according to either A1 or A2 at any given time. Then you can try to find a potential function that certifies both matrices. If one exists, then the global system will be stable, even if it’s switching. The appeal of the potential function method is this sort of robustness. It lets us handle inaccurate or uncertain dynamics in ways that linearization doesn’t. In the next lecture, we’ll apply these ideas to PID controllers and draw some interesting connections between analyzing the most ubiquitous control policies and the most ubiquitous optimization methods.

Subscribe now

By Ben Recht

We study systems of linear equations modulo two in $n$ variables with three variables in each equation. We assume that the system has a solution with $pn$ variables taking the value 1 for some value $00$ it is hard to find a solution of the same weight that satisfies at least a fraction $c_p +\delta$ of the equations. The constant $c_p$ is upper bounded by $.9$ for any value of $p$.

Authors: Xiaowei Ye, Xiaoyu He, Chao Liao, Chen Wu, Pinyan Lu

Transformers serve as the foundation of most modern large language models. To mitigate the quadratic complexity of standard full attention, various efficient attention mechanisms, such as linear and hybrid attention, have been developed. A fundamental gap remains: their expressive power relative to full attention lacks a rigorous theoretical characterization. In this work, we theoretically characterize the performance differences among these attention mechanisms. Our theory applies to all linear attention variants that can be formulated as a recurrence, including Mamba, DeltaNet, etc. Specifically, we establish an expressiveness hierarchy: for the sequential function composition-a multi-step reasoning task that must occur within a model's forward pass, an ($L+1$)-layer full attention network is sufficient, whereas any hybrid network interleaving $L-1$ layers of full attention with a substantially larger number ($2^{3L^2}$) of linear attention layers cannot solve it. This result demonstrates a clear separation in expressive power between the two types of attention. Our work provides the first provable separation between hybrid attention and standard full attention, offering a theoretical perspective for understanding the fundamental capabilities and limitations of different attention mechanisms.

Authors: Noor Islam S. Mohammad

This paper introduces bucket calculus, a novel mathematical framework that fundamentally transforms the computational complexity landscape of parallel machine scheduling optimization. We address the strongly NP-hard problem $P2|r_j|C_{\max}$ through an innovative adaptive temporal discretization methodology that achieves exponential complexity reduction from $O(T^n)$ to $O(B^n)$ where $B \ll T$, while maintaining near-optimal solution quality. Our bucket-indexed mixed-integer linear programming (MILP) formulation exploits dimensional complexity heterogeneity through precision-aware discretization, reducing decision variables by 94.4\% and achieving a theoretical speedup factor $2.75 \times 10^{37}$ for 20-job instances. Theoretical contributions include partial discretization theory, fractional bucket calculus operators, and quantum-inspired mechanisms for temporal constraint modeling. Empirical validation on instances with 20--400 jobs demonstrates 97.6\% resource utilization, near-perfect load balancing ($σ/μ= 0.006$), and sustained performance across problem scales with optimality gaps below 5.1\%. This work represents a paradigm shift from fine-grained temporal discretization to multi-resolution precision allocation, bridging the fundamental gap between exact optimization and computational tractability for industrial-scale NP-hard scheduling problems.

Authors: Sai Soumya Nalli, Karthikeya Polisetty, Jayalal Sarma

Given an $n$-bit Boolean function with a complexity measure (such as block sensitivity, query complexity, etc.) $M(f) = k$, the hardness condensation question asks whether $f$ can be restricted to $O(k)$ variables such that the complexity measure is $Ω(k)$? In this work, we study the condensability of block sensitivity, certificate complexity, AND (and OR) query complexity and Fourier sparsity. We show that block sensitivity does not condense under restrictions, unlike sensitivity: there exists a Boolean function $f$ with query complexity $k$ such that any restriction of $f$ to $O(k)$ variables has block sensitivity $O(k^{\frac{2}{3}})$. This answers an open question in Göös, Newman, Riazanov, and Sokolov (2024) in the negative. The same function yields an analogous incondensable result for certificate complexity. We further show that $\mathsf{AND}$(and $\mathsf{OR}$) decision trees are also incondensable. In contrast, we prove that Fourier sparsity admits a weak form of condensation.

Authors: Manuel Bodirsky, Armin Weiß

We show that the metaproblem for coset-generating polymorphisms is NP-complete, answering a question of Chen and Larose: given a finite structure, the computational question is whether this structure has a polymorphism of the form $(x,y,z) \mapsto x y^{-1} z$ with respect to some group; such operations are also called coset-generating, or heaps. Furthermore, we introduce a promise version of the metaproblem, parametrised by two polymorphism conditions $Σ_1$ and $Σ_2$ and defined analogously to the promise constraint satisfaction problem. We give sufficient conditions under which the promise metaproblem for $(Σ_1,Σ_2)$ is in P and under which it is NP-hard. In particular, the promise metaproblem is in P if $Σ_1$ states the existence of a Maltsev polymorphism and $Σ_2$ states the existence of an abelian heap polymorphism -- despite the fact that neither the metaproblem for $Σ_1$ nor the metaproblem for $Σ_2$ is known to be in P. We also show that the creation-metaproblem for Maltsev polymorphisms, under the promise that a heap polymorphism exists, is in P if and only if there is a uniform polynomial-time algorithm for CSPs with a heap polymorphism.

Authors: Chandrima Kayal, Rajat Mittal, Manaswi Paraashar, Nitin Saurabh

For any Boolean function $f:\{0,1\}^n \to \{0,1\}$ with a complexity measure having value $k \ll n$, is it possible to restrict the function $f$ to $Θ(k)$ variables while keeping the complexity preserved at $Θ(k)$? This question, in the context of query complexity, was recently studied by G{ö}{ö}s, Newman, Riazanov and Sokolov (STOC 2024). They showed, among other results, that query complexity can not be condensed losslessly. They asked if complexity measures like block sensitivity or unambiguous certificate complexity can be condensed losslessly? In this work, we show that decision tree measures like block sensitivity and certificate complexity, cannot be condensed losslessly. That is, there exists a Boolean function $f$ such that any restriction of $f$ to $O(\mathcal{M}(f))$ variables has $\mathcal{M}(\cdot)$-complexity at most $\tilde{O}(\mathcal{M}(f)^{2/3})$, where $\mathcal{M} \in \{\mathsf{bs},\mathsf{fbs},\mathsf{C},\mathsf{D}\}$. This also improves upon a result of G{ö}{ö}s, Newman, Riazanov and Sokolov (STOC 2024). We also complement the negative results on lossless condensation with positive results about lossy condensation. In particular, we show that for every Boolean function $f$ there exists a restriction of $f$ to $O(\mathcal{M}(f))$ variables such that its $\mathcal{M}(\cdot)$-complexity is at least $Ω(\mathcal{M}(f)^{1/2})$, where $\mathcal{M} \in \{\mathsf{bs},\mathsf{fbs},\mathsf{C},\mathsf{UC}_{min},\mathsf{UC}_1,\mathsf{UC},\mathsf{D},\widetilde{\mathsf{deg}},λ\}$. We also show a slightly weaker positive result for randomized and quantum query complexity.

Authors: Prateek P. Kulkarni

We establish tight connections between entanglement entropy and the approximation error in Trotter-Suzuki product formulas for Hamiltonian simulation. Product formulas remain the workhorse of quantum simulation on near-term devices, yet standard error analyses yield worst-case bounds that can vastly overestimate the resources required for structured problems. For systems governed by geometrically local Hamiltonians with maximum entanglement entropy $S_\text{max}$ across all bipartitions, we prove that the first-order Trotter error scales as $\mathcal{O}(t^2 S_\text{max} \operatorname{polylog}(n)/r)$ rather than the worst-case $\mathcal{O}(t^2 n/r)$, where $n$ is the system size and $r$ is the number of Trotter steps. This yields improvements of $\tildeΩ(n^2)$ for one-dimensional area-law systems and $\tildeΩ(n^{3/2})$ for two-dimensional systems. We extend these bounds to higher-order Suzuki formulas, where the improvement factor involves $2^{pS^*/2}$ for the $p$-th order formula. We further establish a separation result demonstrating that volume-law entangled systems fundamentally require $\tildeΩ(n)$ more Trotter steps than area-law systems to achieve the same precision. This separation is tight up to logarithmic factors. Our analysis combines Lieb-Robinson bounds for locality, tensor network representations for entanglement structure, and novel commutator-entropy inequalities that bound the expectation value of nested commutators by the Schmidt rank of the state. These results have immediate applications to quantum chemistry, condensed matter simulation, and resource estimation for fault-tolerant quantum computing.

Authors: Fabian Egidy

We investigate the following longstanding open questions raised by Krajíček and Pudlák (J. Symb. L. 1989), Sadowski (FCT 1997), Köbler and Messner (CCC 1998) and Messner (PhD 2000). Q1: Does TAUT have (p-)optimal proof systems? Q2: Does QBF have (p-)optimal proof systems? Q3: Are there arbitrarily complex sets with (p-)optimal proof systems? Recently, Egidy and Glaßer (STOC 2025) contributed to these questions by constructing oracles that show that there are no relativizable proofs for positive answers of these questions, even when assuming well-established conjectures about the separation of complexity classes. We continue this line of research by providing the same proof barrier for negative answers of these questions. For this, we introduce the SPARSE-relativization framework, which is an application of the notion of bounded relativization by Hirahara, Lu, and Ren (CCC 2023). This framework allows the construction of sparse oracles for statements such that additional useful properties (like an infinite polynomial-time hierarchy) hold. By applying the SPARSE-relativization framework, we show that the oracle construction of Egidy and Glaßer also yields the following new oracle. O1: No set in PSPACE\NP has optimal proof systems, $\mathrm{NP} \subsetneq \mathrm{PH} \subsetneq \mathrm{PSPACE}$, and PH collapses We use techniques of Cook and Krajíček (J. Symb. L. 2007) and Beyersdorff, Köbler, and Müller (Inf. Comp. 2011) and apply our SPARSE-relativization framework to obtain the following new oracle. O2: All sets in PSPACE have p-optimal proof systems, there are arbitrarily complex sets with p-optimal proof systems, and PH is infinite Together with previous results, our oracles show that questions Q1 and Q2 are independent of an infinite or collapsing polynomial-time hierarchy.

Authors: Ashutosh Rai, Soumyashree Rana

A dominating set of a graph G(V, E) is a set of vertices D\subseteq V such that every vertex in V\D has a neighbor in D. An eternal dominating set extends this concept by placing mobile guards on the vertices of D. In response to an infinite sequence of attacks on unoccupied vertices, a guard can move to the attacked vertex from an adjacent position, ensuring that the new guards configuration remains a dominating set. In the one (all) guard(s) move model, only one (multiple) guard(s) moves(may move) per attack. The set of vertices representing the initial configuration of guards in one(all) guard move model is the eternal dominating set (m-eternal dominating set) of G. The minimum size of such a set in one(all) guard move model is called the eternal domination number (m-eternal domination number) of G, respectively. Given a graph G and an integer k, the m-Eternal Dominating Set asks whether G has an m-eternal dominating set of size at most k. In this work, we focus mainly on the computational complexity of m-Eternal Dominating Set in subclasses of chordal graphs. For split graphs, we show a dichotomy result by first designing a polynomial-time algorithm for K1,t-free split graphs with t\le 4, and then proving that the problem becomes NP-complete for t\ge 5. We showed that the problem is NP-hard on undirected path graphs. Moreover, we exhibit the computational complexity difference between the variants by showing the existence of two graph classes such that, in one, both Dominating Set and m-Eternal Dominating Set are solvable in polynomial time while Eternal Dominating Set is NP-hard, whereas in the other, Eternal Dominating Set is solvable in polynomial time and both Dominating Set and m-Eternal Dominating Set are NP-hard. Finally, we present a graph class where Dominating Set is NP-hard, but m-Eternal Dominating Set is efficiently solvable.

Authors: Sujoy Bhore, Liana Khazaliya, Fionn Mc Inerney

Kirkpatrick et al. [ALT 2019] and Fallat et al. [JMLR 2023] introduced non-clashing teaching and proved that it is the most efficient batch machine teaching model satisfying the collusion-avoidance benchmark established in the seminal work of Goldman and Mathias [COLT 1993]. Recently, (positive) non-clashing teaching was thoroughly studied for balls in graphs, yielding numerous algorithmic and combinatorial results. In particular, Chalopin et al. [COLT 2024] and Ganian et al. [ICLR 2025] gave an almost complete picture of the complexity landscape of the positive variant, showing that it is tractable only for restricted graph classes due to the non-trivial nature of the problem and concept class. In this work, we consider (positive) non-clashing teaching for closed neighborhoods in graphs. This concept class is not only extensively studied in various related contexts, but it also exhibits broad generality, as any finite binary concept class can be equivalently represented by a set of closed neighborhoods in a graph. In comparison to the works on balls in graphs, we provide improved algorithmic results, notably including FPT algorithms for more general classes of parameters, and we complement these results by deriving stronger lower bounds. Lastly, we obtain combinatorial upper bounds for wider classes of graphs.

Authors: Ajinkya Gaikwad, Soumen Maity, Leeja R

We study the parameterized complexity of the T(h+1)-Free Edge Deletion problem. Given a graph G and integers k and h, the task is to delete at most k edges so that every connected component of the resulting graph has size at most h. The problem is NP-complete for every fixed h at least 3, while it is solvable in polynomial time for h at most 2. Recent work showed strong hardness barriers: the problem is W[1]-hard when parameterized by the solution size together with the size of a feedback edge set, ruling out fixed-parameter tractability for many classical structural parameters. We significantly strengthen these negative results by proving W[1]-hardness when parameterized by the vertex deletion distance to a disjoint union of paths, the vertex deletion distance to a disjoint union of stars, or the twin cover number. These results unify and extend known hardness results for treewidth, pathwidth, and feedback vertex set, and show that several restrictive parameters, including treedepth, cluster vertex deletion number, and modular width, do not yield fixed-parameter tractability when h is unbounded. On the positive side, we identify parameterizations that restore tractability. We show that the problem is fixed-parameter tractable when parameterized by cluster vertex deletion together with h, and also when parameterized by neighborhood diversity together with h via an integer linear programming formulation. We further present a fixed-parameter tractable bicriteria approximation algorithm parameterized by k. Finally, we show that the problem admits fixed-parameter tractable algorithms on split graphs and interval graphs, and we establish hardness for a directed generalization even on directed acyclic graphs.

Authors: Haitao Wang

Given a set of $n$ circular arcs of the same radius in the plane, we consider the problem of computing the number of intersections among the arcs. The problem was studied before and the previously best algorithm solves the problem in $O(n^{4/3+ε})$ time [Agarwal, Pellegrini, and Sharir, SIAM J. Comput., 1993], for any constant $ε>0$. No progress has been made on the problem for more than 30 years. We present a new algorithm of $O(n^{4/3}\log^{16/3}n)$ time and improve it to $O(n^{1+ε}+K^{1/3}n^{2/3}(\frac{n^2}{n+K})^ε\log^{16/3}n)$ time for small $K$, where $K$ is the number of intersections of all arcs.

Authors: Luis M. B. Varona

An unweighted, undirected graph $G$ on $n$ nodes is said to have \emph{bandwidth} at most $k$ if its nodes can be labelled from $0$ to $n - 1$ such that no two adjacent nodes have labels that differ by more than $k$. It is known that one can decide whether the bandwidth of $G$ is at most $k$ in $O(n^k)$ time and $O(n^k)$ space using dynamic programming techniques. For small $k$ close to $0$, this approach is effectively polynomial, but as $k$ scales with $n$, it becomes superexponential, requiring up to $O(n^{n - 1})$ time (where $n - 1$ is the maximum possible bandwidth). In this paper, we reformulate the problem in terms of bipartite matching for sufficiently large $k \ge \lfloor (n - 1)/2 \rfloor$, allowing us to use Hall's marriage theorem to develop an algorithm that runs in $O(n^{n - k + 1})$ time and $O(n)$ auxiliary space (beyond storage of the input graph). This yields polynomial complexity for large $k$ close to $n - 1$, demonstrating that the bandwidth recognition problem is solvable in polynomial time whenever either $k$ or $n - k$ remains small.

Authors: Taihei Oki, Shinsaku Sakaue

We study online inverse linear optimization, also known as contextual recommendation, where a learner sequentially infers an agent's hidden objective vector from observed optimal actions over feasible sets that change over time. The learner aims to recommend actions that perform well under the agent's true objective, and the performance is measured by the regret, defined as the cumulative gap between the agent's optimal values and those achieved by the learner's recommended actions. Prior work has established a regret bound of $O(d\log T)$, as well as a finite but exponentially large bound of $\exp(O(d\log d))$, where $d$ is the dimension of the optimization problem and $T$ is the time horizon, while a regret lower bound of $Ω(d)$ is known (Gollapudi et al. 2021; Sakaue et al. 2025). Whether a finite regret bound polynomial in $d$ is achievable or not has remained an open question. We partially resolve this by showing that when the feasible sets are M-convex -- a broad class that includes matroids -- a finite regret bound of $O(d\log d)$ is possible. We achieve this by combining a structural characterization of optimal solutions on M-convex sets with a geometric volume argument. Moreover, we extend our approach to adversarially corrupted feedback in up to $C$ rounds. We obtain a regret bound of $O((C+1)d\log d)$ without prior knowledge of $C$, by monitoring directed graphs induced by the observed feedback to detect corruptions adaptively.

Authors: Caleb McFarland

We introduce the tree-decomposition-based parameter totally $Δ$-modular treewidth (TDM-treewidth) for matrices with two nonzero entries per row. We show how to solve integer programs whose matrices have bounded TDM-treewidth when variables are bounded. This extends previous graph-based decomposition parameters for matrices with at most two nonzero entries per row to include matrices with entries outside of $\{-1,0,1\}$. We also give an analogue of the Grid Theorem of Robertson and Seymour for matrices of bounded TDM-treewidth in the language of rooted signed graphs.

Authors: Miles Simmons, Ishan Bansal, Joe Cheriyan

In the Cover Small Cuts problem, we are given a capacitated (undirected) graph $G=(V,E,u)$ and a threshold value $λ$, as well as a set of links $L$ with end-nodes in $V$ and a non-negative cost for each link $\ell\in L$; the goal is to find a minimum-cost set of links such that each non-trivial cut of capacity less than $λ$ is covered by a link. Bansal, Cheriyan, Grout, and Ibrahimpur (arXiv:2209.11209, Algorithmica 2024) showed that the WGMV primal-dual algorithm, due to Williamson, Goemans, Mihail, and Vazirani (Combinatorica, 1995), achieves approximation ratio $16$ for the Cover Small Cuts problem; their analysis uses the notion of a pliable family of sets that satisfies a combinatorial property. Later, Bansal (arXiv:2308.15714v2, IPCO 2025) and then Nutov (arXiv:2504.03910, MFCS 2025) proved that the same algorithm achieves approximation ratio $6$. We show that the same algorithm achieves approximation ratio $5$, by using a stronger notion, namely, a pliable family of sets that satisfies symmetry and structural submodularity.

Authors: Arnav Khinvasara, Alexander Pikovski

Set partitions are arrangements of distinct objects into groups. The problem of listing all set partitions arises in a variety of settings, in particular in combinatorial optimization tasks. After a brief review, we give practical approximate formulas for determining the number of set partitions, both for small and large set sizes. Several algorithms for enumerating all set partitions are reviewed, and benchmarking tests were conducted. The algorithm of Djokic et al. is recommended for practical use.

Authors: Poonam Sharma, Suman Banerjee

Diffusion of information, innovation, and ideas is an important phenomenon in social networks. Information propagates through the network and reaches from one person to the next. In many settings, it is meaningful to restrict diffusion so that each node can spread information to only a limited number of its neighbors rather than to all of them. Such social networks are called closed social networks. In recent years, social media platforms have emerged as an effective medium for commercial entities, where the objective is to maximize profit. In this paper, we study the Profit Maximization in Closed Social Networks (PMCSN) problem in the context of viral marketing. The input to the problem is a closed social network and two positive integers $\ell$ and $B$. The problem asks to select seed nodes within a given budget $B$; during the diffusion process, each node is restricted to choose at most $\ell$ outgoing links for information diffusion; and the objective is to maximize the profit earned by the seed set. The PMCSN problem generalizes the Influence Maximization problem, which is NP-hard. We propose two solution approaches for PMCSN: a sampling-based approximate solution and a marginal-gain-based heuristic solution. We analyze the sample complexity, running time, and space requirements of the proposed approaches. We conduct experiments on real-world, publicly available social network datasets. The results show that the seed sets and diffusion links chosen by our methods yield higher profit than baseline methods. The implementation and data are available at \texttt{https://github.com/PoonamSharma-PY/ClosedNetwork}.

Authors: Poojan Shah, Shashwat Agrawal, Ragesh Jaiswal

We study beyond worst case analysis for the $k$-means problem where the goal is to model typical instances of $k$-means arising in practice. Existing theoretical approaches provide guarantees under certain assumptions on the optimal solutions to $k$-means, making them difficult to validate in practice. We propose the manifold hypothesis, where data obtained in ambient dimension $D$ concentrates around a low dimensional manifold of intrinsic dimension $d$, as a reasonable assumption to model real world clustering instances. We identify key geometric properties of datasets which have theoretically predictable scaling laws depending on the quantization exponent $\varepsilon = 2/d$ using techniques from optimum quantization theory. We show how to exploit these regularities to design a fast seeding method called $\operatorname{Qkmeans}$ which provides $O(ρ^{-2} \log k)$ approximate solutions to the $k$-means problem in time $O(nD) + \widetilde{O}(\varepsilon^{1+ρ}ρ^{-1}k^{1+γ})$; where the exponent $γ= \varepsilon + ρ$ for an input parameter $ρ< 1$. This allows us to obtain new runtime - quality tradeoffs. We perform a large scale empirical study across various domains to validate our theoretical predictions and algorithm performance to bridge theory and practice for beyond worst case data clustering.

Authors: Anxin Guo, Jingwei Li

Large language models often hallucinate with high confidence on "random facts" that lack inferable patterns. We formalize the memorization of such facts as a membership testing problem, unifying the discrete error metrics of Bloom filters with the continuous log-loss of LLMs. By analyzing this problem in the regime where facts are sparse in the universe of plausible claims, we establish a rate-distortion theorem: the optimal memory efficiency is characterized by the minimum KL divergence between score distributions on facts and non-facts. This theoretical framework provides a distinctive explanation for hallucination: even with optimal training, perfect data, and a simplified "closed world" setting, the information-theoretically optimal strategy under limited capacity is not to abstain or forget, but to assign high confidence to some non-facts, resulting in hallucination. We validate this theory empirically on synthetic data, showing that hallucinations persist as a natural consequence of lossy compression.

Authors: Zhao Song, Jianfei Xue, Jiahao Zhang, Lichen Zhang

Given the query, key and value matrices $Q, K, V\in \mathbb{R}^{n\times d}$, the attention module is defined as $\mathrm{Att}(Q, K, V)=D^{-1}AV$ where $A=\exp(QK^\top/\sqrt{d})$ with $\exp(\cdot)$ applied entrywise, $D=\mathrm{diag}(A{\bf 1}_n)$. The attention module is the backbone of modern transformers and large language models, but explicitly forming the softmax matrix $D^{-1}A$ incurs $Ω(n^2)$ time, motivating numerous approximation schemes that reduce runtime to $\widetilde O(nd)$ via sparsity or low-rank factorization. We propose a quantum data structure that approximates any row of $\mathrm{Att}(Q, K, V)$ using only row queries to $Q, K, V$. Our algorithm preprocesses these matrices in $\widetilde{O}\left( ε^{-1} n^{0.5} \left( s_λ^{2.5} + s_λ^{1.5} d + α^{0.5} d \right) \right)$ time, where $ε$ is the target accuracy, $s_λ$ is the $λ$-statistical dimension of the exponential kernel defined by $Q$ and $K$, and $α$ measures the row distortion of $V$ that is at most $d/{\rm srank}(V)$, the stable rank of $V$. Each row query can be answered in $\widetilde{O}(s_λ^2 + s_λd)$ time. To our knowledge, this is the first quantum data structure that approximates rows of the attention matrix in sublinear time with respect to $n$. Our approach relies on a quantum Nyström approximation of the exponential kernel, quantum multivariate mean estimation for computing $D$, and quantum leverage score sampling for the multiplication with $V$.

Authors: Christian Rosenke, Mark Scheibner

Inspired by the eponymous hobby, we introduce Miniature Painting as the computational problem to paint a given graph $G=(V,E)$ according to a prescribed template $t \colon V \rightarrow C$, which assigns colors $C$ to the vertices of $G$. In this setting, the goal is to realize the template using a shortest possible sequence of brush strokes, where each stroke overwrites a connected vertex subset with a color in $C$. We show that this problem is equivalent to a reversal of the well-studied Free Flood-It game, in which a colored graph is decolored into a single color using as few moves as possible. This equivalence allows known complexity results for Free Flood-It to be transferred directly to Miniature Painting, including NP-hardness under severe structural restrictions, such as when $G$ is a grid, a tree, or a split graph. Our main contribution is a polynomial-time algorithm for Miniature Painting on graphs that are free of induced co-gems, a graph class that strictly generalizes cographs. As a direct consequence, Free Flood-It is also polynomial-time solvable on co-gem-free graphs, independent of the initial coloring.

Authors: Wan Fokkink, Georgios Karlos, Andy Tatman

Safra's distributed termination detection algorithm employs a logical token ring structure within a distributed network; only passive nodes forward the token, and a counter in the token keeps track of the number of sent minus the number of received messages. We adapt this classic algorithm to make it fault-tolerant. The counter is split into counters per node, to discard counts from crashed nodes. If a node crashes, the token ring is restored locally and a backup token is sent. Nodes inform each other of detected crashes via the token. Our algorithm imposes no additional message overhead, tolerates any number of crashes as well as simultaneous crashes, and copes with crashes in a decentralized fashion. Correctness proofs are provided of both the original Safra's algorithm and its fault-tolerant variant, as well as a model checking analysis.

Authors: Thomas M. Prinz, Christopher T. Schwanen, Wil M. P. van der Aalst

A central decision problem in Petri net theory is reachability asking whether a given marking can be reached from the initial marking. Related is the covering problem (or sub-marking reachbility), which decides whether there is a reachable marking covering at least the tokens in the given marking. For live and bounded free-choice nets as well as for sound free-choice workflow nets, both problems are polynomial in their computational complexity. This paper refines this complexity for the class of sound acyclic free-choice workflow nets to a quadratic polynomial, more specifically to $O(P^2 + T^2)$. Furthermore, this paper shows the feasibility of accurately explaining why a given marking is or is not reachable. This can be achieved by three new concepts: admissibility, maximum admissibility, and diverging transitions. Admissibility requires that all places in a given marking are pairwise concurrent. Maximum admissibility states that adding a marked place to an admissible marking would make it inadmissible. A diverging transition is a transition which originally "produces" the concurrent tokens that lead to a given marking. In this paper, we provide algorithms for all these concepts and explain their computation in detail by basing them on the concepts of concurrency and post-dominance frontiers - a well known concept from compiler construction. In doing this, we present straight-forward implementations for solving (sub-marking) reachability.

Authors: Samuel McCauley, Benjamin Moseley, Helia Niaparast, Shikha Singh

In this paper, we study the fundamental problem of finding a stable matching in two-sided matching markets. In the classic variant, it is assumed that both sides of the market submit a ranked list of all agents on the other side. However, in large matching markets such as the National Resident Matching Program (NRMP), it is infeasible for hospitals to interview or mutually rank each resident. In this paper, we study the stable matching problem with truncated preference lists. In particular, we assume that, based on historical datasets, each hospital has a predicted rank of its likely match and only ranks residents within a bounded interval around that prediction. We use the algorithms-with-predictions framework and show that the classic deferred-acceptance (DA) algorithm used to compute stable matchings is robust to such truncation. We present two algorithms and theoretically and empirically evaluate their performance. Our results show that even with reasonably accurate predictions, it is possible to significantly cut down on both instance size (the length of preference lists) as well as the number of proposals made. These results explain the practical success of the DA algorithm and connect market design to the emerging theory of algorithms with predictions.

The Theory Group in Brown University’s Computer Science Department invites applications for a postdoctoral position in graph algorithms and/or theoretical machine learning. The postdoc will have the opportunity to work closely with Professors Ellis Hershkowitz, Yu Cheng, and Eli Upfal. The appointment begins Fall 2026 for one year, with possible renewal.

Website: https://dhershko.github.io/postdocAd
Email: delhersh@brown.edu

By shacharlovett

Multiple Assistant Professor positions in CS are available at the University of Warsaw (UW), including two with reduced teaching and increased salary. UW has one of the leading CS institutes in Europe with excellent students (highly successful in ACM ICPC) and strong research teams, especially in algorithms, logic and automata, and algorithmic economy (7 ERC grants in CS running at the moment).

Website: https://jobs.uw.edu.pl/en-gb/offer/WMIM_2026/field/ADIUNKT/
Email: Filip Murlak ; Oskar Skibski

By shacharlovett

This is a live blog of Lecture 2 of my graduate seminar “Feedback, Learning, and Adaptation.” A table of contents is here.

When I was first trying to wrap my head around the subject, Sasha Megretski, in his ineffably Russian way, told me control theory was the study of death. Everything in control theory is about ensuring things “retvrn” to the origin. Most controls text books open this way, drowning you in dense formalism of matrices, rational functions, and integral operators that all more or less certifies a dynamical system will converge to zero. Control theorists call this “stability,” and it’s hard to argue that it’s not the core of the field.

But the hyperfocus on stability undersells what the mathematics initially set out to capture. “Zero” suggests an equilibrium where things will converge without effort. But the origin is almost never a “dead state” in control applications. Instead, zero refers to a steady state far from equilibrium requiring vast resources to maintain. Control theory studies of homeostasis, not heat death.

Homeostasis is the term physiologists and physicians use to describe the various biological processes inside an organism that work overtime to maintain constancy of physiological quantities. For example, our bodies maintain tightly regulated concentrations of oxygen, electrolytes, and glucose in our bloodstream. To keep our such constant constancy, many other systems are in constant action. Heart rate varies, hormones modulate, muscle fibers tear, neurons signal. Vast amounts of energy are consumed and transformed to keep everything working no matter what threatening conditions we might encounter.

Many of the core ideas of control theory are themselves inspired by the human body’s incredible system of homeostatic regulation. The interplay between control and physiology in the twentieth century deserves its own blog post (or five-volume book). Control theory has always been a biomimetic study of life, not death.

In that spirit, let me motivate stability with homeostasis. Let’s assume we have a system working to maintain a setpoint. The system is designed to keep some signal as close to constant as possible. I’ll call this hopefully constant signal the reguland. The system experiences exogenous disturbances that might change its course and disrupt the constancy of the reguland. The system has a state, a collection of variables that at each fixed time predicts the system’s future. The state and disturbance at a particular time determine the next state according to some rule:

next_state = F(state, disturbance)

The reguland can be measured, and is a manifestation of the current system state. That is, we can write the value of reguland as a function of the current state.

reguland = G(state)

For any constant value of the disturbance, we’d like conditions that guarantee the system settles to a state where the reguland equals a specified setpoint level. No matter what the disturbance, the system has to converge to the same value of the reguland, but this might require a different state value for every value of the disturbance.

The goal of control analysis is to find conditions on the maps F and G that guarantee such a steady state is possible and robust to further disturbances. One of the most basic analyses uses calculus. If we assume that F and G are differentiable, then the implicit function theorem guarantees there is a value of the state that maintains the setpoint. This state value is one determined by the value of the disturbance and can be computed from the derivatives of F and G.

These derivatives also tell us something about the system dynamics near the setpoint. If we start at a fixed point associated with a “normal” environmental disturbance, and nature slightly changes, we can approximate the convergence to the new fixed point using linearization. Linearization assumes the dynamics are well approximated by the linear model defined by the Taylor series approximations of F and G at the fixed point. From the linearization, we can derive properties of the derivative of F needed to guarantee that the system shifts to a new setpoint (e.g., the eigenvalues of the Jacobian matrix all need to have magnitude less than one). The idea of using static local information to inform temporal behavior is called Lyapunov’s direct indirect method or Lyapunov’s first method. We transform the problem of general nonlinear control into one of local linear algebra. The linear algebra tells us interesting and surprising things that are generally actionable in engineering design. We just have to be careful to know the limits of these analyses.

One such interesting conclusion is that gradient descent is effectively necessary to maintain setpoints. Following the linear algebra, we can always rewrite the state in such a way that one of the components is the running average of the deviation of the reguland from its setpoint. That is, there is always a component of the state equal to the last value minus the current deviation:

x[new] = x[old] - set_point_deviation

Control theorists call this integral control, and we’ll talk more about it next week. Integral control is an essential tool to maintain setpoints in control design. It turns out that it is in fact a necessary part of any setpoint regulation.1

While Lyapunov’s first method provides useful insights into the local behavior of complex nonlinear dynamics, using these local linearizations in practice relies heavily on the precise specification of the model. Incorporating model uncertainty in these analyses is not straightforward.2 Luckily for us, Lyapunov came up with a second method, an indirect direct method, that can help us analyze the behavior of less well specified systems. Lyapunov’s second method will be the subject of tomorrow’s post.

Subscribe now

By Ben Recht

A walkthrough of this progress is available on the TheCoordinate podcast. A downloadable PDF is available here. The PBFT line of work A: Comparing PBFT, SBFT, Tendermint, HotStuff, and HotStuff-2: post1, post2 B: Explaining the core ideas behind PBFT: principles, PBFT C: Comparing the protocols Tendermint and Simplex, a lecture...

Authors: Ali Asadi, Krishnendu Chatterjee, Ehsan Goharshady, Mehrdad Karrabi, Alipasha Montaseri, Carlo Pagano

Markov decision processes (MDPs) are a fundamental model in sequential decision making. Robust MDPs (RMDPs) extend this framework by allowing uncertainty in transition probabilities and optimizing against the worst-case realization of that uncertainty. In particular, $(s, a)$-rectangular RMDPs with $L_\infty$ uncertainty sets form a fundamental and expressive model: they subsume classical MDPs and turn-based stochastic games. We consider this model with discounted payoffs. The existence of polynomial and strongly-polynomial time algorithms is a fundamental problem for these optimization models. For MDPs, linear programming yields polynomial-time algorithms for any arbitrary discount factor, and the seminal work of Ye established strongly--polynomial time for a fixed discount factor. The generalization of such results to RMDPs has remained an important open problem. In this work, we show that a robust policy iteration algorithm runs in strongly-polynomial time for $(s, a)$-rectangular $L_\infty$ RMDPs with a constant (fixed) discount factor, resolving an important algorithmic question.

Authors: Jin-Yi Cai, Ashwin Maran, Ben Young

We study the complexity of counting (weighted) planar graph homomorphism problem $\tt{Pl\text{-}GH}(M)$ parametrized by an arbitrary symmetric non-negative real valued matrix $M$. For matrices with pairwise distinct diagonal values, we prove a complete dichotomy theorem: $\tt{Pl\text{-}GH}(M)$ is either polynomial-time tractable, or $\#$P-hard, according to a simple criterion. More generally, we obtain a dichotomy whenever every vertex pair of the graph represented by $M$ can be separated using some planar edge gadget. A key question in proving complexity dichotomies in the planar setting is the expressive power of planar edge gadgets. We build on the framework of Mančinska and Roberson to establish links between \textit{planar} edge gadgets and the theory of the \textit{quantum automorphism group} $\tt{Qut}(M)$. We show that planar edge gadgets that can separate vertex pairs of $M$ exist precisely when $\tt{Qut}(M)$ is \emph{trivial}, and prove that the problem of whether $\tt{Qut}(M)$ is trivial is undecidable. These results delineate the frontier for planar homomorphism counting problems and uncover intrinsic barriers to extending nonplanar reduction techniques to the planar setting.

Authors: Alexandra Lassota, Koen Ligthart

We present a new and faster algorithm for the 4-block integer linear programming problem, overcoming the long-standing runtime barrier faced by previous algorithms that rely on Graver complexity or proximity bounds. The 4-block integer linear programming problem asks to compute $\min\{c_0^\top x_0+c_1^\top x_1+\dots+c_n^\top x_n\ \vert\ Ax_0+Bx_1+\dots+Bx_n=b_0,\ Cx_0+Dx_i=b_i\ \forall i\in[n],\ (x_0,x_1,\dots,x_n)\in\mathbb Z_{\ge0}^{(1+n)k}\}$ for some $k\times k$ matrices $A,B,C,D$ with coefficients bounded by $\overlineΔ$ in absolute value. Our algorithm runs in time $f(k,\overlineΔ)\cdot n^{k+\mathcal O(1)}$, improving upon the previous best running time of $f(k,\overlineΔ)\cdot n^{k^2+\mathcal O(1)}$ [Oertel, Paat, and Weismantel (Math. Prog. 2024), Chen, Koutecký, Xu, and Shi (ESA 2020)]. Further, we give the first algorithm that can handle large coefficients in $A, B$ and $C$, that is, it has a running time that depends only polynomially on the encoding length of these coefficients. We obtain these results by extending the $n$-fold integer linear programming algorithm of Cslovjecsek, Koutecký, Lassota, Pilipczuk, and Polak (SODA 2024) to incorporate additional global variables $x_0$. The central technical result is showing that the exhaustive use of the vector rearrangement lemma of Cslovjecsek, Eisenbrand, Pilipczuk, Venzin, and Weismantel (ESA 2021) can be made \emph{affine} by carefully guessing both the residue of the global variables modulo a large modulus and a face in a suitable hyperplane arrangement among a sufficiently small number of candidates. This facilitates a dynamic high-multiplicy encoding of a \emph{faithfully decomposed} $n$-fold ILP with bounded right-hand sides, which we can solve efficiently for each such guess.

Authors: Leonid Dorochko, Michał Wrona

Feder-Vardi conjecture, which proposed that every finite-domain Constraint Satisfaction Problem (CSP) is either in P or it is NP-complete, has been solved independently by Bulatov and Zhuk almost ten years ago. Bodirsky-Pinsker conjecture which states a similar dichotomy for countably infinite first-order reducts of finitely bounded homogeneous structures is wide open. In this paper, we prove that CSPs over first-order expansions of finitely bounded homogeneous model-complete cores are either first-order definable (and hence in non-uniform AC$^0$) or L-hard under first-order reduction. It is arguably the most general complexity dichotomy when it comes to the scope of structures within Bodirsky-Pinsker conjecture. Our strategy is that we first give a new proof of Larose-Tesson theorem, which provides a similar dichotomy over finite structures, and then generalize that new proof to infinite structures.

Authors: Yotam Dikstein, Max Hopkins, Russell Impagliazzo, Toniann Pitassi

We construct the first (locally computable, approximately) locally list decodable codes with rate, efficiency, and error tolerance approaching the information theoretic limit, a core regime of interest for the complexity theoretic task of hardness amplification. Our algorithms run in polylogarithmic time and sub-logarithmic depth, which together with classic constructions in the unique decoding (low-noise) regime leads to the resolution of several long-standing problems in coding and complexity theory: 1. Near-optimally input-preserving hardness amplification (and corresponding fast PRGs) 2. Constant rate codes with $\log(N)$-depth list decoding (RNC$^1$) 3. Complexity-preserving distance amplification Our codes are built on the powerful theory of (local-spectral) high dimensional expanders (HDX). At a technical level, we make two key contributions. First, we introduce a new framework for ($\mathrm{polylog(N)}$-round) belief propagation on HDX that leverages a mix of local correction and global expansion to control error build-up while maintaining high rate. Second, we introduce the notion of strongly explicit local routing on HDX, local algorithms that given any two target vertices, output a random path between them in only polylogarithmic time (and, preferably, sub-logarithmic depth). Constructing such schemes on certain coset HDX allows us to instantiate our otherwise combinatorial framework in polylogarithmic time and low depth, completing the result.

Authors: Archishna Bhattacharyya, Arthur Mehta, Yuming Zhao

An important distinction in our understanding of capacities of classical versus quantum channels is marked by the following question: is there an algorithm which can compute (or even efficiently compute) the capacity? While there is overwhelming evidence suggesting that quantum channel capacities may be uncomputable, a formal proof of any such statement is elusive. We initiate the study of the hardness of computing quantum channel capacities. We show that, for a general quantum channel, it is QMA-hard to compute its quantum capacity, and that the maximal-entanglement-assisted zero-error one-shot classical capacity is uncomputable.

Authors: Amirhossein Akbar Tabatabai, Raheleh Jalali

Proving proof-size lower bounds for $\mathbf{LK}$, the sequent calculus for classical propositional logic, remains a major open problem in proof complexity. We shed new light on this challenge by isolating the power of structural rules, showing that their combination is extremely stronger than any single rule alone. We establish exponential (resp. sub-exponential) proof-size lower bounds for $\mathbf{LK}$ without contraction (resp. weakening) for formulas with short $\mathbf{LK}$-proofs. Concretely, we work with the Full Lambek calculus with exchange, $\mathbf{FL_e}$, and its contraction-extended variant, $\mathbf{FL_{ec}}$, substructural systems underlying linear logic. We construct families of $\mathbf{FL_e}$-provable (resp. $\mathbf{FL_{ec}}$-provable) formulas that require exponential-size (resp. sub-exponential-size) proofs in affine linear logic $\mathbf{ALL}$ (resp. relevant linear logic $\mathbf{RLL}$), but admit polynomial-size proofs once contraction (resp. weakening) is restored. This yields exponential lower bounds on proof-size of $\mathbf{FL_e}$-provable formulas in $\mathbf{ALL}$ and hence for $\mathbf{MALL}$, $\mathbf{AMALL}$, and full classical linear logic $\mathbf{CLL}$. Finally, we exhibit formulas with polynomial-size $\mathbf{FL_e}$-proofs that nevertheless require exponential-size proofs in cut-free $\mathbf{LK}$, establishing exponential speed-ups between various linear calculi and their cut-free counterparts.

Authors: Pascal Lenzner, Paraskevi Machaira

Today's networks consist of many autonomous entities that follow their own objectives, i.e., smart devices or parts of large AI systems, that are interconnected. Given the size and complexity of most communication networks, each entity typically only has a local view and thus must rely on a local routing protocol for sending and forwarding packets. A common solution for this is greedy routing, where packets are locally forwarded to a neighbor in the network that is closer to the packet's destination. In this paper we investigate a game-theoretic model with autonomous agents that aim at forming a network where greedy routing is enabled. The agents are positioned in a metric space and each agent tries to establish as few links as possible, while maintaining that it can reach every other agent via greedy routing. Thus, this model captures how greedy routing networks are formed without any assumption on the distribution of the agents or the specific employed greedy routing protocol. Hence, it distills the essence that makes greedy routing work. We study two variants of the model: with directed edges or with undirected edges. For the former, we show that equilibria exist, have optimal total cost, and that in Euclidean metrics they can be found efficiently. However, even for this simple setting computing optimal strategies is NP-hard. For the much more challenging setting with undirected edges, we show for the realistic setting with agents in 2D Euclidean space that the price of anarchy is between 1.75 and 1.8 and for higher dimensions it is less than 2. Also, we show that best response dynamics may cycle, but that in Euclidean space almost optimal approximate equilibria can be computed in polynomial time. Moreover, for 2D Euclidean space, these approximate equilibria outperform the well-known Delaunay triangulation.

Authors: Alexandre Guillemot, Pierre Lairez

We study the theoretical and practical aspects of computing braids described by approximate descriptions of paths in the plane. Exact algorithms rely on the lexicographic ordering of the points in the plane, which is unstable under numerical uncertainty. Instead, we formalize an input model for approximate data, based on a separation predicate. It applies, for example, to paths obtained by tracking the roots of a parametrized polynomial with complex coefficients, thereby connecting certified path tracking outputs to exact braid computation.

Authors: Kevin Buchin, Jacobus Conradi, Sariel Har-Peled, Antonia Kalb, Abhiruk Lahiri, Lukas Plätz, Carolin Rehs

$\newcommand{\Re}{\mathbb{R}}$We study the minWSPD problem of computing the minimum-size well-separated pairs decomposition of a set of points, and show constant approximation algorithms in low-dimensional Euclidean space and doubling metrics. This problem is computationally hard already $\Re^2$, and is also hard to approximate. We also introduce a new pair decomposition, removing the requirement that the diameters of the parts should be small. Surprisingly, we show that in a general metric space, one can compute such a decomposition of size $O( \tfrac{n}{\varepsilon}\log n)$, which is dramatically smaller than the quadratic bound for WSPDs. In $\Re^d$, the bound improves to $O( d \tfrac{n}{\varepsilon}\log \tfrac{1}{\varepsilon } )$.

Authors: Anastasiia Tkachenko, Haitao Wang

Given a set $P$ of $n$ points in the plane and a collection of disks centered at these points, the disk graph $G(P)$ has vertex set $P$, with an edge between two vertices if their corresponding disks intersect. We study the dominating set problem in $G(P)$ under the special case where the points of $P$ are in convex position. The problem is NP-hard in general disk graphs. Under the convex position assumption, however, we present the first polynomial-time algorithm for the problem. Specifically, we design an $O(k^2 n \log^2 n)$-time algorithm, where $k$ denotes the size of a minimum dominating set. For the weighted version, in which each disk has an associated weight and the goal is to compute a dominating set of minimum total weight, we obtain an $O(n^5 \log^2 n)$-time algorithm.

Authors: Travis Gagie, Meng He, Gonzalo Navarro

We introduce a compressed representation of sets of sets that exploits how much they differ from each other. Our representation supports access, membership, predecessor and successor queries on the sets within logarithmic time. In addition, we give a new MST-based construction algorithm for the representation that outperforms standard ones.

Authors: Yiding Feng, Zonghan Yang, Yuhao Zhang

Large Language Model (LLM) inference presents a unique scheduling challenge due to the Key-Value (KV) cache, where a job's memory footprint grows linearly with the number of decoded tokens. This growth couples scheduling decisions with feasibility: a scheduler must minimize latency under a hard memory budget, yet the response lengths of requests are inherently unknown. While recent works have explored this problem either assuming clairvoyance -- exact knowledge of response lengths -- or relying on machine-learned predictions, obtaining robust performance guarantees without any prior knowledge of job sizes remains a theoretically fundamental and practically important open problem. In this work, we propose the Geometric Slicing Algorithm (GSA), the non-clairvoyant policy to achieve the first constant competitive ratio for this problem in the offline batch setting. GSA manages uncertainty through a geometric phase structure that periodically restarts jobs to bound memory exposure, combined with a staggered pipeline mechanism that enables high concurrency by smoothing aggregate memory consumption. We prove that GSA achieves a competitive ratio of at most 61.92 for general instances, improving to 32 in the large-memory regime. Our algorithmic framework also yields a clairvoyant counterpart, the Geometric Batching Algorithm (GBA), which achieves an approximation ratio of 10.67 for general instances and 6.75 in the large-memory regime -- significantly improving upon the best previously known bound of over 9000. Numerical experiments on real request traces demonstrate that our algorithms perform robustly while preserving these worst-case guarantees.

Authors: Qiangpeng Fang, Jilong Shi, Xiaobin Rui, Jian Zhang, Zhixiao Wang

Influence Blocking Maximization (IBM) aims to select a positive seed set to suppress the spread of negative influence. However, existing IBM methods focus solely on maximizing blocking effectiveness, overlooking fairness across communities. To address this issue, we formalize fairness in IBM and justify Demographic Parity (DP) as a notion that is particularly well aligned with its semantics. Yet enforcing DP is computationally challenging: prior work typically formulates DP as a Linear Programming (LP) problem and relies on costly solvers, rendering them impractical for large-scale networks. In this paper, we propose a DP-aware objective while maintaining an approximately monotonic submodular structure, enabling efficient optimization with theoretical guarantees. We integrate this objective with blocking effectiveness through a tunable scalarization, yielding a principled fairness-effectiveness trade-offs. Building on this structure, we develop CELF-R, an accelerated seed selection algorithm that exploits approximate submodularity to eliminate redundant evaluations and naturally supports Pareto front construction. Extensive experiments demonstrate that CELF-R consistently outperforms state-of-the-art baselines, achieving a $(1-1/e-ψ)$-approximate solution while maintaining high efficiency.

Authors: Bingwei Zhang, Chee Yap

We consider the first-order autonomous ordinary differential equation \[ \mathbf{x}' = \mathbf{f}(\mathbf{x}), \] where $\mathbf{f} : \mathbb{R}^n \to \mathbb{R}^n$ is locally Lipschitz. For a box $B_0 \subseteq \mathbb{R}^n$ and $h > 0$, we denote by $\mathrm{IVP}_{\mathbf{f}}(B_0,h)$ the set of solutions $\mathbf{x} : [0,h] \to \mathbb{R}^n$ satisfying \[ \mathbf{x}'(t) = \mathbf{f}(\mathbf{x}(t)), \qquad \mathbf{x}(0) \in B_0 . \] We present a complete validated algorithm for the following \emph{End Cover Problem}: given $(\mathbf{f}, B_0, \varepsilon, h)$, compute a finite set $\mathcal{C}$ of boxes such that \[ \mathrm{End}_{\mathbf{f}}(B_0,h) \;\subseteq\; \bigcup_{B \in \mathcal{C}} B \;\subseteq\; \mathrm{End}_{\mathbf{f}}(B_0,h) \oplus [-\varepsilon,\varepsilon]^n , \] where \[ \mathrm{End}_{\mathbf{f}}(B_0,h) = \left\{ \mathbf{x}(h) : \mathbf{x} \in \mathrm{IVP}_{\mathbf{f}}(B_0,h) \right\}. \] Moreover, we provide a complexity analysis of our algorithm and introduce a novel technique for computing the end cover $\mathcal{C}$ based on covering the boundary of $\mathrm{End}_{\mathbf{f}}(B_0,h)$. Finally, we present experimental results demonstrating the practicality of our approach.

Last night, I was taken aback to discover that my name appears in the Epstein Files, in 26 different documents. This is despite the fact that I met Jeffrey Epstein a grand total of zero times, and had zero email or any other contact with him … which is more (less) than some of my colleagues can say.

The bulk of the correspondence involves Epstein wanting to arrange a meeting with me and Seth Lloyd back in 2010, via an intermediary named Charles Harper, about funding a research project on “Cryptography in Nature.”

Searching my inbox, it turns out that this Charles Harper did contact me in May 2010, and I then met him at S&S Deli in Cambridge (plausible, although I have zero recollections of this meeting—only of the deli). Harper then sent me a detailed followup email about his proposed Cryptography in Nature project, naming Jeffrey Epstein for the first time as the project’s funder, and adding: “perhaps you will know Jeffrey and his background and situation.”

For whatever reason, I forwarded this email to my parents, brother, and then-fiancee Dana. My brother then found and shared a news article about Epstein’s prostitution conviction, adding to a different article that I had found and shared. (At that time, like many others, I’d probably vaguely heard of Epstein, but he didn’t have 0.1% the infamy that he has now.) Then my mom wrote the following: “be careful not to get sucked up in the slime-machine going on here! Since you don’t care that much about money, they can’t buy you at least.”

It appears from emails that Charles Harper tried again later that summer to arrange a meeting between me and Epstein, but that I took my mom’s advice and largely blew him off, and no such meeting ever happened. Amazingly, I then forgot entirely that any of this had occurred until last night. By way of explanation, some business/finance dude trying to interest me in half-baked ideas involving quantum, AI, cryptography, etc., often dangling the prospect of funding for my students and postdocs, shows up in my life like every month. Most of their world-changing initiatives go nowhere for one reason or another. There really wasn’t much reason to think further about this, until Epstein had become history’s most notorious sex criminal, which (again) wouldn’t happen until years later, after I’d forgotten.

It gets better, though. In the Epstein Files, one also finds a November 2010 letter from Charles Harper to Epstein about organizing a conference on the same Cryptography in Nature topic, which includes the following idea about me:

Scott Aaronson was born on May 21st, 1981. He will be 30 in 2011. The conference could follow a theme of: “hurry to think together with Scott Aaronson while he is still in his 20s and not yet a pitiful over-the-hill geezer in his 30s.” This offers another nice opportunity for celebration.

I see no indication that any such conference ever happened; in any case, I didn’t get invited to one!

On my Facebook, some friends are joking that “it tracks that someone into teenage girls might think Scott Aaronson was a hot property in his nubile 20s, who would get old and boring in his 30s”—and that maybe Epstein was less sexist about such matters than everyone assumes. I replied that I wished I could say the proposition that I’d gradually get slower and more senile through the 2010s and 2020s was entirely false.

But the best comment was that I’ve been incredibly lucky to have such an astute family. If only Bill Gates and Larry Summers had had my mom to go to for advice, they could’ve saved themselves a lot of grief.

By Scott

Lance and I had a blog-debate about What to do about students using ChatGPT to do their Homework.

Some commenters pointed out that we've been here before. I will now list past technologies that looked like they were a problem for student assignments and ponder what happened. 

If students can consult diagrams in their text then they will lose the ability to I DON"T KNOW AND I DON"T CARE . I did a post about this  titled In the 1960's students protested the Vietnam war!/In 1830 students protested...Math? I suspect that students eventually got to consult their texts. Actually, the entire topic of geometry of conic sections,  seems to have gone away.

If students learn how to read then they will lose the ability to listen to their elders tell stories and also lose the ability to memorize. I've heard this was a concern though I don't really know if it was. In any case people are probably worse at memorizing than they used to be, but the plus of having books and reading far outweighs the negative of less good memories. 

If students use spellcheck they will forget how to spell I think people are sloppier with first drafts than they used to be since they know that spellcheck will catch their spelling errors. And even before ChatGPT there were programs to check grammar as well. My spell check wants me to replace ChatGPT with catgut. This points to the need to use spellcheck carefully which foreshadows having to use ChatGPT carefully. My spellcheck does think that spellcheck is spelled correctly.

If students have calculators they will forget that 7*8 equals... hmm, I forgot: I think we ask much fewer questions depending on calculation than we used to.  Do kids in grade school still memorize times-tables? If so, then up to what number?  In my blog post on Numbers That Look Prime But Aren't, I casually mentioned that students learn up to 12x12 but I do not know if that's true. 

SO- for those of you who have kids in grade school, leave a comment on if they 

a) Memorize Times Tables.

b) Learn an algorithm for multiplication ( O(n^2) or O(n^{1.58}) or  O(n log n)) . I used Wikipedia for the pointer to the O(n^{1.58}). The entry describes the algorithm very well. I used Wikipedia for the O(nlog n) algorithm. That entry just says that there is a galactic algorithm (one that needs very large n to be worth using). They did not give the algorithm or a pointer to a paper that has it.) 

c) Are allowed calculators on exams.

d) Some combination of the above or something else. 

If students use Encyclopedias they will not be using primary sources. Over time Encyclopedias became seen as primary sources. My proofreader relayed the following to me: When I was in fourth grade I weren't supposed to use Encyclopedias for their reports if the library had suitable books. So the trick was to find a topic that the library did not have suitable books on. My proofreader is only a few years older than me, and lived in the same state, but I was allowed to use Encyclopedias. 

If students use Wikipedia they will not be using primary sources. I don't hear this debated anymore but I am not sure how the issue was resolved, or if it was resolved. If someone who has kids in school knows, please leave a comment. 

Annie and Lance Fortnow had a blog entry about the Wikipedia issue. 

I reviewed a book titled Should you Believe Wikipedia? by Amy Bruckman. The review is here. Spoiler alert: She thinks yes but I am more skeptical.

I once needed a list of ER-complete problems and asked an expert if there was a survey. He said that the best source was the Wikipedia page. For other examples of Wikipedia being the only source  see this blog post.

A similar issue is referring to papers on arXiv that have not been refereed. That might be the topic for a future blog post. 

If the first programming language is in a high-level language the students will not learn assembly code and stuff about how computers really work. This has happened. I think students do not know as much about low-level code as they used to. Is that a problem? This type of concern happens whenever a  higher level language is available. Students using  ChatGPT  to write code for you is another example of this issue, though it also has other problems. 

If students learn typing too early they will not learn cursive. I am an early example of this---my handwriting was bad (still is) so I eagerly took a typing class in my school in 5th grade (the class was 13 girls whose parents wanted them to be secretaries, and me) and worked really hard at it and began handing in typed book reports.  

The only letters I know how to do in cursive are

 W I L L I A M   G A S A R C H  

and only  in that order.  

ANYWAY, people have lost the ability to write in cursive, or even write in print neatly.  Drew Faust, a former history professor at Harvard (she retired in 2018) has pointed out that students have a hard time reading cursive in her article Gen Z Never Learned to Read Cursive.

I ask non-rhetorically, is losing the ability to read or write cursive  a problem? 

Takeaways: 

1) (From the prior blog on ChatGPT) Grading has been broken for a long time. ChatGPT just makes that more obvious.

2) When a  new technology comes along we may have to rethink education. 

By gasarch

We introduce the SHEDAG (Somewhere Honest Entropic sources over Directed Acyclic Graphs) source model, a general model for multi-block randomness sources with causal correlations. A SHEDAG source is defined over a directed acyclic graph (DAG) $G$ whose nodes output $n$-bit blocks. Blocks output by honest nodes are independent (by default uniformly random, more generally having high min-entropy), while blocks output by corrupted nodes are arbitrary functions of their causal views (all predecessors in $G$). We tightly characterize the conditions under which randomness extraction from SHEDAG sources is possible. $\textbf{Zero-error extraction:}$ We show that perfect extraction from SHEDAG sources with $t$ corruptions is possible if and only if $G$ contains an "unrelated set'' (an antichain under reachability) of size at least $t+1$. Conversely, if every unrelated set has size at most $t$, we show that no function can output a perfectly uniform bit. We also provide a polynomial-time algorithm to find a maximum unrelated set, thus efficiently identifying the largest corruption threshold $t$ allowing perfect extraction. $\textbf{Negligible-error extraction:}$ We identify a quantity that we call "resilience'' of a DAG $G$, denoted $\text{res}(G)$, that characterizes the possibility of randomness extraction with "negligible" error (in the block length). We show that negligible-error extraction is impossible whenever $t>\text{res}(G)$, and, to complement this, for every $t\leq \text{res}(G)$ we construct explicit extractors with polynomial output length and negligible error. Our results generalize prior online source models studied by (Aggarwal, Obremski, Ribeiro, Siniscalchi, Visconti, Eurocrypt 2020) and (Chattopadhyay, Gurumukhani, Ringach, FOCS 2024), which correspond to the special case of a SHEDAG source whose DAG $G$ is a path.

This paper explores the previously studied measure called block number of Boolean functions, that counts the maximum possible number of minimal sensitive blocks for any input. We present close to tight upper bounds on the block number in terms of the function’s sensitivity and the allowed block size, improving previous bounds by a quadratic factor. Moreover, our bound on the block number yields sharper upper bounds on DNF size and decision tree size. We obtain these results by introducing and estimating a novel measure called brick number, which not only upper bounds the block number but also leads to a new characterization of block sensitivity.