Theory of Computing Report

Spreading the Gospel of Theoretical Computer Science to an Ω(1) Fraction of Humanity (Or, How We Can Do Like the Physicists)
Scott Aaronson’s Trevisan Award Acceptance Speech
Salt Lake City, Utah, June 23, 2026

Thank you so much! It’s one of the highlights of my life, frankly, to accept the first-ever Luca Trevisan Award for Expository Work in Theoretical Computer Science—because of, firstly, what this entire STOC community means to me, but also what Luca Trevisan in particular meant to me. Luca was one of the main people who taught me complexity theory—first at an IAS summer school in 2000, then at UC Berkeley, where I took two of his courses and TA’ed for him. As a member of my dissertation committee, Luca once stood on a street corner in San Francisco to meet my friend to sign the signature page of my thesis, as I struggled to get the thing in by the deadline. Later, Luca’s theoretical computer science blog, In Theory, bounced off of my blog.

I wish Luca were here now. But knowing him as well as I did for a quarter century, I feel like I know what he’d say if he learned that I had received the inaugural prize that bears his name. I imagine he’d slap his forehead and say “Seriously, there was no other option??” But I’d like to think that he’d eventually reconcile himself to the choice!

By the way, I noticed that in the committee’s prize announcement, which I found so moving, they added a special paragraph at the end that basically said, “please don’t imagine that to win this prize in the future, you need to behave the way Aaronson behaves. You can just write beautiful textbooks or survey articles or whatnot, and be normal and sane.”

The foundation of my career is that I realized 25 years ago that there were better theoretical computer scientists than me—like many in this room, or like Ryan Williams or Andris Ambainis, both of whom I knew at the time. Certainly there were better quantum physicists than me. There were better writers, better expositors, better performers. On the other hand, if you looked specifically at the intersection of computational complexity and quantum physics and standup comedy, that was just this totally uncontested territory!

I’ll let you in on a secret: pretty much everything I’ve done for decades has just been drawing out one joke. That joke is, basically, “computer scientists they be like this, but physicists they be like that.” The physicists they be like [exaggerated doofus voice] “duhhhh, NP, what’s that stand for? Not Polynomial?” See, but then there’s also a Rodney Dangerfield aspect to it, because it’s like, how come we never get as much respect as the physicists get? (Though when we do get that respect, I confess that I complain all the more, because then I lose my shtick…)

It’s true that the physicists have certain built-in advantages. They had Einstein, Stephen Hawking, the atom bomb—and just the fact that they’re ultimately talking about, or trying to talk about, the world that we can see and touch. A black hole is an actual place that you could visit, even though I wouldn’t recommend it. But physicists also have much better names for things than we do. I mean, black hole? Big Bang? Quark? Gluon? Supersymmetry? Dark matter?

Meanwhile, what names have we got? TFNP. NC¹. And worst of all, PP. These are names that you want to flush down the toilet. But also, the concept of a zero-knowledge protocol, or a two-source extractor, just inherently take longer to explain to people than the concept of a particle, or even a field—even though the latter also turn out to be extremely abstract and mathematical when you push on them. Ask a physicist what a particle is, they’ll tell you that it’s an irreducible representation of the Poincaré group. See, but people think they know what a particle is, it’s just a tiny little hard sphere that moves around, and that’s good enough for them.

So then, how can we win the grand popularity contest against the physicists? How can we, as I put it in my title, spread the gospel of CS theory to a constant fraction of the human race? In my view, the first step is to reframe who we are and what we’re about. We’re not this obscure little community off to the side, proving its little theorems about derandomization and catalytic space. No! What we are is the conceptual and mathematical core of computer science, the field that’s changing the face of civilization in obvious and undeniable ways.

This was even true a long time ago. The physicists had Galileo and Einstein? Well, we had Turing, a figure so heroic and so tragic that no one would’ve believed him as a fictional character. And while we’re at it, we’ll claim Gödel and Shannon and von Neumann, Leibniz and Babbage and Ada Lovelace—they’re all ours too.

That’s our proud history. But then when we turn to today, it’s like, holy crap! Even the densest ignoramus can now see how deep intellectual ideas originating in CS are changing the world.

Blockchains—some people might wish they’d never been invented, but they were invented, so we all need to think about how they change the world’s economy for better and worse. And of course, they’re fundamentally based on hardness assumptions; they couldn’t exist in a world where NP was easy.

Part of my outreach job these days is to explain to finance people, over and over, why a quantum computer could break the elliptic curve signature schemes used by Bitcoin and many other coins, but would have only a more modest effect on the proof-of-work part, the hash function. And it’s like, if you actually want to know, then we need to talk about BQP versus NP, Grover’s algorithm and its optimality, black-box problems with and without abelian group structure—and now we’re deep into TCS!

Speaking of quantum computing—even if we set aside the question of whether quantum computing is going to revolutionize materials science or chemistry or pharmaceuticals design—or whether it will revolutionize AI and machine learning and optimization [I shake my head, make a thumb-down, and blow a raspberry]—even if we set aside those practical questions, quantum computing plausibly represents the most dramatic test of quantum mechanics itself that we’re ever going to see. And it now looks clear that we will see that test within the next decade or sooner. One way or the other, we’re going to learn the truth.

People sometimes ask me, why did it take until the 1980s for anyone to propose the idea of quantum computing? You know, Heisenberg and Schrödinger were in the 1920s, Turing was in the 1930s, so it seems like all the ingredients were in place a half-century earlier! In my Quantum Computing Since Democritus book, I reflected on this, and I think the deepest answer is that not quite all of the intellectual ingredients were in place. Quantum computing is something that it doesn’t make a great deal of sense even to ask about until you’ve established polynomial versus exponential, and even P and NP and NP-hard, as central concepts. And that’s what didn’t happen until the 1970s.

But of course, the biggest thing that our CS concepts have unleashed on humanity—the thing that the entire world now realizes holds even greater promise and greater peril than nuclear energy did in the last century—is [pause for effect] the Razborov-Smolensky lower bound method.

No, I’m kidding of course. It’s generative AI.

Twenty years ago, I remember people in our community—was it Fortnow? Impagliazzo? I’m not sure—saying, “you know the real reason why P vs. NP is such an important problem? Suppose P=NP, via an algorithm that was fast in practice. Then it’s not just that you could break all the encryption systems, or have your computer find a proof of the Riemann Hypothesis, or whatever. No, it’s that you could program your computer to find the shortest efficient compression of, for example, the full text of Wikipedia. For in order to create that compression, it seems plausible that your computer would need to create an AGI as a byproduct.”

I remember thinking to myself: “that’s an amusing thought experiment, I’ll need to steal it sometime, but still, what an utterly simplistic vision of the nature of intelligence! There has to be more to intelligence than sheer data compression!”

Fast forward to spring 2022, when I accepted an invitation to go on leave for a couple of years, to join what was then a relatively obscure little nonprofit foundation by the name of … err … OpenAI. When I flew to San Francisco to start my assignment, I had lunch with Ilya Sutskever, the cofounder of OpenAI and then its chief scientist. And Ilya said to me, “Scott, let me explain to you how we think about things here at OpenAI. For us, intelligence is fundamentally about prediction, and prediction is fundamentally about compressing your training data. As you know, Kolmogorov complexity is uncomputable, but one can get better and better computable upper bounds on it. We conjectured that, in order to get sufficiently good at predicting and compressing all the text on the Internet, you’d need to build a model of the entire world that had led to that text being written. And we made a gamble that large neural nets would do that well enough, despite the problem’s worst-case intractability.”

That conversation was when it hit me that, if only we in CS theory had taken our own concepts and thought experiments more seriously, one of us could’ve started OpenAI 15 or 20 years ago. So OK, we didn’t, and that’s why I flew coach to get here. But this is the kind of story that it seems to me we could be singing from the rooftops.

(Incidentally, the reason why OpenAI wanted me back in 2022, was to use theoretical computer science to figure out how to make AI safe for humanity. Alas, that problem is still open! But I’m thrilled that there are so many sessions about exactly this question at STOC this year, and I hope many of you will choose to get involved.)

In the rest of this talk, I’d like to offer some advice—such as I have—for any of you who’d like to try your hand at speaking or writing or blogging or podcasting about theoretical computer science for a broad audience. You see how my hair is starting to gray? Yeah, that’s what authorizes me to go into advice mode.

Let’s start with the obvious: meeting the audience where they are. This is something that I learned years ago from Steven Rudich, who along with Luca, was another irreplaceable figure who our community recently lost, and lost too soon. I remember 26 years ago, at that same IAS summer school where I learned from Luca, Rudich gave the students a talk about how to give talks. In it, he showed a cartoon of someone lecturing. And there were little thought bubbles that said:

What the speaker thinks the audience is thinking: MORE! HARDER! FASTER! Ah yes, QED, truth is beauty and beauty is truth!

What the audience is actually thinking: What the hell are they talking about? When is this over? Can I get a date with the person sitting next to me?

You know, this misconception that because something has become obvious to you, after thinking about it for years, therefore it should be equally obvious to your readers or listeners encountering it for the first time? This is what Steven Pinker dubbed “the Curse of Knowledge,” and calls the most fundamental problem of all exposition. (I could mention the related misconception that because something has become interesting to you, therefore it’s interesting to your audience. But you can make just about anything that’s interesting to you interesting to your audience, by telling a suitable story about it.)

What can you do about the Curse of Knowledge? Practice giving a buttload of talks to undergrads, high school clubs, even physicists, and listen to the feedback you get. If the same weird confusion shows up at least twice, it’s a safe bet that it’s going to keep showing up—which means, now you can anticipate and preempt it the next time you explain the same concept.

But it’s not just misconceptions that you should listen for. Listen for which of your metaphors and anecdotes actually land. Certainly listen for which of your jokes get a laugh. Use those more the next time. And if saying, for example, “hur hur, I’m in a quantum superposition of two different topics that I could talk about next”—if that fails to get a laugh, then DROP IT.

Eventually, you’ll build up what Carl Sagan once called “consumer-tested stepping stones”: that is, a library of jokes, anecdotes, and metaphors that can get you from wherever you see the audience is to wherever you need them to be. Here’s an intentionally tiny example of one of my stepping stones: “Why is P contained in NP? Because the verifier just says to the prover, dude, take a hike, you’re not needed here.” Or another stepping stone, for when we reach the question of the likelihood of P=NP: “look, if we were physicists, we would’ve declared P≠NP to be a law of nature. We would’ve given ourselves Nobel Prizes for the discovery of that law. And if it later turned out that P=NP? We’d just give ourselves more Nobel Prizes for the law’s overthrow!”

This brings me to a broader point. CS theory is unusually rich with facts that are true for silly or absurd or ironic reasons. Lean into that! Don’t hide it!

I mean, “if NP has small circuits then this theorem is true, but if NP doesn’t have small circuits, the theorem is again true, but now for a totally different reason”? That’s sidesplittingly hilarious! OK, maybe only to some of us.

Or why does IP=PSPACE? An alien lands and is like, “I COME TO EARTH TO TELL YOU THAT WHITE HAS THE WIN IN YOUR GAME CALLED CHESS.” And we’re like, “why should we believe that?” So the alien is like, “LET US PLAY A GAME. I’LL PLAY WHITE AND WILL WIN.” And we’re like, “oh, we assume you’re smarter than us! You came all the way here in a spaceship and all! But that still doesn’t prove it.” So the alien is like, “THEN LET US PLAY A DIFFERENT GAME, MATHEMATICALLY EQUIVALENT TO CHESS, INVOLVING SUMS OF POLYNOMIALS OVER A FINITE FIELD. IN THIS TRANSFORMED GAME, THE BEST YOU CAN DO IS TO MOVE RANDOMLY. SO IF I STILL WIN, YOU’RE STATISTICALLY CERTAIN I WOULD’VE WON REGARDLESS OF HOW YOU PLAYED.” It’s like, dude. Dude!

Of course, our founding irony, our founding absurdity, was self-reference and diagonalization. Like, “you can’t predict what any human brain will do 5 seconds from now, because if you could, you could predict what you yourself were going to do 5 seconds from now, and then do the opposite of that!” BOOM! Therefore the halting problem is undecidable and the Time Hierarchy Theorem is true, QED. But beyond that: “black-box program obfuscation is impossible, because one thing you can always do, if given the actual code of a program, is to run the program on its own code and see what happens.” Dude! Or: the reason why it’s so hard to prove P≠NP, is that it’s presumably true that P≠NP. That’s a wisecrack that, in the context of the Natural Proofs barrier, becomes so much more than a wisecrack.

One special case of leaning into absurdity concerns the central role in our field played by asymptotics. I’m always slightly at a loss when someone asks me, “so, how many times faster would a quantum computer be than a classical computer? A million times faster? A billion?”

Part of me wants to reply: “I must educate you about polynomial versus exponential scaling until you see the profound error of your question, and retract it.” But another part of me simply wants to say: “depending on the problem, a quantum computer could be anywhere from not faster at all to, let’s say, 10¹⁰⁰⁰⁰ times faster.”

The truth is, I think we need to do both. Anytime you’re talking about asymptotics to laypeople, if you can plug in some representative numbers, it will help them understand what you’re talking about. And then, if the asymptotics are what really control the real-world numbers, so much the better! If, on the other hand, the asymptotics are comically disconnected from the real-world numbers—if, for example, you’re trying to improve something from log*(n) to Ackermann^-1(n) or whatever—well then, you can lean into that as an additional source of humor.

Alright, one last piece of advice. Tell true stories about how you came to understand or discover whatever it is that you’re talking about. Don’t be like the mathematicians who love to cover their tracks.

When people ask me how I proved the lower bound on the number of steps needed for a quantum computer to find collisions in a list—a centerpiece of my PhD thesis, and one of the two or three hardest technical things I’ve done in my career—I say, look, I was 20 years old and I had no social life. So I just pulled many all-nighters trying every possible approach. Eventually, I came across some complicated expression that had no right to be a polynomial. But somehow, every term in the denominator cancelled against a corresponding term in the numerator, and it was a polynomial! And that let me use the polynomial method to prove a lower bound. Why was it a polynomial? I still don’t really understand, a quarter-century later! My point is, people want the truth.

The secret of blogging is that, even if people despise what you’re saying, even if they think it’s wrong, offensive, problematic, cringe, you name it, they need to trust that you’re telling them the truth of what you know or believe or remember about the subject at hand, the same as you’d tell your closest friend.

In summary: we, the CS theory community, are sitting on top of one of the greatest conceptual and intellectual goldmines of our whole civilization. I exhort everyone here: please help tell the world about it! As you do so, think about how to honor Luca’s memory and make him proud. But also think about how to make me, and my silly little blog, superfluous and obsolete.

Thank you for this honor, thank you for the incredible privilege of being part of the CS theory community, and thank you for listening.

By Scott

Authors: Noah Fleming, Stefan Grosser, Toniann Pitassi, Robert Robere

We introduce a new family of propositional proof systems, denoted , for an arbitrary TFNP search problem $R$. Informally, a refutation of a CNF formula $F$ in is given by a polynomial-time reduction from the false-clause search problem $Search_F$ to $R$, combined with an Extended Frege proof that the reduction is correct. These are motivated in two ways: 1. They are the propositional translations of witnessing theorems in bounded arithmetic, by which proofs of $\forall Σ^b_1$ formulas $φ$ in a theory $T$ imply algorithms solving the search problem for $φ$ in a TFNP class corresponding to $T$. 2. They are a white-box analogue of the characterizations of proof systems using decision tree reductions to black-box TFNP problems. We consider the proof system , where Iter is a complete problem for PLS. We prove that is polynomially equivalent to the sequent calculus $G_1$, and also to the implicit Resolution proof system [EF, Resolution]. Hence $G_1$ and [EF, Resolution] are equivalent, which is the first characterization of an implicit proof system by a classical proof system beyond the work of Wang. We also consider for general TFNP relations $R$. We observe that if EF can prove that a search problem $R$ is in FP, then is polynomially equivalent to EF. This contrasts to our above result, which shows that Extended-Frege provable reductions to $Iter$, a problem widely believed not to be in FP, yields a proof system ($G_1$) that is believed to be stronger than Extended Frege. Finally, we show that for any proof system $P$ which is sufficiently strong, there is a polynomial-time computable search problem $R_P \in $ FP such that is polynomially equivalent to $P$. Letting $P =$ [EF, Resolution] and combining our two results shows that is polynomially equivalent to .

Authors: Therese Biedl

In a recent paper, Antić et al.~studied collections of planar orthogonal drawings of a graph where every edge is unbent in at least one drawing. This paper generalizes this concept to non-planar drawings, and shows that then two drawings always suffice (for planar drawings three drawings are sometimes needed). The results can also be generalized to $s$-grid drawings for $s\geq 3$.

Authors: Neha Pant, Ryan Williams

For several well-studied triangle detection problems in the literature, the trivial enumeration algorithms are known to be optimal (up to the exponent) assuming popular fine-grained conjectures. For example, All-Edges Sparse Triangle and Sparse Monochromatic Triangle where each node has degree $n^δ$ for some $δ< 1$, and the Exact Triangle where edges have arbitrary weights, all have this property under the 3SUM Conjecture. However, as there are slightly nontrivial algorithms for 3SUM, it is natural to wonder if the trivial algorithm for these tricky triangle tasks might also be improved. Applying a variety of techniques from randomized algorithms, circuit complexity, and communication complexity, we present the first improvements over the trivial algorithms for each of these problems in the Word RAM model. Moreover, our algorithms can be implemented with only polysize $AC0$ operations on words. Extending our techniques, we also show how to solve the notorious 4-cycle detection problem on $n$-node graphs in $o(n^2)$ time, in a Word-RAM model with word size $w > ω(\log^2 n)$. Along the way, we show how to sort $n$ items over a universe of size $2^u$ using only $AC0$ word operations in $O(n u \log n)/w$ time.

Authors: Kijung Jeon, Thuy-Duong Vuong, Molei Tao

Inference-time scaling is a promising paradigm to improve generative models, especially when outputs must satisfy structural constraints or optimize downstream rewards. We consider Masked Diffusion Model (MDM) and introduce MDM-VGB, a discrete diffusion sampler that augments unmasking generation with theoretically principled reward-guided remasking. Inspired by the recent success of the classical Jerrum-Sinclair backtracking Markov chain in reward-tilted generation, MDM-VGB extends the backtracking random walk from a fixed prefix tree to a masked-state graph, allowing tokens to be unmasked and remasked at arbitrary positions. The resulting sampler favors unmasking and remasking moves that lead to higher-value partial configurations, enabling both effective high-reward generation and efficient repair of low-reward samples. We prove that MDM-VGB is robust to process-verifier noise and achieves quadratic complexity, while popular test-time heuristics such as best-of-$N$ can incur exponential complexity due to error accumulation. Our theoretical findings are corroborated by strong empirical performance, particularly on popular constraint-satisfaction and scientific benchmarks such as Sudoku and QM9.

Authors: Pan Peng, Yuyang Wang, Joy Qiping Yang, Yichun Yang

We study lower bounds for estimating the spectral density of the normalized adjacency matrix of a graph. Previously, Cohen-Steiner et al. [KDD 2018] proposed an algorithm for $\varepsilon$-approximate spectral density estimation in the Wasserstein-1 distance, using $2^{O(1/\varepsilon)}$ random walks initiated from uniformly random nodes in the graph. Later, Jin et al. [COLT 2023] established a nearly matching exponential lower bound for \emph{weighted} graphs, assuming the algorithm has access to samples from random walks started at random nodes. It was left open whether this lower bound could be extended to \emph{unweighted} graphs. In this paper, we answer this question in the affirmative by proving an exponential lower bound for unweighted graphs. Specifically, we show that no algorithm can compute an $\varepsilon$-approximation to the spectrum of a normalized graph adjacency matrix with constant success probability, even when given the full transcripts of $2^{Ω(1/\varepsilon^{1/6})}$ random walks, each of length $2^{Ω(1/\varepsilon^{1/6})}$, started from uniformly random nodes.

Authors: Mohsen Ghaffari, Magnús M. Halldórsson, Yannic Maus, Alexandre Nolin

Graph shattering is a central technique underlying sublogarithmic-time distributed algorithms in the LOCAL model. Its analysis typically relies on bounding the probability that large sets of distant nodes remain unresolved, often via independence assumptions justified by locality. We show that these assumptions fail for pre-shattering procedures that run for super-constant rounds, where dependencies accumulate over time. As a result, several standard shattering arguments in the literature are incomplete, including those for maximal independent set, $(Δ+1)$-coloring, and the distributed Lovász Local Lemma (LLL). We provide a systematic repair of these analyses. Our main contribution is a corrected shattering analysis of the Fischer--Ghaffari LLL algorithm. In addition, we develop general tools that capture common patterns in modern algorithms and yield the required decay bounds without relying on independence. We also present explicit counterexamples to commonly used shattering lemmas. Overall, we establish a robust and reusable foundation for shattering arguments in the presence of long-range dependencies.

Authors: Andreas Göbel, Matthew Jenssen, Marcus Michelen, Marcus Pappik, Will Perkins, Leon Schiller

A recent breakthrough of Chen, Chen, Chen, Yin, and Zhang shows rapid mixing for Glauber dynamics for the hard-core model on random regular graphs beyond the tree uniqueness threshold. Their approach builds upon the literature of various local-to-global techniques and applies to a more general setting of discrete distributions supported on downward-closed set families. We give a short and self-contained proof via a Bochner--Bakry--Émery approach and directly show a Poincaré inequality by expanding the Dirichlet form in terms of the $L^2$-norm of the generator applied to a test function and eliminating a sum of squares term. Our proof is a streamlined version of an argument of Kondratiev, Kuna, and Ohlerich used to study spatial birth-and-death dynamics for Gibbs point processes in the continuum, which we adapt to the discrete setting.

Authors: Ilan Doron Arad, Jonathan Gal, Seffi Naor

Dominating Set is a fundamental problem in graph theory: given a graph, find a minimum-weight subset of vertices such that every vertex is either selected or adjacent to a selected vertex. In online settings where vertices arrive sequentially, comparing algorithms against an offline optimum with full knowledge of the input leads to extremely strong lower bounds, where even a simple star graph shows that any online algorithm must have competitive ratio $Ω(Δ)$, with $Δ$ the largest degree of any vertex in the graph, matching the trivial strategy of selecting all vertices. We study the incremental dominating set problem, where the optimal algorithm is constrained to the same choices available to online algorithms. This introduces a benchmark that enables a meaningful comparison between algorithms. We present the first results for vertex-weighted graphs and randomized algorithms in this model. For incremental dominating set, we give an $O(Δ)$-competitive deterministic algorithm and an $O(\log^2Δ)$-competitive randomized algorithm. We extend these results to the Connected Dominating Set problem using a linear-programming formulation that captures connectivity through local constraints. When the neighborhood of each arriving vertex is known \textit{in advance}, deterministic algorithms achieve similar polylogarithmic competitive ratios as their randomized counterparts. Finally, we establish matching lower bounds, showing that our results are optimal up to constant factors.

Peter Brass is a prior NSF theory director. He has written an intelligent guest post on the new NSF guidelines that we present here.

You have received many mails regarding the proposed OMB Uniform Guidance for federal grant making. It is a very long document. So far the OMB has received more than 32,000 comments, which nominally all will be read and taken into account, but actually most are general comments along the lines of “this will destroy scientific research,” and unspecific comments will achieve nothing. You can sample the comments, they are public, and you will be disappointed: much heat but no illumination.

It is my aim to bring a bit more content to the debate, and encourage you to file comments, but on specific issues, in my opinion primarily on the passage against “promoting anti-American Values,” which might indeed be a catch-all for political pressure on research. Otherwise there is little new: reviews were always only advisory.

The relevant section is https://www.federalregister.gov/d/2026-10817/p-amd-155, the revision of section 200.205, especially section (b) “pre-issuance review,” which states (underline and boldface mine):

(b) Pre-issuance review. As part of the merit review process, Federal agencies must perform pre-issuance reviews to ensure that Federal award proposals selected for funding are consistent with applicable law, Federal agency priorities, and the national interest. In doing so, Federal agencies heads must designate one or more senior appointees to conduct a pre-issuance review of all discretionary awards. As part of this pre-issuance review for discretionary awards, senior appointees (or their designee) must, as relevant and to the extent consistent with applicable law, apply the following principles when reviewing Federal award proposals:

This is followed by a list of criteria, but to summarize this: The agency head (a presidential appointment) designates a senior appointee (possibly a presidential appointment) who might designate another person inside the agency, who checks all intended awards that certain criteria are satisfied. This is not really different from the state before 2025: any proposal I proposed for award needed to be checked by the division director.

So if there is a problem, it must be in the criteria. It turns out there might be, depending on the interpretation.

1. Discretionary awards must, where applicable, demonstrably advance the President’s policy priorities.
   Whether this is applicable is the agency’s decision.
2. Discretionary awards must not be used to fund, promote, encourage, subsidize, or facilitate:
   • (i) Racial preferences or other forms of racial discrimination by the recipient, including activities where race or intentional proxies for race will be used as a selection criterion for employment or program participation;
   • (ii) Denial by the recipient of the sex binary in humans or the notion that sex is a chosen or mutable characteristic;
   • (iii) Illegal immigration; or
   • (iv) Any other initiatives that compromise public safety or promote anti-American values.
   That last one is a catch-all, which can indeed be used by politics to suppress research. This is the passage against which we should protest.
3. All else being equal, preference for discretionary awards should be given to institutions with lower indirect cost rates.
   All else is never equal, but it is in the program director’s discretion to consider how much funding actually reaches science.
4. Discretionary awards should be given to a broad range of recipients. Research grants should be awarded to a mix of recipients likely to produce immediately demonstrable results and recipients with the potential for potentially longer-term, breakthrough results, in a manner consistent with the notice of funding opportunity.
   I am quite happy about this explicit recognition of the importance of basic research.
5. In performing activities under Federal awards, applicants should commit to complying with administration policies, procedures, and guidance respecting Gold Standard Science.
   It is fairly unclear what Gold Standard Science is, but that seems to affect only lab or simulation sciences with results that are advisory to politics.
6. Discretionary awards should include benchmarks for measuring success and progress towards relevant goals and, as relevant for awards pertaining to scientific research, a commitment to achieving Gold Standard Science.
   Same. For us the benchmark measuring success is publication, so no news.
7. To the extent institutional affiliation is considered in making discretionary awards, agencies should prioritize an institution’s commitment to rigorous, reproducible scholarship over its historical reputation or perceived prestige. For science grants, agencies should prioritize institutions that have demonstrated success in implementing Gold Standard Science.
   No news either. We should not give extra credit to a proposal coming from a famous institution. Of course that is in the discretion of the program director.

(c) Procedure for pre-issuance review. When conducting a pre-issuance review, senior appointees (or their designee) must not ministerially ratify or routinely defer to the recommendations of others, but must instead use their independent judgment when evaluating Federal award proposals.

(so the designee should actually look at the proposal before approving the award)

(d) Use of peer review. Nothing in this part must be construed to discourage or prevent the use of peer review methods to evaluate proposals for discretionary awards or otherwise inform agency decision making, provided that peer review recommendations remain advisory and are not ministerially ratified, routinely deferred to, or otherwise treated as de facto binding by senior appointees or their designees. Further, nothing in this part must be construed to create any rights to any particular level of review or consideration for any funding applicant except as consistent with applicable law.

(good news: nothing changes)

(e) Agency discretion to reissue funding opportunities. A Federal agency is not required to issue a discretionary award as a result of a NOFO if doing so would fund low-quality proposals or be inconsistent with the principles of this part. The agency may, at its discretion, repost a funding opportunity.

(so the agency can decide not to make any award)

This is the entire section which causes so much outcries. I believe that the proposed budget cuts are a much larger danger to research than these recommended OMB rules.

By gasarch

One of the most popular posts in this blog’s history was Common Knowledge and Aumann’s Agreement Theorem, based on a lecture that I gave to high-school students 11 years ago. One of the impacts of that post, I’m proud to say, is that (according to Steven Pinker) it helped to inspire Steve’s excellent recent popular book, which you should read, entitled What Everyone Knows That Everyone Knows…: Common Knowledge and the Mysteries of Money, Power, and Everyday Life.

Two weeks ago, I was privileged to attend a workshop in Paris on “50 Years of Agreeing to Disagree,” where (among other things) I got to meet the 96-year-old Economics Nobel Laureate Robert Aumann for the first time.

I got to catch up there with Steven Pinker as well, who gave a phenomenal talk on the psychology of common knowledge. My own talk was entitled The Complexity of Agreement, with New Directions and Applications (link goes to my PowerPoint slides).

Aran Nayebi has graciously posted on YouTube some partial video from the meeting, including his talk, brief snippets from my talk, and Aumann’s own remarks:

Meanwhile, here were the Aumannian insights that I remembered to write down:

AUDIENCE QUESTION: What questions did people ask you after you published your famous agreement theorem in 1976?

AUMANN: I don’t remember what happened yesterday, let alone 1976.

Also:

ME: I thought you might enjoy knowing that I just came here from a meeting of rationalists…

AUMANN: A meeting of who?

ME: Rationalists, they call themselves, at a beautiful venue called Lighthaven in Berkeley, and that they named the main building there “Aumann Hall” in your honor.

AUMANN: OK, so I’ve made it then.

One reccent result announced at the workshop, for those who care, is that the proof of Aumann’s Theorem has now been formalized in Lean, by Scott Kominers at Harvard and a group from the startup company Axiom Math.

Thanks so much to Christina Katt-Pawlowitsch, Ziv Hellman, and others for organizing the workshop and for including me in it.

Happy to field questions in the comments, although if someone wants to call me an idiot like usual, we’ll just need to agree to disagree!

By Scott

We introduce a new family of propositional proof systems, denoted $\langle EF, R \rangle$, for an arbitrary TFNP search problem $R$. Informally, a refutation of a CNF formula $F$ in $\langle EF, R \rangle$ is given by a polynomial-time mapping reduction from the false-clause search problem ${\mathrm{Search}}_F$ to $R$, combined with an Extended Frege proof that the reduction is correct. These new systems are naturally motivated in two ways: 1. They are the propositional translations of witnessing theorems in bounded arithmetic, by which proofs of $\forall \Sigma^b_1$ formulas $\phi$ in a theory $T$ imply algorithms solving the search problem for $\phi$ in a TFNP subclass corresponding to $T$ [Bus86, KP90, BK94, KST07, BB09]. 2. They form a white-box analogue of the recent characterizations of proof systems using decision tree reductions to black-box TFNP problems [GHJ+22b, BIK+94, DR23, LPR24, FGJ+26, FIM25]. We consider the proof system $\langle EF, Iter \rangle$, where $Iter$ is the complete problem for the classical TFNP subclass PLS. We prove that $\langle EF, Iter \rangle$ is polynomially equivalent to the quantified boolean sequent calculus $G_1$, and also to the implicit Resolution proof system $[EF, Resolution]$ introduced by Krajícek [Kra04]. Hence $G_1$ and $[EF, Resolution]$ are polynomially equivalent, which is the first natural characterization of an implicit proof system by a classical propositional proof system beyond the work of Wang [Wan13]. We further observe our characterization can be extended to capture $G_i$ via the game induction principles of [ST07]. We also calibrate the strength of $\langle EF, R \rangle$ for general TFNP relations $R$. We observe that if Extended Frege can prove that a search problem $R$ is in FP, then $\langle EF, R \rangle$ is polynomially equivalent to $EF$. This contrasts to our above result, which shows that Extended-Frege provable reductions to $Iter$, a problem widely believed not to be in FP, yields a proof system ($G_1$) that is believed to be stronger than Extended Frege. Finally, and somewhat paradoxically, we show that for any proof system $P$ which is sufficiently strong, there is a polynomial-time computable search problem $R_P \in $ FP such that $\langle EF, R_P \rangle$ is polynomially equivalent to $P$. Letting $P = [EF, Resolution]$ and combining our two results shows that $\langle EF, Iter \rangle$ is polynomially equivalent to $\langle EF, R_{[EF, Resolution]} \rangle$. Hence, despite the widely-believed conjecture that $Iter \not \in $ FP, the problems which $EF$-provably reduce to $Iter$ are exactly the problems which $EF$-provably reduce to a fixed polynomial-time computable set.

This post is a map of the lower-bound posts on Decentralized Thoughts. The Start Here page already lists many of these results by topic, and the lowerbound tag lists the posts themselves. Here we turn that list into a chapter: first the main fault-threshold barriers, then communication, round complexity, latency, validity, privacy, and liveness. In distributed computing, an upper bound is often a condition and a protocol for the honest...

By Ittai Abraham

We design a deterministic algorithm that, given blackbox access to the product $f=\prod_{i=1}^{\ell}{h_i}$ of $\ell$ irreducible $s$-sparse $n$-variate polynomials of bounded individual degree $d$, over fields of characteristic zero, and more generally over fields of sufficiently large positive characteristic, recovers the $h_i$'s and their multiplicities in time $\mathrm{poly}(n,(s\ell d)^d)$. For any constant $d>2$, this is the first \emph{polynomial-time} algorithm for this problem, resolving for the bounded-individual-degree regime an open question of Dutta, Sinhababu, and Thierauf (Random 2026). The previous best deterministic algorithm, due to the authors, runs in $\mathrm{poly}(n,d^d,s^{d\log \ell},\ell^d)$ time, which is quasi-polynomial in $\ell$. The improvement is enabled by a new sparse rational interpolation theorem in the bounded-individual-degree setting, based on reconstructing the denominator from its logarithmic derivatives. Given blackbox access to rational functions $a_1/b,\ldots,a_N/b$ where the $a_j$'s and $b$ are $s$-sparse of individual degree at most $d$ with $\gcd(a_1,\ldots,a_N,b)=1$, we recover the $a_j$'s and $b$ in time $\mathrm{poly}(n,d!,s^d,N)$. In contrast to the rational interpolation theorem of Chuyoon-Shpilka (2026), our algorithm reconstructs the denominator directly and does not require a precomputed list of its irreducible factors.

The Hamiltonian Cycle polynomial, denoted as $HC_n$, is defined to be the sum of the weighted Hamiltonian Cycles in an $n$-vertex complete digraph, with vertices labeled $1$ to $n$ and edges weighted by formal variables $x_{i,j}$. The Permanent and $HC$, defined as the family $\{HC_n | \ n \geq 1\}$, were studied by Valiant (STOC 1979), with the former shown to be VNP-complete over all fields of characteristic other than $2$, and the latter to be VNP-complete over every field. Since its introduction, $HC$ has been studied from the perspective of circuit lower bounds by Jerrum-Snir (JACM 1982), determinantal complexity by Huttenhain-Ikenmeyer (LAA 2016), and its connection with the Permanent and the Determinant polynomials by Goulden-Jackson (EJC 1981) and Grochow (ToC 2017). It has been the most prominent choice for generalising results to all fields, such as in Malod (CCC 2007) and Grochow-Mulmuley-Qiao (ICALP 2016), owing to its VNP-completeness over every field. Hrubes (ToCT, 2016) showed the VNP-completeness of many graph-based polynomial families over every field by using $HC$. In Kayal (STOC 2012), a randomised polynomial time algorithm was given for the following problem: Given an $n^2$-variate degree-$n$ polynomial $f(\mathbf{x}) \in \mathbb{F}[\mathbf{x}]$ as a black box, decide if there exists $A \in \mathrm{GL}_{n^2}(\mathbb{F})$ such that $f(\mathbf{x}) = Perm_n(A\mathbf{x})$. Here, the Permanent polynomial $Perm_n$ computes the permanent of the $n \times n$ symbolic matrix $(x_{i,j})$. This problem is known as testing equivalence to the Permanent, or alternatively, ET for Permanent. In this work, we study ET for $HC$. While both families are VNP-complete, the efficient ET algorithm for Permanent does not imply the same for $HC$. Besides, there are crucial differences between the two polynomials that make studying the complexity of ET for $HC$ interesting: The underlying decision problem corresponding to the Permanent is in P (detecting perfect matchings in a bipartite graph), but that for $HC$ (detecting Hamiltonian cycles in a digraph) is NP-complete. The Permanent polynomial is known to be characterised by its symmetries as shown by Mulmuley-Sohoni (SIAM J. Computing, 2001). This property yields an efficient algorithm for the circuit-testing problem for the Permanent, a special case of ET for the Permanent, in which we check whether a given circuit computes the Permanent. In contrast, we show $HC_n$ is not characterised by its symmetries. In this work, we give a randomised polynomial time ET algorithm for $HC$ with mild constraints on the underlying field. The algorithm is obtained by studying and completely characterising the Lie algebra and the symmetries of $HC_n$. We show that, like the Permanent polynomial, the symmetries of $HC_n$ are generated by permutation and scaling matrices over large enough fields. However, we also show that, unlike the Permanent polynomial, $HC_n$ is not characterised by its symmetries. Nevertheless, like the Permanent polynomial, $HC_n$ is downward self-reducible, as shown in Zhang-Bai (TCS 2011), which implies $HC_n$ is characterised by circuit identities and that we can efficiently test whether a given circuit $\mathrm{C}$ computes $HC_n$. We also get a Flip theorem for $HC_n$ as a result of its circuit identities.

We introduce an approach to distinguishing isomorphism types of graphs based on vector spaces of polynomials that are set-wise invariant under permutations (“separating modules,” which are representations of the symmetric group), inspired by the Geometric Complexity Theory approach to separating complexity classes (Mulmuley & Sohoni, SIAM J. Comput., 2001). We characterize the power of this method for distinguishing non-isomorphic graphs under several different complexity measures: - We show that separating modules of "support-degree" $k$ (each monomial touches at most $k$ vertices) are equivalent to the counts of $O(k)$-vertex subgraphs. This is strictly weaker than $O(k)$-dimensional Weisfeiler--Leman (Fürer, ICALP '01). - We show that separating modules of symmetric circuit size $n^{\Theta(k)}$ are equivalent to $\Theta(k)$-WL. This generalizes and strengthens a result of Dawar & Wilsenach (CSL '18; ICALP '20; ACM Trans. Comput. Log., 2022; Theory Comput., 2025): they proved one direction of this equivalence for invariant polynomials; we generalize to separating modules and prove both directions. - When considering only the multiplicities of separating modules (as was proposed in GCT by Mulmuley & Sohoni, ibid., rather than the polynomials themselves), we show that two graphs are separated by multiplicities if and only if their automorphism groups have different cycle indices. The latter result is notable in the analogy with GCT, as it is the only result we are aware of in which the multiplicity approach to separating isomorphism types of objects has been given an "intrinsic" characterization in terms of the objects themselves. We use this to show that for graphs, multiplicity obstructions are stronger than occurrence obstructions. We also connect invariant polynomials to the Graph Reconstruction Conjectures and Forman's “invariants of finite type” (Adv. Math., 2004).

I’ve been hesitating in writing up a blog post about my latest preprint, “Minimum-weight Steiner triangulation of convex polygons requires interior Steiner points” (with my student Zahra Hadizadeh, arXiv:2606.25302, to appear at CCCG) because, despite being a completely concrete two-dimensional construction, its exponential scale makes it difficult to visualize. In the paper we included an illustration using logarithmic coordinates but I didn’t find that entirely satisfactory so I’m trying again in a different way here.

The new paper is about a problem from a much older paper of mine, “Approximating the minimum weight Steiner triangulation” (SODA 1992 and Discrete Comput. Geom. 1994), on “Steiner triangulation”, adding points to a geometric input to reduce the total edge length of a triangulation of the input. The added points are called Steiner points. The old paper proved that one could get within a constant factor of the minimum possible total edge length, for various kinds of inputs including point sets and convex polygons, using a method based on quadtrees. For convex polygons, you do sometimes need to add Steiner points; for instance the trapezoid below is optimally triangulated with one Steiner point (blue) on its long parallel side.

However, in my earlier work I could only find examples of convex polygons whose optimal Steiner points were on the polygon boundary. When that is the case, the “weak dual” of the triangulation (the graph of triangles and their adjacencies with other triangles) forms a tree. This tree structure should make finding the best triangulation with this structure easier, amenable to dynamic programming algorithms, although there are some difficulties with numerics and nonlinear functions that would need to be overcome. In the older paper, I conjectured that interior Steiner points would never be needed and therefore that we could find optimal Steiner triangulations of convex polygons in polynomial time. The result of the new paper is that the conjecture is false: we construct a polygon whose optimal triangulation requires interior Steiner points.

To understand our counterexample, I think it might be helpful to start with a counter-counterexample, showing why it’s not easy to construct counterexamples. More precisely, it’s not possible to have an optimal interior Steiner point with at most six neighbors and a convex neighborhood. If you had a triangulation like that, you could find a better triangulation with fewer Steiner points by contracting the low-degree Steiner point into its closest neighbor.

In the example above, the Steiner point is \(S\) and the closest of its six neighbors is \(A\). Contracting \(AS\) turns the blue shaded triangulation around \(S\) into the red shaded triangulation, replacing the six edges \(SA\), \(SB\), \(SC\), \(SD\), \(SE\), and \(SF\) by the three edges \(AC\), \(AD\), and \(AE\). Each added edge can be shown to be shorter than a pair of removed edges by using the triangle inequality and the assumption that \(A\) is the nearest neighbor to \(S\):

\[AC\le AS+SC\le BS+SC,\] \[AD\le AS+SD,\] \[AE\le AS+SE\le FS+SE.\]

Combining these inequalities gives

\[AC+AD+AE\le (BS+SC)+(AS+SD)+(FS+SE)\]

so the contracted non-Steiner triangulation is shorter than the Steiner triangulation.

This argument breaks down when a Steiner point has seven or more neighbors, because then there aren’t enough removed edges to pair them up and use the triangle inequality. We found our counterexample to the conjecture by looking for neighborhoods for which, instead, contracting the Steiner point to its nearest neighbor produces a worse triangulation. The resulting convex polygon has an approximate kite shape, with exponentially-spaced sequences of vertices along the short sides of the kite (which are rounded slightly to make the result convex). It has 28 vertices, most of which cluster together near the point where the two short sides of the kite meet:

The next image is a close-up of this cluster, scaled by a factor of approximately 40, with the Steiner point (blue) and its incident edges also shown.

Most of the edges incident to the Steiner point extend rightward, so contracting the Steiner point into its nearest neighbor to the left would lengthen these edges. The same contraction would eliminate the three edges connecting the Steiner point to its three nearest neighbors, but those eliminated edges are very short relative to the number of lengthened edges. A numerical calculation shows that, in fact, the Steiner triangulation is better than the triangulation obtained by connecting all vertices to the nearest neighbor of the Steiner point. More strongly, because of the exponential spacing of the points, that turns out to be the optimal non-Steiner triangulation. So for this polygon, there is a Steiner triangulation with an interior point that is better than any non-Steiner triangulation.

That’s not quite enough to disprove the conjecture. The harder part of the paper, extending to multiple pages of appendices, is proving that there is no good Steiner triangulation using only boundary Steiner points. Therefore, the Steiner triangulation with this one interior Steiner point is better than any Steiner triangulation using only boundary Steiner points. It’s (numerically) the optimal triangulation with a single symmetrically placed Steiner point. We didn’t prove that it’s the optimal Steiner triangulation, because (however implausible it might be) there might be some other way of placing interior Steiner points that is even better. But it’s enough to disprove the conjecture, and prove that some convex polygons require interior Steiner points in their minimum-weight Steiner triangulations.

(Discuss on Mastodon)

By David Eppstein

Authors: Fabio F. G. Buono

Impagliazzo's five worlds classify computational assumptions along a single axis, the existence of cryptographic primitives. All five worlds implicitly assume that every party, including the adversary, observes the full input, that the observer is always $O_{top}$. This assumption is so natural that it is never stated. This work makes it explicit and relaxes it by introducing a second, orthogonal axis, the observational axis, defined by the observer hierarchy introduced in previous work. Relaxing the assumption reveals structural phenomena, such as the collapse $P^{O_{prof}} = NP^{O_{prof}} \subset P$, that the five-world framework cannot express. We prove that this collapse holds unconditionally in all five worlds, showing that observational blindness and computational hardness are independent. We define the Observer World $W_O$, classify all world-observer pairs, identify the labeled cells (a)--(d), and introduce a parametric family $W_O^{\varepsilon}$ modelling partial violations of observational invariants. The framework also interfaces with physical information limits, including thermodynamic, quantum, and cosmological bounds.

Authors: Pablo Concha-Vega, Antonin Loubière, Kévin Perrot

Determining whether predicting two-dimensional sandpiles lies in $\mathbf{NC}$ or is $\mathbf{P}$-complete has been open for decades. Moore and Nilsson proved $\mathbf{P}$-completeness for the three dimensional case by encoding Boolean circuits into sandpiles, but this method fails in two dimension due to the impossibility of crossing gates. In this work, we study the existence of crossing gates on non-uniform and weighted grids. We establish an equivalence between uniform weighted crossing gates and a class of simple non-uniform crossing gates, which we call primal. We also exhibit a crossing gate that inherently requires more than one crossing, rather than a single crossing as in standard constructions. Finally, we show that the equivalence between uniform weighted and primal crossings breaks down in more general settings.

Authors: Tomoyuki Yamakami

In the past literature, families of two-way finite automata and pushdown automata having limited state complexity (i.e., the total number of inner states) and stack-state complexity (i.e., the total number of inner states multiplied by the total number of strings "pushable" to a stack), have been studied in direct connection to (mainstream) space-bounded complexity classes equipped with Karp-Lipton style advice of limited size when all inputs given to the automata have bounded length. Here, we acknowledge two major factors -- size and ceiling -- of such families, which have a significant impact on the complexity of finite and pushdown automata families, where the "size" refers to (stack-)state complexity and the "ceiling" refers to an input's length bound. In this line of study, we further explore those effects caused by different sizes and ceilings.

Authors: Agrim Dewan

The Hamiltonian Cycle polynomial, denoted as $HC_n$, is defined to be the sum of the weighted Hamiltonian Cycles in an $n$-vertex complete digraph, with vertices labeled $1$ to $n$ and edges weighted by formal variables $x_{i,j}$. Valiant (STOC 1979) studied the Permanent and $HC$, defined as the family $\{HC_n | \ n \geq 1\}$, and showed both families are VNP-complete, the former over any field of characteristic other than $2$, and the latter over any field. Since its introduction, $HC$ has been studied from the perspective of lower bounds by Jerrum-Snir (JACM 1982), determinantal complexity by Huttenhain-Ikenmeyer (LAA 2016), and its relation to the Permanent by Goulden-Jackson (EJC 1981) and Grochow (ToC 2017). Its VNP-completeness over any field has been used in Malod (CCC 2007), Grochow-Mulmuley-Qiao (ICALP 2016) and Hrubes (ToCT, 2016). The Equivalence Testing problem for a polynomial $f(\mathbf{x})$ (ET for $f$) is as follows: Given $g(\mathbf{x}) \in \mathbb{F}[\mathbf{x}]$ as a black box, decide if there exists $A \in \mathrm{GL}_{|\mathbf{x}|}(\mathbb{F})$ such that $g = f(A\mathbf{x})$. Kayal (STOC 2012) gave a randomised polynomial time ET algorithm for the Permanent. In this work, we give a randomised polynomial time ET algorithm for $HC$ with mild constraints on the field. We show that, like the Permanent polynomial, the symmetries of $HC_n$ are generated by permutation and scaling matrices over large enough fields. We also show that $HC_n$ is not characterised by its symmetries, unlike the Permanent polynomial, Mulmuley-Sohoni (SIAM J. Computing, 2001). Nevertheless, like the Permanent polynomial, $HC_n$ is downward self-reducible, Zhang-Bai (TCS 2011), implying $HC_n$ is characterised by circuit identities and an efficient algorithm to test if a given circuit $\mathrm{C}$ computes $HC_n$. We also get a Flip theorem for $HC_n$ as a result of its circuit identities.

Authors: Kuize Zhang

In this paper, we formulate a scenario that an agent can never be sure that another agent can uniquely determine the state of a finite-state automaton based on its observations to the automaton at the current and any past time as the property of order-2 bygone-state opacity. Based on our concurrent composition and the classical observer, we derive a tool to verify this property in doubly exponential time. The interest of this result lies in that we extend inference of finite automata from a single agent to two ordered agents.

Authors: Somnath Bhattacharjee, Rishabh Kothary, Shanthanu S. Rai, Shubhangi Saraf

We study factoring algorithms for general sparse polynomials and sparse polynomials of bounded individual degree and prove the following results. 1. We give a deterministic polynomial-time algorithm which takes as input an $n$-variate $s$-sparse polynomial $f$ of bounded individual degree $d$ and outputs a list of circuits which contains all factors of $f$, although there might be additional spurious circuits in the list. The algorithm runs in time $\operatorname{poly}(n, s^d)$. Additionally, every circuit in the list has constant depth. Our algorithm works over all fields of characteristic 0 or sufficiently large characteristic. Our result generalizes a recent result of Chuyoon and Shpilka that gives a $\operatorname{poly}(n, s^d)$-time algorithm for recovering all sparse factors of $f$ (without spurious factors). As a corollary, we can also recover all factors of $f$ in time $\operatorname{poly}(n, s^{d^2 \log n})$, and recover the algorithmic result of Bhargava, Saraf and Volkovich and its improvement by Chuyoon and Shpilka. Both the above consequences follow from known interpolation and divisibility testing techniques. 2. We give a deterministic quasipolynomial-time algorithm which takes as input a general $n$-variate $s$-sparse polynomial $f$ of (unbounded) individual degree $D$ and outputs a list of polynomials which contains all factors of $f$ that have bounded individual degree $d$. The algorithm runs in time $\operatorname{poly}(D^{d \log s}, s^{d^2 \log n})$ and works over arbitrary fields. The list may again contain spurious elements. Our result strengthens results of Dutta, Sinhababu and Thierauf and Kumar, Ramanathan and Saptharishi which give algorithms to recover all factors of $f$ of bounded total degree. A consequence of our algorithm is a new upper bound on the total number of bounded individual degree factors of a sparse polynomial.

Authors: Ioannis Nasios

This paper presents solarsystem, a validated lightweight and dependency-free Python package for planetary positions and solar-lunar event calculations. The package provides heliocentric and geocentric positions for the major planets, selected dwarf planets, the Centaur Chiron, and the Moon, together with sunrise, sunset, moonrise, moonset, and lunar illumination calculations. Additional functionality includes coordinate transformations between commonly used astronomical reference systems. The implemented algorithms employ analytical models that avoid reliance on external ephemeris datasets, resulting in a portable and computationally efficient solution suitable for a broad range of astronomical applications. An optional precession correction model is included, enabling calculations either in a precession-corrected reference frame or in a fixed epoch framework, depending on user requirements. The numerical performance of solarsystem was evaluated against the JPL DE440 planetary ephemerides using the Skyfield framework as a reference. Validation experiments spanning multiple bodies and extended temporal intervals demonstrate good agreement with the reference ephemerides, with mean planetary longitude and latitude deviations of approximately 0.44 and 0.16 arcminutes, respectively. Additional validation of solar and lunar event calculations yielded timing differences of only a few minutes relative to the reference solutions, while lunar illumination estimates differed by approximately 0.2%. The package can be installed directly through PyPI while the source code, documentation, validation notebooks and example workflows are publicly available through the project repository in https://github.com/IoannisNasios/solarsystem.

Authors: Jayanta Pari, Pratibha Bhandari, Soumyendu Raha

Community detection is a key task in network analysis, providing insight into the structural organization of complex systems. Effective resistance, a graph-theoretic metric derived from electrical network theory, has emerged as a powerful tool for evaluating connectivity and influence within networks. This paper proposes an effective resistance-based community detection algorithm that calculates the similarity between nodes using effective resistance values and produces a weighted graph. The sparse graph used in the algorithm is generated after computing the minimum spanning tree (MST) of the weighted graph and adopting a threshold sparsification strategy on non-MST edges. A maximum modularity approach is adopted using the Clauset-Newman-Moore algorithm on the resultant sparse graph. This algorithm is evaluated for both synthetic and real-world networks, demonstrating its effectiveness compared to popular existing methods. The result shows that the effective resistance-based approach accurately captures the structures of the community while maintaining computational efficiency.

Authors: Michael T. M. Emmerich

Selecting a fixed number of representative points from a finite Pareto-front approximation is a fundamental post-processing task in multiobjective optimization. This paper studies this problem for the integral R2 indicator in three objectives, where the indicator is defined as the integral of the lower envelope of weighted Tchebycheff scalarizations over the two-dimensional weight simplex. We provide two complementary algorithmic results. On the positive side, we show that the integral R2 improvement with respect to any fixed baseline is a monotone submodular set function. For the usual ideal-point based R2 indicator, with the ideal point fixed, this yields a direct gap-reduction guarantee: greedy selection closes at least a $(1-1/e)$-fraction of the maximum possible R2 gap between a fixed dominated anchor value and the best cardinality-$k$ value. We also give a tested greedy implementation that evaluates exact integral R2 values by subdivision, with worst-case running time $O(n^6)$. On the negative side, we prove that exact fixed-cardinality subset selection is NP-hard already in three objectives. The hardness proof uses a perspective transformation that maps Tchebycheff-shadow improvements to a weighted anchored-box union problem with density $(x_1+x_2+x_3)^{-4}$, and then adapts the three-dimensional anchored-box construction of Bringmann, Cabello, and Emmerich. Together, these results separate the tractable two-objective case from the three-objective case while identifying a principled approximation route based on submodular optimization.

Authors: Luoning Zhang, Xu Zhuang, Tianhao Wang, Nathan Kaplan

We study certain extremal problems in combinatorial geometry that ask about configurations of points in an $n \times n$ grid that satisfy strict, global geometric constraints. Classical exact solvers suffer from combinatorial explosion for these types of problems, and standard reinforcement learning and transformer-based models struggle with the sparse reward "validity cliff" and quadratic token-consumption limits. To overcome these bottlenecks, we propose a Geometry-Aware Monte Carlo Tree Search (MCTS) framework. Our approach strictly enforces geometric constraints through incremental updates to the feasible action space. For constraints about collections of collinear points, like those that occur in the classic No-Three-in-Line problem (Max-N3IL), this mechanism reduces the constraint checking complexity from $O(n^3)$ to $O(n^2)$. To improve search efficiency, we exploit geometric symmetries in two ways: canonical pruning during node expansion to reduce the branching factor, and symmetric batch transitions to accelerate the discovery of promising configurations. We perform extensive experiments and establish new best-known computational results on five out of six of the problems that we considered. Notably, for Max-N3IL we find configurations of size roughly $1.8 n$ for grids of size $82 \le n \le 119$. For the Smallest Complete Set problem, we find configurations of size roughly $0.95 n$, providing new upper bounds within the tested grids. This work establishes Geometry-Aware MCTS as a highly adaptable framework for discovering novel configurations in combinatorial geometry.

Authors: Weining Zhu

As a type of spatial tessellation model and an important spatial structure of computational geometry, Voronoi diagrams (VDs) are widely used in many fields. Due to differences in generation spaces, types of spatial entities, distance metrics, and relationships between entities and Voronoi regions, Voronoi diagrams vary into many types, such as the ordinary VD, VD on spheres, VD for linear entities, weighted VD, and ordered higher-order VD. These VDs also have their own generation algorithms. In this study, we propose a new cell-merge (CM) Voronoi generation algorithm based on the spatial chromatic model. The advantage of the CM algorithm is that it can quickly generate diverse VDs by retrieving and merging cells from a unified database, without requiring the development of specific algorithms for each VD. The CM Voronoi algorithm can be particularly applied in cases where a variety of Voronoi diagrams are frequently required for computation and analysis, such as in location-based spatial analysis. Furthermore, the proposed CM method can also generate some new types of spatial tessellations, such as competition intensity and couple-cell diagrams which are different from classical VDs.

Authors: Joshua A. Grochow, Jacob Urisman

We introduce an approach to distinguishing isomorphism types of graphs based on vector spaces of polynomials that are set-wise invariant under permutations ("separating modules," which are representations of the symmetric group), inspired by the Geometric Complexity Theory approach to separating complexity classes (Mulmuley & Sohoni, SIAM J. Comput., 2001). We characterize the power of this method for distinguishing non-isomorphic graphs under several different complexity measures: - We show that separating modules of "support-degree" $k$ (each monomial touches at most $k$ vertices) are equivalent to the counts of $O(k)$-vertex subgraphs. This is strictly weaker than $O(k)$-dimensional Weisfeiler--Leman (Fürer, ICALP '01). - We show that separating modules of symmetric circuit size $n^{Θ(k)}$ are equivalent to $Θ(k)$-WL. This generalizes and strengthens a result of Dawar & Wilsenach (CSL '18; ICALP '20; ACM Trans. Comput. Log., 2022; Theory Comput., 2025): they proved one direction of this equivalence for invariant polynomials; we generalize to separating modules and prove both directions. - When considering only the multiplicities of separating modules (as was proposed in GCT by Mulmuley & Sohoni, ibid., rather than the polynomials themselves), we show that two graphs are separated by multiplicities if and only if their automorphism groups have different cycle indices. The latter result is notable in the analogy with GCT, as it is the only result we are aware of in which the multiplicity approach to separating isomorphism types of objects has been given an "intrinsic" characterization in terms of the objects themselves. We use this to show that for graphs, multiplicity obstructions are stronger than occurrence obstructions. We also connect invariant polynomials to the Graph Reconstruction Conjectures and Forman's "invariants of finite type" (Adv. Math., 2004).

Authors: Akitoshi Kawamura

In the pinwheel scheduling problem, each task $i$ is associated with a positive integer $a_i$ called its period, and we want to (perpetually) schedule one task per day so that each task $i$ is performed at least once every $a_i$ days. An obvious necessary condition for schedulability is that the density, defined as the sum of execution rates $1/a_i$, does not exceed $1$. We prove that all instances with density not exceeding $5/6$ are schedulable, as was conjectured by Chan and Chin in 1993. Like some of the known partial progress towards the conjecture, our proof involves computer search for schedules for a large but finite set of instances. A key idea in our reduction to these finite cases is to generalize the problem to fractional (non-integer) periods in an appropriate way. As byproducts of our ideas, we obtain a simple proof that every instance with two distinct periods and density at most $1$ is schedulable, as well as a fast algorithm for the bamboo garden trimming problem with approximation ratio $4/3$.

Authors: Helin Wang, Chenyi Zhang, Xiwen Tao, Yexin Zhang, Tongyang Li

We study the problem of finding stationary points of non-convex functions when access to the objective is provided only through a comparison oracle that, given two points, outputs which has the larger function value. For a twice differentiable $f\colon\mathbb R^n\to\mathbb R$ with Lipschitz gradient and Hessian, we develop an algorithm that visits an $ε$-stationary point using $\widetilde O(n^2/ε^{1.5})$ queries. Our approach uses a subroutine that estimates the normalized Hessian to accuracy $δ$ using $\widetilde O(n^2\log(1/δ))$ queries. We further study this problem with a quantum comparison oracle model where queries can be made in superpositions, and develop the first quantum algorithm that finds an $ε$-stationary point, which takes $\widetilde O(n/ε^{1.5})$ queries.

Authors: Kan Shota, Kazuya Haraguchi

In network vulnerability analysis, it is crucial to evaluate the robustness of $k$-cores against vertex removals. A $k$-core is often fragile since removing a few vertices can trigger a large reduction in the core size, a phenomenon known as core collapse. In this paper, we study the problem of enumerating all minimal removable sets (MinRSs) of a given $k$-core, where a MinRS is a minimal nonempty set of vertices whose removal results in a smaller $k$-core graph. We consider this problem within a general mathematical framework based on monotone systems. We show that, for a monotone system that is given with an underlying graph $G=(V,E)$, all MinRSs of a solution can be enumerated in $O((n+m)nτ_ω)$ time, where $n=|V|$, $m=|E|$ and $τ_ω$ denotes the computation time of evaluating the monotone function of the system. Furthermore, if the system satisfies the newly defined in-dominating seed property, the complexity drops to $O((n+m) \log n \cdot τ_ω)$ time. We prove that standard $k$-cores in undirected graphs satisfy this property, enabling MinRS enumeration in $O((n+m)\log n)$ time, a significant improvement over the baseline. We also extend our framework to enumerate all solutions in a given monotone system. This yields an $O((n+m)\log n)$-delay algorithm for all $k$-core subgraphs, outperforming an algorithm given by [Boley et al., Theoretical Computer Science, 2010]. Our framework is applicable to various $k$-core extensions, including weighted $k$-cores, multi-layer $\boldsymbol{k}$-cores, and $(k,\ell)$-cores.

Authors: Barna Saha, Yinzhan Xu, Christopher Ye

Given a graph, computing distances and reachabilities from a small set of vertices to the whole graph is an important primitive both in theory and in practice. In undirected unweighted graphs, while computing single-source shortest path (SSSP) requires $O(n^2)$ time in dense graphs, all-pairs shortest paths (APSP) can be computed in $\hat{O}(n^ω) = O(n^{2.372})$ time [Seidel '95] providing significant savings over running $n$ SSSP instances separately. However, if one needs to compute multiple-source shortest paths (MSSP) from a set of $n^σ$ vertices, the previously best known running time was $\hat{O}(\min\{n^ω, n^{2 + σ}\})$: either compute APSP or run SSSP from each source. On the other hand, MSSP is only as hard as computing Boolean matrix product (BMM) between an $n^σ\times n$ matrix and $n \times n$ matrix, leaving a significant gap. Our first main result is an almost optimal algorithm for MSSP on undirected unweighted graphs running in $\hat{O}(n^{ω(σ, 1, 1)})$ time, which gives a smooth interpolation between the SSSP and APSP algorithms. The main technical tool behind our result is a novel graph decomposition, which may be of independent interest. Next, we study the multiple-source reachability problem, where we need to determine whether a given set of $n^σ$ vertices can reach each of the vertices in a given directed graph. Multiple-source reachability can also be solved in $\hat{O}(\min\{n^ω, n^{2 + σ}\})$ time, with the same lower bound from rectangular BMM. We give an optimal algorithm that runs in $\hat{O}(n^{ω(σ, 1, 1)})$ time, again matching the running time for BMM. Our algorithm for multiple-source reachability can be generalized to MSSP on DAGs. As an application, we provide an $O(n^{2.084})$ time algorithm for computing an $\widetilde{O}(n)$-size shortcut set that reduces diameter to $O(n^{1/3})$.

Authors: Beaudou Laurent, Foucaud Florent, Lorieau Lucas, Tale Prafullkumar

In DIRECTED GEODETIC SET, we are given a (directed) graph and seek a small solution set $S \subseteq V(G)$ such that every vertex lies on a shortest directed path between two vertices in $S$. It is known that the problem is W[2]-hard when parameterized by the solution size $k$, even on directed acyclic graphs (DAGs). Our first result is a kernel of size $2^{O(vcn)}$ for DIRECTED GEODETIC SET on general digraphs, where $vcn$ denotes the vertex cover number of the underlying (undirected) graph. This implies an algorithm running in time $2^{O(vcn^2)} \cdot n^{O(1)}$. Furthermore, we prove that, assuming the ETH, the problem does not admit an algorithm running in time $2^{o(vcn^2)} \cdot n^{O(1)}$. Next, we show that on general digraphs, DIRECTED GEODETIC SET admits a natural kernel of size $(kΔ)^{O(rdiam)}$, where $Δ$ is the maximum degree and $rdiam$ denotes the reachability diameter of the digraph (a natural analogue of diameter of undirected graphs). This yields an algorithm running in time $(kΔ)^{O(rdiam \cdot k)}\cdot n^{O(1)}$. We further prove that, assuming the ETH, the problem does not admit an algorithm running in time $(kΔ)^{o(rdiam \cdot k)} \cdot n^{O(1)}$. Finally, we justify the necessity of combining parameters by establishing the following hardness results for DIRECTED GEODETIC SET: - It is W[2]-hard parameterized by $k$, even on digraphs of maximum degree 3. - It is para-NP-hard parameterized by maximum degree and reachability diameter. One can infer that the problem remains W[2]-hard when parameterized by k, even on graphs of reachability diameter 3 from Araújo and Arraes [DAM 2022]. All our conditional lower bounds and hardness results hold even when the input digraph is restricted to be a DAG.

Authors: Haitong Liu, Deepak Narayanan Sridharan, David Steurer, Manuel Wiedmer

We study the fundamental problem of learning a high-dimensional Gaussian truncated to an unknown halfspace. Lee, Mehrotra and Zampetakis (FOCS'24) recently obtained the first polynomial time algorithm for this problem, but their resulting sample and time complexity bounds are not optimal. Under non-trivial truncation, for any target accuracy $\varepsilon > 0$ and dimension $d$ we give an efficient algorithm that uses $n = \tilde{O}(d^2/\varepsilon^2)$ samples and learns the underlying Gaussian to error $\varepsilon$ in total variation distance. Our algorithm is also fast: its runtime is dominated by the cost of computing the empirical covariance matrix. Both our sample and time complexity are optimal in terms of $d$ and $\varepsilon$ even without truncation: in this regard, we can learn a Gaussian under halfspace truncation for free. The key ingredient behind our result is a novel reinterpretation of the low-degree moments of the truncated Gaussian in terms of a relative truncation parameter. This relative truncation parameter uniquely determines the parameters of the untruncated Gaussian and enables direct parameter recovery. This reinterpretation allows us to circumvent the time intensive projected stochastic gradient descent procedure that is widely used in learning under truncation.

We study factoring algorithms for general sparse polynomials and sparse polynomials of bounded individual degree and prove the following results. 1. We give a deterministic polynomial-time algorithm which takes as input an $n$-variate $s$-sparse polynomial $f$ of bounded individual degree $d$ and outputs a list of circuits which contains all factors of $f$, although there might be additional spurious circuits in the list. The algorithm runs in time ${poly}(n, s^d)$. Additionally, we can ensure that every circuit in the list has constant depth. Our algorithm works over all fields of characteristic 0 or sufficiently large characteristic. Our result generalizes a recent result of Chuyoon and Shpilka that gives a ${poly}(n, s^d)$-time algorithm for recovering all sparse factors of $f$ (without spurious factors). As a corollary, we can also recover all factors of $f$ (without spurious factors) in time ${poly}(n, s^{d^2 \log n})$, and recover the algorithmic result of Bhargava, Saraf and Volkovich and its improvement by Chuyoon and Shpilka. Both the above consequences follow from known interpolation and divisibility testing techniques. 2. We give a deterministic quasipolynomial-time algorithm which takes as input a general $n$-variate $s$-sparse polynomial $f$ of (unbounded) individual degree $D$ and outputs a list of polynomials which contains all factors of $f$ that have bounded individual degree $d$. The algorithm runs in time ${poly}(D^{d \log s}, s^{d^2 \log n})$ and works over arbitrary fields. The list may again contain spurious elements. Our result strengthens results of Dutta, Sinhababu and Thierauf and Kumar, Ramanathan and Saptharishi which give algorithms to recover all factors of $f$ of bounded total degree. A consequence of our algorithm is a new upper bound on the total number of bounded individual degree factors of a sparse polynomial.

When you start thinking deeply about a mathematics problem you may enter the "zone", a period of intense focus where you think solely about the problem and potential solutions, and more importantly block out all other thoughts and even lose track of time. Mathematicians don't own the zone, actors, musicians, athletes and many others have their own version of the zone. But for math, when working on an open problem, you have no idea how difficult a solution may be, or if a solution exists at all. Most of the time you will fail (if not you need to try harder problems). Failure is not wasted time. You may find a counterexample, a partial solution and always you will come out with a better understanding of the problem. Then days, months or years later, some new proof idea comes from a paper, a talk or just the back of your head, and back in the zone you go. And when you do succeed you get a feeling not unlike scoring a goal in a soccer game. You should see my proof dance.

With AI generated and assisted proofs, we may think of outsourcing the zone to ChatGPT and Claude. We may prove more and stronger theorems, but you'll understand the results just a little bit less and mathematics will become a little less fun. 

By Lance Fortnow

Authors: Nikita Gaevoy

Resolution with symmetries is a natural extension of the Resolution proof system that allows to use symmetries of the formula to simplify the proof. Symmetries can be global (applied to the whole input formula), local (applied to a subformula), or dynamic (applied to newly derived clauses as well). The framework of Resolution with (global) symmetries was introduced by Krishnamurthy (1985) and further extended by Arai and Urquhart (2000) to local symmetries. Later, Szeider (2005) generalized this approach to homomorphisms and introduced the notion of Resolution with dynamic symmetries. While proving superpolynomial proof-size lower bounds for Resolution with dynamic symmetries remains an open problem already for two decades, the power of proof systems with global and local symmetries is well studied: exponential lower bounds have been proven for these proof systems, as well as exponential separations between all of them. However, these systems are too general to reflect practical applications since it is computationally too hard to find and efficiently exploit arbitrary symmetries. In this work, we introduce the notion of small symmetries: symmetries that can operate on a limited number of variables at the same time. Resolution with small symmetries gives hopes both for practical applications and for theoretical study of dynamic symmetries. We show that proof systems with both local and global small symmetries form strict hierarchies w.r.t. the size of symmetries. We prove exponential separations between proof systems with symmetries of different sizes and types. It turns out that even lower levels of these hierarchies are exponentially separated from Resolution and stronger proof systems, such as constant-depth Frege. As a byproduct of our constructions, we obtain an exponential separation between the classical systems SRCI and SRII that was not known before.

Authors: Marcel K. Goh, Hamed Hatami

We construct a point-line incidence problem over the reals whose randomized communication complexity is constant, but whose deterministic communication complexity is linear even when the players have access to an equality oracle. This is the strongest possible separation between these two measures, and it improves on an earlier $O(1)$-versus-$Ω(\sqrt{n})$ separation of Göös, Harms, and Riazanov. Because point-line incidence problems have constant sign rank, our construction also bears on a question of Harms and Zamaraev, who asked whether constant sign rank together with constant randomized communication complexity forces constant equality-oracle complexity. This was already refuted by Göös, Harms, Imbach, and Sokolov with a logarithmic lower bound; our example improves the separation to linear, which is optimal. The proof draws on a construction in the recent disproof of the sum-product conjecture over the reals by Bloom, Sawin, Schildkraut, and Zhelezov, using totally real number fields of large degree and small discriminant.

Authors: Peter Bürgisser

We study the logical relation of the P-NP separation conjecture in the Blum-Shub-Smale-model over the complex numbers with the P-NP separation conjecture in Valiant's algebraic model. This amounts to comparing Hilbert's Nullstellensatz Problem, that is, deciding feasibility of a given system of polynomial equations over the complex numbers, with the problem of evaluating the permanent of a given complex matrix. We compare the respective uniform models of computations and prove that $P_C\ne NP_C$ in the Blum-Shub-Smale-model over $C$ implies the separation $VP^0(u)\ne VNP^0(u)$ of the uniform versions of Valiant's constant-free complexity classes over $C$. For the nonuniform models we show the analogous implication: the separation $P^0_C(nu)\ne NP^0_C(nu)$ of the nonuniform, constant-free Blum-Shub-Smale classes over $C$ implies the separation $VP^0\ne VNP^0$ of Valiant's constant-free complexity classes over $C$. In the reverse direction, we conjecture that $VNP_C\not\subseteq\overline{VP}_C$ implies that $P_C(nu)\ne NP_C(nu)$.

Authors: Nikolas Gärtner, Victor Magron, Frank Vallentin

In this paper, we analyze the bit complexity of deciding whether a given polynomial can be represented as a sum of squares of polynomials. We show that the weak membership problem for the sum-of-squares cone lies in $\mathrm{P}$. Furthermore, we give a polynomial-time algorithm which computes, for a given polynomial and positive parameter $ε$, an $ε$-relaxed closest sum-of-squares polynomial.

Authors: Qisheng Wang

We consider the problem of estimating the fidelity of an unknown quantum state to a known reference state to within additive error $\varepsilon$. We show that the sample complexity is $O(r^2/\varepsilon^2)$ with optimal $\varepsilon$-dependence when the reference state is of rank $r$, improving the previous best $O(r^2\log^2(1/\varepsilon)/\varepsilon^4)$ due to Utsumi, Nakata, Wang, and Takagi (QIP 2026). We also provide a lower bound of $Ω(r/\varepsilon^2)$, improving the previous best $Ω(r/\varepsilon+1/\varepsilon^2)$, with implications to quantum query complexity. Moreover, we further consider the case where the unknown state is of rank at most $r$ while the reference state can be arbitrary, for which the sample complexity is shown to be $O(r^2/\varepsilon^4)$. As an application, we present an approach to tolerant quantum state certification, generalizing the exact certification studied in Bădescu, O'Donnell, and Wright (STOC 2019).

Authors: Barna Saha, Yinzhan Xu, Christopher Ye

Several fundamental problems in computational geometry admit algorithms with running time $f(d) \cdot n^{2-Θ(1/d)}$ for $n$ points in $d$ dimensions, making them among the most prominent examples of barely subquadratic computation. Notable members of this class include Furthest Pair, Bichromatic Closest Pair, (Bichromatic) Maximum Innter Product, and Hopcroft's Problem. Chen [Theory Comput. 2020] proved that, assuming the Strong Exponential Time Hypothesis (SETH), these problems require $n^{2-o(1)}$ time when the dimension satisfies $d=2^{Θ(\log^* n)}$. We extend this lower bound to all efficiently constructible dimensions $d=ω(1)$. Thus, assuming SETH, the dependence of the best known algorithms on the dimension is essentially unavoidable. The proof utilizes techniques in OpenAI's recent disproof of the Erdos unit distance conjecture. The proof was initially discovered by ChatGPT 5.5 Pro. The authors have validated and substantially edited the proof to improve the presentation.

Authors: Raphaël Tinarrage

We analyze the decrease of simplex diameters under iterated refinement of spherical Delaunay complexes. Unlike in ordinary subdivision, the refined Delaunay complex need not be a subdivision of the previous one, so mesh contraction is not automatic. We derive explicit contraction bounds for several families of Steiner points, including Delaunay analogues of barycentric and edgewise subdivision. The proof reduces the problem to sharp covering estimates for Euclidean simplices. These estimates are obtained through a strengthening of Maurey's empirical method via pivotal sampling and a dimension-dependent version of the approximate Carathéodory theorem. Theoretical results and numerical experiments show that Delaunay refinements achieve stronger contraction than their subdivision counterparts.

Authors: David Eppstein, Zahra Hadizadeh

We construct a convex polygon for which the minimum-weight Steiner triangulation requires an interior Steiner point. This provides a counterexample to a 1994 conjecture of Eppstein that minimum-weight Steiner triangulation of convex polygons needs only Steiner points on the boundary of the polygon.

Authors: Satoshi Kanno, Yoshi-aki Shimada

Topological information is widely used in data analysis, network design, and machine learning, and topological constraints naturally arise when optimizing or generating objects with prescribed homological structure. However, directly controlling Betti numbers and persistent homology is difficult because they are discrete and combinatorial. We propose a differentiable framework for topology-constrained optimization based on Hodge-spectral relaxations of homological constraints and low-pass spectral filters. From soft graphs and soft clique complexes, we construct Hodge-Laplacian-type spectral relaxations that unify graph clique complexes and Vietoris--Rips filtrations of point clouds. In the hard limit, the penalty-regularized ambient operator recovers the ordinary Hodge Laplacian on the active subcomplex, while in the soft regime it serves as a differentiable low-frequency spectral surrogate. Homological information is represented by zero and near-zero modes, and differentiable topological objectives are defined using heat filters, resolvent filters, and polynomial Laplacian moments. For point clouds, we show that the proposed Hodge spectral-filter losses yield more spatially distributed gradients, smoother scale-normalized behavior under persistence-pairing changes, and geometry-aware update directions than persistent-homology-based losses. For graph clique complexes, Laplacian moments control normalized first-Betti-type quantities and can be combined with ordinary graph-feature objectives. We also discuss connections to trace-based normalized Betti-number estimation, polynomial spectral methods, and possible quantum trace estimation.

Authors: Anna Brötzner, Omrit Filtser, Bengt J. Nilsson, Christian Rieck, Christiane Schmidt

Motivated by applications for robust guarding, we consider a variant of the multiple-watchmen problem that ensures that every point within a polygon $P$ is seen from more than one direction: we search for two routes $W_1,W_2$, such that every point $p\in P$ is contained in a segment $\overline{w_1w_2}\subseteq P$ such that $w_1\in W_1$ and $w_2\in W_2$. We call such routes segment watchman routes. We show that finding the two routes that are optimal with respect to the min-max criterion is weakly NP-hard even in simple polygons, and that finding the routes that are optimal with respect to the min-sum criterion is NP-hard in polygons with holes. Moreover, we present sufficient conditions for routes to be segment watchman routes, and provide a polynomial-time $2$-approximation under both the min-max criterion and the min-sum criterion, both in simple polygons. Finally, we show how to generalize our results for $k$ watchmen.

Authors: Yuanhao Wang, Wei Wang

Let $n$ and $p$ denote the numbers of vertices and labels, respectively, in an undirected edge-labeled graph. Previous work showed that, under the Exponential Time Hypothesis (ETH), there is no deterministic algorithm with running time \[ (np)^{o\left(\frac{\log n}{(\log\log n)^2}\right)}. \] In this paper, we give a deterministic reduction that strengthens this conditional running-time lower bound to \[ (np)^{o\left(\frac{\log n}{\log\log n}\right)}. \]

Authors: Thekla Hamm, Bart M. P. Jansen, Faezeh Motiei

We study generalizations of the Steiner Tree problem motivated by the design of power networks. While Steiner Tree asks for a single minimum-cost tree connecting given terminal vertices, a power network typically consists of multiple trees, each connecting a subset of the terminals, to avoid electrical overloads. The cost of installing depends on both the cable lengths and the cost of digging underground trenches for putting the cables where the digging costs can be shared. These leads to variants of Steiner Tree where the goal is to compute a minimum-cost set of Steiner trees with a common root, that together connect all terminals while balancing the power demand of the terminals in each tree. Two important variants arise depending on whether the network is intended for low-voltage or high-voltage power. In the low-voltage case, power loss imposes a bound on the maximum depth of each tree, while no such restriction applies in the high-voltage case. We study the parameterized complexity of several power network design problems, parameterized by the number of terminals. While Steiner Tree is fixed-parameter tractable under this parameterization, most of our variants are W[1]-hard. For low-voltage networks, we present an XP-algorithm for planar inputs based on structural bounds on the treewidth of solution subgraphs. We also give a reduction from Grid Tiling showing tightness under ETH. The XP-algorithm extends to the high-voltage setting and general graphs, albeit at a cost in the running time. For high-voltage networks, we show the problem remains W[1]-hard even on planar graphs. Finally, we explore a variant of the cost model for sharing digging costs in which both problems become fixed-parameter tractable.

Authors: Yu Chen, Zihan Tan

We study the following distance realization problem: given a metric $D$ on a set $T$ of terminals, does there exist an (edge-weighted) outerplanar graph $G$, such that $T\subseteq V(G)$, and for every pair $t,t'\in T$, $\textsf{dist}_G(t,t')=D(t,t')$? We first prove that there is no ``local characterization'', forming a contrast with trees and Okamura-Seymour instances. Our main result is an efficient algorithm for this problem whose running time is polynomial in $|T|$. Both our proof and our algorithm utilize a recent new approach of analyzing graph structures, by viewing graphs as paths and their intersections, which we believe is of independent interest.