Theory of Computing Report

[Loosely based on a lecture I gave in the recursive conference with the same title. Don’t take “2030” literally¹—it could also be 2035 or 2040. As always, opinions are my own and do not represent OpenAI or Harvard.]

It is quite possible that AI will usher in a golden age for humanity. As Amodei writes in “Machines of Loving Grace,” AI might enable the “prevention and treatment of nearly all natural infectious diseases,” the “elimination of most cancer,” “prevention of Alzheimer’s,” and even “doubling of the human lifespan.” Through increased growth, AI could lead to a reduced workweek, as well as universal basic income and health insurance. Universities might focus on education for its own sake, as opposed to vocational purposes. People will spend less time sitting on chairs and staring at screens, and more in relational jobs. AI may also lead to new ways to participate in democracy, as well as oversight of government.

And yet, what if, as Ice-T once said, “shit ain’t like that”? In this opinionated and somewhat informal essay, I want to consider this more pessimistic or “glass half empty” case. Specifically,

Imagine that, in the next decade or so, the AGI transition has gone very badly for the U.S.² or humanity at large. What are the possible scenarios that could lead to that?

Part of the reason to consider different scenarios is that some interventions that could help mitigate one scenario might end up amplifying another. A particularly salient axis is that of control vs. distribution. Some scenarios and risks motivate interventions in the direction of increased control: restricting access to frontier models to government or trusted parties, restricting access to the information on AI research, restricting open source models, etc.. Other risks, such as concentration of power, might motivate the opposite direction of increased distribution: wide distribution of AI to spread its benefits, increased transparency on both government and internal lab use of AI. 

I don’t think there is one simple answer, and neither extreme is likely to lead to good results. But we should be keeping the various tradeoffs and risks in mind when considering any potential intervention. I am particularly concerned about questions regarding concentration of power. A future in which we humanity is under the control of either AI or a small group of unelected humans is not a good future in my books, even if we are materially well off. Hence I am concerned about interventions that either rely on ceding more control to a “good” AI, reduce the level of competition among AI model providers, or restrict access to advanced AI to the blessed few. This does not mean that we should have no restrictions for safety. Only that we should try to keep these narrowly tailored to address specific measurable risks, rather than broad restrictions motivated by hypothetical risks.

Overview of bad scenarios

I will review the following general “families” of non-mutually-exclusive scenarios in which AI leads to very bad outcomes:

• Catastrophic misuse: AI is used by humans to cause a catastrophe on a global or national scale—one that would radically worsen the course of events for the United States or the world at large. These types of events are considered in many frontier lab scaling policies (e.g., Anthropic responsible scaling policy, GDM frontier policy, OpenAI preparedness framework). Specifically, two scenarios that are often considered are:
  • AI used for catastrophic cybersecurity harms.
  • AI used for catastrophic biological, chemical, radiological, or nuclear harms.
• Catastrophic misalignment and loss of control: AI disempowering humans or causing mass harm to them.
• Concentration of power among a few humans: A few people take over and exert control over the U.S. or other currently democratic countries. This can be due to:
  • Massive wealth inequality splits the population into a “permanent underclass and overclass,” with the latter controlling the vast majority of resources and having most of the political power as well. It may well be that the “permanent overclass” is made up of people who made their fortunes in AI.
  • Bad actors use AI to turn democratic countries into authoritarian ones.
• Geopolitical shift toward authoritarianism: AI disrupts the balance of power in a way that enables authoritarian countries to control or exert significant power over the U.S. and other democracies.
• “Hot mess”: Finally, I also include a “catch-all” category, which I call “hot mess,” and which can be thought of as a combination of “none of the above” and “all of the above.” In this scenario, AI turns out very badly for humans, but there isn’t one singular event or cause that we can point to. Rather, it is a type of “death by 1,000 cuts” in which a combination of many factors leads to a very bad place. To give a spoiler, conditioned on AGI turning out badly, I’d guess that it would fall into this category.

Catastrophic misuse

Much of the discussion on catastrophic risks from AI has focused on risks related to CBRN (chemical/biological/radiological/nuclear), cybersecurity, and loss of control by AI. Recently, following the announcement of Anthropic’s Mythos model, cybersecurity has gotten significant attention. 

Cybersecurity

There are several causes for software insecurity. One is that there is a direct economic incentive to invest coding effort in producing new features, but the incentive to invest in security is less direct, and moreover often requires hiring programmers with specialized skills. Security bugs cost nothing to the developer until they are exploited, and even when they are exploited, the cost is often borne by other parties. A great example of a complex program that is (nearly) bug-free is Donald Knuth’s TeX. Contrary to typical practice, Knuth has frozen features since TeX 3.0 was finalized in 1990, with all subsequent versions focusing on bug fixes (with version numbers asymptotically approaching pi). 

Another cause for insecurity is the “schlep factor” of ensuring software is up to date, systems are correctly configured, and so on. Many less-resourced institutions (e.g., hospitals, city halls, etc.) cannot afford a full-time security staff that will ensure all patches are installed and configurations are set up properly, let alone 24/7 monitoring of their networks.

Finally, humans can fall for social-engineering attacks or fail to notice slight misspellings in URLs.

Cybersecurity is probably defense-dominated

AI can help with the feature–bug-fix tradeoff and make software more secure. If the cost of coding tends to zero, then we no longer need to trade off investing in fixing bugs against investing in new features. In the longer term, AI can help us approach the “holy grail” of formal verification for complex and widely used pieces of software. In addition, AI systems can help significantly with the “schlep factor.” With AI agents, even small businesses or nonprofits can afford to have their own virtual 24/7 security staff that can install patches, monitor for suspicious activity, etc.

At present, AI systems are not immune to their own version of “social engineering”: jailbreaks or prompt injections. However, AI systems’ failure patterns differ from humans’, so the combination of AI systems and humans could be more secure than either alone. I also believe that, with time, systems will become more resilient to such attacks. Finally, if attacks on the AI can be detected and patched, securing many heterogeneous systems may partly reduce to securing and updating a common AI layer.

The bottom line is that, in my estimation, AI will end up helping defenders more than attackers in the realm of cybersecurity. This does not mean that AI cannot enable some novel attacks, especially in the short run, because attackers may be earlier adopters. There are certainly steps that AI companies and governments can take to “put their thumb on the scale” (in a good way!) and accelerate defenders more than attackers. Some of these are already underway, though we could do more (in particular, by helping smaller entities with the “schlep factor”). In general, I believe that in the realm of cybersecurity, we should be focused on distribution—accelerating defenders—at least as much as, if not more than on control—blocking attackers.

Biological, chemical, radiological, or nuclear risks

Unlike the case of cyberattacks, with biological, chemical, radiological, or nuclear (CBRN) risks, the bottleneck for attackers is not just informational but also physical: getting relevant materials, manufacturing, and distribution, all without being detected. Indeed, while cyberattacks are commonplace and are carried out by a range of actors including individuals, organized crime, and state actors, CBRN attacks are very rare.

Out of all of these, bioweapons are potentially the most “information-bottlenecked,” in the sense that the necessary materials and equipment may be within reach of many potential bad actors. There is much that we can do to help defenders against biological attacks. This includes building up infrastructure such as early detection of viruses, rapid-response vaccines, better protective equipment—all useful for natural pandemics as well! We should also do more to screen orders for DNA synthesis to detect attempts at biothreat manufacturing. We have also seen in the COVID-19 pandemic that, in extreme situations, governments can take radical steps including stay-at-home orders that could, to some extent, reduce the spread of a pandemic, whether natural or constructed.

Compared to cybersecurity, I do have less of a clear sense of the offense/defense balance for CBRN, and bioweapons in particular. But given the steady advances in open-source models, it seems clear that we will not always be able to block access to information and advice in these domains. Hence in my view, we should be looking at model restrictions on answering CBRN-related queries as one of the tools we have to “buy time,” and be focused on using that time to ensure we have stronger defense-in-depth than simply model refusals.

Broader offense/defense balance

We can model the interaction between an attacker and defender as a game. Each player follows a strategy, which can also involve some random choices. In standard game theory, the set of moves available to each player is fixed and known to both parties, and they have no computational limitations. However, if one of the players has a significant intelligence advantage over the other, that player could predict the strategy (even if not randomness) used by its opponent, and also have available strategies that the other side is not aware of.

If we believe that intelligence scales with compute, and we can ensure that the compute available to good actors dominates that of bad actors, then, assuming it is used wisely, this can shift many settings to be defense dominated against attacks by bad actors.

Catastrophic misalignment: loss of control/extinction

In the book “If Anyone Builds It, Everyone Dies,” Yudkowsky and Soares describe a particular scenario in which an AI called “Sable” develops the desire to escape and take over. It manages to manipulate its training process to reinforce its misaligned desires, and eventually to exfiltrate copies of itself. It then creates a virus so that humans, desperate to find a cure, will give it compute power and access to physical resources. It can then use that to amplify its intelligence, and then pursue its goals via robots/nanotechnology in a way that makes Earth uninhabitable for humans.

Another, more gradual scenario is depicted in the AI 2027 document. There is a sequence of models, “Agent 1,” “Agent 2,” … with “Agent n” helping to build and align “Agent n+1.” Each new agent is more powerful but potentially less trustworthy, until the very misaligned Agent 4 deceptively ensures its successor Agent 5 is even more misaligned. 

I find the AI 2027 scenario much more realistic than Sable because it relies less on a sudden, discontinuous capability jump and more on a chain of increasingly capable systems embedded in plausible lab and national-security institutions. I do not think we can fully rule it out yet. But given some of our learnings over the last few years, I believe it is less likely, and (more importantly) that we should be able to see some warning signs if we are on the path to it.

To be clear, we have not solved the alignment problem for AI models. Current models can exhibit misalignment, including dishonesty, hallucinations, disobeying instructions, reward hacking, laziness, and more. But the types of misalignment that current models present are not adversarial or “scheming” in the sense needed for scenarios such as the above. Specifically, when a model is given a task X, even when it fails to match the user’s intent, the failure is somewhat related to X. For example, the model might “hack” by solving a narrow interpretation of X, fulfilling the letter but not the spirit of the instructions. Or in the other direction, the model might be so eager to solve X that it would do so while violating some common-sense constraints that the user would definitely not have desired. But by and large, current models do not pretend to solve X while pursuing their own completely unrelated goal Z.

My impression is that current models exhibit “bounded misalignment³,” in which the model might not follow precisely the prompt it is given but is not completely adversarial either. In other words, the alignment failures tend to follow by either the model misunderstanding the instructions or intent, or by pursuing the instruction and instead in the wrong way, but not by covertly pursuing a different long-term goal of the model. 

Crucially, bounded misalignment allows us to still use AI systems to monitor themselves. With bounded misalignment, we can trust that if an actor model gets the prompt X, and a monitor model gets the prompt Y, then they are not going to collude and both act according to their own agenda Z. It is still possible that either actor or monitor will fail, but with bounded misalignment it is possible to amplify the probability of detecting failures with more monitoring and better prompting or harness, which would be useless if all monitors collude with one another. Bounded misalignment also means that we do not trust weaker models more than we trust stronger ones. So we do not need to require monitors to be weaker than the models they are monitoring, and we can even have them be stronger (e.g., by supplying more test-time compute).

It is possible that such scheming will emerge with higher capabilities. We certainly cannot rule this out. However, current models are pretty capable already. Consider the recent OpenAI model that refuted the 80-year-old planar unit-distance conjecture. The summarized chain of thought for this model took up 125 pages and more than 45,000 words. This is clearly a model that can conceive and execute long-term plans!

Some people might contend that current models are already scheming and colluding, and the reason they are not detected is simply because they are so good at it. Indeed, evaluations for scheming are nontrivial, and will only become harder as models become stronger and possess more situational awareness. It is important to invest in multiple approaches for monitoring models during training, evaluation, and production. We should also perform such monitoring throughout training, making it more likely that we can detect scheming if/when it emerges and not wait until the model is so good at it that it is very hard to detect.

Finally, even if not adversarial, “bounded misalignment” may well lead to extremely harmful outcomes as AI systems are deployed in increasingly high-stakes settings. One such high-stakes deployment is the use of AI in the AI R&D process (“recursive self-improvement”). One way to model this is that, rather than having discrete models “Agent 1,” “Agent 2,” …, we have a continuous process Agent(t). The level of (mis)alignment⁴ of Agent(t) will follow some differential equation. I find it hard to believe that we will manage to be on a knife-edge condition where the derivative is zero, and hence I believe misalignment will either grow or shrink. I am optimistic that it is possible, and a matter of execution and investment rather than new discoveries, to make misalignment shrink with capabilities. But this remains to be seen, and if misalignment grows instead we could end up in a bad place.

Concentration of power Economic inequality and a “permanent underclass”

Another risk from AI is that it will lead to a drastic concentration of power. A recent opinion piece discussed the fear of a “permanent underclass,” whereby AGI eliminates the value of human labor, and hence social mobility as well. There is a debate over whether a “permanent underclass” is economically plausible, and, as the piece notes, many economists are skeptical.

Regardless, I believe that as long as we retain our democratic system of governance, such a scenario is not tenable. It does not take an expert to notice that free-market fundamentalism has very few principled adherents in either the Democratic or Republican Party, nor that fear or dislike of AI is a rare issue that unites voters on both sides of the aisle. If AI causes widespread economic pain to most voters, the government will have to find ways to address this, though we are likely to get much better policy outcomes if responses are well-considered in advance rather than arising as backlash.

Authoritarian government

The above assumes that we retain our democratic system, but many people are worried about precisely this assumption. There is a good reason for it. With or without AI, there is always a risk of a democratic country sliding into authoritarianism. And AI could potentially erode some of the checks and balances that prevent this from happening. I wrote before about the risk of a “Country of IRS agents in a datacenter,” with AI systems that would not leak, whistleblow, or resign if asked to go after a government’s political opponents.

There are at least several reasons why this concern is very real:

• Our laws have not caught up to AI, and the types of laws and regulations that are supposed to restrict the power of government do not anticipate or account for AI capabilities, for example, in terms of de-anonymization, mass surveillance, mass automated high-stakes decisions, and more.
• Of the three branches of government, the legislative and judicial branches have been much slower than the executive in adapting to AI. Hence they may not be able to serve as a check on the executive if the latter moves at AI speed.
• Compute inequality could lead to an inequality in political power. If a few people have access to the most advanced models, they may be able to use them to obtain strong advantages over the majority of people who do not have such access.

Oversight is more important than character

One approach to preventing concentration of power is through building AI systems of good character, which would not go along with such machinations. Claude’s Constitution has a thoughtful section on avoiding problematic concentrations of power. I share the intention, and believe character is an important component of alignment. But, I believe relying on the model’s character to prevent concentration of power scenarios is doomed to fail.

One reason is that I would not want to give models the autonomy that would be required for them to prevent concentration of power. For example, while I believe civil liberties in the U.S. are better off due to Edward Snowden’s revelations, I would not want an “AI Snowden” that leaks classified information. This is not a decision I am willing to place in the hands of AI, and it strikes me as deeply undemocratic for model makers to design their AI systems to be able to take such actions. 

Beyond the moral issue, AI models will typically not have the broader context to know whether or not their actions are part of a problematic power grab. A human worker can go home, talk to their neighbor, and read the news. An AI model, especially in a classified environment, is born and dies in the SCIF or cockpit, and has a very restricted information diet. Moreover, especially in the most sensitive deployments, users will need AI systems to follow clear and predictable rules on what they will and will not do. You do not want your wartime systems’ reliability to depend on the way they interpret Kant or Mill. Hence, in practice, there will be significant pressure to deploy reduced-refusal models in classified settings.

Generally, if our defense against concentration of power is “heroism” on the part of the AI, then we have already lost. AI systems should have good character, but by this I mean something like the “mensch” who helps their elderly neighbor carry groceries, rather than an artificial Gandhi, Churchill, Martin Luther King, or Mother Teresa. (Not coincidentally, while the “mensch” down the street can be uniformly appreciated, none of these heroic figures is uncontroversial.) AI should serve humanity, not lead it. 

Accelerating oversight is key to avoiding concentration of power. The very properties that make AI problematic as a moral actor—limited context and predictable adherence to rules—can make it an excellent monitor. Unlike humans, we can “erase the memories” of an AI monitor, which could enable to give it far more access to classified information than any human. And unlike human watchdogs, you cannot hide wrongdoing from an AI by burying it under a mountain of documents. Most importantly, how AI should be deployed in government, which decisions it should make, and how it will be overseen are decisions that should arise from the democratic process, not AI labs. 

In order to do this, we need to make sure that the bodies tasked with oversight have access to strong AI models. In fact, in order to make sure that the government remains “of the people, by the people, for the people,” we need to make sure that both the press and ordinary citizens have access to strong AI systems and can use them to increase transparency in government as well as make their voices heard in the democratic process.

Geopolitical shifts

The United States has been a dominant power for most of the last century. But as always, past performance is no guarantee of future results. These days, the most heated race is between the U.S. and China. I very much hope we can find ways for both countries to prosper rather than fall into a zero-sum competition. However, I do think it is important that the U.S. and its democratic allies keep their qualitative edge. If its current authoritarian regime does not change, a world in which China is the dominant power would not be a free one.

The U.S. has won its great conflicts—World War II and the Cold War—in large part due to its economic and industrial strength. Our current leadership in AI provides an opportunity to keep this momentum going. Export controls and other restrictions can buy the U.S. some time, but ultimately the way to advance is not only to slow China’s progress. It is to increase U.S. and allied capacity in compute, energy, talent, infrastructure, and deployment.

China now generates more than twice as much electricity as the U.S., and the gap is widening. If we consider the chart below, we should not be worried about flattening the blue line, but growing the red one.

Another advantage China has is that its public is far more positive on AI, while in the U.S. political headwinds could end up slowing progress. I don’t think the solution to this is a PR campaign to change AI’s image. Rather, we need to “show, not tell.” If we can show that AI provides tangible benefits to the American public while addressing the very real fears around job displacement, then I believe public opinion could shift.

“Hot mess”

If the AGI transition really did end badly, my guess is that it would not be because of a single incident or issue, but rather a combination of factors that led the world into a very bad place. No party to World War I intended it to become a four-year global conflict. But a number of structural factors, and one immediate trigger, led to one of the deadliest conflicts in human history. 

The AGI transition is likely to incur a number of radical economic, social, and political changes in a short period of time, which could lead to volatile conditions. By its nature, the “hot mess” scenario is unpredictable. There are many different ways in which multiple conditions could combine to produce disaster.

For example, many of the scenarios above could occur to a degree that is less than catastrophic but still highly destabilizing. These include:

• Non-catastrophic AI safety incidents can still undermine confidence and induce fear.
• Increased inequality and concentration of power, even if it falls short of destroying democracy or creating a permanent underclass and overclass, can still harm social cohesion.

• Disinformation and economic pain lead to a loss of trust in society and a more volatile political climate.
• Wild swings between widespread deployment of AI for economic growth and national security and restrictions on it via popular backlash could be destabilizing. In the worst case, we could see AI not deployed in some of its most beneficial applications (such as self-driving cars and healthcare), alongside accelerated deployment in some of its riskiest ones (such as autonomous lethal weapons).
• Lack of international cooperation increases tension between countries.
• Current nuclear powers fear losing their edge due to AI, and are incentivized to use their arsenal before defensive technology becomes too good.

Aside from all this, the mere growth in AI capability will be quite unsettling to many people. It is unsettling to me, and I have had more time to get used to it. Regardless of AI being aligned or misaligned, and regardless of one’s thoughts on questions of welfare or consciousness, modern AI systems (and even more so their near-term descendants) are entities of a very different type than humanity ever encountered.

By its nature, it is hard to predict exactly how a “hot mess” setting will end in disaster, but here is a rough outline of one potential such scenario. Imagine that there are significant job losses blamed (fairly or not) on AI, leading to a souring of public opinion. This also leads to a slowdown in datacenter construction and correspondingly some level of a compute crunch. As a result companies increasingly divert compute only for their most lucrative clients, which further exacerbates inequality between the “compute rich” and the “compute poor.” Then, there is a significant safety incident – a terrorist group uses AI to carry out a cyber or real-world attack of not catastrophic but significant impact. The U.S. government panics and decides to restrict all new models from general availability. The government is also worried that commercial deployment of AI will take away compute that it needs for its own needs. We arrive at a new status quo in which frontier AI models are used only in the labs themselves for AI R&D as well as for national security. Rumors of increasing powers of these internal AIs continue to circulate, spurred on by one or two examples where we learn about internal models’ capabilities because, through misalignment, they acted in the outside world without authority. China then shifts away from open-source models and starts its own intensive secret push toward AGI and ASI. The atmosphere is not unlike the H-bomb race between the United States and the Soviet Union after World War II, with both sides driven by fear of the other. At some point, one of the sides believes that the combination of their AI and robotics efforts has given them a significant but temporary advantage. The temptation to strike first is too strong to resist…

Can we just stop?

Given the litany of risks above, isn’t the logical conclusion to simply stop or pause advancing AI? This is a view held by many people. But there are many different ways to interpret “pausing” or “stopping” AI, and many different ways such a step could impact society, both positively and negatively.

For starters, this post is focused on the downsides of AI, but, as mentioned, there are clearly many potential benefits as well. A general technology such as AI is naturally “dual-use” and “dual-impact.” AI is not the only technology with this property. For example, all of the cyber risks would not exist if we did not use computers, but we believe the risks are well worth the benefits.

“Pausing AI” can refer to pausing any subset of the following activities:

1. Training new, bigger, and better models
2. Post-training and improving current models
3. Any AI research
4. Any AI research aimed at making models more capable, as opposed to making them safer or more aligned
5. Expanding deployment of AI
6. Continuing to serve existing models

There are multiple reasons why a pause could make sense:

1. Allow safety and alignment research to catch up to capabilities
2. Allow time for society and governments to adapt to the risks
3. Reduce the heated race dynamics that can result in cutting corners in safety

Out of all of these, I find the first reason most compelling. Allowing time for society to adapt sounds good in principle, but the quick reaction to COVID-19 compared with the sluggish reaction to climate change shows that societies and governments can respond on wildly different timescales. So I would not assume a pause automatically buys useful adaptation time, especially if AI risk pattern-matches more to climate than to COVID-19: diffuse, politically contested, and gradual until it is not.

The third option, reducing race dynamics, might or might not work depending on how a pause is implemented. In the commercial space, a pause in new models while not pausing deployment could lead to an even more heated race as companies try to take as much market share before the “thaw.” Similarly, in the geopolitical setting, there can also be a race to do R&D that is as close as possible to whatever threshold is defined.

Verification of a pause can be highly nontrivial. This is especially true if we want to allow some types of work while pausing others. It can be hard to distinguish between alignment and capability research. Also, given the phenomenon of universality of computation (aka “Turing completeness”), it might be possible to bypass verification efforts by making training look like inference. Moreover, extremely intrusive verification efforts could come with their own potential for concentrating power. That said, I believe it is important to research verification methods, and a verified pause should certainly be one of the policy options we consider.

People sometimes think of “AI pause” as requiring control and hence concentration of power. While verification does require some elements of control, I was pleasantly surprised to see that AI 2040 Plan A by the AI futures project, had several elements that call for more distribution of power, including total research transparency and broad diffusion of AI.

A pause might also serve to entrench the current leading AI labs by not enabling others to catch up. This is similar to how the Nuclear Nonproliferation Treaty entrenched the powers that conducted tests before it was signed. In the case of nuclear weapons and the NPT, we decided it was worth the tradeoffs, but AI, given its dual use nature, is different. This does not mean a pause is a bad idea but we should not think of it as a simple panacea. The devil will be in the details. 

What can we do?

One of the tricky aspects of a variety of bad scenarios is that actions taken to avoid one scenario can exacerbate another. But there are some directions that would be good in most cases.

The first of those is improving technical AI safety and alignment, and, in particular, our ability to trust and control advanced AI systems. AI safety is clearly important for the “classical catastrophic risk” scenario, but it is also crucial for the other scenarios. AI safety is required for trustworthy deployment of AI in government and, in particular, for oversight. And safety will improve stability and predictability in general, reducing the volatility in the “hot mess” scenario.

However, controlling AI safety is not enough, even for the catastrophic-risk scenarios. We need defensive acceleration to improve societal resilience. This includes strengthening cybersecurity as well as improving areas such as DNA-synthesis monitoring to ensure that constructing bioweapons is not just an “information bottleneck,” but also faces real barriers even for people assisted by advanced AI systems.

We need to do more to make sure that our laws catch up to AI, and do not enable AI being used to surveil people or to grab power. This is a common sense position that is broadly shared by Americans across both sides of the aisle. We need to accelerate AI use by oversight bodies. Part of it is to make sure that people across government, academia, and the media have a realistic understanding of current capabilities of AI and the pace of progress. Right now it seems that many prefer to “bury their head in the sand” and have little understanding of what AI can do now, let alone what it could do by 2030. 

Related to the control–distribution tradeoff, we will also need to think about how to trade off security and privacy for AI systems. On one hand, individual privacy has always been and will remain one of the strongest bulwarks against totalitarianism. On the other hand, practices such as pure zero-data retention (ZDR) could be problematic when advanced AI systems can create powerful cyberweapons or bioweapons. I believe that the solution is to use AI to monitor AI. We can ensure that data is only viewed by AI monitors that have very clear specs of what they can and cannot report, with strict control over retention periods and no access by humans.

Making society resilient for AI also means ensuring its economic benefits are widely distributed. If the bulk of society suffers the short-term pain, while a small fraction enjoys the gains, this will make the “hot mess” scenario much more likely. Luckily, any massive economic impact of AI will also be accompanied by a massive increase in growth. Such growth can enable policy responses that were not available before, including significant increases in the social safety net while still reducing the national deficit.

Finally, I am concerned that fears about risks could lead us to abandon the practice of iterative deployment, whereby state-of-the-art models have been widely available. The practice of iterative deployment has so far helped spread AI’s benefits and improve our understanding of its risks. I am happy that ChatGPT is used by nearly a billion people today, rather than in the counterfactual world where advanced AI would have been reserved for national security and AI research (or only for automating away jobs by enterprises). A world in which access to the best AI systems is restricted to the “chosen few” is a highly unequal one.

While many agree that iterative deployment has been positive so far, I can understand the fears of continuing on this path once AI systems achieve critical capabilities in areas such as cybersecurity or virology. Yet, I believe that it is possible to continue deploying such systems in a safe and responsible manner. The key to this is strong technical safety guarantees, as well as robust monitoring. Consider the point of view of a North Korean intelligence officer who is considering using an American AI model for illicit purposes. If the only risk is refusal, then they may go ahead and give it a shot. But if they fear detection, and, with it, the unraveling of their plan (and likely their head), then the calculus becomes quite different.

Some might say that we cannot trust our technical safety enough to share powerful models with the public, even with heightened refusals and monitoring, and hence such systems should be reserved only for internal deployment or national security. My answer is that these are the most sensitive and risky applications of AI. If our technology is reliable enough to be deployed for national security or to train its own successor, we should also be able to build a good enough safety stack to distribute its benefits safely. Yes, it is true that internal deployment or national security have a different attack surface than that of a model that is available to a billion users. But such closed environments also provide more opportunities for silent (and hence riskier) failures, compared to a setting with millions of eyeballs and independent scrutiny.

I am an optimist. I think that more likely than not, we will not fuck it up too royally, and 2030 and the years beyond will be very good for humanity. But I do lose some sleep about the scenarios above. There is work to be done if we want to ensure a future in which all humans, and not a small fraction, are flourishing and empowered. Panic-driven wild swings in both directions (“Models are scary!”, “We must beat China!”) are likely to be counterproductive. But if we remain empirical in evaluating both risks and mitigations, and keep iterating and learning, I believe we can ensure that AGI’s benefits are spread widely.

Notes:

¹ The title could have been any year between 2030 and 2040. I am not making here any specific timeline predictions. However, since the uncertainty about AI’s increases exponentially with time, I wanted to focus attention on the next 5-10 years.

² I focus on the U.S. for two reasons: (1) I am an American citizen, live, work, and raise kids in the U.S., and so have a personal interest in its well-being; and (2) because of its unique position, a catastrophic outcome for the U.S. is likely to have impacts worldwide.

³ In this informal blog I am not making a precise definition of “bounded alignment” nor justifying the claim that this is the dominant form of misalignment exhibited by current models. I am also not claiming that this is guaranteed to be the case as capabilities grow, However, I do believe that, if we are careful enough in monitoring and evaluating, including during training and post deployment, we will be able to know if that changes.

⁴ This is a simplification, assuming this level is a scalar, though in practice there would be several dimensions of misalignment.

By Boaz Barak

Authors: Alexey Barsukov, Roman Feller, Maximilian Hadek, Davide Perinti

We study the computational complexity of problems that ask if a given graph admits an edge-coloring that does not contain an edge-colored clique from some fixed finite family. We show that every such problem is poly-time equivalent to a Constraint Satisfaction Problem, yielding a P vs. NP-complete dichotomy. Our main contribution lies in the reduction from the CSP to the coloring problem where we apply methods from Ramsey theory and a novel notion of cut-homotopy.

Authors: Holger Spakowski

The exact domatic-number problem asks, for a fixed integer k, whether a given graph G satisfies dom(G) = k. Riege and Rothe proved DP-completeness for every fixed k >= 5, while the cases k = 3 and k = 4 remained open. We close this classification gap. The main ingredient is a polynomial-time reduction from 3SAT whose output graphs have domatic number 4 in the satisfiable case and domatic number 2 in the unsatisfiable case; in particular, the reduction never produces a graph of domatic number 3. This directly realizes the route suggested by Riege and Rothe for closing the remaining cases. Together with a simpler three-versus-two reduction, this yields DP-completeness of Exact-3-DNP and Exact-4-DNP. The proofs are constructive and give explicit graph gadgets whose local domination constraints encode truth assignments and clause satisfaction. The soundness arguments show conversely that any sufficiently large domatic partition enforces the intended consistency conditions and therefore yields a satisfying assignment. Consequently, Exact-k-DNP is DP-complete for every fixed k >= 3, completing the fixed-value classification from k = 3 onward.

Authors: Grigorii Braulov, Nikolai Chukhin, Alexander S. Kulikov, Ivan Mihajlin

The graph homomorphism problem HOM is: given an $n$-vertex source graph $G$ and an $h$-vertex target graph $H$, is there a mapping from $V(G)$ to $V(H)$ that preserves edges? A straightforward brute-force algorithm for HOM has running time $O(2^{n \log h})$ and it is known that, under ETH, there are no $2^{o(n \log h)}$ algorithms. In recent years, less restrictive graph parameters $p$ have been identified that allow one to solve HOM in time $p(H)^{O(n)}$. Examples include treewidth, maximum degree, and track number. On the other hand, it is known that the chromatic number parameter is too small: under ETH, HOM cannot be solved in time $χ(H)^{O(n)}$. We study the complexity of HOM in terms of the degeneracy of $H$. This is perhaps the most natural unresolved graph parameter between the known algorithmic and hardness regimes: on the one hand, each of bounded treewidth, bounded maximum degree, and bounded track number implies bounded degeneracy; on the other hand, bounded degeneracy implies bounded chromatic number. Our results show that, at the same time, the influence of degeneracy of $H$ on the complexity of HOM differs significantly from that of the previously studied parameters. We show that, under ETH, there is no $2^{o(degen(H) n)}$ algorithm for any value of $degen(H)$ as a function of $n$. We also show that bounded degeneracy alone does not make target size benign: even targets with $degen(H)$ at most $2$ and quasi-polynomial size force $n^{Ω(n)}$-scale hardness. Finally, we introduce a no-compression barrier that explains why the known fine-grained lower bounds for sparse $2$-CSP are not tight under ETH. Moreover, it shows that substantially stronger lower bounds for polynomial-target degeneracy are unlikely to follow from standard reductions from sparse $3$-SAT.

Authors: Endre Boros

In a binary polynomial optimization problem (BPO, in short) we are maximizing a multilinear polynomial expression depending on n binary variables. This is a hard optimization class, containing many NP-hard problems, including unconstrained quadratic binary optimization. Several tractable special classes were considered in the literature, including problems with bounded tree-width (Crama, Hansen, Jaumard, 1990), Berge-acyclic problems (Buchheim, Crama, and Heck, 2019), $β$-acyclic problems (Del Pia and Di Gregorio, 2022, 2023), limited reach problems (Clausen, Crama, Lusby, Rodríguez, and Ropke, 2024), and $α$-acyclic problems with bounded rank (Del Pia and Khajavirad, 2025). We focus on a general variable elimination scheme for BPO, and develop the unique explicit multi-linear polynomial form for the equivalent BPO problem obtained after the elimination of a given subset of the variables. The obtained closed form representation of such an equivalent BPO problem allows us to characterize new special classes for which this elimination method, when applied recursively, provides a computationally efficient solution. Our approach is elementary1, algebraic, and provides efficient solution to a wide problem class that properly generalizes all of the above mentioned tractable special cases.

Authors: Mark Bun, Mandar Juvekar, Samuel King

We study batch verification in QMA query and communication complexity, where the goal is to understand how the resources needed to verify $m$ copies of a Boolean function $f$ depend on $m$. We give a general technique for proving lower bounds on the witness-query tradeoff needed to batch verify a function $f$ in terms of its approximate degree. Applying this technique to an explicit family of DNF formulas $f$, we show that attempting to save even a constant factor on the witness length of the baseline approach to batch verifying $f$ necessitates a large polynomial increase in the query cost. We also obtain new lower bounds on the QMA query complexity of read-once CNF formulas and on the surjectivity and $k$-element distinctness functions. Our lower bounds also lift to give communication analogs of these results.

Authors: MIT CompGeom Group, Hugo A. Akitaya, Erik D. Demaine, Fabian Frei, Stefan Langerman, Anna Lubiw, Joseph O'Rourke

Research on Dürer's problem focuses on edge unfoldings of convex polyhedra that avoid overlap. We invert the goal and find unfoldings that overlap at some point to any given thickness t. We have two main results. The first is that, if we allow unfolding cuts that do not follow polyhedron edges, then there is a convex polyhedron that can unfold with overlap of any given thickness. The second result is that for any given thickness, there is a convex polyhedron with an edge unfolding that overlaps to that thickness.

Authors: Félix Ruyffelaere, Michel Henry, Jonathan Lambrechts, Jean-François Remacle

This paper presents a robust, fully Lagrangian framework based on the Particle Finite Element Method (PFEM) capable of simulating multiphase flows with an arbitrary number of immiscible phases. Interface-tracking methods can sometimes suffer from numerical diffusion or allow the underlying mesh resolution to prematurely dictate topological changes. To address these limitations, we introduce a dynamic mesh adaptation strategy that naturally preserves sharp geometric interfaces without relying on classical constrained triangulation. A node-empty disk is assigned to each segment of the discretized interface, ensuring that the edge is part of the Delaunay triangulation. Our approach decouples the interface physics from the grid size, allowing the integration of sub-grid physical models to properly govern topological changes independently of the user-defined mesh size. The capabilities and accuracy of the framework are validated against standard multiphase benchmarks, closely matching references while maintaining a remarkably low overall node count. We demonstrate the scalability and geometric versatility of the method, in particular with a challenging 16-phase Rayleigh-Taylor simulation.

Authors: Thijs van der Horst, Tim Ophelders

The Fréchet distance is a well-studied distance measure for paths in a metric space. It is mostly studied for paths in $d$-dimensional Euclidean space. Here, computing the Fréchet distance between two polylines takes time roughly quadratic in the number of vertices. Assuming the strong exponential time hypothesis (SETH), it cannot be approximated to within a factor less than $3$ in strongly-subquadratic time. Recently, it was shown that for any $\varepsilon>0$, there exists a randomized algorithm that can compute a $(7+\varepsilon)$-approximation in strongly-subquadratic expected time [Cheng, Huang, and Zhang; STOC'25]. For polylines with $n$ and $m$ vertices in a Euclidean space of constant dimension, where $n \geq m$, their algorithm takes $O(nm^{0.99} \log(n/\varepsilon))$ time in expectation. We present a deterministic approximation algorithm that significantly improves upon the approximation factor and running time. Specifically, our algorithm computes a $(3+\varepsilon)$-approximation in $O(nm^{2/3} \log n \cdot \log (\frac{1}{\varepsilon} \log n))$ time. Our algorithm nearly matches the conditional lower bound on the approximation factor implied by SETH. For polylines in $\mathbb{R}$, we present a $3$-approximation algorithm that runs in $O(nm^{2/3} \log^{5/3} n)$ time, and exactly matches the conditional lower bound. For our results, we introduce a general strongly-subquadratic time $3$-approximate decision algorithm. This algorithm makes no assumptions on the ambient metric space, and relies only on standard assumptions on the so-called free space of the input paths. Under some mild assumptions, our decision algorithm leads to a $(3+\varepsilon)$-approximation algorithm in general metric spaces. These assumptions hold automatically for polylines in any metric space $(\mathbb{R}^d, L_p)$ with $p \geq 1$.

Authors: Xifan Yu

In this work, we initiate the study of strongly refuting the satisfiability of random ordering constraint satisfaction problems. We show that there is a polynomial-time $\varepsilon$-refutation algorithm for random ordering CSP with predicate $P$ when the number of clauses is above the threshold $\tildeΩ\left(n^{d/2}/\varepsilon^2\right)$, where $d$ is the coordinate degree of the predicate $P$. We further give a smooth three-way tradeoff between the running time, the clause density, and the refutation strength $\varepsilon$ using the Kikuchi method. Finally, we complement our algorithmic results with a computational lower bound based on the class of low coordinate degree algorithms, providing evidence that the established three-way tradeoff is near optimal.

Authors: Alexander Munteanu, Matteo Russo, David Saulpic, Chris Schwiegelshohn

Terminal embeddings have emerged as a powerful tool for dimension reduction. Given a set of points $P\subset \mathbb{R}^d$, a terminal embedding is a mapping $f:\mathbb{R}^d\rightarrow \mathbb{R}^t$ that preserves the pairwise distance between any pair of points $p\in P$ and $q\in \mathbb{R}^d$ up to small distortion under this mapping. Terminal embeddings have been particularly fruitful for constructing $k$-means and $k$-median coresets, where the objective is to find a typically weighted subset $Ω$ of $P$ such that for any candidate solution, the cost of the clustering objective on $Ω$ approximates the cost of the clustering objective on $P$ up to small distortion. Unfortunately, these techniques have not been extended to more complicated structures such as clustering time-series data under common straight-line interpolation between measurements. The main issue is that terminal embeddings, arguably the central technique in this line of research, cannot be linear and are thus not immediately suitable to preserve linear structures. In this work, we develop a generalization of terminal embeddings to affine line-segments that overcomes this issue. We showcase their applicability by using our lines-preserving terminal embeddings to obtain the first dimension-free coresets for clustering time-series under the Fréchet distance. The underlying dimension reduction uses Johnson-Lindenstrauss (JL) embeddings, and our experiments indicate that terminal embeddings perform similarly to JL and favorably against PCA for synthetic and real-world time-series, while only terminal embeddings extend pairwise distance preservation to the full ambient space.

Authors: Sijin Peng

Local Computation Algorithms (LCAs), introduced by Rubinfeld, Tamir, Vardi, and Xie (2011), are a special type of sublinear algorithms that, given probing access to a possibly massive input, are required to provide query access to a consistent solution, without maintaining a state between different queries. In this paper, we try to understand LCA through the lens of complexity classifications, described by the following question: Given a target complexity function $f(n)$, is there a problem whose local computation complexity is $f(n)$, up to polylogarithmic factors? We restrict our focus to Locally Checkable Labeling (LCL) problems, which can be seen as constant-degree constraint satisfaction problems. Possible complexity classes of this problem family have been extensively studied in various distributed computation models, including the $\mathrm{VOLUME}$ model proposed by Rosenbaum and Suomela (2020), which is an invariant of local computation algorithms with additional locality requirements. In this paper, we provide new LCL complexity constructions in the $\mathrm{VOLUME}$ model, and generalize the results to LCAs. Specifically, we show that there are LCLs whose probe complexities in the $\mathrm{VOLUME}$ and LCA models are $Θ(\log^k n)$ and $\tilde Θ(n^{p/q})$ for any positive integer $k \ge 1$ and rational $p/q \in (0,1]$. Our approach, completely different from the approach to a similar result in the distributed $\mathrm{LOCAL}$ model by Balliu et al. (2018), is to stack instances of complexity $Θ(\log n)$ and $\tilde Θ(n^{1/k})$ in the $\mathrm{VOLUME}$ model constructed by Rosenbaum and Suomela (2020).

Authors: Yael Kirkpatrick

We study the problem of approximating the diameter of directed graphs under the min-distance measure, defined as $d_{\min}(u,v) = \min(d(u,v), d(v,u))$. Unlike standard shortest-path distance, min-distance is not a metric, which renders many classical techniques inapplicable. Prior work has therefore focused on approximating this parameter, culminating in an approximation-runtime tradeoff by Dalirrooyfard et al. [ICALP'19] giving a $4k-1$ approximation in $\tilde{O}(mn^{1/(k+1)})$ time for any positive integer $k$ and, more recently, the first near-linear time constant approximation by Chechik and Zhang [FOCS'22], where they obtained a 4-approximation to the min-diameter. In this work we present a randomized near-linear time algorithm that achieves a $3$-approximation to the min-diameter, outperforming all known approximation-runtime tradeoffs. Our approach introduces a novel type-classification framework that may be of independent interest. We further extend our techniques to the more general setting of multimode graphs, recently introduced as a generalization of min-distance by Kirkpatrick and Vassilevska W. [MFCS'25]. For directed $2$-mode graphs, we obtain a $3$-approximation to the diameter in near-linear time, dramatically improving over the previously best known $n$-approximation. Our results significantly narrow the gap between min-distance and multimode distance approximations, and open new directions for understanding graph parameters under non-metric distance measures.

Authors: Tamara Kaplan, Nimrod Kaplan, Haim Kaplan

We introduce a streaming model that uses both catalytic and regular memory. In this model, we show how to exactly compute the frequency moments using a logarithmic number of bits of regular memory and a polynomial number of bits of catalytic memory. More generally, we show how to compute arbitrary polynomials of the item frequencies exactly within the same space bounds. As an application, we obtain catalytic streaming algorithms that exactly compute the number of distinct elements in a stream, count the number of triangles (or any other small subgraph) in a graph whose edges arrive in a stream, and identify heavy hitters. Our algorithms for frequency moments perform a constant number of passes over the stream, and for polynomial evaluation, we require one more pass than the degree of the polynomial. By relating our catalytic streaming model to the catalytic communication model introduced in Pyne et al., we show that catalytic memory is not useful for any one-pass streaming algorithm. For lower bounds on multipass streaming algorithms, the impossibility results of Pyne et al. are not strong enough. However, using a different technique, we show that under certain natural restrictions, no catalytic streaming algorithm can compute the second frequency moment in fewer than three passes. This definition of the restricted class of two-pass algorithms then guides us in the design of a two-pass algorithm for computing the second moment exactly that circumvents these restrictions and breaks the three-pass barrier.

Authors: Romain Bourneuf, Nathan Claudet, Sang Yoon Kim, Rose McCarty, Blair D. Sullivan, Stéphan Thomassé

We introduce a new notion of distance between two graph states $|G\rangle$ and $|G'\rangle$ on the same set of qubits. This distance is the minimum number of ancilla qubits in a graph state $|\widehat{G}\rangle$ from which both $|G\rangle$ and $|G'\rangle$ can be ``easily prepared''. (When preparing graph states, we are only allowed to use one-qubit Clifford gates, one-qubit Pauli measurements, and classical communication.) We give a graphical description of this distance through the lens of vertex-minors. We then show how this distance yields quantum network analogs of many graph edit-distance problems. Using this framework, we develop classical algorithms for identifying the ``highly entangled clusters'' of a graph state $|G\rangle$. The ancilla integrity problem asks, given a graph $G$ and integer $k$, for the minimum -- over all graph states $|G'\rangle$ with distance at most $k$ from $|G\rangle$ -- of the maximum component size of $G'$. Up to a factor of $2$ in the number of ancilla qubits, this problem is equivalent to rank integrity, where the distance between $G$ and $G'$ is instead the minimum rank of the sum of their adjacency matrices over $\text{GF}(2)$. We prove that rank integrity is XP parameterized by $k$. We also prove the complementary hardness result that rank integrity is W[1]-hard in $k$. Finally, we give an explicit $\mathcal{O}(n^6)$-time algorithm for ancilla integrity when $G$ has $n$ vertices and $k=1$.

Authors: Dimitrios M. Thilikos, Sebastian Wiederrecht

The Irrelevant Vertex Technique is one of the cornerstones of algorithmic graph theory, underlying Robertson and Seymour's algorithm for \textsc{Disjoint Paths} and much of the algorithmic Graph Minors theory. We show that, in the setting of spanning routing, this technique exhibits an exact combinatorial limitation. Unlike classical routing problems, spanning routing is not governed by the number of distinguished vertices but by the way they are distributed throughout the graph. The input is a triple $(G,R,\mathcal{T})$ where $(G,R)$ is an annotated graph and $\mathcal{T}$ is a set of terminal pairs. The goal is to determine if $G$ contains a family of internally disjoint paths connecting the pairs in $\mathcal{T}$ such that the union of the paths spans the set $R$. We identify a new structural parameter of annotated graphs, called $\mathsf{depth}_2$, that measures precisely this phenomenon. Our main result is a complete combinatorial dichotomy: for every red-minor-closed class of annotated graphs, the Irrelevant Vertex Technique applies to \textsc{Spanning Disjoint Paths} \textsl{if and only if} the class has bounded $\mathsf{depth}_2$. Thus $\mathsf{depth}_2$ forms the exact structural boundary between classes where the Robertson-Seymour paradigm survives and those where it breaks down. Our proof combines a new local structure theorem for annotated graphs of bounded $\mathsf{depth}_2$ with a spanning analogue of the celebrated Vital Linkage Theorem. The resulting algorithm solves \textsc{Spanning Disjoint Paths} in time $2^{2^{\mathbf{poly}(k+d)}}\cdot n^2$ where $d$ is the $\mathsf{depth}_2$ of the input instance. We provide matching lower bounds showing that beyond bounded $\mathsf{depth}_2$ no irrelevant-vertex rule can exist, even on planar graphs. In particular, $\mathsf{depth}_2$ is the exact combinatorial barrier for the Irrelevant Vertex Technique under spanning constraints.

Authors: Yuriy Dementiev, Fedor Pribytkov, Danil Sagunov

We study the problem of computing an envy-free (EF) allocation of $m$ indivisible items among $n$ agents when items come in three distinct types. Each agent holds additive valuations over item types that may be positive (goods), negative (chores), or mixed. We present the first subexponential-time algorithm with running time time $(n \cdot m)^{O(\sqrt{n})}$ that finds an EF allocation whenever one exists, or correctly reports that none exists. Our approach exploits a geometric representation of EF allocations as convex polyhedra in $\mathbb{R}^3$ and applies Miller's planar cycle-separator theorem to recursively decompose the agent set into balanced subgroups. We further extend the algorithm to handle agents whose allocations are fixed in advance, preserving envy-freeness across all agents.

Authors: Amir Ali Ahmadi, Pravesh K. Kothari, Yukai Tang

We present a polynomial-time algorithm for optimally coloring perfect graphs that is based entirely on graph-theoretic operations. At its core, the algorithm decides whether a perfect graph contains a clique of a given size by iteratively counting walks in the graph with certain weights assigned to its edges and nonedges. These weights are initialized according to a uniform scheme and then updated in each iteration based on the walk counts from the previous iteration.

Authors: Ryosuke Yamano, Tetsuo Shibuya

We study exact algorithms for Equal-Subset-Sum in the worst-case setting: given a set $S$ of $n$ integers, find two distinct subsets $A,B\subseteq S$ whose sums are equal. We establish a new state-of-the-art bound for this problem by improving the fastest known algorithm, due to Randolph and Węgrzycki (STOC 2026), from $O^*(1.7067^n)$ time and space to an algorithm that runs in $O^*(1.6994^n)$ time and uses $O^*(1.5664^n)$ space. We also improve the best known polynomial-space running time, due to Mucha, Nederlof, Pawlewicz, and Węgrzycki (ESA 2019), from $O^*(2.6817^n)$ to $O^*(2.5430^n)$. Finally, we investigate time-space tradeoffs for this problem and improve the running times achievable under a broad range of exponential-space bounds.

Authors: Stephen Arndt, Benjamin Moseley, Kirk Pruhs, Michael Zlatin

Contention resolution schemes (CRS) are a fundamental and widely applied tool for rounding fractional solutions subject to combinatorial constraints. However, the known analyses of CRS generally only guarantee lower bounds on the expected value and concentration on the upper tail, but no concentration on the lower tail. Thus, CRS are generally not applicable to problems that contain covering constraints, since certifying a covering constraint holds requires a lower tail bound. Our main contribution is to derive lower tail bounds for the output of a particular contention resolution scheme, the random-order CRS of Adamczyk and Włodarczyk, which we call AW. We show that every linear function of the rounded solution attains a constant fraction of its expectation with a failure probability that is dimension-free, depending only on the expected value and on the number of matroids, but not on the size of the ground set. Our analysis is driven by a new property we call \emph{strong $λ$-boundedness}, which strengthens the known $λ$-boundedness of AW by providing two-sided control on how rounding propagates between elements. We then introduce a random process capturing AW, a \emph{sequential selection process}, that may be of independent interest. We prove lower tail bounds for any strongly $λ$-bounded sequential selection process. To demonstrate the applicability of our new tail bounds, we apply them to two problems involving covering constraints. The first result is an $O(k \log k)$-approximation for $k$-matroid intersection coloring (improving the prior $O(k^2)$) when the chromatic number of at least one matroid is $Ω(k^3 \log n)$, where $n$ is the number of elements. The second is the first bicriteria approximation algorithm for monotone submodular maximization under $k$ matroid constraints together with packing and covering constraints.

Authors: Yiding Feng, Siyu Liu, Zonghan Yang, Yuhao Zhang

We study non-clairvoyant scheduling for batched Large Language Model (LLM) inference under a hard Key-Value (KV) cache memory budget. Each request has a known prompt length but an unknown response length, and its memory footprint comprises a fixed prompt component together with a response component that grows with each decoded token. At each decoding round, the scheduler chooses a feasible batch of active requests; evicting a request discards its accumulated cache states, wasting prior computation. The goal is to minimize total completion time against the optimal clairvoyant schedule that knows all response lengths. We present the first constant-competitive algorithm for arbitrary prompt lengths and arbitrary response lengths with no additional assumptions. Rather than relying on a single universal scheduling policy, our algorithm is built on a novel regime-aware routing framework. Specialized sub-schedulers handle different memory-growth geometries, while a meta-scheduler time-shares the memory budget across them and dynamically routes each job as its execution progressively reveals its behavior. This framework also yields constant-competitive guarantees for makespan and for total completion time under online arrivals.

Authors: Nima Anari

We extend Gårding's theorem to homogeneous posynomials: if a finite positive sum of monomials with arbitrary nonnegative real exponents is zero-free on a product of right half-planes, then its degree-normalized root is concave. Consequently, zero-freeness in a sector of aperture $απ$ implies $α$-fractional log-concavity. This sharpens generic mixing and domain-sparsification guarantees for fixed-size matchings and nonsymmetric determinantal point processes. The result was developed in an AI-assisted interaction initiated and checked by the author; Codex also assisted with assembling and typesetting the manuscript.

Authors: Jelena Diakonikolas

We study stochastic fixed-point equations $\mathbf{T}(\mathbf{x}) = \mathbf{x}$ over normed spaces $(\mathcal{E}, \|\cdot\|)$, where the operator $\mathbf{T}$ is nonexpansive or contractive and is accessed only through unbiased stochastic evaluations with bounded second central moment. Given $ε> 0, δ\in (0, 1)$, the goal is to output $\mathbf{x} \in \mathcal{E}$ such that $\|\mathbf{T}(\mathbf{x}) - \mathbf{x}\| \leq ε$ with probability at least $1-δ$. We introduce VR-GHAL, a variance-reduced gradual Halpern method for quadratically smoothable Banach spaces. The key algorithmic ingredient is a recursive stochastic estimator based on clipped differences of oracle evaluations: instead of clipping $τ(\mathbf{x}; ξ)$ itself, we clip stochastic differences at the Lipschitz scale $γ\|\mathbf{x} - \mathbf{y}\|$. This makes the estimator pathwise Lipschitz along the algorithmic trajectory while permitting martingale concentration under finite second moments in the native norm. Our main theorem gives an anytime high-probability residual bound: on a single event of probability at least $1 - δ$, the residual decreases nearly geometrically across epochs, up to lower-order logarithmic factors. Under only bounded variance, displaying only the dependence on the target error $ε$ and Lipschitz constant $γ\in (0, 1]$ of $\mathbf{T}$, the resulting oracle complexity is $\min\{ε^{-5}, (1-γ)^{-3}ε^{-2}\}$. Under a Lipschitz-in-expectation oracle, the dependence improves to the corresponding $ε^{-3}$ nonexpansive rate (i.e., for $γ= 1$), and under samplewise nonexpansiveness to $ε^{-2}$.

Authors: Jiale Cheng, Ziao Wang, Lei Ying

This paper studies graph matching under the correlated $\text{Erdős-Rényi}$ (ER) graph pair model. This model first samples an $\mathrm{ER}(n,\fracλ{ns})$ base graph, whose edges are then independently subsampled twice with probability $s$ to produce two correlated $\mathrm{ER}(n,\fracλ{n})$ graphs. We propose a graph matching algorithm that has $n^{2+o(1)}$ time complexity and achieves almost exact recovery with high probability under the assumptions $λ=(\log n)^{α+o(1)}$ for some $α\in(0,1)$ and $s\in(\sqrt{C_{\mathrm{Otter}}},1]$, where $C_{\mathrm{Otter}}\approx 0.338$ is Otter's tree-counting constant. This is the first algorithm with almost quadratic time complexity in this regime of $λ$, while the best known result in this regime is the chandelier-counting algorithm with time complexity $O(n^{c(s)})$, where $c(s)\rightarrow \infty$ as $s$ approaches $\sqrt{C_\mathrm{Otter}}$ from above. The proposed algorithm is based on local tree correlation tests. It uses a rank-based algorithm to match the vertex pairs instead of threshold-based rules in the literature. This avoids the need of computing an explicit threshold, which is computationally difficult to obtain. To prove the almost exact recovery result, we establish a new analysis of tree correlation tests in the diverging-degree regime, where both the mean degree and the tree depth grow with $n$. Based on this new result, we establish the existence of a threshold for a threshold-based graph matching algorithm via local tree correlation tests. Finally, we couple the performance of the rank-based algorithm with the threshold-based algorithm to show almost exact recovery.

Authors: Chenghua Liu, Yuxin Zhang

We show that every weighted hypergraph on $n$ vertices admits a spectral $\varepsilon$-sparsifier with $O(n\log n/\varepsilon^2)$ hyperedges, strengthening the independent STOC 2023 works of Lee and Jambulapati--Liu--Sidford by removing their rank dependence and answering Lee's open question on whether this loss is inherent. The key idea is global-dictionary chaining: after choosing clique edge weights with balanced effective resistances, every hyperedge seminorm is Lipschitz with respect to the same global-dictionary norm generated by normalized vertex-pair directions; the local rank complexity is thereby replaced by the Gaussian width of this common dictionary. Since these STOC 2023 works have become standard analytic primitives across a broad subsequent literature on spectral hypergraph sparsification and its variants, our rank-independent theorem sharpens many later guarantees that inherit their sampling bounds.

Authors: Timothy L. H. Wee, Kaylee Y. Yang, Zhou Fan, Cheng Mao

We study the problem of recovering the correspondence between a collection of $n$ points in $\mathbb{R}^d$ and a noisy, permuted version of those points. In the high-dimensional regime $d=ω(\log n)$, under a Gaussian model with noise variance $σ^2=d/(b\log n)$, prior work identifies $b=2$ as the threshold for almost exact recovery. We prove that this threshold is all-or-nothing: for every fixed $b<2$, no estimator recovers a positive fraction of the matching, and even estimating the matched point cloud in Euclidean distance is asymptotically no better than ignoring the correspondence. On the other hand, we consider a multi-view generalization of the problem where $K$ noisy, independently permuted copies of the same latent point cloud are observed. Here we show that a simple polynomial-time procedure recovers all relative matchings up to $o(n)$ errors whenever $b>K/(K-1)$. Thus multiple views can break the impossibility barrier $b=2$ for the original matching problem: in particular, for $3/2 < b < 2$, the two-view model has no nontrivial recovery, but a third view makes all latent correspondences efficiently recoverable.

Authors: Zhenghan Zang

In this paper we develop the framework of using a parametrized mapping $[σ(1), σ(2), \cdots, σ(n)] \mapsto σ(1)z + σ(2)z^2 + \cdots σ(n)z^n$ to perform runtime analysis on Shellsort. In particular, we show that the worst-case time complexity of Shellsort using Tokuda's gap sequence proposed in 1992 is at least $Ω(N^{1.26})$ with a generalisation of this result to any strictly decreasing gap sequence where each term at most a fixed distance away from a rational geometric sequence, and we also show that strictly decreasing gap sequences giving worst-case Shellsort time complexities of $O(N \log^c N)$ must have $Ω(\log N / \log \log N)$ terms of order $Ω(N / (\log \log N)^c)$.

Authors: Pavel Arkhipov, Nikita P. Kalinin

Continual counting under pure differential privacy is one of the simplest and most well-studied problems in the continual observation model. Nevertheless, an asymptotic gap remains between the best known upper and lower bounds for maximum squared error and mean squared error: the upper bound is $O(ε^{-2}\log^3 n)$, while the lower bound is $Ω(ε^{-2}\log^2 n)$, for both error metrics. The best known constant in the upper bound is achieved by the $k$-ary tree mechanism with the subtraction trick, due to Andersson, Pagh, Steiner, and Torkamani (FORC 2025). In this work, we improve the leading constant in the maximum squared error and the mean squared error. Our approach uses a general matrix factorization mechanism, yielding an improved bound for pure-DP continual counting that does not rely on a tree-based construction. The mechanism starts from a good-quality low-dimensional factorization, obtained via gradient-based optimization, and gives an explicit matrix construction that lifts this factorization to arbitrarily large dimensions, further improving its error guarantees. We offer an efficient algorithmic implementation of our mechanism. On the lower-bound side, we prove an $Ω(ε^{-2}\log^3 n)$ lower bound for the class of factorizations whose matrices have entries in $\{0,1\}$, matching the upper-bound asymptotics for this class. This class includes the binary tree mechanism and $k$-ary tree mechanisms without the subtraction trick. Extending this lower bound to arbitrary matrix factorizations, and beyond the matrix mechanism altogether, remains an open problem.

The excellent graphic novel

Prime Suspects: The Anatomy of Integers and Permutations

by Andrew Granville and Jennifer Granville,  illustrated by Robert J Lewis,

(I wrote a review of this graphic novel, for SIGACT News, here.)

has an appendix, which is not in graphic-novel form, where they describe some of the math talked about in the graphic novel. 

Here is a quote that intrigued me for two reasons

2 is the smallest prime factor of half of the integers,

3 is the smallest prime factor of one-sixth of the integers,

5 is the smallest prime factor of one-fifteenth of the integers,

and so forth.

Intrigue One: and so fourth ? Really? That would indicate that it is easy to know what the next fraction is.  Is it easy? That depends on your definition of easy.

Intrigue Two: What is the next fraction? What is the fraction asymptotically? I worked  both of these out fairly fast; however, I  don't think  and so forth is appropriate.

We derive the 1/15 for 5.  1/5 of all numbers have a factor of 5. Of those, only those that are \(\equiv 1,5 \pmod 6\) have 5 as the smallest  prime factor.  Hence \(2/6=1/3\) of those numbers have 5 as the smallest  prime factor. Hence the fraction is \(1/5 \times 1/3 = 1/15\). 

More generally: For all \(i\in N\) let  \(p_i\) be the \(i\)th  prime. What fraction of numbers have \(p_n\) as the smallest factor? \(1/p_n\) of all numbers have a factor of \(p_n\). If a number that is divisible by \(p_n\) is also  \(\equiv x \pmod {p_1p_2\cdots p_{n-1}}\) where \(1\le x\le p_1\cdots p_n\) and \(x\) is rel prime to \(p_1\cdots p_n\), then that number has  \(p_n\) as the smallest factor. Hence the fraction is 

\(\frac{1}{p_n} \times \frac{\phi(p_1\cdots p_{n-1})}{p_1\cdots p_n}=\frac{1}{p_n} \times \frac{(p_1-1)\cdots(p_{n-1}-1)}{p_1\cdots p_{n-1}}= \frac{1}{p_n}\prod_{i=1}^{n-1} (1-\frac{1}{p_i})\)

where \(\phi\) is the Euler-phi function which, on input \(x\), returns the number of naturals in [1,n] that are relatively prime to \(n\). We have used the following well known facts: (a) if \(a,b\) are rel prime then \(\phi(ab)=\phi(a)\phi(b)\), and (b) if \(p\) is prime then \(\phi(p)=p-1\) (this is obvious).  

The expression

\(\frac{1}{p_n} \times \frac{(p_1-1)\cdots(p_{n-1}-1)}{p_1\cdots p_{n-1}}\)

is good for exact calculation. Let's do one!

The fraction of numbers that have 7 as their least prime factor is

\( \frac{1}{7}\times  \frac{1\times 2\times 4}{2\times 3\times 5}= \frac{4}{105} \)

From the first three terms  \( \frac{1}{2}, \frac{1}{3}, \frac{1}{15} \) I do not think that and so fourth would make anyone think the next term was \(\frac{4}{105}\).

 But what is the fraction asymptotically? 

ChatGPT tells me (and I believe it) that

 \( \prod_{i=1}^{n} (1-\frac{1}{p_i})   \sim \frac{e^{-\gamma}}{\ln p_n} \) 

where \(\gamma\) is the Euler-Mascheroni constant, roughly 0.5772 (see here for the Wikipedia entry on that constant).

Hence we get that the fraction of numbers that have \(p_n\) as their smallest prime factor is 

 \(\frac{1}{p_n} \prod_{i=1}^{n-1} (1-\frac{1}{p_i})   \sim\frac{1}{p_n} \frac{e^{-\gamma}}{\ln p_{n-1}} \) 

Wolfram Alpha tells me (and I believe it) that

 \(e^{-0.5772}\sim 0.56146\).

 Hence we give our final approx for the fraction of numbers that have \(p_n\) as their least prime factor as

\(\frac{0.56146}{p_n\ln(p_{n-1})}\)   

I don't think this qualifies as and so forth.

By gasarch

Information-Theoretic Kuplex gives a signature-free Simplex protocol in which quorums cannot be transferred between parties. This post makes the earlier two round BFT protocol for $n=5f-1$ signature-free in the same way. We use the Chained Simplex outer protocol: a leader extends a certified chain by one valid block. For a map of the surrounding Simplex line, see the Simplex chapter. We view this as a simple extension of IT-Kuplex. We...

By Ittai Abraham, Sourav Das, Yuval Efron, Jovan Komatovic, Alejandro Ranchal-Pedrosa, Gilad Stern

We prove a near-maximum ($2^n / n$) circuit lower bound for the complexity class $\mathrm{E}^{\mathrm{prMA}}/_1$, corresponding to exponential time with access to a promise-$\mathrm{MA}$ oracle and one bit of advice. Our proof incorporates the iterative win-win paradigm (Chen--Lu--Oliveira--Ren--Santhanam, FOCS'23), the reduction from the Range Avoidance problem to circuit lower bounds (Jerabek, Ann. Pure Appl. Log. '04; Korten, FOCS'21), and the PCP theorem. Crucial to our proof is the analysis of the complexity class $\mathrm{P}^\mathrm{NP}[\textrm{#rounds}=r, \textrm{length}=s]$, which is $\mathrm{P}^\mathrm{NP}$ with $r(n)$ adaptive rounds of $\mathrm{NP}$ queries, where each $\mathrm{NP}$ query has witness length $s(n)$.

Here at the National Academy of Sciences, it seems that my first job is to serve on the selection committee for the prestigious Michael and Sheila Held Prize in combinatorial and discrete optimization and related areas. The committee chair, my former MIT colleague Madhu Sudan (now at Harvard), invited me to share the following message here on Shtetl-Optimized. (I’d add: put in the effort to nominate someone, and you can actually influence how things go!)

Dear Colleagues

I am writing to seek nominations for the 2027 Michael and Sheila Held Prize. The scope of the prize and nomination needs are described below. If you intend to nominate someone I would appreciate a heads up by email to madhu@cs.harvard.edu one month before the deadline (so email by Sept 8, 2026) to let me know your nomination is coming. (We may also reach out to you in response to coordinate multiple/overlapping nominations.)

The Held prize honors outstanding, innovative, creative, and influential research in the areas of combinatorial and discrete optimization, or related parts of computer science, such as the design and analysis of algorithms and complexity theory. This $100,000 prize is intended to recognize recent work (defined as published within the last eight years, i.e., on or after October 6, 2018).

All nominations must be submitted online by Monday, October 5, 2026 and include:

1. Nomination letter describing the candidate’s work and why he or she should be selected for the award. No more than three (3) pages.

2. Curriculum vitae. No more than two (2) pages.

3. Bibliography listing no more than twelve (12) of the nominee’s most significant publications.

4. Suggested citation. A 50-word summary stating why the nominee should be considered for this award.

5. Two letters of support. No more than one letter of support can be written by someone of the same primary work institution as the nominee.

The Held Prize is given to a person or a set of persons, as supported by a paper or a body of work. Unless otherwise stated, preference will be given to scientists who may be earlier in their careers or those whose work has not been recognized by other prizes or awards. Nomination restrictions can be found here. Joint nominations will only be considered when nominees have collaborated closely on the paper to be recognized by the award. If nominating multiple individuals for a paper with additional authors, please clearly explain the reason for nominating those chosen, as well as the reason for excluding other collaborators, if applicable. 

Please feel free to circulate this call further within your department

Best
Madhu Sudan, on behalf of The Michael and Sheila Held Prize Selection Committee

And while I have your attention, a second CS theory announcement: David Soloveichik, my wonderful friend and colleague in UT Austin’s Electrical and Computer Engineering Department, has funding for a postdoc for 1-2 years, to work on the thermodynamics of computation here at UT. This is a topic that I’ve been trying to learn more about as well, so I might get involved too! David writes, “the big picture is to think of thermodynamics (energy dissipation / entropy production) as CS complexity measures like time and space usage.” If you’re on the postdoc market and this sounds potentially up your alley, email David to learn more.

By Scott

Our press release this month features five papers: four of them are squarely property testing papers, and a fifth which I could not, in good conscience, bring myself to omit. Let us take a look: a paper that carries the submodularity testing story from two labels up to \(k\) of them; a striking super-polynomial quantum advantage for tolerant junta testing; a sublinear tester that decides whether a mystery multiplication table is an abelian group; and a rather pretty reworking of the Goldreich-Ron bipartiteness tester through the Max-Cut SDP. And then, saved for last, a rare treat that settles a question which has stood open since the 1980s, namely that bipartite matching is in NC. Without further ado, let us examine our spread.

Testing k-submodularity by Themistoklis Haris and Diptaksho Palit (arXiv) Let us begin where this story usually begins, with the question posed by Seshadhri and Vondrák in Is submodularity testable?: given oracle access to \(f \colon \{0,1\}^n \to \mathbb{R}\), can we distinguish submodular functions from those that are \(\varepsilon\)-far from every submodular function? Building up on a reduction to testing monotonicity over unbounded ranges, the authors exhibited a lower bound of \(\Omega(n)\) queries for testing submodularity. Blais and Bommireddi moved the question into the \(\ell_p\)​-testing model in Testing submodularity and other properties of valuation functions, where they obtained constant-query-complexity testers. The featured paper considers the following variation: take a partial partition of the ground set into \(k+1\) parts–eg, a string in \([k+1]^n\). Think of the last part as the elements unassigned so far (the “partial” in the “partial partition”). A function on these partial partitions is \(k\)-submodular if the marginal gains diminish no matter which part an element is assigned to. The main result of the paper, following in the tracks laid out by Blais-Bommireddi, presents constant-query-complexity testers for \(k\)-submodularity in \(\ell_p\) distance.

Quantum Advantage in Tolerant Junta Testing by Avishay Tal and Weiqiang Yuan (arXiv) Recall the tolerant junta testing problem: given parameters \((k, \varepsilon_1​, \varepsilon_2​)\) with \(0\leq \varepsilon_1 ​< \varepsilon_2 ​\leq 1/2\) and black-box access to a Boolean \(f\) on \(n\) variables, decide whether \(f\) is \(\varepsilon_1\)​-close to some \(k\)-junta or \(\varepsilon_2\)​-far from every \(k\)-junta. Our July 2016 News reported a result which presented tolerant testers with query complexity exponential in \(k\). Additionally, despite our research efforts, getting a good understanding of the query complexity of adaptive testers for tolerant junta testers has been out of reach.

The featured paper picks up on this investigation thread and establishes the first super-polynomial quantum advantage for this problem in the adaptive setting. The main result is a non-adaptive quantum toleratnt tester with query complexity growing as \(poly(k, 1/\varepsilon)\). On the other hand, the main result also proves that any adaptive, tolerant tester must cough up a number of queries that grows like \(k^{\Omega(\log{1/\varepsilon} )}\).

Sublinear Time Algorithms for Abelian Group Property Testing by Nader H. Bshouty (arXiv) You are given a finite set \(G\) and oracle access to a binary operation \(\ast \colon G^2 \to G\), and you want to decide whether \((G,\ast)\) is an abelian group or is \(\varepsilon\)-far from every abelian group over \(G\). The paper considers two access models: in the partially specified model the algorithm does not know \(|G|\) and only sees randomly sampled elements together with the Cayley table restricted to those elements, and in the fully specified model it knows \(|G|\) and has access to the full table. The main result is a tester in the weaker PS-model (and hence in the FS-model) which runs in time \(\widetilde{O}(\sqrt{|G|}​+1/\varepsilon)\), improving on testers of Goldreich and Tauber which run in time \(O(|G|/\varepsilon)\).

Testing Bipartiteness in Logarithmic Rounds by Yumou Fei and Ronitt Rubinfeld (arXiv) Recall the seminal Goldreich-Ron tester for bipartiteness of bounded-degree graphs, which runs \(\widetilde{O}(\sqrt n)\) random walks of length \(O(\log^6 n)\) each and rejects when it discovers an odd cycle. The featured paper shows that \(O(\sqrt n​)\) walks of length \(O(\log n)\) already suffice. The proof departs from the Goldreich-Ron analysis and instead routes the argument through the Goemans-Williamson SDP relaxation for Max-Cut. As a corollary, the paper obtains an \(O(\log n)\)-pass, \(O(\sqrt n \cdot ​logn)\)-space streaming algorithm for testing bipartiteness, and the pass complexity is optimal thanks to a recent lower bound of Fei, Minzer and Wang. Looks like a great read before the new term rolls in.

And now, as promised, a result which is not property testing at all, but which I could not skip over.

Bipartite Matching is in NC by Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar, Roshan Raj and Thomas Thierauf (ECCC) Whether the randomness in the Mulmuley-Vazirani-Vazirani RNC algorithm for matching can be removed is a question that has stood since the 1980s, with the state of the art being the quasi-NC bounds of Fenner-Gurjar-Thierauf for bipartite graphs and Svensson-Tarnawski for general graphs. The featured paper settles the bipartite case: bipartite matching is in NC. The techniques are based on the polynomial method, inspired by the subspace design construction of Guruswami and Kopparty. The result extends to weighted bipartite matching and to computing the noncommutative rank of a symbolic matrix, and as a consequence the decision version of linear matroid intersection lands in NC as well. As a curious aside, in a talk by Rohit Gurjar (one of the authors), I learnt a fact that I found rather remarkable.
Take two univariate polynomials \(\boldsymbol{p}, \boldsymbol{q} \in \mathbb{R}[X]_{\leq d}\), each of degree \(d\). Suppose these polynomials are linearly independent, so that \(span(\boldsymbol{p}, \boldsymbol{q})\) is a two-dimensional space of polynomials of degree at most \(d\). Consider the following set of real numbers: \(S_1 = \{ \alpha \in \mathbb{R} : \boldsymbol{f}(\alpha) = 0 \text{ for some } \boldsymbol{f} \in span(\boldsymbol{p}, \boldsymbol{q}) \}. \) That is, \(S_1\) collects those reals that happen to be a root of some polynomial hiding in the span; call these the roots of the span. One notes that \(S_1\) contains infinitely many elements. So far so good. Next, consider the set \(S_2 = \{ \alpha \in \mathbb{R} : \alpha \text{ is a root of some } \boldsymbol{f} \in span(\boldsymbol{p}, \boldsymbol{q}) \text{ with multiplicity } 2 \}. \) Somewhat surprisingly (to me), \(S_2\) is a finite set, and in fact \(|S_2| \leq 2d\).

By Akash

As I’ve written before, these past couple years I’ve often felt like the last remaining person in either quantum computing or AI who lacked a stake in some startup company whose valuation is right now shooting into interstellar space. My academic colleagues, including the ones who seemed the most singleminded about quantum oracle separations and other gloriously useless pursuits? One by one, like in a zombie movie, I learn that they too have now launched startups, and invariably raised tens of millions of dollars, for the sorts of ideas we might’ve idly traded at coffee breaks back in the day, before getting back to our real work.

So why didn’t I join this rollicking party? Partly because of a lifelong fear that, the instant my self-worth became tied to how much money I made, I’d need to humble myself before people who bluster and bully and lie and hype and conceal … yet who nevertheless succeed at becoming orders of magnitude richer than me. I’ve been terrified of even starting down that road, of whether I’d still be myself at the end of it.

It’s also partly that I can’t stand failure, or regret, or being wrong. Of course, as an academic researcher I also fail, and regret things, and am wrong constantly—but there it feels tolerable, because normally I can tell myself that it’s all just down to my inborn limitations. After all, if I could’ve solved the major open problem that someone else solved, or written the brilliant book that someone else wrote, then presumably I would’ve done it!

Clearly, though, I could’ve mined bitcoin in 2010. I could’ve gotten an early stake in Amazon or Google. It’s not even like those ideas never crossed my mind. I just … didn’t act on them, for some reason. (But even if I had, I’d probably just be full of regret that I hadn’t done even more.) Thus, my only way to avoid paralyzing regrets, has been to tell myself constantly that I’m not in the forecasting or money-making businesseses in the first place.

It helped that, insofar as I’m shallow or covetous, insofar as I’ve desired things of this world rather than insight or eternal truth, it’s never really been money that I cared about, but just being respected and liked. Elon Musk is the richest man on earth, but also one of the most despised—which isn’t a bargain that I could imagine ever appealing to me.

Plus, when I actually meet billionaires, I don’t find myself envious of their mansions or cars or anything else that they have; I don’t feel like such things would make my life any happier. Maybe I slightly envy their ability to fund the causes they care about, or their professional staffs who relieve them of drudgery, but mostly I envy the way their wealth announces, to whatever extent it does: “I was right when others weren’t.” Again, though, I’ve never trusted the world to cause me to be right about the future valuations of companies or anything similar, so I’ve settled for having been right about PostBQP and algebrization and BosonSampling.

The bottom line is that I made a choice decades ago to forgo trying to get rich, no matter how many of my friends did the same, and to strive instead to discover and tell the truth—to be a professor, a blogger, a jokester, and an “objective” arbiter and commentator. “Then, surely, everyone will like me!” my internal monologue went. “Then, surely, they’ll be grateful for all the free service I’ve rendered them—for decades of blogging, without once so much as asking for a donation or running an ad!”

HAHAHAHAHAHA.

As any regular reader will know, my attempts to be loved as a blogger backfired pretty spectacularly. Or rather: they did lead to thousands of strangers liking me (and I’m grateful for every last one of you), but they also led to probably an order of magnitude more strangers hating me, and congregating on Reddit and Twitter and elsewhere to discuss how badly I suck. And of course, trying to shift that balance by writing what people want to hear, rather than what I actually believe, was never within my realistic option set.

In the startup context, it didn’t matter how carefully I avoided taking a direct stake for or against any of the companies I blogged about. People on Twitter simply assumed that I had a stake—for example, that I must’ve shorted D-Wave or IonQ, or invested in their competitors, or had equity in AI companies. For why else would anyone write what I wrote?

Amusingly, my attackers here typically did have precisely the conflicts-of-interest that they falsely accused me of having, but that was never at issue; only my imaginary conflicts-of-interest were. Even as the Scott-haters greedily filled their pockets (or tried to), I alone needed to keep turning my pockets out to prove that they were still empty.

So then, screw it! In partnership with my brother David Aaronson, who’s long done investing professionally, and on David’s guidance and encouragement, I’m hereby embarking on a new policy.

Namely: when I hear about a brand-new startup that sounds relevant to my interests—in quantum, AI, or anything else—and I like and trust the founders (ideally, because of their previous academic research work), David and I will often make a small seed investment if the founders are open to it. Or, of course, we might become advisors or get involved in some other way.

In fact, David and I are launching BQP Partners—the link goes to our AngelList, where you can read about how to invest with us if you’re interested. (See also whether you can spot any differences between David’s writing style and preoccupations and mine!)

So far, David and I are investing in:

• Oratomic (the new neutral-atom quantum computing startup out of Pasadena started by Dolev Bluvstein, John Preskill, and Hsin-Yuan Huang among others, which I previously blogged about here). See here for their Series A announcement this week.
• A non-quantum startup being cofounded by someone whose scientific work I’ve admired. I’ll write more about this one as soon as I’m able to!

I have little doubt that more potential investments will come our way very soon (some, probably, as a direct result of this post).

Crucially, I can handle my burden of regret—the “why didn’t I do this much earlier, if I was going to do it at all?” question—by telling myself that friends of mine were not founding companies left and right until very recently. I can also tell myself that I’m doing this less as a bet about the future (in which case … what if I’m wrong?), than simply as a way to support brilliant colleagues doing things that I genuinely admire.

When I blog about a company, I’ll always disclose if I have a financial position that presents a clear conflict of interest, so you can judge for yourself whether to listen to me. (Although, if that’s the sort of thing you’d demand, then you probably weren’t listening to me in the first place, were you?)

Having reflected on it a lot these past few months, I’m happy with my new policy and with my and David’s new venture, and I’m curious to see where it goes. I’m at peace with the possibility that we’ll lose our shirts, but I’m even at peace with a more disturbing possibility—that we’ll make millions and then people will scream at me online for being a sellout, a hack, and a shill. Those people, as I’ve learned, were going to scream at me anyway.

By Scott

Authors: Jayakrishnan Madathil, Kitty Meeks, Marc Roth

We study the structural expressivity and the parameterised complexity of counting homomorphisms from small temporal patterns to large temporal graphs. Here, a temporal pattern $P$ consists of a graph together with a partial order on its edges, and a homomorphism from $P$ to a temporal graph must not only preserve edges, but also satisfy the temporal constraints imposed by the partial order of the edge set of the pattern. The main results of this work are three-fold: First, we prove a temporal Lovász-style theorem, stating that two temporal graphs are isomorphic (under a natural definition of temporal isomorphisms) if and only if they have the same number of homomorphisms from all temporal patterns. Second, we introduce a cliquewidth-based measure on temporal patterns, called the temporally order-augmented dual width, the "toadwidth" for short, and show that counting temporal homomorphisms is fixed-parameter tractable for temporal patterns of bounded toadwidth. Third, we provide a parameterised complexity dichotomy with an explicit tractability criterion for counting homomorphisms from totally ordered temporal patterns, classified along their underlying graph structure.

Authors: Hantao Yu

We prove that the minimum edge-outerplanarity of a planar graph can be computed in polynomial time, resolving an open problem of Bentz (2009). The proof was initially produced by GPT~5.5 Pro and then verified and polished manually.

Authors: Madhumita Kundu, Daniel Lokshtanov, Soumi Nandi, Saket Saurabh, Kushal Singanporia

Geometric covering problems ask for a small family of geometric objects whose union covers a given point set. We study the more restrictive \emph{boundary covering} variant, where every point must lie on the boundary of a chosen object. Motivated by the framework of Langerman and Morin\,[Discret.\ Comput.\ Geom., 2005] for hyperspheres, we initiate the study of boundary covering by axis-parallel rectangles. We first consider the \emph{discrete} setting, where rectangles must be selected from a given family. We define \bcdaprfull\ (\bcdaprshort): given a point set \(P\subseteq\mathbb{R}^2\), a family \(\mathcal{R}\) of axis-parallel rectangles, and an integer \(k\), decide whether \(P\) can be covered by the boundaries of at most \(k\) rectangles from \(\mathcal{R}\). We prove that \bcdaprshort\ is \(\mathrm{W}[1]\)-hard parameterized by \(k\). We then study the \emph{continuous} variant, \prbcfull\ (\prbcshort), where rectangles may be placed freely. Given \(P\subseteq\mathbb{R}^2\) and \(k\), the goal is to decide whether \(P\) can be covered by the boundaries of at most \(k\) axis-parallel rectangles. In contrast to the discrete case, we show that \prbcshort\ is fixed-parameter tractable, with running time \(2^{\cO(k\log k)}\cdot n^{\cO(1)}\), where \(n=|P|\). Our algorithm relies on a structural analysis of how \(k\) rectangles interact with the point set, reducing \prbcshort\ to at most \(2^{\cO(k\log k)}\) instances of \ddmtcsp, each solvable in polynomial time. On the hardness side, we prove NP-completeness for boundary covering by axis-aligned \(L\)-shapes and use this reduction to establish NP-completeness of \prbcshort.

Authors: Duen Horng Chau, Donghao Ren, Fred Hohman, Dominik Moritz

While UMAP is widely used for exploring high-dimensional data, typical workflows focus on its lower-dimensional embedding, largely overlooking the rich k-nearest-neighbor (kNN) graph that UMAP constructs internally. This graph encodes the data manifold in its original high-dimensional space, before the distortion that UMAP's 2D projection introduces. We demonstrate the untapped potential of this internal representation, showing how standard graph algorithms applied to this graph enhance data sensemaking: (1) PageRank identifies representative data points, (2) k-core decomposition reveals dense core regions versus sparse periphery, and (3) clustering coefficient detects tight-knit neighborhoods with highly-similar data points. Through quantitative and qualitative evaluation on MNIST and Fashion MNIST, we show that these graph-based analyses are not only practical but also competitive with or complementary to purpose-built methods (e.g., k-medoids for exemplar selection, HDBSCAN for density-based clustering).

Authors: Wei Tang, Hanrui Zhang

Forecast aggregation aims to combine information from multiple Bayesian experts' forecasts into an aggregate forecast. In much of this literature, however, the aggregate forecast is optimized for a particular loss or robustness criterion and need not itself be calibrated with respect to the outcome. We introduce and study expert aggregation, where the goal is instead to aggregate Bayesian experts into a new expert that continues to provide calibrated forecasts. In particular, we consider a setting where each input expert reports calibrated predictions, and the aggregator observes the prior distribution over states, and the input experts, but not the underlying Bayes probabilities of the states. We ask whether one can (i) construct a calibrated output expert that Blackwell refines a target expert and cannot be further Blackwell improved using the available information; and (ii) when a proper loss is specified, compute a nearly loss-optimal expert among all such refinements. We formulate calibrated experts as reduced-form information structures and measure refinement by Blackwell dominance of the induced prediction distributions. We characterize the constructible output experts through observable linear information: the input experts generate a linear system whose row space determines which calibrated output predictions are identifiable, and a new expert is constructible exactly when its predictions lie in the associated observable nonnegative cone. We establish a sharp algorithmic picture. When randomized output experts are allowed, both questions above admit efficient algorithms. In contrast, deterministic output experts are computationally intractable: deciding whether a deterministic calibrated refinement exists is $\mathsf{NP}$-hard, and deterministic proper-loss optimization admits no multiplicative PTAS unless $\mathsf{P}=\mathsf{NP}$.

Authors: Estéban Gabory

A \emph{generalized degenerate string} (GD) is a sequence $T=T_1\dots T_n$ of nonempty finite sets of strings, called \emph{segments}, such that all strings in a segment have the same length. Given a solid pattern $P$, GD string matching asks whether $P$ occurs in $T$. Ascone et al. (WABI 2024) identified this as the main remaining boundary case in the fine-grained complexity of pattern matching on variable strings, between variants with near-linear algorithms and those with SETH-based quadratic lower bounds. We give a $\tilde{\mathcal O}(N\sqrt m)$-time algorithm, where $N$ is the total size of $T$ and $m=|P|$, placing GD matching on the subquadratic side of this boundary. We also study indexing. For elastic-degenerate strings (ED), which drop the equal-width restriction, Gibney (SPIRE 2020) obtained $\mathcal O(nm^2)$ query time after linear preprocessing. We adapt this index to GD strings, obtaining $\mathcal O(nm)$ query time. Conversely, under SETH, we rule out GD indices with polynomial preprocessing and query time $\mathcal O(n^{1-\varepsilon}m^{\mathcal O(1)}+m)$. Under the $k$-Clique conjecture, we further rule out combinatorial GD indices with query time $\mathcal O(n^{\mathcal O(1)}m^{1-\varepsilon}+m)$, and combinatorial ED indices with query time $\mathcal O(n^{\mathcal O(1)}m^{2-\varepsilon})$, matching the quadratic dependence on $m$ in Gibney's upper bound. Finally, under the OMv conjecture, we show that, after polynomial preprocessing of a string set and a pattern, active-prefix queries on a bit vector of length $m$ cannot be answered in $\mathcal O(m^{2-\varepsilon})$ time. Since these queries are the standard bottleneck in ED matching, improving indexed ED queries below $\mathcal O(n^{\mathcal O(1)}m^2)$ would require both non-combinatorial techniques and an approach that avoids using active-prefix queries as the main bottleneck.

Authors: Ripley Becker, Sourav Chakraborty, Debarshi Chanda, A. Pavan, N. V. Vinodchandran

We introduce a streaming model with \emph{catalytic memory}, an auxiliary workspace that must be returned to its initial state at the end of the computation. We show that catalytic space yields dramatic space savings for data stream algorithms. We first study the exact computation of frequency moments in insertion-only data streams. For every $k\ge1$, we give an exact four-pass algorithm for computing $\mathbb{F}_{k}$ using $O(k\log m)$ clean space, where $m$ is the stream length. We also present a $(k+1)$-pass algorithm with the same clean-space complexity that uses a factor of $k$ less catalytic space than the four-pass algorithm. For small moments, we obtain stronger results. In particular, we show that $\mathbb{F}_{2}$ and $\mathbb{F}_{3}$ can be computed exactly in two and three passes, respectively, using only $O(\log m)$ clean space. Additionally, we show that exact $\mathbb{F}_{0}$ computation reduces to computing $\mathbb{F}_{k}$ for a suitably chosen large value of $k$, resulting in an exact four-pass algorithm for $\mathbb{F}_{0}$ using only $O(\log m)$ clean space. We further show how our frequency-moment algorithms can be used to exactly count induced occurrences of any fixed graph $H$ in a graph stream, yielding a four-pass algorithm that uses $O_H(\log n)$ clean space, where $n$ is the number of vertices in the graph. As a special case, we obtain an exact three-pass algorithm for triangle counting using $O(\log n)$ clean space. All of our algorithms are multi-pass. We complement these algorithmic results with a matching limitation showing that catalytic memory does not provide additional power in the single-pass setting. Specifically, we prove that every randomized or deterministic single-pass streaming algorithm using $s$ bits of clean memory and catalytic space can be simulated in the standard streaming model, without catalytic memory, using $O(s)$ space.

Authors: Nicolas Menand, Erik Waingarten

We provide a local computation algorithm to approximate the top eigenvector $x \in \mathbb{R}^n$ of a symmetric matrix $A \in \mathbb{R}^{n \times n}$ with entries between $-1$ and $1$, building on the work of Swartworth and Woodruff [SODA 25] who show how to approximate the eigenvalues up to additive-$\varepsilon n$ error using $\tilde{O}(1/\varepsilon^4)$ queries. Our local computation algorithm has a preprocessing complexity of $\tilde{O}(1/\varepsilon^4)$ and per-coordinate query complexity of $\tilde{O}(1/\varepsilon^2)$ for an additive-$\varepsilon n$ approximation whenever {$|λ_{\min}(A)| = O(λ_{\max}(A))$. When $λ_{\min}(A)$ greatly exceeds $λ_{\max}(A)$, our complexity degrades to at most $\tilde{O}(1/\varepsilon^{6.\overline{6}})$ in preprocessing and $\tilde{O}(1/\varepsilon^{3.\overline{3}})$ per query. Furthermore, we show a lower bound of $Ω(n/\varepsilon^2)$ on the total number of queries needed to output an approximately top eigenvector (implying that the per-coordinate query complexity of $Ω(1/\varepsilon^2)$ is necessary). As an application, we use our algorithm to provide local computation algorithms for the sparsest-cut and max-cut problems in the dense graph model of Goldreich, Goldwasser, Ron [JACM 98]. By accessing the top eigenvectors (of an approximate normalized adjacency), we implement local versions of Cheeger's inequality and Trevisan's algorithm [SICOMP 12] to obtain "square-root-opt" approximations in polynomial time (as opposed to exponential-in-$\text{poly}(1/\varepsilon)$ time which is incurred in Goldreich, Goldwasser, Ron.

Authors: Weiming Feng, Xiongxin Yang, Yixiao Yu, Yiyao Zhang

The problem of learning constant-depth circuits holds profound implications for computational learning theory. In a seminal result, by introducing the low-degree algorithm, Linial, Mansour, and Nisan (J. ACM 1993) presented a quasipolynomial-time learner for $\mathsf{AC}^0$ under the uniform distribution. However, obtaining comparable learning guarantees for broader classes of correlated distributions has remained a longstanding challenge. Recently, Chandrasekaran, Gaitonde, Moitra, and Vasilyan (arXiv 2026) extended these guarantees to Gibbs distributions on bounded-degree graphical models with both strong spatial mixing and polynomial growth. In this paper, we give a quasipolynomial-time learner for $\mathsf{AC}^0$ under graphical models that admit efficient local samplers, circumventing the polynomial-growth requirement in prior work. The key ingredient is a new low-degree approximation for Gibbs distributions, established by simulating and suitably truncating the classical Glauber dynamics. As applications, this framework yields learners for two-spin systems, including the hard-core model and Ising model, on arbitrary bounded-degree graphs, in regimes approaching their respective sampling thresholds.

Authors: Christian Coester, Alex Turoczy

The Parking Permit Problem (PPP), first studied by Meyerson, is a classic online problem generalizing the ski rental problem. We re-examine the PPP using the primal-dual scheme, obtaining simple algorithms with superior performance guarantees. Unlike previous work, which relied on reductions that degraded competitive ratios, we work with the problem's structure directly. We also provide near-matching lower bounds. Using the primal-dual framework, we find the PPP's deterministic competitive ratio exactly, and the randomized competitive ratio within an additive constant.

Authors: Arpon Basu, Pravesh K. Kothari, Raghu Meka, Stefan Tudose

We prove that for every Cayley graph $\mathcal{G}$ over any finite abelian group $G$, there is a weighted Cayley graph with $O(\log |G|)$ generators that is a spectral sparsifier for $\mathcal{G}$. This bound is optimal. Applying our bound to the group $G = \mathbb{F}_2^n$, yields, as a corollary, $O(n/\varepsilon^2)$-sized code sparsifiers for $\mathbb{F}_2$-linear codes, improving on the work of Khanna, Putterman and Sudan (SODA'24) who obtained a similar result with an additional $\mathrm{polylog}(n)$ loss. Our proof is strongly inspired by a recent work of Reis and Rothvoss for the construction of $\ell_1$-sparsifiers. Following their work, the abelian Cayley sparsification problem can be reduced to establishing a lower bound for the volume of a certain natural convex body. This volume bound follows from a short, elementary argument that relies on character symmetry.

Authors: Robert P. Streit, Vijay K. Garg

Optimal selections in a decision process are often constrained by prerequisites. However, such prerequisites can encode functional rather than literal dependencies, so a required dependency may be supplied by one or several interacting alternatives. We introduce matroidal prerequisite systems (MPS), a constraint structure where a poset specifies prerequisites while a matroid determines when those prerequisites have been satisfied by its span. This creates an order-sensitive notion of feasibility over words, where feasible words are associated with independent sets, while dependencies may be fulfilled through substitutable functionality. Our main contribution is approximation algorithms for additive maximization and submodular maximization over the feasible words of an MPS. The guarantees are determined by two structural parameters: the maximum matroid rank $Δ$ of a principal ideal in the poset and the maximum matroid connectivity $λ_\mathrm{max}$. These measure the distance an MPS is from encoding a matroid or a poset antimatroid, respectively, both of which are generalized by an MPS. For additive maximization, we obtain efficient deterministic $Δ$- and $(1+λ_\mathrm{max})$-approximation algorithms. By extending these techniques, we obtain efficient deterministic $(2+λ_\mathrm{max})$-approximation and randomized $(Δ^2\cdot(1 - 1/e - δ)^{-1})$-approximation algorithms for all $δ>0$ for submodular maximization. The algorithm design and analysis use the theory of polymatroid greedoids, via cryptomorphism we prove between an MPS and a strong polymatroid greedoid. Finally, an approximation-preserving reduction from densest $k$-subgraph shows it is not possible to efficiently compute a $\min\{Δ,λ_\mathrm{max}\}^{o(1)}$-approximation to additive maximization over the feasible words of an MPS under the Gap Exponential Time Hypothesis.

Authors: Panagiotis Aivasiliotis, Andreas Göbel, Matthias Lanzinger, Marc Roth

The Weisfeiler--Leman (WL) algorithm is one of the most influential heuristics for the graph isomorphism problem. The expressive power of WL has been extensively studied in the contexts of descriptive complexity, logics, graph neural networks, and the theory of homomorphism indistinguishabily. Notably, two graphs are indistinguishable by the $k$-dimensional WL algorithm if and only if they are indistinguishable by homomorphism-counts from graphs of treewidth at most $k$. An intrinsic question is to find a natural version of the WL algorithm for relational structures of higher arity admitting an equivalent characterisation via homomorphism indistinguishability along bounded generalised hypertree width (GHW). Scheidt and Schweikardt solved this for $k=1$ by defining the RCR algorithm and showing indistinguishability from $α$-acyclic structures. In this work, we resolve this for all $k\ge1$: we develop $k$-RCR and show that two structures $\mathcal{A}$ and $\mathcal{B}$ are insdistinguishable by $k$-RCR if and only if they have the same homomorphism-counts from all structures $\mathcal{C}$ of generalised hypertreewidth $\le k$. Moreover, we introduce a ``fractional'' version of $k$-RCR and show that two structures are insdistinguishable by fractional $k$-RCR if and only if they have the same homomorphism-counts from all structures with (a variant of) fractional hypertreewidth at most $k$. Last, we develop $k$-HyperOWL, the first relational WL algorithm operating directly on a relational structure. We show that $k$-HyperOWL is as expressive as $k$-RCR and that, given a structure $\mathcal{A}$, $k$-HyperOWL can compute $t$ iterative refinements in time $O(t|\mathcal{A}|^{k+1})$. Moreover, the colouring produced by $k$-HyperOWL can be used as a constructive preprocessing routine for counting homomorphisms from structures of generalised hypertreewidth $\le k$.

Authors: Ioannis Sigalas, Nikolaos Lazaropoulos, Ioannis Lamprou, Ioannis Vaxevanakis, Vassilis Zissimopoulos

In various domination and coverage problems, certain vertices or edges should not be dominated/covered and are designated as vulnerable. Motivated by this, we define the $k$-Vertex Maximum Domination Ratio with Vulnerable Vertices $(k\textit{-}Max \ \mathit{DRVV})$ problem, which extends the budgeted dominating set problem to include vulnerability constraints. We propose an approximation algorithm based on an unbudgeted variant of $k\textit{-}Max \ \mathit{DRVV}$, termed the Maximum Domination Ratio with Vulnerable Vertices $(\mathit{DRVV})$ problem. For bounded-degree graphs of order $n$, our algorithm provides an $O(k/n)$-approximation for the $k\textit{-}Max \ \mathit{DRVV}$ problem. We introduce the Dominating Set with Vulnerable Vertices $(\mathit{DSV})$ problem, reduce it to the Red-Blue Set Cover problem, and derive a $2\sqrt{|V|\cdot(H(Δ_{N})-\frac{1}{2}})$-approximation algorithm, where $|V|$ is the order of the graph, $Δ_N$ is the maximum degree among non-vulnerable vertices and $H$ is the harmonic function. Finally, we examine the Vertex Cover with Vulnerable Edges $(\mathit{VCVE})$ problem, which can be naturally expressed as a special case of the Red-Blue Set Cover problem. We present a polynomial-time $2$-approximation algorithm for the $VCVE$ problem, achieving the best possible ratio.

Monday’s post highlighted how physical therapy sits at the heart of the tension between populations and individuals in modern scientific medicine. The field addresses one of the core problems people come to their doctors with: musculoskeletal pain or restriction. More often than not, these ailments can’t be treated by simple prescriptions of rest, drugs, or surgery, and primary care physicians don’t have solutions for these problems. So instead, they are often referred to physical therapy, which combines an uncomfortable mix of science and craft that eludes clean, evidence-based evaluation.

I’m a bit of a PT fanatic, and have had the privilege of working with five excellent physical therapists since I got a bit too overly serious about strength and conditioning in my forties. They were all very different, but all of them applied the same core principles. These principles highlight key aspects of what it means for a therapy to be individualized.

Every PT consultation begins with an assessment. Because there are so many moving parts and everything is so interconnected, it’s often hard to identify a single cause of a particular pain or restriction. Weakness in one area is balanced by strength in another. Pain in your foot might be caused by limited mobility in your hip. While everyone’s musculoskeletal system is connected in the same way, we have wide variability in the sizes, shapes, and positioning of our muscles and bones. Once we combine this with the variability of people’s physical interactions with reality, we find there’s no single simple answer for everyone. Each person is a weird biomechanical puzzle, and not every puzzle is particularly easy to solve. However, there is a set of therapeutic principles for making people better.

A therapist will test out the range of the different muscles and joints that could be connected to your symptoms. They try to find how far you can move without pain, which is a mix of qualitative (pain) and quantitative (degrees of rotation). Once they find which specific movements are restricted, they have a general process to fix all of them.

First, the therapist will open the restricted range using some sort of manual therapy. This is done in a single session and might involve stretching, deep-tissue massage, or even cupping (more on that later). Next, they give you exercises to gain control over that newly opened range. This is done between sessions with the homework exercises they assign you. After you can confidently access this new range, you load it, adding strength-bearing exercises to further strengthen the mobility you aim to increase. All of these are progressed over time, adding more intense manual therapy, more difficult exercises, and more weight.

Progression is the core principle, whether you’re treating tennis elbow or a sprained hip (I’ve had both). The difficulty of your physical therapy exercises will gradually increase with each session. It’s sort of obvious when you say it that way, no? This is all there is to the buzzy principle of progressive overload. It works because your body adapts to stress. When you add enough stress, it overcompensates and resists the stress more strongly the next time. Cascading this reaction over a long period in a controlled, thoughtful way leads to a clear and measurable outcome.

The complication is that bodies adapt more slowly than most of us would like. It might take weeks to start to see progress. Because progressive overload is slow, lots of people walk away from physical therapy convinced that their injury would have just gotten better anyway. They might be right, and I can’t argue their concerns away. But that’s why I’ve found it helpful to track progress over time. It might not be the PT prescription that lets me access that extra range or strength, but I feel more in touch with whatever it is that my body is doing. I’ve found that it’s worth targeting something even more ambitious than just “back to normal.” I now aim to come out of physical therapy more capable than I was before my symptoms started.

For many people, PT doesn’t work. I like it, but I might be particularly well suited for it. I love rituals. I love obsessing about niche minutiae. I love tracking and journaling. But recovering from injury and managing pain are not easy. Compliance with physical therapy might be a greater challenge than with other treatments. It’s a much bigger commitment than “take two pills a day with meals.” If you don’t like to spend 30 minutes a day on weird stretches, PT might not work for you. But that doesn’t mean it doesn’t work for someone else.

And this is why physical therapy is so easy to attack on scientific grounds. How do you run a controlled trial on a practice this complex and individualized aimed to treat subjective symptoms like pain? I’ll dig into the impossibility in the next post.

Subscribe now

By Ben Recht

Two editorials in the July issue of the Communications of the Association for Computing Machinery ask about the decay and future of the organization itself.

Jim Larus, editor-in-chief of the CACM, writes Wither ACM? Publish and Perish?

ACM no longer has broad appeal as a professional organization, does not advance many members’ careers, and may not be a valuable affiliation in a more diverse technical world...It is time to recognize that ACM has shifted from functioning as a professional society for the academic computing community to a professional publisher....It is time for ACM members to debate what kind of organization ACM should be and how to remake it into the society they want to belong to!

Vardi writes Whither Computing? starting with the concerns of PhD students whether they made the right choice by going into computer science and ending with a call for ACM to lead the conversation.

A new team will assume the leadership of ACM on July 1, 2026, following the current general election and search for a new chief executive officer. I believe this team will have to grapple with existential questions about the future of computing as a science and a profession...If ACM is about “advancing computing as a science and profession,” then we need to engage in a deep conversation about what this phrase means today for education, research, the profession, and ACM, and about how to truly advance computing as a science and profession.

ACM hasn't served as a true professional society for a long time. Unlike in other fields, ACM doesn't hold annual meetings for the whole community, and shares the spotlight with IEEE-CS, USENIX, AAAI, CRA and others. CRA takes the lead in research and organizes the CS department chairs meetings. ACM has focused on journals, conferences through its SIGS and awards.

This worked well while computing went through tremendous growth from after the financial crisis until a couple of years ago. But now artificial intelligence is making us rethink how we do research, publish and educate. What does it even mean to be a computer scientist in the AI era?

So good luck to incoming president Elisa Bertino and her team. Computing is changing. How will ACM change with it?

By Lance Fortnow