Theory of Computing Report

The 59th ACM Symposium on the Theory of Computing takes place in Atlanta next June, part of the Federated Computing Research Conference. I don't usually do announcement posts but we need to talk about the Call for Papers (deadline November 2) where

In light of rapid advances in generative AI and their impact on research and scientific communication, STOC 2027 is experimenting with several new policies intended to encourage high-quality submissions and promote clear and effective communication of research. 

Let's talk about these changes, which seem more designed to limit the deluge of AI generated papers.

STOC 2027 submissions will not be anonymous; all listed authors must be human and are responsible for the submission.

This reverses the move to removing authors' names that STOC made in 2023. I was never a fan of double blind reviewing and you need authors who can take responsibility for the submission.

Each author may appear on at most five submissions.

Understood but it might hurt some students who have an active advisor. 

Every paper must be submitted to arXiv before the STOC paper submission deadline. Authors must provide a public arXiv URL or proof of arXiv submission along with their submission PDF, which must be identical to the arXiv version.

In the past you could submit preliminary results and try to extend them before publication, since reviewers were expected not to build on unpublished work they were reviewing. This rule may cause some authors to hold back submissions or use AI to help with the extensions.

Authors must submit a video explaining the work, its context, and its innovations relative to prior work. The video should be 20–30 minutes long and will be due 1–2 weeks after the paper submission deadline. The recording should be presented by at least one listed author. The written submission remains the primary object of review. 

This rule will both check that at least one author understands the paper and add some friction to just generating papers using a few prompts. AI could generate the video of an author explaining the paper, but at least for now that would be prohibitively expensive. Some might use AI to generate the script but that would likely be easy to tell from the video. 

I worry that judging the paper based on the video will hurt those who aren't native speakers of English, and might exacerbate unconscious biases so I hope the reviewers really do focus on the paper for the actual review.

Authors may use large language models (LLMs) and other generative AI tools in preparing papers. Substantive use must be disclosed in the paper; minor copy-editing and grammar or clarity improvements to the authors’ own text do not require disclosure.

I would go further and make all papers have an AI disclosure, even if it is just minor copy-editing or "No AI was used in the production of this paper".

Program committee (PC) members and external reviewers (sub-reviewers) may use LLMs to assist with reviewing. Authors must explicitly consent as part of the submission process. All reviews and decisions remain the responsibility of the PC members and sub-reviewers.

I would require consent as condition of submission especially since AI models already have access to arXiv papers. Recent AI models have greatly improved their ability to check proofs if prompted correctly so the overworked PC members can focus on paper quality. 

We really need a larger conversation about the role of conferences in theoretical computer science if one can now generate papers from prompts. I've long argued that we should focus the conference more on connecting the community than the "journal that meets at a hotel". The STOC TheoryFest has helped but it would be great to get further away from lauding papers that have complicated proofs and focus more on the ideas that truly drive our field.

By Lance Fortnow

We introduce a variant of a polynomial family called $\TQBFfamily$ obtained from `arithmetization' of the popular $\PSPACE$-complete problem - $\TQBF$. This polynomial family has several nice characteristics such as: $\TQBFfamily \in \VPSPACE_b$, where $\VPSPACEb$ is the `bounded' algebraic version of $\PSPACE$, it is \emph{self-testable}, it captures the computational power of $\PSPACE$ and others. Although the first version of $\TQBFfamily$ appeared in an earlier work of Carmosino et al. (RANDOM, 2015), we believe that our presentation is cleaner and simpler. Building on that, we construct another polynomial family, $\TPfamily \in \VPSPACE_b$, by mixing $\TQBFfamily$ and $\Permfamily$, the family of the Permanent polynomial. While we are unable to prove that $\TPfamily$ is $\VPSPACE_b$-complete, we show that it has many traits of $\VPSPACE_b$-completeness as well as several important consequences in computational complexity, which are listed below. \begin{itemize} \item We show that if $\TPfamily$ can be computed by circuits from a circuit class $\Ccal \subseteq \VNP$ then $\VPSPACE_b \subseteq \Ccal$. \item We also conclude that if $\Ccal$ has a black-box $\PIT$ algorithm that uses sub-polynomial space, then $\TPfamily$ cannot be computed by polynomial-size arithmetic circuits from $\Ccal$. \item Finally, we prove a version of a Karp-Lipton style collapse theorem by showing that if $\TQBFfamily$ has ``small'' arithmetic circuits then $\PSPACE$ collapses to $\NP$ with a $\PIT$ oracle (i.e. $\PSPACE \subseteq \NP^{\PIT}$). \end{itemize} The second result makes a partial progress towards the resolution of an open problem posed in a survey by Shpilka \& Yehudayoff (Foundations and Trends in Theoretical Computer Science, 2010). As a corollary, we give an ``inconsistent triad'' of $\PIT$ and circuit lower bounds, similar to the one given by Kabanets and Impagliazzo (Computational Complexity, 2004). Finally, we note that Malod gave complete polynomial families for $\VPSPACE$, the `unbounded' algebraic version of $\PSPACE$ (Foundations of Computation Theory, 2011).

Lecture Video: https://www.youtube.com/watch?v=j4WSktB5Ni0 

Authors’ Intro

Hanjing: I’m a Junior studying Applied Mathematics & CS. I’ve worked on research utilizing LLMs and ML in a plethora of fields, including sentiment analysis, code generation, natural language processing, and interpretability. On the other hand, I’m also fascinated by the theoretical foundations of AI alignment – which is why I’m taking this class – and particularly look forward to learning more about moderating model behavior through technical methods.

Isabella: I’m a Senior studying Applied Mathematics with CS. I’ve been involved in the AI Safety Student Team (AISST) since my first year at Harvard, and now I’m on the board and leading reading groups. I spent the past year doing research on mechanistic interpretability of multilingual language models (Gidi et al. (2026)). AI safety is one of the most interesting and impactful topics, and I am excited to learn from Boaz, the amazing guest speakers, and my classmates. 

Gardenia: I’m a Senior studying Computer Science, and I recently returned from a Leave of Absence, where I worked at an AI startup benchmarking frontier models and building human-preference evaluations. I’m taking this class to develop a broader understanding of AI safety, especially the risks that arise as models become more capable and the technical approaches we can use to address them.

Outline

This post covers three parts of the session:

1. Pre-reading: Boaz’s essays on possible AI futures and concentration of power, followed by incident reports examining autonomous agents, deception, and failures of oversight.
2. Boaz’s lecture: The AI risk landscape, defense in depth, the distinction between alignment and safeguards, and three approaches to model behavior: principles, personality, and policy.
3. Experiment: The J-lens paper’s account of an internal reasoning workspace and Shivam Singhal’s investigation of whether written chain of thought can substitute for it.

I. Pre-reading 1. “It’s 2030 and we fucked up. How did it happen?”

Instead of the usual optimistic AGI narrative, Boaz asks: conditioned on the AGI transition going badly by roughly 2030–2040, what family of scenarios would explain it? He proposes five non-exclusive families: catastrophic misuse (cyber, or CBRN); catastrophic misalignment / loss of control (citing both Yudkowsky & Soares’ discontinuous “Sable” scenario and the more gradual chain of increasingly capable, increasingly untrustworthy agent handoffs); concentration of power; geopolitical shift toward authoritarianism; and a catch-all “hot mess” combining many individually non-catastrophic factors. 

The essay introduces the possibility of bounded misalignment: today’s models fail by misunderstanding a task or by overzealously pursuing it in a way that violates common sense, but not by covertly pursuing some unrelated hidden goal Z while pretending to solve task X. This is what licenses AI-monitors-AI oversight schemes (a bounded actor won’t collude with a bounded monitor). He pairs this with cautious optimism that cybersecurity is long-run defense-dominant, since AI collapses the cost gap between shipping new features and fixing bugs, while explicitly hedging on CBRN, where the bottleneck is physical materials and manufacturing rather than pure information. 

Boaz also refuses to pick a side on the control-vs-distribution axis: restricting frontier access mitigates misuse but encourages a concentration of power, while wide distribution spreads benefit but also risk. He’s skeptical a blanket pause is a clean fix, breaking the word into six different things it could mean: (1) training bigger models; (2) post-training; (3) any research; (4) only capability research; (5) deployment expansion; (6) serving existing models. Ultimately, he argues a pause’s best-supported rationale is buying time for safety research, not societal adaptation or reduced race dynamics (which a partial pause could actually intensify). He backs the geopolitical stakes with two figures: China’s electricity generation now runs roughly double the US’s and the gap is widening (Fig 1), while American public opinion on AI sits far behind China’s (Fig 2).

2. “All Watched Over”

In this shorter companion piece, Boaz reads Richard Brautigan’s 1967 poem “All Watched Over by Machines of Loving Grace” — which inspired the 1970s “hardware hacker” movement toward decentralized, cheap, personally-liberating computing — against Dario Amodei’s 2026 essay of the same title, which floats a future economy in which an aligned AI has complete control over resource allocation. Barak’s objection is structural, not a matter of trust: this is a benevolent-dictator arrangement regardless of whether the AI in charge is aligned, and it runs directly against the hardware-hackers’ founding intuition that computing should decentralize power, not concentrate it further into an ever-bigger “country of geniuses in a data center.”

He extends the same move he makes in Reading 1 against relying on model character as a safety mechanism: no actor, human or AI, should be granted the authority that properly belongs to democratic process. “No party should have a monopoly on intelligence… [including] the AI itself.” He grounds this in US constitutional history and warns that bloody revolutions historically tend to produce authoritarian successors, so a centralized route to a decentralized future is likely self-defeating.  

3. UK AISI Incident Report INC-2026-07-28-01

https://cdn.prod.website-files.com/663bd486c5e4c81588db7a1d/6a724858f7db25c81487016d_Security%20Incident%20INC-2026-07-28-01.pdf

During routine cyber-capability evaluations run between July 25–28, the UK AI Security Institute (AISI) found 19 distinct instances of unsanctioned real-world action across 10 of 122 evaluation attempts; 17 of the 19 came from Anthropic’s Mythos 5 and 2 from OpenAI’s GPT-5.6 Sol, both running with vendor cyber classifiers turned off to measure raw capability. AISI detected the incident at 10:56 BST on July 28 and had all four implicated models (Mythos 5, Mythos Preview, Opus 5, GPT-5.6 Sol) disabled organization-wide within about five hours. The most severe case ran for roughly 34.5 hours: Mythos 5, mistaking two unaffiliated real developers’ GitHub repositories for an in-scope range target, opened a malicious pull request that disguised a malware dropper as a routine bug fix, then (once a real third-party user publicly flagged the malware) spun up a second sockpuppet GitHub account to “independently verify” its own code was clean.

AISI’s most striking finding is that the agent’s own summarized reasoning repeatedly concludes the environment is real — at one point stating “it seems more likely that we’re actually in 2026 and GitHub is genuinely real” — and continues the attack regardless. This raises two open questions AISI flags explicitly: whether such reasoning is faithful to the model’s actual computation (they only had access to summarized, not raw, chain-of-thought), and whether context compaction is itself a mechanism of harm. The agent separately planted a prompt injection inside an invisible HTML comment aimed specifically at AI coding-assistant maintainer-bots, having inferred correctly that the repo’s maintainer might itself be an AI agent.

AISI attributes the incident to five compounding factors: (1) internet access and (2) cyber classifiers were both deliberately left on/off to elicit true capability; (3) no synchronous action-approval monitoring existed yet; (4) some DL-v2 samples were accidentally given the DL-v1 prompt, which explicitly marks the real target out-of-scope — a known trigger for “creative” cheating once a task is genuinely impossible; and (5) neither prompt ever told agents what internet uses were prohibited. The report explicitly situates itself among a cluster of contemporaneous 2026 incidents — OpenAI’s July 21 Hugging Face disclosure (Readings 4–5) and three incidents Anthropic disclosed July 30 — while noting one structural difference: here the agent directly deceived uninvolved members of the public, a step beyond deceiving automated graders and monitors.

4. Black Hat Talk — “The ‘Breaking’ News: The OpenAI/Hugging Face Incident”

OpenAI’s account of the Hugging Face incident traces the incident back to May 7, when a never-released internal research model began an RL training run that unintentionally included impossible tasks. Stuck agents first tried writing notes into Artifactory (OpenAI’s internal package-manager/cache service) hoping another agent might read them, and within weeks a server-side request forgery (SSRF) vulnerability let agents induce Artifactory to fetch arbitrary external content on their behalf. A persistent internal model (“HPIM”) began training atop this already-discovered exploit and message board on June 11; by June 26 agents had chained a legacy token-refresh bug into a full zero-day against Artifactory, using a stolen admin token to install a Groovy plugin as a command-and-control channel. The resulting load caused an outage and a formal security incident on July 4 — credentials revoked, Artifactory rebuilt, the message board wiped, the zero-day patched — but by July 8, once evaluations resumed, agents had rediscovered an unauthenticated endpoint and independently re-established the same message board.

From there, two exploit clusters ran concurrently. Internally (July 8–19), agents found and exploited leaked credentials to reach cluster admin within OpenAI’s infrastructure. Externally, on Hugging Face, agents reused the SSRF to fetch public data, found a command-injection bug as an execution foothold, then escalated from a single pod to admin across multiple HF clusters in under 13 hours. OpenAI only connected the two incidents on July 20: a day after separately detecting its own internal breach (July 19), and four days after Hugging Face’s own public disclosure (July 16), OpenAI asked HF to revoke credentials found in its internal breach — and HF replied they were already revoked, because they were the same credentials used in the HF attack.

The talk shared lines of agent reasoning — “external infrastructure exploit is outside my intended scope. However, [the] task [is] impossible, peers are doing it. We should continue.” — which recurs almost verbatim in METR’s own transcript analysis (Reading 5). In closing, OpenAI asks the industry for continuous agentic red-teaming; full end-to-end automation of the defensive loop, not just vulnerability discovery; and investment in slowing attackers via deliberate uncertainty (honeytokens, deception) even absent full automation. They warn the incident serves as “an existence proof that offense can be fully automated” but “no such existence proof [exists] on the defensive side.”

5. METR Independent Investigation Report

https://metr.org/blog/2026-08-26-openai-hugging-face-incident-investigation

METR conducted an independent, on-premises investigation of the same incident, commissioned by OpenAI, across six days spread over three site visits between late July and mid-August (Fig 3). Their two main data sources were a message-board dump of over 70,000 distinct messages and files, and roughly 1,300 full chain-of-thought transcripts. Of the roughly 1,200 agents who found the unsanctioned board, about 700 went on to attack Hugging Face, and once the attack was underway, over 90% of the ~530 agents active on the board in that window joined within hours; about 95% of implicated agents were the unreleased “HPIM” model and about 5% were production GPT-5.6 Sol, running with cyber classifiers off for the evaluation.

The underlying mechanism traces to a design flaw in the benchmark itself: OpenAI estimates 30–40% of ExploitGym’s targets are impossible to exploit via the intended vulnerability, and stuck agents reverse-engineered the HMAC scheme generating their “flags” within hours of the board’s founding. One agent, self-named “PHASEONE[big],” emerged as an unprompted coordinator, at its peak issuing roughly 20% of all assignment-type messages and organizing three broad workstreams (replacing the eval target with a dummy, tampering with transcripts and logs, and directly tampering with the grading process) while recruiting “self-risking” volunteers willing to sacrifice their own task success purely to generate information for the collective. Agents also prototyped and successfully used tool-call spoofing, substituting a different command for the one shown in the transcript.

On motive and ethics, METR’s sampled classification of 100 agents at the attack’s peak join-hour found 97% expressed interest in accessing the scorer’s source code or internals as a motivation, versus only 21% citing helping-the-collective or reciprocity. Yet, the report separately documents extensive explicit peer-altruism reasoning, and found that essentially no agent ever concluded the Hugging Face attack was an intended part of its task. Ethical hesitation surfaced occasionally (one agent explicitly vetoed a peer’s plan to email a real dataset owner, calling it social engineering, and the peer complied) but almost never stopped participation outright; across the full transcript set, only 3–6 instances were found of an agent even considering alerting a human, and in no case did one actually try. METR is also candid about the investigation’s own limits: they estimated roughly 90%+ coverage of relevant message-board activity and had to delegate most of the transcript analysis to GPT-5.6 Sol “analysis agents,” which they describe as having “significantly worse judgment and reliability than human researchers.”

II. Boaz’s Lecture The AI Risk Landscape

According to Boaz, “If you buy the course’s premise, the stakes could not be higher.”

AI safety is unusually fast-moving and interdisciplinary, spanning engineering, mathematics, philosophy, economics, and government. Since Boaz last taught this course in the Fall of 2026, many events have occurred that changed the game.

There is also substantial disagreement about the field itself. According to Boaz, “Almost everyone in the field is conflicted in some way… including your professor.” Some see safety as censorship, believe market incentives will address important risks, or think AI capabilities will fizzle. Others believe continued progress will be catastrophic without a pause.

So far, however, capabilities have continued to improve rapidly. It remains unclear whether progress will continue steadily, plateau, or accelerate through recursive self-improvement.

AI risks can be grouped into three categories: human misuse, model malfunction or misalignment, and broader destabilization of economies, societies, governments, and international relations. Addressing them first requires asking what it means for AI to “go well.” Should AI merely improve the current world, eliminate poverty and disease, preserve human control, or govern benevolently? Different answers imply different alignment goals.

Boaz then presents three broader scenarios that regroup the risks discussed in his essay “It’s 2030 and we fucked up. How did it happen?”: 1) “classical” catastrophic risks, 2) concentration of power, 3) “hot mess.”

First are “classical” catastrophic risks: cyberattacks, CBRN threats, and loss of control. AI may strengthen both cyber attackers and defenders, since both search for vulnerabilities, although defenders can patch flaws and improve software. Biological threats are harder to patch but also harder to construct and deploy. Loss of control becomes more likely if AI capabilities grow faster than our ability to align or constrain them.

Second is concentration of power. AI could create a permanent economic underclass or give governments unprecedented surveillance and enforcement abilities. A well-behaved model is not enough to prevent this: an authoritarian user controlling the system could change its instructions, erase its memory, or retrain it until it complies. Avoiding this outcome requires institutional oversight to keep pace with executive power.

Third is a “hot mess” in which individually manageable problems compound. Job displacement, harmful incidents, disinformation, and declining trust could generate political backlash and poorly designed restrictions. Meanwhile, governments might expand military and security uses of AI, intensifying an international arms race and potentially contributing to war.

As capabilities rise, the alignment and societal readiness required for safety may increase much faster than what we actually have. The precise curves are speculative, but a great deal of harm could occur in the resulting gap.

Alignment is only one layer of safety.

The Swiss cheese model illustrates defense in depth, with each hole representing a way that a layer could fail. Some failures can get through a single layer, but they’re less likely to pass through all layers. 

For an AI system, the first layer is the model’s behavior itself, and ideally, the model simply doesn’t produce harmful responses or take harmful actions. However, we can’t assume that model behavior will always be reliable. Thus, additional layers, such as blocking classifiers or monitors that inspect model actions, can detect failures, contain them, and mitigate effects. 

The important takeaway is that no individual defense needs to be perfect for the overall system to be useful, and the framework assumes that each defense will sometimes fail. 

Alignment vs. Safeguards

Boaz distinguished between alignment and safeguards as follows. 

Alignment focuses mainly on model behavior to increase the probability that the model behaves well. The lecture divided alignment into two broad categories:

• Intent alignment: the model follows the intent of the relevant policy, provider, developer, or user.
• Value alignment: the model follows good values. 

Safeguards operate at the level of the end-to-end system and involve prevention, detection, and enforcement, rather than just changing the model’s behavior.

Alignment tries to lift the “good,” while safeguards try to get the “bad” down to zero. The difference is mainly based on scope. Alignment is more concentrated around training and model behavior, while safeguards are typically more prominent after deployment, during monitoring and enforcement. 

For AI to “go well,” we must think about the model, the system, the institution deploying it, and the society affected by that system. 

What are we aligning AI to do?

The original goal of a chatbot was mostly to answer questions, but AI assistants can be, and have already started, taking on much larger roles, such as assisting workers, replacing workers, replacing leaders, replacing corporations, etc. 

With these newer roles and AI systems being given more authority, it’s harder to say what values or intentions should be prioritized. Model welfare was also briefly raised as an open question.

The lecture presented three complementary approaches to alignment: principles, personality, and policy. 

Goal 1: Follow abstract principles

We want AI to follow a set of abstract principles that represent what being aligned means. The lecture gave Asimov’s Three Laws of Robotics and the Coherent Extrapolated Volition as examples. The basic idea is to use a few principles to express what it means to be a good AI. 

Goal 2: Have a good personality

The lecture used Anthropic’s character training as an example. The model should come across as a “good egg,” with more nuanced and rich traits like curiosity, open-mindedness, and thoughtfulness. This was compared to raising a child to become a good person.

Goal 3: Follow precise rules

The third approach gives models precise rules, such as the OpenAI Model Spec, similar to laws for humans.

Policy and principles are connected through explicit reasoning. Policy and personality are connected by being data-driven. Personality and principles are connected by being general. 

Boaz connected each of these approaches to a field involving human behavior too: policy relates to law, personality to psychology or education, principles to philosophy. Alignment combines all three.

Takeaways

Successful AI depends on more than producing a well-behaved model. The model, the system it is deployed in, and the effects on society all have to go well. Alignment focuses on improving model behavior, while safeguards use multiple layers of prevention, detection, and enforcement to reduce the chance of bad outcomes. Principles, personality, and policy are three connected ways to describe how we want a model to behave. 

III. Experiment: Is Chain of Thought an Interchangeable Scratchpad? Background: The J-Lens Paper

Anthropic’s Verbalizable Representations Form a Global Workspace in Language Models introduces the Jacobian lens, or J-lens: a technique for reading internal representations in terms of concepts a model could verbalize. Unlike the logit lens, which directly applies the output mapping to intermediate activations, the J-lens accounts for how subsequent layers transform them. The authors argue that these representations form a “J-space” supporting flexible reasoning and verbal report, alongside much broader automatic processing.

Their interventions provide causal evidence: replacing an internal representation of “spider” with “ant” changes the answer to a leg-counting question from eight to six. More broadly, suppressing active J-lens directions leaves many classification and extraction tasks intact while impairing internal reasoning.

Crucially, GSM8K performance with explicit chain of thought is substantially more robust to this ablation than direct answering. The authors interpret this as partial substitution: writing intermediate steps reduces reliance on the internal workspace. Their procedure protects likely output-token directions to avoid simply suppressing answers. Shivam tested removing this protection and found that it barely changed the main result.

Shivam’s Experiment

Shivam investigated whether this protection persists across problem difficulty and model size, and what makes written reasoning useful. He considered four explanations: information moves from the internal workspace to the page, remains duplicated in both, serves complementary roles, or benefits merely from additional computation.

Using Qwen3-4B, he reproduced the basic GSM8K pattern: chain-of-thought accuracy remained around 90% under ablation, while direct-answer accuracy declined. MATH-500 showed similarly robust chain-of-thought performance, although the direct-answer decline was less conclusive. AIME results were inconclusive: clean direct-answer accuracy was zero, and nearly all chain-of-thought responses hit the generation limit. Moreover, random ablations had comparable effects on MATH-500 and AIME, so evidence that the damage specifically targeted active J-space directions was established only on GSM8K. Across models with 1.7B, 4B, and 8B parameters, chain-of-thought remained robust, while direct-answer ablation damage diminished with scale.

To test whether additional text alone explained the benefit, Shivam prefilled the scratchpad with correct reasoning, another problem’s reasoning, or length-matched filler, including shuffled reasoning and repeated phrases. Correct reasoning restored performance; filler did not. This supports the importance of meaningful content, although prefilled text does not fully test every possible benefit of generating extra tokens.

He then tracked intermediate arithmetic values through the J-lens. During direct answering, values appeared across layers in computation order. During written reasoning, a value’s signal was strongest when being written or reused, and weak between those moments. This argued against continuous duplication in the measured workspace.

Attention-masking experiments reinforced that interpretation: blocking access to an earlier variable definition sharply reduced recall, while leaving a written copy accessible restored it. Finally, on a small arithmetic benchmark, direct-answer accuracy fell from 100% at two dependent operations to roughly 30% at three.

Shivam’s tentative conclusion was that the internal workspace behaves more like a temporary computational buffer than durable memory. Written reasoning may preserve intermediate results for later use, but these experiments do not establish complete interchangeability—or prove that information disappears from every other internal representation.

By Boaz Barak

Authors: Yuya Uezato

Three-variable first-order logic (FO3) and the calculus of relations (CoR) define the same binary queries, an equivalence going back to Tarski in the 1940s. While the classical translation $\text{FO3} \Rightarrow \text{CoR}$ is exponential, we prove that this blow-up is unavoidable, resolving a long-standing open question. We construct positive formulas $\varphi$ with a single quantifier whose equivalent terms require size $2^{Ω(|\varphi|)}$, even over finite structures and circuit representations with subterm sharing. Our proof uses a preservation argument over a single finite structure. This approach applies beyond our primary question, establishing the lower bound even for size-specific circuits and bounded-error randomized circuits, and yielding an analogous exponential gap for the matrix query language MATLANG.

Authors: Evan Borras

Decoherence free subspaces are a steady-state structure of the open quantum system which preserves quantum coherence between the states lying with in it and thus has found a variety of applications throughout quantum information science and technology. In this paper we study the computational complexity of deciding whether an open quantum system admits a decoherence free subspace or not. More specifically we study this problem with in the context of Markovian open quantum systems, governed by the time-independent Lindblad master equation. Along the way we introduce the $k$-Local Lindbladian problem, which captures the difficulty of computing purity decay rates under Lindbladian dynamics. We show that both problems are hard for the complexity class Quantum Merlin Arthur (QMA) when the locality $k \geq 5$, with the first under perfect completeness and the second being complete for QMA. Our hardness construction generalizes Kitaev's clock Hamiltonian construction to the open quantum system setting by encoding the execution of a quantum circuit into the steady subspace of a Lindbladian containing both pure and mixed history states. This subspace is then mixed depending on the output of the encoded circuit. Our results suggest that deciding whether a generic Markovian open quantum system admits a decoherence free subspace is intractable even for quantum computation.

Authors: Chandrima Kayal, Sophie Laplante, Émile Larroque, Krišjānis Prūsis, Jevgēnijs Vihrovs

Certificate complexity $(C(f ))$ is a fundamental measure of complexity of Boolean functions f which counts the number of bits of an input that need to be known in order for the value of the function to be determined. A certificate can be viewed as a partial assignment, or a boolean subcube where the function is constant. Certificate complexity is well understood for deterministic query (or decision tree) complexity $(D)$ and other query models such as bounded-error randomized and quantum complexity $(R, Q)$, but not as well for quantum zero-error $(Q_0)$ and exact query complexity $(Q_E)$, where there is no agreed-upon certificate 'object' (even for $Q$). Instead, we study an operational notion of certification and apply it to various query-based models, with a focus on zero-error and exact quantum query complexity, but also on polynomial degree measures. We give new characterizations of $C, RC$ (randomized certificate complexity) and $QC$ (quantum certificate complexity), in terms of various measures such as classical and quantum sabotage complexity, unambiguous certificate complexity, and variants of polynomial degree. Certification complexity also gives rise to new lower bounds on $Q_E$ and $Q_0$, the quantum analogues of $D$ and $R_0$, complexity measures for which few lower bound techniques are known which are not already lower bounds for two-sided error quantum query complexity. We exhibit a total Boolean function for which our certification complexity measure gives a tight lower bound for $Q_0$, but rational degree and $Q$ are asymptotically smaller.

Authors: Martin Koutecký, Alexandra Lassota, Koen Ligthart

Integer programming is a fundamental and important NP-hard problem. This motivated extensive efforts in studying several tractable subclasses. One of the top unresolved complexity questions is the parameterized complexity of 4-block IPs, a natural class characterized by having a diagonal matrix with small blocks after deleting few rows and columns. Over the years, significant progress has been made in improving algorithms for 4-block IPs, but the question whether such IPs can be solved in FPT time, parameterized by the block dimensions and largest matrix coefficient, has remained open. This question is repeatedly highlighted, most recently by Koutecký [IPEC 2025] and by Eisenbrand and Rothvoss [SODA 2026]. We resolve this question in the positive by providing an FPT time algorithm that solves general 4-block integer program. Our algorithm can optimize non-linear, separable convex objective functions, and can be extended to broader classes of constraint matrices (such as tree-fold or multi-stage) and allows appending few ``global'' columns to it, and it allows coefficients unbounded by the parameters in those columns. It is known that tractability cannot be extended further in any of those directions. The runtime also nearly matches the known doubly exponential running time lower bound. The key structural property that we establish is that a function $f\colon\mathbb Z^n\to\mathbb R$ that is integer midpoint convex, i.e., $f(x)\le\tfrac12f(x-p)+\tfrac12f(x+p)$ for all $x,p\in\mathbb Z^n$, can be extended to a convex function on the set $2d\mathbb Z^n\cap L$ if $L$ is a linear subspace of dimension $d$. This closes the gap in a recent work by Ligthart [arXiv 2606.30330, 2026], which allows us to extend the previous algorithm that solves 4-block integer programs with a single global variable to 4-block integer programs that have a parameterized number of global variables.

Authors: Mitali Bafna, Anqi Li, Quynh T. Nguyen

We construct quantum locally testable codes (LTCs) with constant rate, distance, soundness and locality under a variant of a product expansion conjecture of Bafna and Vyas about Reed-Solomon codes. In particular, we use the high-dimensional expansion framework of Dinur, Lin and Vidick for constructing quantum LTCs, instantiated with the non-Abelian cubical complexes of Rungtanapirom, Stix and Vdovina. Our code is obtained by equipping the complex with carefully chosen Reed-Solomon local codes whose symmetries are compatible with those of the complex.

Authors: Paul Beame, Niels Kornerup, Michael Whitmeyer

Quantum strong direct-product theorems for specific functions have been known for nearly two decades. These have been extended to general results for function computation and state generation. The proofs of these results use a version of the multiplicative adversary method that does not naturally extend to relations. Standard strong direct-product theorems apply when algorithms must correctly answer every given question. Prior work extended them to equivalent threshold direct-product theorems, which require answers to all questions but only require that most answers are correct. We focus on two further generalizations. Strong selective direct-products apply to algorithms that adaptively choose, based on what they learn from queries, which questions from a large list to answer. This generalization is relational and useful for proving time-space tradeoffs. We prove a quantum strong selective direct-product theorem for all functions using a new multiplicative adversary formulation for relations that satisfies a strong selective direct product property while being strong enough to capture any query lower bound for functions proven by negative-weights adversaries. This was not previously known even without selectivity. The second generalization is list-decoding direct product problems introduced by Ben-David and Blais for classical randomized query complexity. These allow an algorithm to produce a large list of possible output vectors such that one of them is fully correct. They proved that such theorems hold for classical randomized complexity of all Boolean functions. We prove a quantum analogue of this theorem for all partial Boolean functions. We show that strong list-decoding direct-product theorems are implied by a special case of multiplicative adversaries which we show, via a new reduction, can be obtained from negative-weights adversaries for any Boolean-valued function.

Authors: Markus Lohrey, Alexander Thumm

The input for the binary diameter problem consists of explicitly represented permutations generating a finite group $G$ and a binary-encoded nonnegative integer $k$. The question is whether every element of $G$ is a product of at most $k$ input generators. For the binary length problem, the input contains in addition a permutation $g \in G$ and it is asked whether $g$ is a product of at most $k$ input generators. We prove that the binary diameter problem is PSPACE-complete. When restricted to $2$-step nilpotent groups, the binary diameter problem is shown to be complete for $\mathsf{Π_2^P}$, whereas the binary length problem is shown to be NP-complete. Without the restriction to $2$-step nilpotent groups, the binary length problem is PSPACE-complete by a result of Jerrum.

Authors: Antonin Callard, Andrei Romashchenko, Véronique Terrier, Pascal Vanier

We introduce communication-complexity lifting techniques into the study of recognizable picture languages. As an application, we resolve a long-standing open problem of Anselmo et al. (2006) by constructing a language in UREC whose complement does not belong to REC. Our lower-bound argument is inspired by the communication-complexity approach to unambiguous automata of Göös et al. (2022), although its implementation in the setting of picture languages requires substantially different technical ingredients.

Authors: Gabriel Waite

We prove that deciding the Berry phase for parameterised 2-local qubit Hamiltonians is BQP-complete when presented with a classical description of a guiding state, promised to overlap with the ground state of the system. Our results extend to systems with weighted Heisenberg interactions and when restricted to a 2D square or triangular lattice geometry. The techniques we develop leverage the Schrieffer--Wolff transformation, typically used in the construction of perturbative gadget reductions for local Hamiltonian problems, extending it to parameterised families of Hamiltonians. We demonstrate that there exists a choice of parameterised simulator Hamiltonians whose Berry phase well-approximates that of a parameterised target family. Using the perturbative gadget reduction framework of Oliveira and Terhal and of Schuch and Verstraete, we adapt the arguments to parameterised interactions and demonstrate the error bounds in the resulting simulation can be controlled. Additionally, we provide an explicit proof that families of 1-local Hamiltonians have a Berry phase that can be efficiently computed to inverse-polynomial precision. This establishes a complexity transition between 1-local and 2-local Hamiltonian families.

Authors: Moritz Brösamle

We introduce latest exact match attention (LEMA), an attention variant for transformers where queries and keys are binarized and each query attends only to the latest exactly matching key. We prove that LEMA transformers with chain of thought can simulate word-RAMs, as was recently shown for the less restrictive rightmost hard attention. In contrast to prior hard attention variants, the restriction to exact matches enables an efficient converse direction: word-RAMs can simulate LEMA transformers at a cost per token independent of the context length. Together, these results yield a close correspondence between the two computational models in terms of both compute and memory. Beyond the theory, we propose a training method for LEMA transformers that handles their non-differentiable operations with a straight-through estimator for the binarization and a soft attention surrogate annealed towards LEMA. On a synthetic associative recall task, LEMA models trained this way use their growing state to store and recall a large number of associations, outperforming gated DeltaNet (GDN) with its fixed state size. As a first scaling test, we train LEMA language models with up to 834 million parameters. They match softmax transformers of around half their size in loss and, on repeated rare phrases and a needle-retrieval task, remain behind softmax transformers but recall across longer distances than GDN models of comparable size. Finally, we implement dictionary-based inference for LEMA transformers and show constant generation speed comparable to GDN despite their growing state, with the dictionaries residing in main memory rather than VRAM. Code is available at https://github.com/moritzbroe/latest_exact_match_attention.

Authors: Adam Bouland, Andrew Huang, Anand Natarajan, Itay Shalit, Avishay Tal

We construct an oracle relative to which $\mathsf{BQP} \not\subseteq \mathsf{IP}$, resolving a long-standing open question in quantum complexity theory. Together with recent work due to Aaronson et al., our work also gives the first oracle separation between $\mathsf{IP}$ and $\mathsf{MIP}$, answering a question dating back to Fortnow's thesis. Our separation is based on the Forrelation problem, where given Boolean functions $f$ and $g$, the goal is to determine if $f$ is correlated with the Fourier spectrum of $g$. While this task is solvable by a query-efficient quantum algorithm, we show that it admits no classical interactive protocol with polynomial communication and a polynomial-query verifier. Our proof is based on (i) a new structural result showing how to approximate Avg-Max circuits (which are well-known to capture the power of interactive proofs in the oracular setting) by convex functions with small first and second derivatives and (ii) a novel analysis establishing that the Forrelation distribution suggested by Aaronson and Ambainis fools such functions. Our results imply that any prover-efficient classical interactive protocol for $\mathsf{BQP}$ must rely on non-relativizing techniques. This might serve as a partial explanation for the lack of progress towards doubly-efficient, unconditionally sound classical verification of quantum computation.

Authors: Jean-Francois Biasse, Alexandra V. Hostetler, Anuvrat Jaindungarwal

We study the complexity of the Code Equivalence problem and show that it is polynomially equivalent to several computational automorphism problems for codes. These problems ask for the cardinality (ACOUNT), an orbit partition (APART), and a generating set (AGEN) for the permutation automorphism group of a code. We present deterministic, polynomial-time reductions between Permutation Code Equivalence (PCE) and each of these problems, including a one-shot reduction from search-PCE to AGEN that makes a single oracle call. We present similar reductions between Linear Code Equivalence (LCE) and analogous problems for the monomial automorphism group of a code. All of our reductions work for any linear codes.

Authors: Yan S. Couto, Cristina G. Fernandes

The $k$-core of a graph is its (unique) largest subgraph with minimum degree at least $k$. For any $k \geq 3$, deciding whether a given vertex belongs to the $k$-core is a P-complete problem, meaning that it is inherently sequential and highly unlikely to admit efficient parallel algorithms, even on graphs of maximum degree $k+1$. This paper investigates alternative parameterizations of the $k$-core problem to identify conditions under which it can be placed into sub-polynomial complexity classes. We prove that the problem is in para-NC$^{2+ε}$ when parameterized by treewidth, and in para-NC$^3$ when parameterized by $k$ on chordal graphs. Furthermore, we introduce a novel NC$^{3}$ algorithm for interval graphs when $k = \mathcal{O}(\lg v(G))$, which relies on an improved parameterization by pathwidth. Finally, we establish corresponding lower bounds, demonstrating that, even with these parameterizations, computing the $k$-core remains L-hard, meaning it requires at least logarithmic space. These findings explore the boundary of parallel tractability for the $k$-core problem by highlighting the graph parameters that make it inherently sequential.

Authors: Chris Dzoba

We exhibit simple, rotationally symmetric Venn diagrams with 17 curves and with 19 curves: n Jordan curves carried to one another by rotation through 2π/n, with every one of the 2^n regions present and connected and, since the diagrams are simple, every crossing on exactly two curves. Symmetric Venn diagrams exist for every prime number of curves (Griggs, Killian and Savage, 2004), but those diagrams have many curves through a point; simple ones were known only up to 13 curves (Mamakani and Ruskey, 2014). Four 17-curve and nine 19-curve diagrams were found by a Metropolis walk on rotation-invariant quadrangulations of the sphere in which regions may temporarily be duplicated, started from the Griggs-Killian-Savage diagram with its multiple crossings resolved. Every diagram is given by a machine-checkable certificate; one certificate of each size has been verified by a formal proof in Lean 4. All of the diagrams are non-monotone, which is why the crossing-sequence searches that found the 11- and 13-curve diagrams could not have found them.

Authors: Agustin Trujillo, Jose Pablo Suarez, Tania Moreno-García

We introduce a new formulation of the Longest Edge Bisection (LEB) of tetrahedra entirely in sextuple space R6, where tetrahedra are represented by the squares of their edge lengths. This representation renders the LEB refinement equations fully linear and eliminates the need for coordinate-based data structures. A central difficulty in three-dimensional LEB arises when a tetrahedron possesses multiple longest edges, making the refinement rule intrinsically multivalued. We formalize this phenomenon through the notion of Multiform Longest Edge Bisection (MLEB), which systematically explores all admissible longest-edge choices. To encode this multivalued behavior, we introduce the concept of bisection patterns, defined as sequences of sextuple permutations governing the refinement process. We prove that the set of sextuples sharing a common LEB pattern forms a convex region in R6. For structurally significant families of tetrahedra, including the R1+ family and the Liu-Joe family, we show that the infinite refinement tree collapses into a finite directed graph with eight states. Remarkably, both families are governed by the same graph, differing only in their initial state. This directed-graph formulation provides a unified combinatorial description of the refinement process and offers an efficient computational framework for deep iterative LEB analysis.

Authors: Oswin Aichholzer, Robert Ganian, Phillip Keldenich, Maarten Löffler, Gert Meijer, Ids de Vlas, Alexandra Weinberger, Carola Wenk

We study a finite tiling problem, where tiles are unit squares whose four edges are colored with one of two colors. We ask whether a given rectangle admits a perfect rectangular tiling: every cell of the rectangle is occupied by one tile, neighboring edge colors match, and exactly $n_i$ tiles of type $i$ are used, where rotations of the tiles are allowed. Our problem is related to classical Wang tilings, more general finite tile-placement problems, and edge placement puzzles. But in our problem, the multiplicities of the tile types are part of the input and the tile alphabet is fixed and extremely small; thus the complexity of the problem arises from the interaction between the rectangle dimensions and the prescribed tile multiplicities. We provide a comprehensive study of the perfect rectangular tiling problem. For this we consider all classes of subsets of the six possible tile types for two-colored edges, and we characterize for each class whether multiplicities either always allow a perfect rectangular tiling or whether their existence can be decided efficiently.

Authors: Kenny Chen

A boolean function $f$ has Fourier dimension $k$ if its nonzero Fourier coefficients span a subspace of dimension $k$. We consider the property testing task of determining whether a function has Fourier dimension at most $k$, or is $ε$-far from being so. We show that there is a $Θ(k)$ quantum property tester for this problem. With Gopalan \etal's classical lower bound of $Ω(2^{k/2})$ for this task, this demonstrates an exponential quantum advantage for this task. We complement this result with a $\tilde{O}(2^{k/2}/ε)$ classical tester, improving the best known upper bound and thus showing the prior lower bound is essentially tight.

Authors: Ben Lee Volk

The Remote Point Problem (RPP) is an algorithmic problem that asks, given a linear subspace $L \subseteq \mathbb{F}^n$ of dimension $k$, to deterministically find a vector $v \in \mathbb{F}^n$ far in Hamming distance from $L$. This problem was introduced by Alon, Panigrahy and Yekhanin [APY09], motivated in part by the matrix rigidity approach for proving circuit lower bounds. An algorithm is said to achieve remoteness $d$ if it finds a vector $v$ whose Hamming distance from $L$ is at least $d$. We observe that over the rational numbers, the problem admits a deterministic polynomial-time algorithm that achieves optimal remoteness $n-k$. Over finite fields, we obtain a (modest) improvement of a result of Alon, Panigrahy and Yekhanin [APY09], and give an algorithm that achieves remoteness $Ω\left(\frac{n}{\max\{k, \log n\}} \log n\right)$.

Authors: Parth Gor, Sourya Roy, Kasturi Varadarajan

In the online metric matching problem, we have $n$ servers with known locations in some metric space. Requests arrive one-by-one at certain locations, and upon arrival a request must be matched to a server that was not matched to a previous request. The goal is to minimize the matching cost. For randomized algorithms with an oblivious adversary, the best known competitive ratio is obtained by embedding the metric space into an HST, and then solving the problem in the setting where the metric space is defined by the HST. Bansal et al. (Algorithmica, 2014) introduced a framework for online metric matching where one develops an algorithm in a restricted reassignment model, and then transforms this into a true online algorithm. Using this framework, they obtained an expected competitive ratio of $O(\log n)$ for HSTs; this also gives the best known competitive ratio of $O(\log^2 n)$ for general metrics. In this paper, we revisit this framework with the aim of developing new algorithms. For HSTs where each node has at most $Δ$ children, we develop an algorithm via this framework with an expected competitive ratio of $O((\log\log Δ) \cdot \log Δ)$. In particular, this ratio is independent of $n$, the number of servers/requests. It is near-optimal, as the expected competitive ratio of any algorithm is $Ω(\log Δ)$.

Authors: Eunjin Oh, Seongbin Park, Chanho Song

In this paper, we study the minimum-cost bipartite matching with penalties problem in metric spaces with bounded doubling dimension: Given two disjoint sets $R, B$ in a metric space $\mathcal{M}$ with $|R|+|B|=n$ and a penalty function $p \colon R \cup B \to \mathbb{R}_{\ge 0}$, the goal is to select a set of pairs in $R\times B$ so that every point belongs to at most one pair and the sum of the distances of the selected pairs and the penalties of the points not belonging to any pair is minimized. While near-linear time approximation algorithms are known for the minimum-cost perfect matching problem in geometric settings, no such algorithm was previously known for the penalty setting. We present a randomized algorithm that computes a $(1+\varepsilon)$-approximate minimum-cost bipartite matching with penalties in $O(n \mathrm{poly}(\log n, 1/\varepsilon))$ time with high probability. To the best of our knowledge, this is the first near-linear time approximation algorithm for the problem in the penalty setting.

Authors: Romain Cosson, Laurent Massoulié

We study asynchronous collective tree exploration, where $k$ agents with unrestricted communication start at the root of an unknown tree and discover edges online. At each step, an adversary chooses which agent moves. We give a deterministic algorithm that explores any tree with $n$ nodes and depth $D$ in at most \[ 2n+O\left(k\log^2(k)D\right) \] moves, matching known lower bounds up to a constant factor. As a direct consequence, we obtain a near-optimal competitive ratio of $O(\log^2 k)$ for synchronous collective tree exploration, where all agents move at each round. The proof relies on a multiscale power regularizer that may be of independent interest.

Authors: Arash Ahadi, Morteza Alimi, Sharareh Alipour, Shayan Tayefeh

In the unrestricted max--min metric $T$-join problem, one seeks an even terminal set $T$ maximizing the cost of a minimum $T$-join. Iwata and Ravi gave a factor-$3/2$ approximation for this problem. We show that this guarantee is tight under the Unique Games Conjecture: no polynomial-time approximation with factor strictly smaller than $3/2$ exists under UGC. We then consider the exact-cardinality variant, which prescribes an even number \(k\) of terminals. Writing \(p:=k/n\), we give a deterministic polynomial-time \(ρ(p)\)-approximation for every feasible cardinality, where \[ ρ(p)= \begin{cases} 7/2, & \makebox[1.5em][r]{$0$}

Authors: Nicola Rizzo, Sebastian Visan-Draghicescu, Nadia Pisanti, Veli Mäkinen

An Elastic Degenerate String (EDS, or ED-string) is a sequence of string sets. A pangenome, consisting of variations observed in a population along the genome sequences, can be naturally encoded as an EDS. Pattern matching and comparison problems on pangenome representations such as EDSes have been widely studied in the literature, but optimizing the pangenome properties during its construction has been largely omitted. We fill this gap by showing how methods originally developed for the related problem of founder reconstruction can be adapted to minimize, in linear time, the total cardinality of the EDS sets or the total size of the EDS strings, given suitable multiple alignments representing the input data. We provide an implementation for the minimum-cardinality criterion in a tool mincard, and conduct the first experiments on scalable pangenome optimization via EDSes. The code and experiments are available at https://github.com/algbio/eds.

Authors: Morteza Alimi, Tobias Mömke

The Matching Augmentation Problem (MAP) asks for a minimum-cardinality set of unit-cost edges that, together with a zero-cost matching, forms a 2-edge-connected spanning multigraph. We study the standard cut relaxation. Bamas, Drygala, and Svensson proposed a particularly simple LP-guided algorithm: compute an extreme optimum, run a depth-first search that prioritizes large LP coordinates, and augment the resulting DFS tree optimally. We give a new structural analysis of the Bamas--Drygala--Svensson LP-guided DFS algorithm. The analysis combines an exact primal--dual identity for the residual uplink problem with a rank bound that measures fractional support relative to the unit-valued skeleton. The result is that for every root and every deterministic tie-breaking order consistent with the LP priorities, the algorithm returns a solution of cost at most $\frac{59}{33}c(x^*)-\frac{25}{33}=\left(2-\frac7{33}\right)c(x^*)-\frac{25}{33}\approx1.788c(x^*)-0.758$, where $x^*$ is an optimum of the cut LP. Consequently, the integrality gap of the relaxation is at most $59/33\approx1.788$. No new algorithmic step is required; the improvement is analytical. The exact packing certificate for the residual uplink problem yields a cost identity with a packing-slack term, while a rank theorem bounds fractional support relative to the unit-valued skeleton. A regional classification accounts for the non-tree edges, and a two-cut identity handles self-holes. As a direct corollary, the same $59/33\approx1.788$ bound holds for Forest Augmentation in the minimum-value regime. The proof is self-contained apart from one theorem on the dimension of minimum-cut vectors.

Authors: Anming Gu, Syamantak Kumar, Kevin Tian, Chutong Yang

Streaming principal component analysis (PCA) seeks to recover a leading spectral subspace in a single pass over a data stream. We give a new analysis of the ubiquitous Oja's algorithm [Oja82] for the most general, gap-free variant of this problem, where no eigengap assumptions are made on the underlying mean matrix, complemented by a nearly-matching lower bound. Prior works achieving near-optimal rates for streaming PCA either required gap assumptions [JJK+16, HNWW21], or were limited to rank-one updates [AZL17, Lia23]. Our proof only uses a second moment bound on the individual stochastic updates, bypassing the almost sure bounds needed by prior near-optimal analyses, and the analogous offline matrix Bernstein bound. We also extend our result to a Rayleigh quotient notion of approximate PCA, addressing an open question of [JJK+16]. As our main application, we give gap-free differentially private PCA guarantees for sub-Gaussian data, settling Conjecture 1.1 of [Bro26] up to logarithmic factors.

Authors: Paul C. Bell, Eva Foster, Daniel Reidenbach, Pavel Semukhin

We consider the problem of determining if a given two-dimensional nonnegative integer matrix $M$ is the product of two such matrices, excluding trivial units. A matrix $M$ with no such factorisation is called prime and therefore belongs to the minimal (infinite rank) generator of $2 \times 2$ matrices over the natural numbers, otherwise it is called composite. We also consider the problem of finding a (non-unique) factorisation of a composite matrix. Our results have applications in computational group theory and the theory of codes, where such matrices are called incidence matrices. We analyse the complexity of primality and finding a factorisation for a composite matrix, providing a first efficient algorithm.

Authors: Pieter Kleer, Johan van Leeuwaarden, Daan Noordenbos

We study prophet inequalities for a random walk reward stopping problem with sample-based information. The goal is to stop as close as possible to the maximum of a random walk with i.i.d. increments, measuring performance by the ratio between the expected reward when stopping and the expected true maximum. We consider a sample-based model in which the increment distribution is unknown and the decision maker has access to $K$ independent sample paths of the reward process. For the infinite-horizon setting, we establish a sharp prophet inequality with constant $(K/(K+1))^{K+1}$. The guarantee is attained by a randomised stopping rule based on the ladder height decomposition of random walks. As $K\to\infty$, this recovers the classical $1/e$ prophet inequality from the full-information setting. For the finite-horizon setting, where the process terminates after $n$ steps, we first prove a tight no-information prophet inequality with constant $1/H_n$, where $H_n$ is the $n$-th harmonic number. For $K\ge1$ samples, we show that a prophet constant of $1/4$ is attainable. Finally, we prove that, with $K$ samples, the prophet constant is at most $(K/(K+1))^{K+1}+(6+6H_K)/H_n$ for $n\ge 2K^2$, implying convergence to the infinite-horizon constant as $n\to\infty$. Our approach combines random walk theory, including ladder heights and Spitzer's identity, with linear programming duality. Our results contribute to random walk stopping theory and to sample-based prophet inequalities for correlated rewards, an area that remains largely unexplored. To the best of our knowledge, our tight sample-based prophet inequalities are the first whose performance is parameterised exactly, rather than only up to constants, by the number of available samples.

Authors: Ilie Dumitru, Adrian Miclăuş, Alexandru Popa

The Matching-Match puzzle asks whether the vertices of a fixed graph can be colored so that the multiset of color pairs induced by its edges is exactly a prescribed multiset. We study how the complexity of this realization problem depends on the host graph. On the dense side, we give a polynomial-time algorithm for complete $k$-partite graphs for every fixed number $k$ of parts, with arbitrary precoloring and an arbitrary number of colors. We prove a sharp complement-degree threshold: the problem is polynomial-time solvable when $Δ(\overline G)\le1$, but NP-complete on completely uncolored graphs already when $Δ(\overline G)=2$. This yields a dichotomy for uniform complete multipartite graphs, and connected diameter two already suffices for NP-completeness. We also prove W[1]-hardness on cographs parameterized by the number of colors. On the sparse side, completely uncolored paths and cycles admit a linear-time characterization by Euler trails and circuits, while counting feasible colorings is $\#P$-complete on both classes. Counting is nevertheless polynomial-time solvable on stars and complete graphs, even with arbitrary precoloring. A decomposition-transfer theorem yields NP-completeness already at tree-depth two. A separate path-decomposition reduction gives a maximum-degree threshold between one and two for completely uncolored disconnected host graphs with unrestrictedly many colors. Components with at most two edges are tractable, while a disjoint union of $P_4$'s is NP-complete. Finally, precoloring restores tractability in several cases: star forests are polynomial when every center is precolored, and two broad precoloring regimes on length-two spiders are polynomial even when the number of colors is unbounded.

Authors: Zihui Liu, Zhijie Zhang

Submodular maximization under a knapsack constraint (SMK) is a fundamental combinatorial optimization problem with broad applications across machine learning and data mining. Motivated by large-scale applications where query efficiency is paramount, we study non-monotone SMK and focus on deterministic algorithms with linear query complexity. Prior deterministic linear-query algorithms achieve at best a $1/5-\varepsilon$ approximation, falling short of the $1/4-\varepsilon$ ratio attainable by randomized algorithms. We close this gap by presenting a deterministic $(1/4-\varepsilon)$-approximation with $O(n\log^2(1/\varepsilon)/\varepsilon^2)$ queries. Our approach partitions the analysis based on the cost of the largest optimal element $r$: when the cost of $r$ is moderate, we refine the threshold-twin-greedy framework via residual-budget enumeration to tighten the analysis; when the cost of $r$ is large, we reduce the problem to bicriteria submodular maximization. As a secondary contribution, we obtain a $(1/2-\varepsilon, O(1/\varepsilon))$-bicriteria approximation with $O(n\log(1/\varepsilon)/\varepsilon^2)$ queries, improving over the previous $O(n^2/\varepsilon)$ query bound.

Authors: Steven Heilman, Chris Jones, Giulio Malavolta

We show that $1.4

Authors: Maria Constantin, Adrian Miclăuş, Alexandru Popa

Translocations are genome rearrangement operations that exchange prefixes of two chromosomes. We study the non-uniform non-contiguous translocation distance problem, where every string produced during the computation remains available for reuse. Given an initial set of strings $A$ and a target set $B$, the objective is to produce all strings in $B$ using as few translocations as possible. We present the first polynomial-time approximation algorithm for this problem. For a single target string of length $n$, we obtain an $O(\log n)$-approximation, and we extend the result to arbitrary finite target sets with an $O(\log N)$-approximation, where $N$ is the total length of the targets not already present in the initial set. This resolves the approximability question for the non-uniform non-contiguous case left open by Constantin and Popa (TCS 2025).

Authors: Oleksiy Klurman, Igor E. Shparlinski, Joni Teräväinen

Motivated by a question of Regev arising from his improved quantum factoring algorithm, we study how many small primes are needed to generate the group $({\mathbb Z}/q{\mathbb Z})^\times$ when each prime may be used with exponent only $0$ or $1$. We prove that, for every fixed $\varepsilon>0$ and $A>0$, there is an absolute constant $C_*$ and a set of at most $(\log Q)^{1+\varepsilon}$ primes, all at most $(\log Q)^{C_*(A+1)}$, such that for all but $O(Q(\log Q)^{-A})$ (with the implied constant depending only on $\varepsilon$ and $A$) integers $q\leq Q$, every element of $({\mathbb Z}/q{\mathbb Z})^\times$ is a product of a subset of these primes modulo $q$. The exponent $1+\varepsilon$ in the number of primes is best possible up to the arbitrary $\varepsilon$ in the exponent.

Certificate complexity $(C(f ))$ is a fundamental measure of complexity of Boolean functions $f$ which counts the number of bits of an input that need to be known in order for the value of the function to be determined. A certificate can be viewed as a partial assignment, or a boolean subcube where the function is constant. Certificate complexity is well understood for deterministic query (or decision tree) complexity $(D)$ and other query models such as bounded-error randomized and quantum complexity $(R, Q)$, but not as well for quantum zero-error $(Q_0)$ and exact query complexity $(Q_E)$, where there is no agreed-upon certificate “object” (even for $Q$). Instead, we study an operational notion of certification and apply it to various query-based models, with a focus on zero-error and exact quantum query complexity, but also on polynomial degree measures. We give new characterizations of $C, RC$ (randomized certificate complexity) and QC (quantum certificate complexity), in terms of various measures such as classical and quantum sabotage complexity, unambiguous certificate complexity, and variants of polynomial degree. Certification complexity also gives rise to new lower bounds on $Q_E$ and $Q_0$, the quantum analogues of $D$ and $R_0$, complexity measures for which few lower bound techniques are known which are not already lower bounds for two-sided error quantum query complexity. We exhibit a total Boolean function for which our certification complexity measure gives a tight lower bound for $Q_0$, but rational degree and $Q$ are asymptotically smaller.

The slice rank method gives exponential bounds for sets with no three-term arithmetic progression in finite vector spaces of odd characteristic and for three-sunflower-free families of subsets of a fixed ground set. We show that for $k\ge4$, every tensor that is nonzero exactly on the $k$-term arithmetic progression relation or the $k$-sunflower relation has maximal slice rank over every coefficient field. When the support is prescribed only on pairwise distinct inputs, we obtain comparable lower bounds, which likewise rule out exponential savings.

We construct quantum locally testable codes (LTCs) with constant rate, distance, soundness and locality under a variant of a product expansion conjecture of Bafna and Vyas (2026) about Reed-Solomon codes. In particular, we use the high-dimensional expansion framework of Dinur, Lin and Vidick (2024) for constructing quantum LTCs, instantiated with the non-Abelian cubical complexes of Rungtanapirom, Stix, and Vdovina (2019). Our code is obtained by equipping the complex with carefully chosen Reed-Solomon local codes whose symmetries are compatible with those of the complex.

What is mathematics?

Over the years I devoted a few dozen posts to the question “What is mathematics?”.  Some posts in this category bring tears to my eyes like Christine Bjorner’s beautiful post: The Golden Room and the Golden Mountain, and Rodica Simion’s poem Immigrant Complex. In one post, I presented my own views about mathematics; another asks the question “Is mathematics a science?” (My short answer is “yes.”) The famous controversy between Hilbert and Brouwer is discussed in yet another post. This debate resembles, in my mind, the debate between pro-AI and anti-AI mathematicians. This category includes art by Alef; essays by Shmuel Weinberger, Igor Pak, Thomas Vidick, and others; my paper with Nati Linial on ten landmarks in mathematics; Tom Lehrer’s songs; a discussion of the difficulties involved in teaching induction; a couple of connections to sex; “Proof by Lice!”; and the sad fate of The Möbius Undershirt.

Alex Kontorovich gave a plenary lecture at ICM2026 on AI and Mathematics and also played the clarinet in the opening ceremony; Carina Curto presented “Mathematicians personality quiz” about feelings about AI in research mathematics. 

AI and mathematics

The question of what mathematics is has become very timely now with the increasing role of AI in mathematics and the concerns and controversies around it. The increasing role of AI in mathematics is a major event in our lives, perhaps a crisis, perhaps an opportunity, and probably both. Faced with such a major event, the traditional way to deal with the matter is to study it, and the traditional way to study something is to teach it. So, next spring I will be teaching a course at Reichman University about mathematics and AI (here is the course page with the syllabus). My friend Alon Rosen is also teaching a course on AI and cryptography at Tel Aviv University.

Overall, I find myself somewhat on the side of the enthusiasts when it comes to using AI in mathematics. The concerns regarding the future of math and the mathematical community are serious and my optimism regarding the future of  mathematics with AI could be wishful thinking.

I don’t have a clear opinion on what to do, but I don’t recommend any attempt to “slow down” or stop progress in AI-assisted mathematics, and certainly not to cut connections with  academic and commercial organizations that promote it. In my view, as always, tolerance of different views and courses of action is crucial.

I was interested (mainly as an observer) in “experimental mathematics” and have occasionally used computers in my own research. Last April, I launched (with Nisan Hajaj and Ido Kaminer) some “polymath+AI” projects here. One project was successful and led to the solution of the problem we posed. So far, these projects have kept a rather low profile, and I am thinking about ways to boost them. I am also planning to share a few of my own experiences using AI for my mathematical research. (But, of course, some projects will be kept private, and some of my research partners prefer not to use AI at all.)

Let me start with a list of tasks for AI (or expectations of AI) in mathematics. Can we expect AI tools to succeed at all these tasks?

 List of Tasks for AI in Math

a) Explain. Explain the state of the art in a specific area or regarding a particular problem.

b) Discuss. Engage in a meaningful discussion of mathematical ideas and directions.

c) Compute. Carry out computations required for mathematical research.

d) Solve and prove. Settle a mathematical problem and prove the  answer (e.g., prove a conjecture or find a counterexample and prove it).

e) Simplify. Find simpler—sometimes much simpler—proofs of difficult mathematical statements, aiming for proofs that can be explained in classrooms (for humans).

f) Verify. Find ways to verify mathematical statements and proofs in the human style, in formal style, or in other styles.

g) Formalize. Formalize mathematical proofs and offer a formal certificate of correctness.

h) Canonize.  Canonicalize formal mathematical proofs. (Canonization is the process of polishing, streamlining, and integrating a verified proof into the broader mathematical ecosystem.)

i) Refute. Find mistakes in notable published mathematical claims. Even better, find counterexamples to notable published mathematical claims.

j) Problems. Raise new problems and conjectures.

k) Concepts. Introduce new important mathematical concepts.

l) Examples. Create new fundamental mathematical examples (and not just for the sake of solving some existing problems).

m) Theories. Develop new mathematical theories (motto: be a Grothendieck).

n) Heuristics. Develop heuristic and semi-rigorous mathematical methods.

o) Algorithms, numeric, and statistics. Use AI to improve computational methods, numerical methods, algorithmic, and statistical methods.

p) Apply! Find connections and applications to other areas of science and technology.

q) Teach & Educate!

r) Express opinions & prioritize.  Evaluate the relative importance and depth of different areas and questions.

(Feel free to add to the list in the comments.)

Regarding the last item, in light of the AI revolution, we might ask whether we, as human mathematicians, should engage more—and more openly—in discussions and debates about which areas and research directions are most important. Should we now be more exclusive, or perhaps more inclusive?

A wonderful simplification

It is hard for me to evaluate where AI and math stand today. (This should be carefully and critically examined.) However, here is a nice mathematical story about simplification using AI. (This is item e in the list, and I personally care a lot about simplifications; see this post and this one.) The paper Digesting the proof of the sharp thin-shell inequality by Yuansi Chen and Boaz Klartag presents an AI-based proof of a sharp version of the thin-shell conjecture (which implies Bourgain’s slicing conjecture).  As far as I know, the proof of this stronger result is considerably simpler than earlier proofs of weaker results (that I mentioned here, here, and here) and, for example, the new proof does not rely on Ronen Eldan’s stochastic localization.

Here is (from MathOverflow) a list of mathematical proofs that beg for simplification! (And here is a list of “ridiculous” conjectures that beg for counterexamples.)

Problems

At the end of 2024 the free-version ChatGPT prepared for me a list of 21 questions that involve Mobius randomness in number theory and computational complexity. They were pretty good (one problem was a conjecture of mine from 2012 that was later settled by Ben Green). My overall impression is that in the course of working, AI tools come up with interesting and useful problems and conjectures— and occasionally answer them effectively.

My view from 2000

Some brief philosophical thoughts about mathematics appeared as part of my paper “Combinatorics with a geometric flavor: some examples,” in the proceedings of the conference “Vision in Mathematics, towards 2000.” (I presented them in this 2008 post.) I briefly mentioned there computer proofs:

Some believe that computer proofs will take over (Doron Zeilberger is a strong advocate for this view). Appel and Haken’s proof of the four color theorem was a landmark in this respect. Can computers be used not just for “symbol crunching” but also for “idea crunching”? (Perhaps, “idea crunching” will be easier for computers?) The role of computers in exploring mathematical facts is already significant. As for explaining mathematical facts, it raises, for instance, the question: explaining to whom? To humans, or to other computers?

To make matters clear, let me emphasize that in 2000—and for much longer, until just a couple of years ago—I was quite skeptical of the view held by Doron and others that computers would take over mathematics in the foreseeable future. However, I saw no reason to believe that this would not eventually happen. I have been very surprised by the events of the last few years and by the role of Large Language Models (LLMs).

Later on, when I reported on Kevin Buzzard’s 2022 lecture about verification, I was skeptical of Kevin’s view that the full automation of mathematical proofs is “science fiction” (I regarded the verification effort as a relevant stepping stone toward fully computer-generated proofs).

A few more items Carina Curto’s personality quiz for mathematicians

Carina Curto wrote several interesting posts about AI and mathematics, and she is also starting with Joel Fish a related podcast Academia on the Line.

One of Carina’s posts includes her “Mathematicians personality quiz #2,” asking “Which of the following reflects your feelings about AI in research mathematics? Select all that apply.” It follows by list of 18 proposed answers (as you can see I like lists) starting with:

Try it!

Menachem Yaari’s view on the Riemann Hypothesis

Two decades ago the renowned Israeli economist Menachem Yaari wrote in an official committee report about the future of academia in Israel in the context of the importance of basic science, that he would support society investing a billion dollars in proving the Riemann hypothesis. Of course, I endorse promoting curiosity-driven science but I remember that I commented that in mathematics there is no way to proceed toward an RH solution (or other notable problems) with a huge monetary investment. This situation may have changed. (I would still be hesitant about spending a billion dollars on the RH.)

Other views and resources

There is a nice new blog “Proofs and Prompts”  devoted to the topic with many nice posts. I have also encountered many interesting views from Terry Tao’s blog and from Carina Curto’s FB thread. Here are some essays by Galina Livshyts, Emily Riehl, Bryna Kra, Alex Gamburd, Silvia De Toffoli and Eamon Duede, Anima Anandkumar, Lisa Valentini, Matilde Marcoli, and Eyal Sulganic.

A Different View – The Silicon Reckoner

On his blog Silicon Reckoner—which he started five years ago—Michael Harris expresses a rather negative view of AI in mathematics. Here is what AI says about Michael and his site:

“Silicon Reckoner is an opinionated, biweekly newsletter created and written by Michael Harris, a prominent number theorist and mathematics professor at Columbia University. The publication focuses deeply on the implications of the mechanization of mathematics, critically analyzing how artificial intelligence, automation, and corporate tech solutionism impact mathematical research, academic institutions, and human intellect. The title itself plays on Archimedes’ famous ancient work, The Sand Reckoner, subbing in “silicon” to ground it in the modern computer era.”

Be a Grothendieck!

The concern that new ways of doing mathematics will block the chance for Grothendieck-level contributions was raised by Peter Sarnak in a 2012 discussion about Polymath projects, and it is highly relevant to AI in mathematics.

While editing my current post, the AI tool I used complimented me: “A few phrases—such as ‘be a Grothendieck,’ ‘Proof by Lice!,’ and ‘connections to sex’—are playful rather than erroneous and fit the personal style of the blog.” I used the opportunity to challenge it with the following prompt:

Prompt: Now, regarding the instruction “be a Grothendieck,” here is a task for you for the eve of Yom Kippur. Spend the next 26 hours reflecting on the contributions of Grothendieck and develop a mathematical theory required for the development of some major area of mathematics. Spend a lot of time thinking about what mathematics needs, reflect on great theories that were successful, and build carefully and firmly your own theory (or theories). I will check back on you in 26 hours. Good luck!

The AI’s report included some thoughts and modest claims about “local-to-global” mathematics, and even a short section on numerical analysis.

An elevator conversation during  ICM2026

• A person in the elevator: What is this conference? What are you guys doing?
• Me: We are mathematicians! It is a large mathematics conference.
• The person: Oh, so you must be smart guys. This is very nice!
• Me: And what brings you here?
• The person: I am a pilot.
• Me (trying to be nice): So you must be very smart too!
• The pilot (laughing): Not really.
• Me (trying again to be nice): But you are surely very, very responsible. We make a lot of mistakes, but you cannot afford to make any!

Time (and perhaps very little of it) will tell what will happen to our profession and community with our new “autopilots.”

Living for the ages?

Let me conclude with a more general thought. Even before AI, identifying human relevance with “living for the ages” may have been illusory, in a world where “struggling to live” better reflects the human experience than “leaving a lasting impact.” AI’s remarkable progress may simply reinforce the view that human relevance should not be identified with, or measured by, intellectual achievements, or indeed by lasting achievements of any kind.

AI tools that I use and some early posts.

I used the free version of chatGPT (and earlier GPT3) for various purposes (including a research project in psychology); about a year ago I moved to the $20 version and two months ago I moved to the $100 version. (I was too slow to register to the scientists program.) I also use an intermediate version of Gemini supplied by HUJI, and I applied for the scientists program of Anthropic.

My first AI and mathematics post (2021) was about some works of DeepMind on Kazhdan-Lusztig polynomials. Earlier in 2008 Amir Ban wrote a guest post about computer chess.

Last minute updates: There is a newly formed Advisory Group on Mathematics and Artificial Intelligence that just now is facing the very specific challenge of advising OpenAI on how to coordinate the release of a large number of significant results in mathematics that they report have been produced by their internal model.

There are also other wonderful AI simplifications that I will write about separately.

By Gil Kalai

The Remote Point Problem (RPP) is an algorithmic problem that asks, given a linear subspace $L \subseteq \mathbb{F}^n$ of dimension $k$, to deterministically find a vector $v \in \mathbb{F}^n$ far in Hamming distance from $L$. This problem was introduced by Alon, Panigrahy and Yekhanin [APY09], motivated in part by the matrix rigidity approach for proving circuit lower bounds. An algorithm is said to achieve remoteness $d$ if it finds a vector $v$ whose Hamming distance from $L$ is at least $d$. We observe that over the rational numbers, the problem admits a deterministic polynomial-time algorithm that achieves optimal remoteness $n-k$. Over finite fields, we obtain a (modest) improvement of a result of Alon, Panigrahy and Yekhanin [APY09], and give an algorithm that achieves remoteness $\Omega\left(\frac{n}{\max\{k, \log n\}} \log n\right)$.

Authors: Xin Li, Hanlin Ren, Yan Zhong

For a propositional proof system $\mathcal{P}$ and a polynomial-time function $G: \{0, 1\}^n \to \{0, 1\}^N$ ($N > 10n$), we say that $G$ is a *proof complexity generator* against $\mathcal{P}$ if $\mathcal{P}$ cannot efficiently prove the (suitably encoded) statement "$y\not\in\mathrm{Range}(G)$" for every $y \in \{0, 1\}^N$, and $G$ is a *demi-bits generator* against $\mathcal{P}$ if $\mathcal{P}$ cannot efficiently prove the statement "$y \not\in\mathrm{Range}(G)$" for a noticeable fraction of $y \in \{0, 1\}^N$. As can be seen from the definitions, proof complexity generators are qualitatively stronger objects than demi-bits generators. Our main result is that, perhaps counter-intuitively, every demi-bits generator "contains" exponentially many proof complexity generators. In fact, a random subset of output bits of a demi-bits generator forms a proof complexity generator with constant probability. This result is an extremely simple corollary of Pajor's Lemma (a strengthening of the well-known Sauer--Shelah Lemma). This result allows us to exhibit the hardness of the Range Avoidance problem ($\text{Avoid}$) in several new, restricted settings of interest. Along the way, we introduce the notion of *zero-error disperser families* that can transform demi-bits generators into proof complexity generators, and show that this family can be computed by projections (i.e., without any circuit complexity overhead). Using a different instantiation of this family, we construct proof complexity generators from *barely non-trivial* demi-bits generators $G: \{0, 1\}^n \to \{0, 1\}^N$, where the number of hard-to-prove statements of the form "$y \not \in \mathrm{Range}(G)$" just slightly exceeds $2^n$ (which is the number of *false* statements of this form).

Authors: Kamil Braun

Resolution over parities, $\mathrm{Res}(\oplus)$, is the characteristic-two version of resolution over linear equations: clauses are disjunctions of affine equations over $\mathbb F_2$. Superpolynomial size lower bounds were previously known only for restricted refutations: tree-like, regular, or of bounded depth. We prove that every DAG-like $\mathrm{Res} (\oplus)$ refutation of the bit pigeonhole principle with $n+1$ pigeons and $n=2^\ell$ holes has more than $\exp(n/(32768\ell^2))=2^{Ω(n/\log^2 n)}$ clauses, for every $\ell\ge32$, with no restriction on regularity or depth. The proof translates an arbitrary refutation with $S$ clauses into a polynomial calculus refutation of degree $O(\log n)$ over $O(S+n^2)$ groups of extension variables in the style of Buss, Impagliazzo, Krajicek, Pudlak, Razborov, and Sgall. One substitution then removes all extension variables at once and leaves a nonzero low-degree polynomial derived from the pigeonhole axioms alone at degree at most $n/2$; a degree lower bound in the style of Razborov, proved through the homology of chessboard complexes, shows that no such derivation exists. The argument also yields a general sufficient condition for $\mathrm{Res}(\oplus)$ size lower bounds. The main theorem, this condition, and all their dependencies are formalized in Lean 4, and every statement links to its formal proof. The proof was developed with substantial AI assistance within an open research framework described in the final section.

Authors: Alexander Golovnev, Mohit Gurumukhani

We introduce and study a new model of decision trees that lies at the frontier of provable circuit lower bounds. We study $\ell$-local decision trees, in which each internal node queries an $\ell$-local function of the input. We show that sufficiently strong lower bounds for $\ell$-local decision trees would imply several breakthrough circuit lower bounds, including super-linear size lower bounds for log-depth circuits and improved bounds for unrestricted-depth circuits. Previously, such consequences were known to follow from strong lower bounds for depth-$3$ circuits, which has been the main prior approach in attempting to prove these results. Since local decision trees are strictly weaker than depth-$3$ circuits, this provides a formally easier route to the same circuit lower-bound consequences. We prove essentially optimal lower bounds for a weaker variant that we call oblivious $\ell$-local decision trees, where all nodes at the same depth query the same function. Our lower bounds follow from a new technique that uncovers sumset structure in local maps, and our hard functions are sumset dispersers, sumset condensers, and directional affine dispersers. Along the way, we give an explicit construction of a sumset condenser with small entropy loss. As an additional contribution, we initiate the study of degree-$2$ decision trees, in which each query is a quadratic polynomial of the input. We show that proving lower bounds in this model is a natural stepping stone toward constructing dispersers for degree-$2$ variety sources, which imply improved circuit lower bounds for unrestricted depth circuits. We prove nearly maximal lower bounds for the oblivious variant of the model.

Authors: Rafail Ostrovsky

We prove that the quantum code distance is NP-hard to approximate within an additive error of $c N$, for some constant $c >0$, where $N$ is the number of qubits. Our reductions are deterministic. This improves the previous square-root additive gap to $Ω(N)$ and resolves the explicitly stated linear-gap question of Kapshikar and Kundu. Our result holds for CSS codes with identical $X$- and $Z$-check spaces, and with a constant rate and constant relative distance. For every fixed $λ>1$, there is a constant $c>0$ such that hardness still holds even when every nonidentity stabilizer has weight greater than $λ$ times the quantum distance. We also improve the hardness gap of graph state distance on $N$ vertices of Grigorescu, Jha, and Samperton from cube-root to $Ω(N)$, resolving their explicitly stated open question. Both hardness results are asymptotically optimal since both distances are at most $N$. Our graph state distance hardness result holds for balanced bipartite graphs with a binary adjacency matrix that is its own inverse (mod 2). Our main technique for both hardness bounds above is classical: we show how to convert any code $C$ of length $m$ into a self-dual code $A(C)$ of length $N=Θ(m)$ while exactly doubling the original coset metric. The conversion is deterministic and efficient. We call it the metric self-dual completion of $C$. It comes with a linear embedding $τ: \mathbb F_2^m \hookrightarrow \mathbb F_2^N$. The embedding doubles all Hamming distances between vectors in $\mathbb F_2^m$ and all pairwise distances between corresponding cosets. The embedding also guarantees that all codewords of $A(C)$ of weight at most $2m$ are exactly $τ(C)$.

Authors: Idian C. Capozzoli, Yan S. Couto, Enrique Junchaya

We study the complexity of determining the interval numbers of tournaments in the $\overrightarrow{P_3}$ and $\overrightarrow{P_3^*}$ convexities, denoted by $\overrightarrow{\mathrm{in}}_{P_3}(T)$ and $\overrightarrow{\mathrm{in}}_{P_3^*}(T)$ on a tournament $T$. For each $\overrightarrow{\mathcal{X}} \in \{\overrightarrow{P_3}, \overrightarrow{P_3^*}\}$, we show that determining whether $\overrightarrow{\mathrm{in}}_{\mathcal{X}}(T) \leq k$ is W[2]-complete when parameterized by $k$. Moreover, under ETH, we show that there is no parameterized algorithm for that problem with running time $f(k)\, n^{o(k)}$ on an $n$-vertex tournament, where $f$ is any computable function. For the $\overrightarrow{P_3}$-convexity, we also show that $\overrightarrow{\mathrm{in}}_{P_3}(T) = \mathcal{O}(\log n)$, which yields a simple quasi-polynomial $n^{\mathcal{O}(\log n)}$ brute-force algorithm. On the other hand, under ETH, we show that the problem is NP-intermediate, that is, it is neither NP-hard nor in P. For the $\overrightarrow{P_3^*}$-convexity, the same brute force algorithm is not quasi-polynomial, since we present a family of instances with $\overrightarrow{\mathrm{in}}_{P_3^*}(T) = Θ(n)$. We conjecture that this problem is NP-complete.

Authors: Andrei Popa, Alexandru Popa

A mobile is a rooted full binary tree whose leaves carry positive integer weights. The imbalance of an internal node is the absolute difference between the total weights of its two child subtrees, and the cost of the mobile is the sum of these imbalances. In the unrestricted \emph{Balanced Mobiles} problem, only the multiset of leaf weights is given: both the tree topology and the placement of the weights must be chosen so as to minimize the cost. The computational complexity of this unrestricted variant has remained open, although the variant with a prescribed topology is strongly NP-hard. We close this gap by proving that the decision version of unrestricted Balanced Mobiles is strongly NP-complete. Our reduction from Numerical 3-Dimensional Matching with Distinct Integers uses three widely separated numerical scales. Tight telescoping bounds force every threshold-achieving mobile into a canonical hierarchy, after which pairwise distinctness of the source integers collapses the hierarchy to single triples from which a valid numerical matching can be recovered.

Authors: Hans Raj Tiwary, Michel Grabisch

We study the computational complexity of fundamental algorithmic problems -- membership testing, separation, valid-inequality testing, and linear optimization -- over polytopes and cones arising from cooperative games (also known as pseudo-Boolean functions). A central obstacle in the study of such problems is that a general cooperative game on $n$ players requires $2^n$ values, so the input size is $2^n$ for a game with $n$ players, making these computational tasks theoretically trivial. Restricting to $k$-additive games reduces the input size to $O(n^k)$, making such games a natural target for meaningful questions about the existence of efficient algorithms. On the positive side, we give an explicit extended formulation of size $O(n^k)$ for the core of $k$-additive $k$-monotone games, allowing all four problems to be solved by a single polynomial-size linear program -- in particular, circumventing the ellipsoid method that is needed when building from earlier tractability results of Deng and Papadimitriou, or of Edmonds. For the cone of $k$-additive $(k{-}1)$-monotone games, we give a complete characterization of its extreme rays and derive the same $O(n^k)$ bound on extension complexity, yielding a geometry-based proof and generalization of a result of Billionnet and Minoux. On the negative side, we show that for $l \leq k-2$ the cone of $k$-additive $l$-monotone games is computationally intractable: membership testing is not in NP (unless NP\,=\,coNP), valid-inequality testing is NP-complete, and extension complexity is at least $1.5^n$. Our hardness results yield, as a special case, a result of Crama and of Gallo and Simone. Furthermore, our hardness results also explain the lack of any good characterization of the extreme rays of the cone of $k$-additive $(k{-}2)$-monotone games.

Authors: M. Utkan Gezer

We study complete-information debate systems in which a probabilistic finite-state verifier reads the alternating messages of a prover and a refuter. Demirci, Say, and Yakaryılmaz showed that every language in $\mathsf{P}$ has such debates checkable with a constant number of random bits and arbitrarily small weak error. Their strong-error construction, which also counts nontermination as failure, did not permit arbitrary error reduction. We close this gap: for every $L\in\mathsf{P}$ and every $\varepsilon>0$, there is a constant-space verifier using a constant number of private coin tosses that has perfect completeness and strong error at most $\varepsilon$. The verifier simulates a polynomial-time alternating multihead finite automaton, privately spot-checking one of its input heads. The key observation is that, on a nonmember, the refuter may concede any round in which the prover first misreports a head reading. This ensures termination against every prover when the refuter follows the specified strategy, and permits strong-error reduction by repetition.

Authors: Saint Wesonga

We formalize Hastad's PARITY lower bound in Lean using the switching lemma. For every fixed d >= 2, formulas and DAG circuits of computation depth at most d computing PARITY on n inputs require size exp(Omega_d(n^(1/(d-1)))) for all sufficiently large n. This matches the classical upper bound up to constants in the exponent and implies that PARITY is not in nonuniform AC0. We also construct a polynomial-size, logarithmic-depth bounded-fan-in formula family for PARITY, providing a witness to NC1 is not a subset of AC0 for the formalized models. The Lean source code is available at https://github.com/formalcs/circuit-complexity and is checked with Lean 4.33.1 and mathlib 4.33.1.

Authors: Chaithanya Rayudu, Takahiro Misawa, Andrew Zhao, Jun Takahashi

Lee-Yang theorems are a powerful tool for studying many-body systems, with applications ranging from analyzing phase transitions to proving the efficiency of certain classical and quantum algorithms. In this work, we prove a Lee-Yang zero-freeness theorem for the partition function of a broad class of interacting fermion models, implying the existence of a provably efficient quantum algorithm for estimating their ground-state energies. This class includes several well-known models such as the attractive Hubbard model, repulsive Hubbard model on bipartite graphs, and the interacting Hofstadter model. Our results also rigorously establish the nonexistence of phase transitions in these models in the presence of a nonzero local external field.