Theory of Computing Report

Interview with Krishnendu Chatterjee, Tom Henzinger and Nir Piterman, CONCUR 2026 ToT Award recipients

Krishnendu Chatterjee, Thomas Henzinger and Nir Piterman will receive one of the two CONCUR 2026 Test-of-Time Awards at CONCUR 2026. Those colleagues kindly agreed to answer some questions of mine on their award-winning paper via email. You can find their answers to my questions below. I hope you'll enjoy reading them as much as I did. Thanks, Krishnendu, Nir and Tom!

Luca: You receive the CONCUR ToT Award 2026 for your paper Strategy Logic, which appeared at CONCUR 2007 and, in archival form, in Information and Computation. In that article, you introduced a seminal logic for expressing properties of strategies over two-player games on graphs. Could you briefly explain to our readers what the main features of strategy logic are? Could you also tell us how you came to study the question addressed in your award-winning article? Which of the results in your paper did you find most surprising or challenging?

Krishnendu, Nir and Tom (henceforth abbreviated to KNT): The defining feature of Strategy Logic is that it treats strategies as explicit, first-class objects: strategies are named by variables, and the logic can quantify over them. Our main motivation was to express central concepts from game theory, such as equilibria, within a logical framework for games on graphs. As for the results, what we find most appealing is that a logic this expressive still admits decidability, and that several natural fragments come with clean and reasonable computational complexity. Establishing these decidability and complexity results for various fragments was also the most technically challenging part of the work.

Luca: With the benefit of hindsight, having a logic to describe properties of games that treats strategies as first-class objects sounds like an extremely natural idea. However, previous logics such as ATL, ATL*, the alternating-time µ-calculus and game logic followed a different path. Do you recall how you came to the realisation that treating strategies explicitly was the "way to go"?

KNT: One of the key application areas for graph games has been reactive synthesis, and until 2004 reactive synthesis was studied primarily as an adversarial game. Hence logics such as ATL, ATL*, alternating-time µ-calculus, and game logic, all focus on strictly competitive or cooperative behaviors of game theory. Around 2004-2005, we started working on connections between algorithmic game theory and graph games. As a consequence we considered aspects of Nash equilibria and other not strictly competitive notions of game theory (such as secure equilibria) in graph games. A natural question was to build a logical framework that can express these aspects of game theory, which led to Strategy Logic. In fact we first isolated the one-alternation fragment, which suffices to express these equilibria, and only afterwards arrived at the full, more expressive logic. In hindsight, the shift to treating strategies explicitly was driven by the questions we were asking rather than by a single eureka moment.

Luca: Strategy logic builds on LTL, which is a very natural choice, IMHO. Did you consider defining a version of strategy logic basing it on the (linear-time) modal μ--calculus? Would it be worth doing so and how would such a logic relate to the alternating-time μ-calculus?

KNT: There is always a tension between LTL and stronger formalisms that can recognize all ω-regular languages. Following the tradition of ATL and ATL*, we naturally chose to go with LTL for defining the (linear-time) objectives of players. As the techniques that we developed were automata based, it was clear that extensions of LTL that can express all ω-regular languages would be handled by the same techniques. The exact choice of the linear-time formalism (for example, ETL, QLTL, LDL, or the linear-time μ-calculus) is not very important as long as it can be readily translated to automata. In the alternating-time μ-calculus, however, by carefully nesting fixpoints and coalition quantification, we can define infinitely many changes of strategic context. But only in a completely adversarial manner.

Luca: As you are hinting, in your paper, amongst other results, you showed that the alternating-time μ-calculus and strategy logic have incomparable expressive power. Would a fixed-point version of strategy logic, based on the modal μ-calculus, be a way of achieving a logic that offers the "best of both worlds" while maintaining some of the good computational properties of strategy logic? Has anyone worked on such a logic?

KNT: We did not consider such a version of Strategy Logic. Intuitively, both classical and alternating-time μ-calculi combine local, single-transition branching operators such as Pre with fixpoint operators, whereas strategies express global behavioral choices and the objectives of players are defined on outcomes that are linear paths. An important expressive difference between the alternating-time μ-calculus and Strategy Logic is therefore due to the distinction between branching and linear time.
It seems interesting to consider a logic that would combine two types of pre operators: those that continue exploring pre-defined strategies and their induced behaviors and those that allow to change the strategic context starting a new behavioral exploration. But we believe that the techniques that handle alternating-time mu-calculus would work for such a logic and the mix of behavior and control might be very hard to understand.

Luca: Did you or anyone else ever implement the model-checking algorithms you present in your award-winning paper? If the answer is negative, do you think that there would still be interest in such a model checker and in its experimental evaluation?

KNT: As far as we know there is no full implementation of Strategy Logic. In general, we have very good implementations supporting the manipulation and analysis of automata on infinite words (such as Spot and Owl). They are also used as a basis for creating tools that solve reactive synthesis. But we do not have good tool support for using automata on infinite trees, which would be required in order to fully support Strategy Logic. The community studying Multi-Agent Systems adopted Strategy Logic and they have some support for the analysis of some questions. There are implementations of equilibrium checking and rational synthesis in the tool Eve that is developed in the group of Michael Wooldridge in Oxford. They support the analysis of concurrent game structures for such questions. There is also a restricted version of an epistemic extension of Strategy Logic that is included in the model checker MCMAS for Multi-Agent Systems, which was developed in the group of Alessio Lumoscio in Imperial College London.
MCMAS also supports ATL model checking and, in principle, it is possible to reduce the one-alternation fragment of Strategy Logic to ATL model checking, but we are not aware of this having been implemented.

Luca: You mentioned the uptake of strategy logic by the multi-agent systems community. How is strategy logic relevant and did you think that this work would be relevant to multi-agent systems?

KNT: Strategy Logic answered a natural need in Multi-Agent Systems research. For MAS, questions about the goals of agents and hence strategies are very natural. Many questions relate to rational behavior: whether agents have an incentive to follow a protocol, stability of behavior, what can coalitions do, and whether individuals can profitably deviate. The way Strategy Logic puts strategies in the center as explicit objects makes it very natural to study these questions.
We wouldn’t say that we saw it coming, but the signs of early adoption of strategic reasoning by the MAS community were already there. The uptake of ATL and ATL* started in the early 2000s and by 2004-2005 people were using it regularly. We are also very happy that some of the major developments of Strategy Logic came from this community.

Luca: Are there any problems that you left open in your award-winning article that you'd still love to see solved? Did you or any colleagues study the problem of "strategy synthesis"?

KNT: Definitely. For the complete logic, our paper established only a non-elementary upper bound and left the matching lower bound open. This gap was later closed by colleagues, who proved a matching non-elementary lower bound and thereby settled the computational complexity of the full logic. We also concentrated on the case of two-player games rather than multi-player games. The interaction between the logic and the game structure means that the two-player framework, in a sense, already captures the complexity of the logic. Indeed, the same techniques based on tree automata were later used by others to extend the logic to the multi-player setting (and concurrent game structures).

Luca: I am interested in how research collaborations start, as I like to tell "research-life stories" to PhD students and young researchers of all ages. Could you tell us how you started your collaboration on the award-winning paper?

KNT: The collaboration grew naturally out of a question from Tom (Thomas Henzinger): could notions such as the equilibria we had been studying be expressed in ATL or ATL*, and if not, what would be a natural and concise logic that could express them? Pursuing this led us to the one-alternation fragment. We then realized that strategies can be viewed as trees, which meant tree automata were the right tool — and Nir (Nir Piterman) was our automata expert. So the paper really came together at the meeting point of three ingredients: the study of non-zero-sum games, the wish for a logical framework to express their concepts, and tree-automata techniques.

Luca: How did the results and the techniques you developed in your award-winning paper influence your subsequent research? Is there any result obtained by other researchers that builds on your work and that you like in particular?

KNT: The result had a lasting influence. The interplay between games and automata that we exploited in the paper fed directly into later lines of work. e.g., from the connection of games and automata the notion of good-for-games (a.k.a. history-deterministic) automata emerged. Among the results by others that build on Strategy Logic, the matching non-elementary lower bound and the work on special classes of strategies — such as the distinction between behavioral and non-behavioral strategies — are very elegant.

Luca: To my mind, games on graphs ought to be viewed as one of the unifying themes within TCS, bridging the Volume A-Volume B divide, and I am happy to see that there is a book-length treatment covering the subject now. What is your view on this matter? What impact do you think that your work has had, if any, on the community working on algorithmic game theory, broadly construed? (I am reminded of the slides for a, typically thought-provoking, talk delivered by Moshe Vardi.) What has our community learnt from the work done in the field of computational game theory? And what, if anything, did they learn from the work done within the concurrency theory community?

KNT: Indeed, games on graphs is one of the unifying themes between Volume A and Volume B: it connects with logic and automata theory from Vol. B, and it connects with the notion of alternation from complexity theory and graph algorithms from Vol. A. The inflow of ideas from algorithmic game theory, or game theory in general, is a key source of ideas in this work, e.g., to express equilibria in a logical framework. Other notions of equilibria have also been studied in the context of reactive synthesis (e.g., rational synthesis), and Vol. B researchers have explored many concepts from general game theory beyond strictly competitive games. The broad area of algorithmic game theory also benefited from logical reasoning grounded in concurrency theory, e.g., Strategy Logic is the key logic for reasoning about behaviors in Multi-Agent Systems, and axiomatic characterizations for reasoning about strategy spaces have been influential in evolutionary game theory. There is also work using Strategy Logic in mechanism design.

Luca: What are the research topics related to logics for games on graphs that you find most interesting right now?

KNT: We can think of several interesting open questions: (i) the relationship between games and automata through the lens of history-determinism and similar concepts is an exciting direction; (ii) algorithmic bounds for several fundamental problems remain open, e.g., a polynomial-time algorithm for parity games; (iii) the degree to which sources of randomness can be shared between different players is an active area of research in concurrent games; and (iv) the study of computationally efficient logics which lie between ATL* and Strategy Logic is also under-explored.

Luca: What advice would you give to a young researcher who is keen to start working on topics related to logics for games and other computational problems related to games?

KNT: The rapid progress in AI makes this question a difficult one. We believe that formal methods in general will become a central part of computing, more than they have ever been, because AI-generated software needs checks even more than software written by humans, but even more so, because modern AI can, for the first time, provide or at least support such checks on a scale that was hitherto impossible. Formal checks do not necessarily have to take the form of, say, Lean proofs, but they could also include state-based reasoning involving automata and games. It is always difficult to predict the future, but finding the right place for our field in this future seems a uniquely exciting opportunity.

By Luca Aceto

Krishnendu Chatterjee, Thomas Henzinger and Nir Piterman will receive one of the two CONCUR 2026 Test-of-Time Awards at CONCUR 2026. Those colleagues kindly agreed to answer some questions of mine on their award-winning paper via email. You can find their answers to my questions below. I hope you'll enjoy reading them as much as I did. Thanks, Krishnendu, Nir and Tom!

Luca: You receive the CONCUR ToT Award 2026 for your paper Strategy Logic, which appeared at CONCUR 2007 and, in archival form, in Information and Computation. In that article, you introduced a seminal logic for expressing properties of strategies over two-player games on graphs. Could you briefly explain to our readers what the main features of strategy logic are? Could you also tell us how you came to study the question addressed in your award-winning article? Which of the results in your paper did you find most surprising or challenging?

Krishnendu, Nir and Tom (henceforth abbreviated to KNT): The defining feature of Strategy Logic is that it treats strategies as explicit, first-class objects: strategies are named by variables, and the logic can quantify over them. Our main motivation was to express central concepts from game theory, such as equilibria, within a logical framework for games on graphs. As for the results, what we find most appealing is that a logic this expressive still admits decidability, and that several natural fragments come with clean and reasonable computational complexity. Establishing these decidability and complexity results for various fragments was also the most technically challenging part of the work.

Luca: With the benefit of hindsight, having a logic to describe properties of games that treats strategies as first-class objects sounds like an extremely natural idea. However, previous logics such as ATL, ATL*, the alternating-time µ-calculus and game logic followed a different path. Do you recall how you came to the realisation that treating strategies explicitly was the "way to go"?

KNT: One of the key application areas for graph games has been reactive synthesis, and until 2004 reactive synthesis was studied primarily as an adversarial game. Hence logics such as ATL, ATL*, alternating-time µ-calculus, and game logic, all focus on strictly competitive or cooperative behaviors of game theory. Around 2004-2005, we started working on connections between algorithmic game theory and graph games. As a consequence we considered aspects of Nash equilibria and other not strictly competitive notions of game theory (such as secure equilibria) in graph games. A natural question was to build a logical framework that can express these aspects of game theory, which led to Strategy Logic. In fact we first isolated the one-alternation fragment, which suffices to express these equilibria, and only afterwards arrived at the full, more expressive logic. In hindsight, the shift to treating strategies explicitly was driven by the questions we were asking rather than by a single eureka moment.

Luca: Strategy logic builds on LTL, which is a very natural choice, IMHO. Did you consider defining a version of strategy logic basing it on the (linear-time) modal μ--calculus? Would it be worth doing so and how would such a logic relate to the alternating-time μ-calculus?

KNT: There is always a tension between LTL and stronger formalisms that can recognize all ω-regular languages. Following the tradition of ATL and ATL*, we naturally chose to go with LTL for defining the (linear-time) objectives of players. As the techniques that we developed were automata based, it was clear that extensions of LTL that can express all ω-regular languages would be handled by the same techniques. The exact choice of the linear-time formalism (for example, ETL, QLTL, LDL, or the linear-time μ-calculus) is not very important as long as it can be readily translated to automata. In the alternating-time μ-calculus, however, by carefully nesting fixpoints and coalition quantification, we can define infinitely many changes of strategic context. But only in a completely adversarial manner.

Luca: As you are hinting, in your paper, amongst other results, you showed that the alternating-time μ-calculus and strategy logic have incomparable expressive power. Would a fixed-point version of strategy logic, based on the modal μ-calculus, be a way of achieving a logic that offers the "best of both worlds" while maintaining some of the good computational properties of strategy logic? Has anyone worked on such a logic?

KNT: We did not consider such a version of Strategy Logic. Intuitively, both classical and alternating-time μ-calculi combine local, single-transition branching operators such as Pre with fixpoint operators, whereas strategies express global behavioral choices and the objectives of players are defined on outcomes that are linear paths. An important expressive difference between the alternating-time μ-calculus and Strategy Logic is therefore due to the distinction between branching and linear time.

It seems interesting to consider a logic that would combine two types of pre operators: those that continue exploring pre-defined strategies and their induced behaviors and those that allow to change the strategic context starting a new behavioral exploration. But we believe that the techniques that handle alternating-time mu-calculus would work for such a logic and the mix of behavior and control might be very hard to understand.

Luca: Did you or anyone else ever implement the model-checking algorithms you present in your award-winning paper? If the answer is negative, do you think that there would still be interest in such a model checker and in its experimental evaluation?

KNT: As far as we know there is no full implementation of Strategy Logic. In general, we have very good implementations supporting the manipulation and analysis of automata on infinite words (such as Spot and Owl). They are also used as a basis for creating tools that solve reactive synthesis. But we do not have good tool support for using automata on infinite trees, which would be required in order to fully support Strategy Logic. The community studying Multi-Agent Systems adopted Strategy Logic and they have some support for the analysis of some questions. There are implementations of equilibrium checking and rational synthesis in the tool Eve that is developed in the group of Michael Wooldridge in Oxford. They support the analysis of concurrent game structures for such questions. There is also a restricted version of an epistemic extension of Strategy Logic that is included in the model checker MCMAS for Multi-Agent Systems, which was developed in the group of Alessio Lumoscio in Imperial College London.

MCMAS also supports ATL model checking and, in principle, it is possible to reduce the one-alternation fragment of Strategy Logic to ATL model checking, but we are not aware of this having been implemented.

Luca: You mentioned the uptake of strategy logic by the multi-agent systems community. How is strategy logic relevant and did you think that this work would be relevant to multi-agent systems?

KNT: Strategy Logic answered a natural need in Multi-Agent Systems research. For MAS, questions about the goals of agents and hence strategies are very natural. Many questions relate to rational behavior: whether agents have an incentive to follow a protocol, stability of behavior, what can coalitions do, and whether individuals can profitably deviate. The way Strategy Logic puts strategies in the center as explicit objects makes it very natural to study these questions.

We wouldn’t say that we saw it coming, but the signs of early adoption of strategic reasoning by the MAS community were already there. The uptake of ATL and ATL* started in the early 2000s and by 2004-2005 people were using it regularly. We are also very happy that some of the major developments of Strategy Logic came from this community.

Luca: Are there any problems that you left open in your award-winning article that you'd still love to see solved? Did you or any colleagues study the problem of "strategy synthesis"?

KNT: Definitely. For the complete logic, our paper established only a non-elementary upper bound and left the matching lower bound open. This gap was later closed by colleagues, who proved a matching non-elementary lower bound and thereby settled the computational complexity of the full logic. We also concentrated on the case of two-player games rather than multi-player games. The interaction between the logic and the game structure means that the two-player framework, in a sense, already captures the complexity of the logic. Indeed, the same techniques based on tree automata were later used by others to extend the logic to the multi-player setting (and concurrent game structures).

Luca: I am interested in how research collaborations start, as I like to tell "research-life stories" to PhD students and young researchers of all ages. Could you tell us how you started your collaboration on the award-winning paper?

KNT: The collaboration grew naturally out of a question from Tom (Thomas Henzinger): could notions such as the equilibria we had been studying be expressed in ATL or ATL*, and if not, what would be a natural and concise logic that could express them? Pursuing this led us to the one-alternation fragment. We then realized that strategies can be viewed as trees, which meant tree automata were the right tool — and Nir (Nir Piterman) was our automata expert. So the paper really came together at the meeting point of three ingredients: the study of non-zero-sum games, the wish for a logical framework to express their concepts, and tree-automata techniques.

Luca: How did the results and the techniques you developed in your award-winning paper influence your subsequent research? Is there any result obtained by other researchers that builds on your work and that you like in particular?

KNT: The result had a lasting influence. The interplay between games and automata that we exploited in the paper fed directly into later lines of work. e.g., from the connection of games and automata the notion of good-for-games (a.k.a. history-deterministic) automata emerged. Among the results by others that build on Strategy Logic, the matching non-elementary lower bound and the work on special classes of strategies — such as the distinction between behavioral and non-behavioral strategies — are very elegant.

Luca: To my mind, games on graphs ought to be viewed as one of the unifying themes within TCS, bridging the Volume A-Volume B divide, and I am happy to see that there is a book-length treatment covering the subject now. What is your view on this matter? What impact do you think that your work has had, if any, on the community working on algorithmic game theory, broadly construed? (I am reminded of the slides for a, typically thought-provoking, talk delivered by Moshe Vardi.) What has our community learnt from the work done in the field of computational game theory? And what, if anything, did they learn from the work done within the concurrency theory community?

KNT: Indeed, games on graphs is one of the unifying themes between Volume A and Volume B: it connects with logic and automata theory from Vol. B, and it connects with the notion of alternation from complexity theory and graph algorithms from Vol. A. The inflow of ideas from algorithmic game theory, or game theory in general, is a key source of ideas in this work, e.g., to express equilibria in a logical framework. Other notions of equilibria have also been studied in the context of reactive synthesis (e.g., rational synthesis), and Vol. B researchers have explored many concepts from general game theory beyond strictly competitive games. The broad area of algorithmic game theory also benefited from logical reasoning grounded in concurrency theory, e.g., Strategy Logic is the key logic for reasoning about behaviors in Multi-Agent Systems, and axiomatic characterizations for reasoning about strategy spaces have been influential in evolutionary game theory. There is also work using Strategy Logic in mechanism design.

Luca: What are the research topics related to logics for games on graphs that you find most interesting right now?

KNT: We can think of several interesting open questions: (i) the relationship between games and automata through the lens of history-determinism and similar concepts is an exciting direction; (ii) algorithmic bounds for several fundamental problems remain open, e.g., a polynomial-time algorithm for parity games; (iii) the degree to which sources of randomness can be shared between different players is an active area of research in concurrent games; and (iv) the study of computationally efficient logics which lie between ATL* and Strategy Logic is also under-explored.

Luca: What advice would you give to a young researcher who is keen to start working on topics related to logics for games and other computational problems related to games?

KNT: The rapid progress in AI makes this question a difficult one. We believe that formal methods in general will become a central part of computing, more than they have ever been, because AI-generated software needs checks even more than software written by humans, but even more so, because modern AI can, for the first time, provide or at least support such checks on a scale that was hitherto impossible. Formal checks do not necessarily have to take the form of, say, Lean proofs, but they could also include state-based reasoning involving automata and games. It is always difficult to predict the future, but finding the right place for our field in this future seems a uniquely exciting opportunity.

By Luca Aceto

Friday, August 21 2026, 14:56

Runbooks for Microconferences

from Ben Recht

A few fun ideas on how to organize, implement, and archive your microconference.

Thanks to everyone for the constructive feedback on Monday’s microconferences post. I wanted to take a beat to engage with two salient themes in the replies: runbooks and homophily. I’ll start with runbooks today, and tackle homophily next week.

No two microconferences are alike, and we shouldn’t impose hard-and-fast rules on their structure. One of the fun things about small conferences is you can tailor them to particular goals and dreams. And there are so many ways to do this well.

However, I think it will be useful to compile a runbook of agreements, strategies, and rules that you can use to help modularly assemble your ideal microconference. Today, I’ll run down a bunch of disorganized examples. You tell me your favorite ideas in the comments. I’ll assemble these more coherently into a document that I’ll widely share.

We can learn a lot from existing institutions, and many people spoke fondly of places I should have shouted out in the first post, e.g., BIRS, Oberwolfach, Dagstuhl.1 I also adore the quirkiness of the American Institute of Mathematics, which has a very particular and very fun way to run a microconference, disallowing canned and prepared talks.2 I am inspired by unconferences that bring together dozens of people to spontaneously generate many microconferences. All of their best practices should be part of the runbook.

I’ve found an easy model for microconferences is a bundle of short, 5-10 minute talks with adjoined group discussions led by the speakers. The past four microconferences I’ve attended have run this way. Short talks are fun because they force people to think hard about messaging and concision, and lead to a lot of interesting back-and-forth with the right serendipitous assignments. I was somewhat randomly assigned to a panel with Dan Wang and Dan Davies on cybernetics, and it was probably the most fun and rewarding 90 minutes I’ve ever had at a conference. That single brief session reshaped the narrative arc of The Irrational Decision.

Johan Ugander raised several good ideas in his comment. About archiving and proceedings, he wrote: “The non-proceedings nature of workshops is key to drawing in a diverse set of people.” I agree. We should think broadly about what should count as “proceedings” or “archiving.” I liked Johan’s suggestion of simply inviting participants to submit to a special issue. You could consider this series of blogs ([1], [2], [3], [4]) and this youtube video the “proceedings” of the Cultural AI workshop organized by Leif Weatherby and Tyler Shoemaker this spring. I just want to suggest that we explore creative ways to archive, evaluate, and credit microconferences in the broader academic ecosystem. I’d add to my list of core microconference values that “archiving should encourage, not discourage dissemination and broader engagement.”

As Johan wrote:

“ACM EC has a forward-to-journal mechanism, which gets Computer Science, Operations Research, and Economics folks together for a coherent conference but lets them still go harvest their respective tokens. The EC reviews get passed to the journal. And EC also organizes a ‘Highlights beyond EC’ session, which lets people request to present work recently/already published “elsewhere” but relevant to the community. Both of these mechanisms help keep the ‘conference’ and ‘publication’ goals separate.”

Endorsed!

Anna Gilbert raised the idea of “bump sessions”:

“The Dagstuhl and Oberwolfach type conferences in TCS used to also have “bump sessions” (maybe they were called rump!) where people proposed open problems, noodled over difficulties, etc. Sometimes these micro workshops even “published” open problems from these bump sessions. They were quite useful and engaging!”

Anna also raised one of my favorite ideas, which I’m looking for an opportunity to try:

“Another model I’d like to advocate for is to have members of a PC present the papers they selected (see my rant about paper reviewing and big conferences) and then an audience discussion. Like what the statisticians do but in person and with a publication resulting for the authors.”

I call this the “Not-so-royal Society.” The conference or session would center on a single paper written before the conference is organized. The organizers invite discussants to compose a response/review of this paper. The meeting could start with a presentation of the paper by the author. Many papers have multiple authors, and the presentation can be as collaborative as the writing. The author’s presentation is followed by commentary from the discussants. The remainder of the session is a conversation that invites commentary from the rest of the workshop participants.

After the workshop, the author can revise the paper, the discussants can write formal commentaries, and the author can write a rejoinder if they choose. All of this writing could be posted to arXiv as refereed conference proceedings and linked from the microconference proceedings webpage. This format might be the most legible in the current regime of bean counting and could perhaps serve as a “gentle introduction” to the microconference format. If you have ideas of papers we should use as testbeds for this format, reach out! I’d love to help set something like this up.

Finally, I want to give a shout out to Henry Farrell and Cosma Shalizi, who have been experimenting with clever microconference formats for years. Cosma wrote up the idea of having people present others’ work. Everyone writes a talk or slides, but then the presentation is assigned to someone else. They found that doing this at the start of the workshop creates a shared comprehension, allowing for a lot of multidisciplinary crosstalk. And they also found that speakers had to work extra hard to make their points comprehensible.

This is by no means an exhaustive list of ideas. And it shouldn’t be. My next major to-do is posting a working document of this runbook somewhere. But before I jump in and commit myself to a design, I’m looking for pointers to good online institutional memories that allow for edits and revisions. I love the minimalism of PMLR and bactra.org, but I also want to host a living mission statement and runbook on the same site. Let me know what platforms I should look into. Tech tips would be most appreciated!

Subscribe now

1

You can get a sense of the skew of my readership by the institutions they love.

2

I also love that it used to be in the backrooms of a Fry’s Electronics store

By Ben Recht

Friday, August 21 2026, 14:43

TR26-151 | Sparse polynomials and orthogonal representations of combinatorial graphs | Siddharth Iyer, Pavel Hrubes

from ECCC Papers

We give quantitative bounds on the sparsity of a real polynomial with non-negative coefficients vanishing on a slice of the Boolean cube $\{\pm1\}^n$. We obtain similar bounds on the dimension of real orthogonal representations of (the complement of) Johnson-type graphs. The estimates are related to the classical problem about coloring of $\mathbb{R}^n$, as well as the existence of error-correcting codes. We also give a simple combinatorial application to $k$-fold Hadamard matrices.

Friday, August 21 2026, 14:19

Pod-Deployability in Kubernetes with Inter-Pod Affinity Constraints is PSPACE-Complete

from arXiv: Computational Complexity

Authors: Saverio Giallorenzo, Jacopo Mauro, Gianluigi Zavattaro

Kubernetes is the de-facto platform for container orchestration. Its scheduler combines resource capacities with label-based affinity and anti-affinity rules, and the interaction of these features can make the eventual placement of a pod. In this paper, we study the pod-deployability problem: given an initial cluster, a pod type, and a designated node, does some legal sequence of pod deployments and deletions cover the target pair? We give three complexity results. First, when dynamic constraints contain no affinity (anti-affinity is allowed), pod-deployability is decidable in polynomial time. Second, required affinity together with required anti-affinity makes the problem PSPACE-complete. Third, required affinity alone is already enough for PSPACE-completeness on a single node with one scalar capacity. The lower bounds encode, respectively, 1-safe Petri-net coverability and bounded black pebbling. These results isolate two independent sources of state-space complexity in Kubernetes scheduling: logical exclusion and resource-bounded prerequisite management.

Authors: Saverio Giallorenzo, Jacopo Mauro, Gianluigi Zavattaro

Kubernetes is the de-facto platform for container orchestration. Its scheduler combines resource capacities with label-based affinity and anti-affinity rules, and the interaction of these features can make the eventual placement of a pod. In this paper, we study the pod-deployability problem: given an initial cluster, a pod type, and a designated node, does some legal sequence of pod deployments and deletions cover the target pair? We give three complexity results. First, when dynamic constraints contain no affinity (anti-affinity is allowed), pod-deployability is decidable in polynomial time. Second, required affinity together with required anti-affinity makes the problem PSPACE-complete. Third, required affinity alone is already enough for PSPACE-completeness on a single node with one scalar capacity. The lower bounds encode, respectively, 1-safe Petri-net coverability and bounded black pebbling. These results isolate two independent sources of state-space complexity in Kubernetes scheduling: logical exclusion and resource-bounded prerequisite management.

Friday, August 21 2026, 00:00

Constant-round quantum advantage in communication complexity for total functions

from arXiv: Computational Complexity

Authors: Atsuya Hasegawa, François Le Gall

We show that there exists a total function for which there is a polynomial gap between the randomized and the constant-round quantum communication complexity. Previously, such a separation was known only for quantum protocols using polynomially many rounds.

Authors: Atsuya Hasegawa, François Le Gall

We show that there exists a total function for which there is a polynomial gap between the randomized and the constant-round quantum communication complexity. Previously, such a separation was known only for quantum protocols using polynomially many rounds.

Friday, August 21 2026, 00:00

Proof of the hiding conjecture for Gaussian boson sampling with an arbitrary number of squeezed input modes

from arXiv: Computational Complexity

Authors: Laura Shou, Alexey V. Gorshkov, Victor Galitski, Sarah H. Miller

Gaussian boson sampling (GBS) is a sampling task proposed to demonstrate quantum advantage. We consider Gaussian boson sampling on $M$ optical modes, with $K$ equally squeezed input modes and $N$ observed photon counts. We complete the proof of the hiding conjecture for Gaussian boson sampling with an arbitrary number of squeezers $K$, which is a part of the argument for classical hardness of GBS. In particular, we show that for any $K$ and $N=o(\sqrt{K})$, the symmetric product $MK^{-1/2}U_{NK}U_{NK}^T$, for $U_{NK}$ the top left $N\times K$ submatrix of an $M\times M$ Haar random unitary $U$, is close in total variation distance to both an $N\times N$ symmetric complex Gaussian matrix $\mathbf G$ with independent entries, and the symmetric product $GG^T/\sqrt{K}$ for $G$ an $N\times K$ matrix of iid standard complex Gaussians. We show however that the density-based instance generating method of [Aaronson and Arkhipov, Theory Comput. 9, 143 (2013), Lemma 5.8] used to efficiently implement a hiding procedure fails for Gaussian boson sampling with $K=cM$ if $c<1/2$. Instead we use approximate instance generating to implement the hiding for the usual classical hardness reduction.

Authors: Laura Shou, Alexey V. Gorshkov, Victor Galitski, Sarah H. Miller

Gaussian boson sampling (GBS) is a sampling task proposed to demonstrate quantum advantage. We consider Gaussian boson sampling on $M$ optical modes, with $K$ equally squeezed input modes and $N$ observed photon counts. We complete the proof of the hiding conjecture for Gaussian boson sampling with an arbitrary number of squeezers $K$, which is a part of the argument for classical hardness of GBS. In particular, we show that for any $K$ and $N=o(\sqrt{K})$, the symmetric product $MK^{-1/2}U_{NK}U_{NK}^T$, for $U_{NK}$ the top left $N\times K$ submatrix of an $M\times M$ Haar random unitary $U$, is close in total variation distance to both an $N\times N$ symmetric complex Gaussian matrix $\mathbf G$ with independent entries, and the symmetric product $GG^T/\sqrt{K}$ for $G$ an $N\times K$ matrix of iid standard complex Gaussians. We show however that the density-based instance generating method of [Aaronson and Arkhipov, Theory Comput. 9, 143 (2013), Lemma 5.8] used to efficiently implement a hiding procedure fails for Gaussian boson sampling with $K=cM$ if $c<1/2$. Instead we use approximate instance generating to implement the hiding for the usual classical hardness reduction.

Friday, August 21 2026, 00:00

Polyomino Nets Covering Three Different Boxes of Area 106 and Related Results

from arXiv: Computational Geometry

Authors: Erik D. Demaine, Jenny Diomidova, Nicole Jacobus, Landon Kryger, Matthew T. Parker, Michael Tardibuono, Ryuhei Uehara, Hanyu Alice Zhang

We present new results for polyomino nets that fold into 2 and 3 different cuboids through a computer search. The main result is the finding of 40 nets that fold into all three different cuboids with a surface area of 106. The secondary results are the finding of infinite families of nets that fold into three cuboid shapes, and the calculation of the number of common nets between smaller cuboids. The algorithms used to make the searches feasible will also be explained. The algorithms include taking advantage of some hidden structures in the nets that fold into the Nx1x1 cuboids, taking advantage of how a lot of nets fold into cuboid shapes in a 'striped' way, and using a variant of Redelmeier's algorithm. The paper ends with open questions that encourage the reader to broaden our collective understanding of the subject of creating polyomino nets.

Authors: Erik D. Demaine, Jenny Diomidova, Nicole Jacobus, Landon Kryger, Matthew T. Parker, Michael Tardibuono, Ryuhei Uehara, Hanyu Alice Zhang

We present new results for polyomino nets that fold into 2 and 3 different cuboids through a computer search. The main result is the finding of 40 nets that fold into all three different cuboids with a surface area of 106. The secondary results are the finding of infinite families of nets that fold into three cuboid shapes, and the calculation of the number of common nets between smaller cuboids. The algorithms used to make the searches feasible will also be explained. The algorithms include taking advantage of some hidden structures in the nets that fold into the Nx1x1 cuboids, taking advantage of how a lot of nets fold into cuboid shapes in a 'striped' way, and using a variant of Redelmeier's algorithm. The paper ends with open questions that encourage the reader to broaden our collective understanding of the subject of creating polyomino nets.

Friday, August 21 2026, 00:00

Quantifying over Optimal MSO-Definable Sets on Graphs of Bounded Clique-Width

from arXiv: Data Structures and Algorithms

Authors: Tatsuya Gima

We introduce $\mathsf{AmCMSO}$, an extension of counting monadic second-order logic ($\mathsf{CMSO}$) with predicates that refer to minimum- and maximum-value satisfying assignments. We establish fixed-parameter tractable model-checking meta-theorems for $\mathsf{AmCMSO}_1$ on graphs of bounded clique-width and for $\mathsf{AmCMSO}_2$ on graphs of bounded treewidth. These meta-theorems yield fixed-parameter tractable algorithms for several bilevel graph optimization problems, including interdiction and preassignment problems for solution uniquification, as well as algorithms for maximizing the diversity of optimal solutions without parameterizing by the optimum value. In contrast, allowing an optimality predicate to depend on an external set variable makes model checking hard for every level of the polynomial hierarchy, even on trees of fixed depth.

Authors: Tatsuya Gima

We introduce $\mathsf{AmCMSO}$, an extension of counting monadic second-order logic ($\mathsf{CMSO}$) with predicates that refer to minimum- and maximum-value satisfying assignments. We establish fixed-parameter tractable model-checking meta-theorems for $\mathsf{AmCMSO}_1$ on graphs of bounded clique-width and for $\mathsf{AmCMSO}_2$ on graphs of bounded treewidth. These meta-theorems yield fixed-parameter tractable algorithms for several bilevel graph optimization problems, including interdiction and preassignment problems for solution uniquification, as well as algorithms for maximizing the diversity of optimal solutions without parameterizing by the optimum value. In contrast, allowing an optimality predicate to depend on an external set variable makes model checking hard for every level of the polynomial hierarchy, even on trees of fixed depth.

Friday, August 21 2026, 00:00

The Complexity of Boolean Connectivity Problem of $k$-Horn Formulas

from arXiv: Data Structures and Algorithms

Authors: Takashi Horiyama, Shoon Mineyoshi, Yuto Okura, Kazuhisa Seto, Junichi Teruyama

The Boolean connectivity problem asks whether the set of satisfying assignments of a given Boolean formula forms a connected subgraph in the $n$-dimensional hypercube. This problem is known to be $\mathsf{coNP}$-complete, even when restricted to $k$-Horn formulas for $k \geq 3$, as shown by Makino, Tamaki, and Yamamoto. In this paper, we further investigate the computational complexity of {\sc Conn $k$-Horn}, the Boolean connectivity problem for $k$-Horn formulas. We provide algorithmic and hardness results for {\sc Conn $k$-Horn}. On the algorithmic side, we first present an exact exponential-time algorithm for arbitrary $k$ without any structural restrictions. Our algorithm builds on the deterministic PPZ algorithm proposed by Paturi, Pudlák, and Zane. It runs in $O^*(2^{(1 - 1/2k)n})$ time and polynomial space, achieving an exponential improvement over the previously known algorithm for the Boolean connectivity problem of $k$-CNF formulas, shown by Makino, Tamaki, and Yamamoto. We next give two polynomial-time algorithms for arbitrary $k$ under the following two restrictions: (i) each variable appears at most twice, and (ii) each clause has length exactly $k$ and each variable appears at most $k$ times. On the hardness side, we prove that {\sc Conn $3$-Horn} remains $\mathsf{coNP}$-complete even when each variable appears exactly three times.

Authors: Takashi Horiyama, Shoon Mineyoshi, Yuto Okura, Kazuhisa Seto, Junichi Teruyama

The Boolean connectivity problem asks whether the set of satisfying assignments of a given Boolean formula forms a connected subgraph in the $n$-dimensional hypercube. This problem is known to be $\mathsf{coNP}$-complete, even when restricted to $k$-Horn formulas for $k \geq 3$, as shown by Makino, Tamaki, and Yamamoto. In this paper, we further investigate the computational complexity of {\sc Conn $k$-Horn}, the Boolean connectivity problem for $k$-Horn formulas. We provide algorithmic and hardness results for {\sc Conn $k$-Horn}. On the algorithmic side, we first present an exact exponential-time algorithm for arbitrary $k$ without any structural restrictions. Our algorithm builds on the deterministic PPZ algorithm proposed by Paturi, Pudlák, and Zane. It runs in $O^*(2^{(1 - 1/2k)n})$ time and polynomial space, achieving an exponential improvement over the previously known algorithm for the Boolean connectivity problem of $k$-CNF formulas, shown by Makino, Tamaki, and Yamamoto. We next give two polynomial-time algorithms for arbitrary $k$ under the following two restrictions: (i) each variable appears at most twice, and (ii) each clause has length exactly $k$ and each variable appears at most $k$ times. On the hardness side, we prove that {\sc Conn $3$-Horn} remains $\mathsf{coNP}$-complete even when each variable appears exactly three times.

Friday, August 21 2026, 00:00

Fast Algorithms for Stoquastic Spin Systems

from arXiv: Data Structures and Algorithms

Authors: Ryan L. Mann

We establish a general framework for developing fast sampling and counting algorithms for stoquastic spin systems at high temperature. Our framework is based on a rapidly mixing Markov chain for polymer models and a subcritical percolation process for sampling individual polymers. We apply our framework to obtain fast algorithms for approximating the partition function and sampling from the thermal distribution of (1) general stoquastic spin systems, (2) ferromagnetic Heisenberg models, and (3) antiferromagnetic Heisenberg models on bipartite graphs. For the Heisenberg models, we obtain an improved bound on the inverse temperature by using their respective cycle and loop representations.

Authors: Ryan L. Mann

We establish a general framework for developing fast sampling and counting algorithms for stoquastic spin systems at high temperature. Our framework is based on a rapidly mixing Markov chain for polymer models and a subcritical percolation process for sampling individual polymers. We apply our framework to obtain fast algorithms for approximating the partition function and sampling from the thermal distribution of (1) general stoquastic spin systems, (2) ferromagnetic Heisenberg models, and (3) antiferromagnetic Heisenberg models on bipartite graphs. For the Heisenberg models, we obtain an improved bound on the inverse temperature by using their respective cycle and loop representations.

Friday, August 21 2026, 00:00

Differentially Private Continual Release with Relative Error

from arXiv: Data Structures and Algorithms

Authors: Bo Li, Wei Wang, Peng Ye

This work investigates several fundamental tasks, including $\mathsf{MaxSum}$, $\mathsf{MinSum}$, $\mathsf{MaxSelect}$, and $\mathsf{MinSelect}$, in the continual release model under differential privacy. Previous research has demonstrated that any algorithm for these tasks must admit a large purely additive error. We show that the error can be substantially reduced if a relative error term is allowed, provided that the input stream is generated non-adaptively. However, when input data records can be selected adaptively, we prove that a large error is inevitable for the task of selecting an attribute with a small cumulative sum, whereas small error bounds remain achievable for other tasks. This reveals a significant separation between non-adaptive and adaptive streams. We also complement our algorithms with nearly matching lower bounds.

Authors: Bo Li, Wei Wang, Peng Ye

This work investigates several fundamental tasks, including $\mathsf{MaxSum}$, $\mathsf{MinSum}$, $\mathsf{MaxSelect}$, and $\mathsf{MinSelect}$, in the continual release model under differential privacy. Previous research has demonstrated that any algorithm for these tasks must admit a large purely additive error. We show that the error can be substantially reduced if a relative error term is allowed, provided that the input stream is generated non-adaptively. However, when input data records can be selected adaptively, we prove that a large error is inevitable for the task of selecting an attribute with a small cumulative sum, whereas small error bounds remain achievable for other tasks. This reveals a significant separation between non-adaptive and adaptive streams. We also complement our algorithms with nearly matching lower bounds.

Friday, August 21 2026, 00:00

Parameterized Complexity of Temporal Agony

from arXiv: Data Structures and Algorithms

Authors: Tom-Lukas Breitkopf, Vincent Froese, Anton Herrmann, Pascal Kunz

Real-world networks are often organized in several layers forming a hierarchy which determines the interaction between the individual components. In order to discover such hierarchies in temporal networks, Tatti [ECML PKDD 2018] introduced the temporal agony problem Seg-Agony. Here, the goal is to assign each vertex a certain rank (from 1 to $k$) such that arcs only point from lower ranks to higher ranks. Backward arcs are penalized depending on the difference between the corresponding ranks. Since arcs may change over time, each vertex is allowed to change its rank $\ell\ge 1$ times in order to minimize the overall penalty $α$ (called temporal agony). We study the parameterized complexity of Seg-Agony with a special focus on the number $k$ of possible ranks for which we identify the precise complexity border. We show that the problem is polynomial-time solvable for $k=2$, NP-hard for $k=3$ and $\ell=1$ but polynomial-time solvable for constant $α$, and NP-hard for $k=4$ and $\ell=1$ even for $α=0$. We further show a polynomial-time algorithm for a constant number $n$ of vertices and fixed-parameter tractability for the combined parameter $n+\ell$.

Authors: Tom-Lukas Breitkopf, Vincent Froese, Anton Herrmann, Pascal Kunz

Real-world networks are often organized in several layers forming a hierarchy which determines the interaction between the individual components. In order to discover such hierarchies in temporal networks, Tatti [ECML PKDD 2018] introduced the temporal agony problem Seg-Agony. Here, the goal is to assign each vertex a certain rank (from 1 to $k$) such that arcs only point from lower ranks to higher ranks. Backward arcs are penalized depending on the difference between the corresponding ranks. Since arcs may change over time, each vertex is allowed to change its rank $\ell\ge 1$ times in order to minimize the overall penalty $α$ (called temporal agony). We study the parameterized complexity of Seg-Agony with a special focus on the number $k$ of possible ranks for which we identify the precise complexity border. We show that the problem is polynomial-time solvable for $k=2$, NP-hard for $k=3$ and $\ell=1$ but polynomial-time solvable for constant $α$, and NP-hard for $k=4$ and $\ell=1$ even for $α=0$. We further show a polynomial-time algorithm for a constant number $n$ of vertices and fixed-parameter tractability for the combined parameter $n+\ell$.

Friday, August 21 2026, 00:00

A Canonical m-Atomic Decomposition of Bipartite Graphs via a Grid Model

from arXiv: Data Structures and Algorithms

Authors: Béla Jónás

We study finite, connected, simple bipartite graphs in a grid model, in which a graph is drawn as a rectangular array and its structure is read off from empty subrectangles, called holes. In this model we attach to every brick a numerical invariant, its characteristic m, the difference between the number of rows and the largest proper independent set. A brick is excessive if m > 0. Our main results concern this invariant. We determine the characteristic of a disconnected excessive brick from those of its components, showing that m = min_i min{m_i, imb(W_i)} while the imbalance is additive; and we prove that an m-excessive brick is m-extendable, that is, every matching of size m extends to a maximum matching. Since Plummer's notion of n-extendability is defined only for graphs carrying a perfect matching, and our proof nowhere uses balance, the characteristic extends that notion canonically to unbalanced bipartite graphs. Using the characteristic we partition bipartite graphs into eleven structural classes. The underlying decomposition into atomic blocks is the classical decomposition into elementary components, and the description of the maximum proper independent sets by ideals of the block poset is likewise classical; the paper states precisely which results are classical and are not claimed here. What the grid model adds is a single geometric framework in which holes, characteristics and the block triangular form are read off from one picture.

Authors: Béla Jónás

We study finite, connected, simple bipartite graphs in a grid model, in which a graph is drawn as a rectangular array and its structure is read off from empty subrectangles, called holes. In this model we attach to every brick a numerical invariant, its characteristic m, the difference between the number of rows and the largest proper independent set. A brick is excessive if m > 0. Our main results concern this invariant. We determine the characteristic of a disconnected excessive brick from those of its components, showing that m = min_i min{m_i, imb(W_i)} while the imbalance is additive; and we prove that an m-excessive brick is m-extendable, that is, every matching of size m extends to a maximum matching. Since Plummer's notion of n-extendability is defined only for graphs carrying a perfect matching, and our proof nowhere uses balance, the characteristic extends that notion canonically to unbalanced bipartite graphs. Using the characteristic we partition bipartite graphs into eleven structural classes. The underlying decomposition into atomic blocks is the classical decomposition into elementary components, and the description of the maximum proper independent sets by ideals of the block poset is likewise classical; the paper states precisely which results are classical and are not claimed here. What the grid model adds is a single geometric framework in which holes, characteristics and the block triangular form are read off from one picture.

Friday, August 21 2026, 00:00

The Greedy Superstring Algorithm Achieves Ratio 2 for Strings of Length 6 Already

from arXiv: Data Structures and Algorithms

Authors: Nikolai Chukhin, Alexander S. Kulikov, Ivan Mihajlin, Alexander Smal

In the Shortest Common Superstring (SCS) problem, one is given a set of strings and asked to find a shortest string containing every input string as a substring. The greedy superstring conjecture states that the natural greedy algorithm, which repeatedly merges a pair of strings with maximum overlap, has approximation ratio $2$. The greedy algorithm runs in linear time and is arguably the simplest approximation algorithm for SCS. If the conjecture holds, it would also surpass the approximation guarantees of the best known algorithms. The conjecture has remained open for 40 years. Even the approximation ratio $ρ_k$ for instances whose strings all have length $k$ is unknown; for every $k \ge 3$, we have $2 - 1/k \le ρ_k \le \min\{(k+1)/2, 3.396\}$. We prove that strings of length 6 already suffice to achieve approximation ratio $2$: $ρ_k \ge 2$ for every $k \ge 6$. We also prove that $ρ_3 = 9/5$, completely characterizing the worst-case behavior of the greedy algorithm for strings of length 3.

Authors: Nikolai Chukhin, Alexander S. Kulikov, Ivan Mihajlin, Alexander Smal

In the Shortest Common Superstring (SCS) problem, one is given a set of strings and asked to find a shortest string containing every input string as a substring. The greedy superstring conjecture states that the natural greedy algorithm, which repeatedly merges a pair of strings with maximum overlap, has approximation ratio $2$. The greedy algorithm runs in linear time and is arguably the simplest approximation algorithm for SCS. If the conjecture holds, it would also surpass the approximation guarantees of the best known algorithms. The conjecture has remained open for 40 years. Even the approximation ratio $ρ_k$ for instances whose strings all have length $k$ is unknown; for every $k \ge 3$, we have $2 - 1/k \le ρ_k \le \min\{(k+1)/2, 3.396\}$. We prove that strings of length 6 already suffice to achieve approximation ratio $2$: $ρ_k \ge 2$ for every $k \ge 6$. We also prove that $ρ_3 = 9/5$, completely characterizing the worst-case behavior of the greedy algorithm for strings of length 3.

Friday, August 21 2026, 00:00

New Complexity Results for Fair Repetitive Scheduling

from arXiv: Data Structures and Algorithms

Authors: Moran Koren, Michael L. Pinedo, Dvir Shabtay

We revisit the problem of finding fair solutions to repetitive scheduling problems with a single machine. In this problem, we are given a set of $n$ clients and a planning horizon consisting of $q$ periods (days). Each day, every client submits a single job that must be processed by the machine. The objective is to construct a set of $q$ schedules, one for each day, such that the quality of service (QoS) received by each client meets a predefined threshold. The QoS measure may be any standard scheduling criterion, such as the total waiting time or total completion time of a client's jobs over the entire planning horizon. This problem has been studied in the literature, with previous works providing complexity classifications and approximation algorithms for various QoS measures. Nevertheless, several important questions remain open. In this paper, we resolve three of these questions and identify several additional directions for future research.

Authors: Moran Koren, Michael L. Pinedo, Dvir Shabtay

We revisit the problem of finding fair solutions to repetitive scheduling problems with a single machine. In this problem, we are given a set of $n$ clients and a planning horizon consisting of $q$ periods (days). Each day, every client submits a single job that must be processed by the machine. The objective is to construct a set of $q$ schedules, one for each day, such that the quality of service (QoS) received by each client meets a predefined threshold. The QoS measure may be any standard scheduling criterion, such as the total waiting time or total completion time of a client's jobs over the entire planning horizon. This problem has been studied in the literature, with previous works providing complexity classifications and approximation algorithms for various QoS measures. Nevertheless, several important questions remain open. In this paper, we resolve three of these questions and identify several additional directions for future research.

Friday, August 21 2026, 00:00

Palette Sparsification for General Uniform Hypergraphs

from arXiv: Data Structures and Algorithms

Authors: Ruizhe Shi

We prove a palette sparsification theorem for general $r$-uniform hypergraphs. For all sufficiently large $n$, every $r\ge 3$, and every $α\ge 7.1$, we show that an $n$-vertex $r$-uniform hypergraph of maximum degree $Δ$ is w.h.p. colorable from independently sampled lists of size $O(\sqrt{\log n})$ drawn from an ambient palette of size $\lceil αΔ^{1/(r-1)}\rceil$. The $\sqrt{\log n}$ dependence is asymptotically tight.

Authors: Ruizhe Shi

We prove a palette sparsification theorem for general $r$-uniform hypergraphs. For all sufficiently large $n$, every $r\ge 3$, and every $α\ge 7.1$, we show that an $n$-vertex $r$-uniform hypergraph of maximum degree $Δ$ is w.h.p. colorable from independently sampled lists of size $O(\sqrt{\log n})$ drawn from an ambient palette of size $\lceil αΔ^{1/(r-1)}\rceil$. The $\sqrt{\log n}$ dependence is asymptotically tight.

Friday, August 21 2026, 00:00

A simple and practical $o(\sqrt{n})$-time algorithm for shortest paths in power law graphs

from arXiv: Data Structures and Algorithms

Authors: Jiaqi Mao

Computing shortest paths in large graphs is, and remains, a fundamental and practically motivated problem. While many algorithms were proposed to calculate shortest path between pairs of vertices efficiently, many of them (index-based methods) require substantial preprocessing, while others (traversal-based methods) have higher time complexity. In this paper, we propose and analyze Pruned Bidirectional Search (PBS), a simple sublinear approximation algorithm for power-law graphs with parameter $β\in[2,3)$: our algorithm does not require any preprocessing, yet exhibits performance comparable to light index-based algorithms (of linear or sublinear index size): that is, PBS runs in time $O(n^{(1-1/\log\log n)/2})$ and, with high probability, returns a path with length within $\frac{41}{32}$ of the shortest path. Moreover, if one does allow a $n^{Θ(2-1/\log\log n)}$-time preprocessing step, its query time improves to $n^{Θ(1/\log\log n})$. We complement our theoretical results by experiments on both real-world and synthetic power-law graphs, which show that PBS is typically $1.84\times$-$7.76\times$ times faster than existing alternatives, while achieving an approximation ratio at most 1.05.

Authors: Jiaqi Mao

Computing shortest paths in large graphs is, and remains, a fundamental and practically motivated problem. While many algorithms were proposed to calculate shortest path between pairs of vertices efficiently, many of them (index-based methods) require substantial preprocessing, while others (traversal-based methods) have higher time complexity. In this paper, we propose and analyze Pruned Bidirectional Search (PBS), a simple sublinear approximation algorithm for power-law graphs with parameter $β\in[2,3)$: our algorithm does not require any preprocessing, yet exhibits performance comparable to light index-based algorithms (of linear or sublinear index size): that is, PBS runs in time $O(n^{(1-1/\log\log n)/2})$ and, with high probability, returns a path with length within $\frac{41}{32}$ of the shortest path. Moreover, if one does allow a $n^{Θ(2-1/\log\log n)}$-time preprocessing step, its query time improves to $n^{Θ(1/\log\log n})$. We complement our theoretical results by experiments on both real-world and synthetic power-law graphs, which show that PBS is typically $1.84\times$-$7.76\times$ times faster than existing alternatives, while achieving an approximation ratio at most 1.05.

Friday, August 21 2026, 00:00

Breaking the $2^n$ Barrier for Counting Linear Extensions with a Short Elementary Algorithm

from arXiv: Data Structures and Algorithms

Authors: Keigo Oka

A linear extension of a finite partially ordered set is a total ordering that respects the partial order. We give a deterministic exact algorithm that counts the linear extensions of an arbitrary $n$-element poset in time $O^*(1.89^n)$, where $O^*(\cdot)$ suppresses polynomial factors. This breaks the $2^n$ barrier for the general problem and resolves a question explicitly posed by Koivisto at Dagstuhl 2013. The proof refines an argument of Kozma for two-dimensional posets. A chain partition handles the case in which the poset is sufficiently far from an antichain. Otherwise, fix a maximum antichain (a largest set of pairwise incomparable elements). For each of its elements that has a comparable element above it outside the antichain, we record only which such element appears first. A decoding lemma enumerates the resulting patterns from their multiplicities. Once a pattern is fixed, each antichain element has a release condition and at most one deadline, so the dynamic program stores only the number of released elements in each deadline class. A stars-and-bars count bounds the total number of states.

Authors: Keigo Oka

A linear extension of a finite partially ordered set is a total ordering that respects the partial order. We give a deterministic exact algorithm that counts the linear extensions of an arbitrary $n$-element poset in time $O^*(1.89^n)$, where $O^*(\cdot)$ suppresses polynomial factors. This breaks the $2^n$ barrier for the general problem and resolves a question explicitly posed by Koivisto at Dagstuhl 2013. The proof refines an argument of Kozma for two-dimensional posets. A chain partition handles the case in which the poset is sufficiently far from an antichain. Otherwise, fix a maximum antichain (a largest set of pairwise incomparable elements). For each of its elements that has a comparable element above it outside the antichain, we record only which such element appears first. A decoding lemma enumerates the resulting patterns from their multiplicities. Once a pattern is fixed, each antichain element has a release condition and at most one deadline, so the dynamic program stores only the number of released elements in each deadline class. A stars-and-bars count bounds the total number of states.

Friday, August 21 2026, 00:00

Better than gold

from Scott Aaronson

What’s about the only thing more badass than a 17-year-old winning a gold medal at the International Olympiad in Informatics (IOI)? That 17-year-old intentionally forfeiting his gold medal by wearing an Israeli flag while the medal was announced, defying the IOI’s boycott of Israel (for background on this boycott, see my post from 2024). Kol […]

What’s about the only thing more badass than a 17-year-old winning a gold medal at the International Olympiad in Informatics (IOI)?

That 17-year-old intentionally forfeiting his gold medal by wearing an Israeli flag while the medal was announced, defying the IOI’s boycott of Israel (for background on this boycott, see my post from 2024).

Kol HaKavod (mad respect) to Yotam Budnik, who incredibly, has also won a Gold Medal (which he was allowed to keep, apparently) at the International Math Olympiad. And congratulations to the entire Israeli team, which (incredibly) would apparently have had a higher overall score than the US team, had it been allowed to compete as an official team at all.

By Scott

Thursday, August 20 2026, 16:27

PhD/MS at Tennessee Tech University (apply by October 1, 2026)

from CCI: jobs

A fully-funded PhD position and MS positions with RA/TA support are available under the supervision of Prof. Prantar Ghosh at Tennessee Tech University starting Jan 2027 (Spring 2027 semester). Research will focus broadly on graph algorithms. A good mathematical background and prior experience in Theoretical CS is required. Please email CV and a brief description […]

A fully-funded PhD position and MS positions with RA/TA support are available under the supervision of Prof. Prantar Ghosh at Tennessee Tech University starting Jan 2027 (Spring 2027 semester). Research will focus broadly on graph algorithms. A good mathematical background and prior experience in Theoretical CS is required. Please email CV and a brief description of background to the email below.

Website: https://sites.google.com/view/prantarg/home
Email: pghosh@tntech.edu

By shacharlovett

Thursday, August 20 2026, 15:23

Quantum Speedups Require Structure or Depth

from arXiv: Computational Complexity

Authors: Guy Blanc, Jordan Docter, Carmen Strassle, Li-Yang Tan

One of the most basic conjectures in quantum complexity theory states that every $t$-query quantum algorithm can be simulated on most inputs by a $\mathrm{poly}(t)$-query classical algorithm. If true, this would provide broad justification for the need for structure in quantum speedups. We settle this conjecture for parallel quantum algorithms, showing that every $t$-query $d$-round quantum algorithm can be simulated on most inputs with $t^{O(d^2)}$ classical queries. This suggests that for unstructured problems, superpolynomial speedups would require quantum circuits of superconstant depth, and exponential speedups would further require polynomial depth. In contrast, most known speedups for structured problems are achieved by highly parallel, low-depth algorithms. Our techniques also carry new implications for the status of $\mathsf{BPP}$ vs. $\mathsf{BQP}$ relative to a random oracle, a similarly longstanding problem.

Authors: Guy Blanc, Jordan Docter, Carmen Strassle, Li-Yang Tan

One of the most basic conjectures in quantum complexity theory states that every $t$-query quantum algorithm can be simulated on most inputs by a $\mathrm{poly}(t)$-query classical algorithm. If true, this would provide broad justification for the need for structure in quantum speedups. We settle this conjecture for parallel quantum algorithms, showing that every $t$-query $d$-round quantum algorithm can be simulated on most inputs with $t^{O(d^2)}$ classical queries. This suggests that for unstructured problems, superpolynomial speedups would require quantum circuits of superconstant depth, and exponential speedups would further require polynomial depth. In contrast, most known speedups for structured problems are achieved by highly parallel, low-depth algorithms. Our techniques also carry new implications for the status of $\mathsf{BPP}$ vs. $\mathsf{BQP}$ relative to a random oracle, a similarly longstanding problem.

Thursday, August 20 2026, 00:00

Structure and Complexity of 2-Nilpotent Mal'cev Algebras

from arXiv: Computational Complexity

Authors: Patrick Wynne

We investigate the structure of central extensions for algebras in a congruence modular variety. We use a multisorted algebraic object called a clonoid to understand the term clone of such a central extension. We develop the difference clonoid of such a central extension and use it to show that the number of $2$-step nilpotent algebras on a fixed finite set is finite if and only if the set is of squarefree order. The subpower membership problem for a finite algebraic structure $\mathbb{A}$ is the problem of deciding on input $a_1,\dots,a_k, b \in A^n$, whether $b$ is in the subalgebra of $\mathbb{A}^n$ generated by $a_1, \dots, a_k$. We show that for a large class of nilpotent Mal'cev algebras the subpower membership problem is solvable in polynomial time, in particular for $2$-step nilpotent Mal'cev algebras of squarefree order.

Authors: Patrick Wynne

We investigate the structure of central extensions for algebras in a congruence modular variety. We use a multisorted algebraic object called a clonoid to understand the term clone of such a central extension. We develop the difference clonoid of such a central extension and use it to show that the number of $2$-step nilpotent algebras on a fixed finite set is finite if and only if the set is of squarefree order. The subpower membership problem for a finite algebraic structure $\mathbb{A}$ is the problem of deciding on input $a_1,\dots,a_k, b \in A^n$, whether $b$ is in the subalgebra of $\mathbb{A}^n$ generated by $a_1, \dots, a_k$. We show that for a large class of nilpotent Mal'cev algebras the subpower membership problem is solvable in polynomial time, in particular for $2$-step nilpotent Mal'cev algebras of squarefree order.

Thursday, August 20 2026, 00:00

Lower Bounds for Domination-Type Problems Parameterized by Rank-Width

from arXiv: Computational Complexity

Authors: Chenghua Liu, Boning Meng

For graphs of rank-width $w$, the algorithms of Bui-Xuan, Telle, and Vatshelle (\emph{Theor. Comput. Sci.}, 2013) for fixed finite/cofinite $(σ,ρ)$-problems and of Bergougnoux and Kanté (\emph{SIAM J. Discrete Math.}, 2021) for Connected Dominating Set run in $2^{O(w^2)}n^{O(1)}$ time. Bergougnoux, Korhonen, and Nederlof (STACS 2023) proved a matching lower bound under the Exponential Time Hypothesis (ETH) for \emph{Weighted} Dominating Set, but left the unweighted problem open. We prove that, unless ETH fails, Dominating Set admits no $2^{o(w^2)}n^{O(1)}$-time algorithm, even on split graphs and, separately, on bipartite graphs of diameter at most four, and even with a rank-decomposition or witnessing vertex order supplied. The proof replaces the earlier weights by a two-guard gadget and uses a low-rank equality gadget to carry $k^2$ assignment bits through cuts of rank $O(k)$. The construction also gives the same lower bound for Independent, Connected, and Total Dominating Set on restricted graph classes and applies to a broad family of $(σ,ρ)$-set problems. This family includes cases in which $σ$ is neither finite nor cofinite and contains the entire nontrivial cofinite--cofinite minimization regime. Every solution within the target budget has target size and corresponds bijectively to a satisfying assignment. Under the counting Exponential Time Hypothesis ($\#\mathrm{ETH}$), the same bounds therefore hold for counting solutions of size at most or exactly the target. Together with the known algorithms, our results show that the quadratic dependence on the rank-width $w$ is optimal up to constant factors in the exponent for the classical problems above and throughout the covered finite/cofinite regime.

Authors: Chenghua Liu, Boning Meng

For graphs of rank-width $w$, the algorithms of Bui-Xuan, Telle, and Vatshelle (\emph{Theor. Comput. Sci.}, 2013) for fixed finite/cofinite $(σ,ρ)$-problems and of Bergougnoux and Kanté (\emph{SIAM J. Discrete Math.}, 2021) for Connected Dominating Set run in $2^{O(w^2)}n^{O(1)}$ time. Bergougnoux, Korhonen, and Nederlof (STACS 2023) proved a matching lower bound under the Exponential Time Hypothesis (ETH) for \emph{Weighted} Dominating Set, but left the unweighted problem open. We prove that, unless ETH fails, Dominating Set admits no $2^{o(w^2)}n^{O(1)}$-time algorithm, even on split graphs and, separately, on bipartite graphs of diameter at most four, and even with a rank-decomposition or witnessing vertex order supplied. The proof replaces the earlier weights by a two-guard gadget and uses a low-rank equality gadget to carry $k^2$ assignment bits through cuts of rank $O(k)$. The construction also gives the same lower bound for Independent, Connected, and Total Dominating Set on restricted graph classes and applies to a broad family of $(σ,ρ)$-set problems. This family includes cases in which $σ$ is neither finite nor cofinite and contains the entire nontrivial cofinite--cofinite minimization regime. Every solution within the target budget has target size and corresponds bijectively to a satisfying assignment. Under the counting Exponential Time Hypothesis ($\#\mathrm{ETH}$), the same bounds therefore hold for counting solutions of size at most or exactly the target. Together with the known algorithms, our results show that the quadratic dependence on the rank-width $w$ is optimal up to constant factors in the exponent for the classical problems above and throughout the covered finite/cofinite regime.

Thursday, August 20 2026, 00:00

Quantum Mixedness Testing with Pauli Measurements

from arXiv: Computational Complexity

Authors: Jayadev Acharya, Abhilash Dharmavarapu, Yuhan Liu, Nengkun Yu

We consider a fundamental problem of \emph{mixedness testing}: Given $n$ copies of an $N$-qubit state $ρ$, determine whether $ρ= \mathbb{I}_d/d$ or $\|ρ-\mathbb{I}_d/d\|_1 \geq \varepsilon$ with high probability, where $d = 2^N$. In particular, we focus on performing this task in the practical setting of single-qubit measurements, where measurements are prepared independently on each qubit. We provide a nearly complete picture of single-qubit mixedness tesing by showing $n = \widetildeΘ\left(\sqrt{10}^N/\varepsilon^2\right)$. To establish our lower bound, we introduce a new measurement-dependent lower bound framework for adaptive single-copy state certification. For the upper bound, we present a randomized Pauli basis measurement protocol, which relies on a new primitive for computationally efficient uniformity testing of correlation-concentrated distributions on the Boolean hypercube.

Authors: Jayadev Acharya, Abhilash Dharmavarapu, Yuhan Liu, Nengkun Yu

We consider a fundamental problem of \emph{mixedness testing}: Given $n$ copies of an $N$-qubit state $ρ$, determine whether $ρ= \mathbb{I}_d/d$ or $\|ρ-\mathbb{I}_d/d\|_1 \geq \varepsilon$ with high probability, where $d = 2^N$. In particular, we focus on performing this task in the practical setting of single-qubit measurements, where measurements are prepared independently on each qubit. We provide a nearly complete picture of single-qubit mixedness tesing by showing $n = \widetildeΘ\left(\sqrt{10}^N/\varepsilon^2\right)$. To establish our lower bound, we introduce a new measurement-dependent lower bound framework for adaptive single-copy state certification. For the upper bound, we present a randomized Pauli basis measurement protocol, which relies on a new primitive for computationally efficient uniformity testing of correlation-concentrated distributions on the Boolean hypercube.

Thursday, August 20 2026, 00:00

On the quantum communication complexity of total functions

from arXiv: Computational Complexity

Authors: Dmytro Gavinsky

We present a total function with a polylogarithmic two-message quantum protocol, whereas every randomised protocol, even with arbitrarily many rounds, requires polynomial communication.

Authors: Dmytro Gavinsky

We present a total function with a polylogarithmic two-message quantum protocol, whereas every randomised protocol, even with arbitrarily many rounds, requires polynomial communication.

Thursday, August 20 2026, 00:00

Hardness of Forcing Unique Perfect Matchings in Bipartite Graphs of Maximum Degree 3

from arXiv: Computational Complexity

Authors: Ryoma Aoshima, Takashi Horiyama, Atsuki Nagao, Fumiya Sakamoto, Hibiki Sato, Kazuhisa Seto, Karin Umebayashi

In a graph $G$, a set of edges $F$ is called a \emph{forcing set} if there exists a unique perfect matching $M$ such that $F \subseteq M$. Similarly, a set of edges $A$ is called an \emph{anti-forcing set} if the graph with edge set $ E(G)\setminus A$ has a unique perfect matching. It is known that, given a bipartite graph $G$ of maximum degree~$3$ and a perfect matching $M$, the problem of deciding whether there exists a forcing set of size at most $k$ for $M$ is NP-complete. Moreover, given a bipartite graph $G$ of maximum degree~$4$ and a perfect matching $M$, the problem of deciding whether there exists an anti-forcing set of size at most $k$ for $M$ is NP-complete. Furthermore, given a bipartite graph of maximum degree~$5$, the problem of deciding whether there exists a perfect matching $M$ that can be made unique by a forcing set of size at most $k$ is also NP-complete. In contrast, the computational complexity of deciding whether there exists a perfect matching $M$ that can be made unique by an anti-forcing set of size at most $k$ is not known, even for general graphs. In this paper, we show that all of these problems remain NP-complete even when restricted to bipartite graphs of maximum degree~$3$.

Authors: Ryoma Aoshima, Takashi Horiyama, Atsuki Nagao, Fumiya Sakamoto, Hibiki Sato, Kazuhisa Seto, Karin Umebayashi

In a graph $G$, a set of edges $F$ is called a \emph{forcing set} if there exists a unique perfect matching $M$ such that $F \subseteq M$. Similarly, a set of edges $A$ is called an \emph{anti-forcing set} if the graph with edge set $ E(G)\setminus A$ has a unique perfect matching. It is known that, given a bipartite graph $G$ of maximum degree~$3$ and a perfect matching $M$, the problem of deciding whether there exists a forcing set of size at most $k$ for $M$ is NP-complete. Moreover, given a bipartite graph $G$ of maximum degree~$4$ and a perfect matching $M$, the problem of deciding whether there exists an anti-forcing set of size at most $k$ for $M$ is NP-complete. Furthermore, given a bipartite graph of maximum degree~$5$, the problem of deciding whether there exists a perfect matching $M$ that can be made unique by a forcing set of size at most $k$ is also NP-complete. In contrast, the computational complexity of deciding whether there exists a perfect matching $M$ that can be made unique by an anti-forcing set of size at most $k$ is not known, even for general graphs. In this paper, we show that all of these problems remain NP-complete even when restricted to bipartite graphs of maximum degree~$3$.

Thursday, August 20 2026, 00:00

Good Stabilizer Codes from Shallow Clifford Circuits with Random Matchings

from arXiv: Computational Complexity

Authors: Emile Anand, Elia Gorokhovsky, Jennifer Hritz, Jingtong Sun

Encoding quantum information with low circuit overhead is a fundamental challenge in fault-tolerant quantum computation. Random circuits provide a natural mechanism for rapidly spreading logical information through simple gates applied in parallel. Brown and Fawzi showed that random Clifford circuits on two-qubit Clifford gates provide such encoders that achieve the quantum Gilbert-Varshamov rate-distance tradeoff with depth $O(\log^3 n)$. We show that the same asymptotic tradeoff is attained in optimal $O(\log n)$ depth under a gate distribution with a more restricted support. For every fixed $δ>0$ and sufficiently large $n$, if $\frac kn < 1 - H(\frac{d}{n}) - \frac{d}{n}\log_2 3 - δ$, we can construct random circuits of depth $O(\log n)$ which define, with high probability, an $[n,k]$ stabilizer code of distance at least $d+1$, which matches the $Ω(\log n)$ light-cone lower bound for linear distance encoders. Our ensemble employs a random matching circuit architecture consisting of $T$ independent permutation-invariant layers. In each layer, the qubits are paired up by a uniformly random perfect matching, and a random independent two-qubit Clifford gate is applied to each pair. The gate distribution need not be uniform over, or even have full support on, the two-qubit Clifford group; rather, we allow for very general distributions on Clifford gates satisfying three regularity conditions. In particular, the construction can be implemented using $n/2$ CNOT gates on randomly matched pairs in each layer, with parallel one-qubit Clifford twirls. These regularity conditions allow us to reduce the second-moment dynamics of our random circuits to a reversible Markov chain on binary support strings. We establish logarithmic hitting-time bounds for this Markov chain and comparisons of its stationary distribution to prove the coding properties of the circuits.

Authors: Emile Anand, Elia Gorokhovsky, Jennifer Hritz, Jingtong Sun

Encoding quantum information with low circuit overhead is a fundamental challenge in fault-tolerant quantum computation. Random circuits provide a natural mechanism for rapidly spreading logical information through simple gates applied in parallel. Brown and Fawzi showed that random Clifford circuits on two-qubit Clifford gates provide such encoders that achieve the quantum Gilbert-Varshamov rate-distance tradeoff with depth $O(\log^3 n)$. We show that the same asymptotic tradeoff is attained in optimal $O(\log n)$ depth under a gate distribution with a more restricted support. For every fixed $δ>0$ and sufficiently large $n$, if $\frac kn < 1 - H(\frac{d}{n}) - \frac{d}{n}\log_2 3 - δ$, we can construct random circuits of depth $O(\log n)$ which define, with high probability, an $[n,k]$ stabilizer code of distance at least $d+1$, which matches the $Ω(\log n)$ light-cone lower bound for linear distance encoders. Our ensemble employs a random matching circuit architecture consisting of $T$ independent permutation-invariant layers. In each layer, the qubits are paired up by a uniformly random perfect matching, and a random independent two-qubit Clifford gate is applied to each pair. The gate distribution need not be uniform over, or even have full support on, the two-qubit Clifford group; rather, we allow for very general distributions on Clifford gates satisfying three regularity conditions. In particular, the construction can be implemented using $n/2$ CNOT gates on randomly matched pairs in each layer, with parallel one-qubit Clifford twirls. These regularity conditions allow us to reduce the second-moment dynamics of our random circuits to a reversible Markov chain on binary support strings. We establish logarithmic hitting-time bounds for this Markov chain and comparisons of its stationary distribution to prove the coding properties of the circuits.

Thursday, August 20 2026, 00:00

Formal Verification of Romanov's Triplet Logic: A Verified Filter for Sliding-window 3-CNF with Application to Structured Formulas

from arXiv: Computational Complexity

Authors: Dmitry V. Alexandrov

We present the first mechanised formalisation of Romanov's Triplet Logic (TLS) in the Rocq proof assistant. TLS is a triplet-based combinatorial framework for reasoning about compatible paths through layered triplet structures, called Compact Triplets Structures (CTS), and their intersection via Romanov's Effective Procedure, which we refer to as Simple Vertex Intersection (SVI). Originally motivated by Boolean satisfiability, TLS constitutes a self-contained mathematical theory whose formal properties had not been previously established. We formalise the core of TLS in Rocq, including Compact Triplets Formulas (CTF), CTS, hyperstructures, clearing, and SVI. For the well-formed sliding-window fragment we verify a clause-by-clause CNF-to-CTF translation, the clearing procedure, and aligned intersection, and we prove explicit polynomial-time bounds for the filter stages. Our main contribution is a precise correctness boundary: the existence of a joint satisfying set implies non-emptiness of SVI, but the converse does not hold in general; for aligned structures we recover a complete bi-implication, extended to systems of structures. We also formalise soundness of grouped-window translation and exhibit a formal counterexample to its completeness. We introduce VFR, an extracted OCaml prototype that provides a verified decision procedure for the sliding-window fragment and a sound one-sided filter for general 3-CNF, with a Python runtime and reproducible Docker packaging. Benchmarks on random and structured instances confirm the predicted behaviour, and the complete toolchain is available as a curated Zenodo artifact. The Rocq development comprises more than 23,000 lines of code across seventeen files, with 427 proved lemmas and theorems and zero admitted goals.

Authors: Dmitry V. Alexandrov

We present the first mechanised formalisation of Romanov's Triplet Logic (TLS) in the Rocq proof assistant. TLS is a triplet-based combinatorial framework for reasoning about compatible paths through layered triplet structures, called Compact Triplets Structures (CTS), and their intersection via Romanov's Effective Procedure, which we refer to as Simple Vertex Intersection (SVI). Originally motivated by Boolean satisfiability, TLS constitutes a self-contained mathematical theory whose formal properties had not been previously established. We formalise the core of TLS in Rocq, including Compact Triplets Formulas (CTF), CTS, hyperstructures, clearing, and SVI. For the well-formed sliding-window fragment we verify a clause-by-clause CNF-to-CTF translation, the clearing procedure, and aligned intersection, and we prove explicit polynomial-time bounds for the filter stages. Our main contribution is a precise correctness boundary: the existence of a joint satisfying set implies non-emptiness of SVI, but the converse does not hold in general; for aligned structures we recover a complete bi-implication, extended to systems of structures. We also formalise soundness of grouped-window translation and exhibit a formal counterexample to its completeness. We introduce VFR, an extracted OCaml prototype that provides a verified decision procedure for the sliding-window fragment and a sound one-sided filter for general 3-CNF, with a Python runtime and reproducible Docker packaging. Benchmarks on random and structured instances confirm the predicted behaviour, and the complete toolchain is available as a curated Zenodo artifact. The Rocq development comprises more than 23,000 lines of code across seventeen files, with 427 proved lemmas and theorems and zero admitted goals.

Thursday, August 20 2026, 00:00

The Limits of Black-Box Reductions for All-Pairs Triangle Detection

from arXiv: Data Structures and Algorithms

Authors: Nathan Sheffield, Virginia Vassilevska Williams, Zoe Xi

For any tripartite relation $R\subseteq \mathbb{Z}^3$, the $R$-Triangle problem asks, given an edge-weighted graph, whether it contains a triangle whose weights form a triple in $R$. The All-Edge $R$-Triangle problem asks to determine for every edge whether it is contained in such a triangle. It is known that $R$-Triangle and All-Edge $R$-Triangle are subcubically fine-grained equivalent for every $R$ [Vassilevska W.-Williams'10]. However, while it is conjectured that these problems are tightly equivalent, this reduction only shows that if $R$-Triangle has an $O(n^{3-ε})$-time algorithm for some $ε>0$, then All-Edge $R$-Triangle has an $O(n^{3-ε/3})$-time algorithm. This paper provides a strong unconditional barrier to a tight equivalence: the reduction of [Vassilevska W.-Williams'10] is optimal for black-box reductions that work for arbitrary $R$. We give further results about black-box reductions between a variety of $R$-triangle problems. Our positive results yield new reductions between several classes of triangle and matrix problems --- for instance, we demonstrate that an $O(n^{2.53})$-time algorithm for computing equality or dominance product would imply an improvement on known algorithms for computing boolean $(\min, +)$-product, giving the first conditional lower bound for dominance and equality product. Our negative results can be thought of as barriers against natural fine-grained proof techniques. Besides the result that a tighter equivalence between $R$-Triangle and All-Edge $R$-Triangle is not possible, we also show that no appropriately "black-box" reductions are capable of demonstrating a subcubic equivalence between triangle counting and binary integer matrix multiplication, or a tight equivalence between boolean matrix multiplication and listing $n^2$ triangles, and more, despite the fact that all of these equivalences are conjectured to hold.

Authors: Nathan Sheffield, Virginia Vassilevska Williams, Zoe Xi

For any tripartite relation $R\subseteq \mathbb{Z}^3$, the $R$-Triangle problem asks, given an edge-weighted graph, whether it contains a triangle whose weights form a triple in $R$. The All-Edge $R$-Triangle problem asks to determine for every edge whether it is contained in such a triangle. It is known that $R$-Triangle and All-Edge $R$-Triangle are subcubically fine-grained equivalent for every $R$ [Vassilevska W.-Williams'10]. However, while it is conjectured that these problems are tightly equivalent, this reduction only shows that if $R$-Triangle has an $O(n^{3-ε})$-time algorithm for some $ε>0$, then All-Edge $R$-Triangle has an $O(n^{3-ε/3})$-time algorithm. This paper provides a strong unconditional barrier to a tight equivalence: the reduction of [Vassilevska W.-Williams'10] is optimal for black-box reductions that work for arbitrary $R$. We give further results about black-box reductions between a variety of $R$-triangle problems. Our positive results yield new reductions between several classes of triangle and matrix problems --- for instance, we demonstrate that an $O(n^{2.53})$-time algorithm for computing equality or dominance product would imply an improvement on known algorithms for computing boolean $(\min, +)$-product, giving the first conditional lower bound for dominance and equality product. Our negative results can be thought of as barriers against natural fine-grained proof techniques. Besides the result that a tighter equivalence between $R$-Triangle and All-Edge $R$-Triangle is not possible, we also show that no appropriately "black-box" reductions are capable of demonstrating a subcubic equivalence between triangle counting and binary integer matrix multiplication, or a tight equivalence between boolean matrix multiplication and listing $n^2$ triangles, and more, despite the fact that all of these equivalences are conjectured to hold.

Thursday, August 20 2026, 00:00

Computing All Optimal Partial $p$-Wasserstein Matchings on the Line

from arXiv: Data Structures and Algorithms

Authors: Sebastian Angrick, Jacobus Conradi, Mónika Csikós, Niko Hastrich, Danny Mittal, André Nusser, Krzystof Onak, Sharath Raghvendra

For $p \ge 1$, the $p$-Wasserstein distance measures the minimum cost of transporting probability mass between distributions, where moving unit mass between two points costs the $p$th power of their distance. For discrete distributions in one dimension, full transport is especially simple: after sorting, mass is matched in order along the line. By contrast, partial and unbalanced transport on the line remains much less understood. Recently, Chapel and Tavenard [ICLR'25] showed that, for $p=1$, all optimal partial transport plans between distributions supported on $n$ points, with uniform mass at each point, can be computed in $O(n\log n)$ time by exploiting the metric structure of the cost. For $p>1$, this structure no longer applies, and existing approaches require $Ω(n^2)$ time. Our main contribution is an FFT-based data structure for balanced-interval transport queries, which bypasses this quadratic bottleneck and yields an $O(p\,n\log^2 n)$-time algorithm for computing all optimal partial transports on the line for every finite $p\ge 1$. We also provide an open-source C++ implementation that outperforms the state-of-the-art baseline on a range of synthetic instances. Finally, we establish a conditional lower bound for $p=\infty$: any subquadratic-time algorithm for computing all optimal partial transport plan costs on the line would violate the $(\min,+)$-Convolution Hypothesis. This separates the problem from full optimal transport, which is solvable in $O(n\log n)$.

Authors: Sebastian Angrick, Jacobus Conradi, Mónika Csikós, Niko Hastrich, Danny Mittal, André Nusser, Krzystof Onak, Sharath Raghvendra

For $p \ge 1$, the $p$-Wasserstein distance measures the minimum cost of transporting probability mass between distributions, where moving unit mass between two points costs the $p$th power of their distance. For discrete distributions in one dimension, full transport is especially simple: after sorting, mass is matched in order along the line. By contrast, partial and unbalanced transport on the line remains much less understood. Recently, Chapel and Tavenard [ICLR'25] showed that, for $p=1$, all optimal partial transport plans between distributions supported on $n$ points, with uniform mass at each point, can be computed in $O(n\log n)$ time by exploiting the metric structure of the cost. For $p>1$, this structure no longer applies, and existing approaches require $Ω(n^2)$ time. Our main contribution is an FFT-based data structure for balanced-interval transport queries, which bypasses this quadratic bottleneck and yields an $O(p\,n\log^2 n)$-time algorithm for computing all optimal partial transports on the line for every finite $p\ge 1$. We also provide an open-source C++ implementation that outperforms the state-of-the-art baseline on a range of synthetic instances. Finally, we establish a conditional lower bound for $p=\infty$: any subquadratic-time algorithm for computing all optimal partial transport plan costs on the line would violate the $(\min,+)$-Convolution Hypothesis. This separates the problem from full optimal transport, which is solvable in $O(n\log n)$.

Thursday, August 20 2026, 00:00

Cell-Probe Lower Bounds and Complexity-Preserving Reductions for Suffix Array Queries

from arXiv: Data Structures and Algorithms

Authors: Dominik Kempa, Tomasz Kociumaka

For a text $T$ of length $n$ over an alphabet of size $σ$, its suffix array lists the starting positions of the suffixes of $T$ in lexicographic order, and its inverse suffix array gives the lexicographic rank of the suffix starting at each position. Since the introduction of the FM-index and the compressed suffix array in 2000, both queries have been supported in $O((\log_σn)^ε)$ time using $O(n\logσ)$ bits, for any constant $ε>0$. Yet no nontrivial time-space lower bound for suffix-array queries was known. We give the first such lower bound. Specifically, we show that, in the cell-probe model with $Θ(\log n)$-bit words, every $S$-bit data structure answering suffix-array queries on binary strings of length at most $n$ has query time $Ω(\log\log n/\log((S/n)\log\log n))$. Consequently, every structure using $O(n(\log\log n)^{O(1)})$ bits requires $Ω(\log\log n/\log\log\log n)$ query time, while constant query time requires $Ω(n\log^εn)$ bits for some constant $ε>0$. In particular, no $O(n)$-bit suffix-array representation for binary texts supports constant-time queries, answering the 25-year-old question of Grossi and Vitter. We also give exact complexity-preserving equivalences between suffix-array access and simpler prefix queries on short strings. For every $2\leqσ\leq n$, suffix-array queries are equivalent to prefix-select queries, and inverse-suffix-array queries are equivalent to prefix-special-rank queries. The reductions in both directions preserve all four standard measures up to constant factors: space, query time, preprocessing time, and preprocessing space. Unlike previous reductions, they incur no additive $O(\log\log n)$ query-time term. Thus, the corresponding prefix-query problems capture suffix-array and inverse-suffix-array access without asymptotic loss in any of the four measures.

Authors: Dominik Kempa, Tomasz Kociumaka

For a text $T$ of length $n$ over an alphabet of size $σ$, its suffix array lists the starting positions of the suffixes of $T$ in lexicographic order, and its inverse suffix array gives the lexicographic rank of the suffix starting at each position. Since the introduction of the FM-index and the compressed suffix array in 2000, both queries have been supported in $O((\log_σn)^ε)$ time using $O(n\logσ)$ bits, for any constant $ε>0$. Yet no nontrivial time-space lower bound for suffix-array queries was known. We give the first such lower bound. Specifically, we show that, in the cell-probe model with $Θ(\log n)$-bit words, every $S$-bit data structure answering suffix-array queries on binary strings of length at most $n$ has query time $Ω(\log\log n/\log((S/n)\log\log n))$. Consequently, every structure using $O(n(\log\log n)^{O(1)})$ bits requires $Ω(\log\log n/\log\log\log n)$ query time, while constant query time requires $Ω(n\log^εn)$ bits for some constant $ε>0$. In particular, no $O(n)$-bit suffix-array representation for binary texts supports constant-time queries, answering the 25-year-old question of Grossi and Vitter. We also give exact complexity-preserving equivalences between suffix-array access and simpler prefix queries on short strings. For every $2\leqσ\leq n$, suffix-array queries are equivalent to prefix-select queries, and inverse-suffix-array queries are equivalent to prefix-special-rank queries. The reductions in both directions preserve all four standard measures up to constant factors: space, query time, preprocessing time, and preprocessing space. Unlike previous reductions, they incur no additive $O(\log\log n)$ query-time term. Thus, the corresponding prefix-query problems capture suffix-array and inverse-suffix-array access without asymptotic loss in any of the four measures.

Thursday, August 20 2026, 00:00

Simple Low-Overhead Communication-Efficient String Reconciliation and Edit Distance

from arXiv: Data Structures and Algorithms

Authors: Michael T. Goodrich, Gonzalo Navarro, Claire A. To

Suppose two parties, Alice and Bob, hold long character strings, $X$ and $Y$, respectively, and they are interested in determining how similar $X$ and $Y$ are. {Moreover, they want to exchange the strings with cost proportional to their degree of dissimilarity.} Such problems arise, for example, in database and file system synchronization operations, as well as in DNA sequence comparisons. Since the strings are long, we are interested in methods that are communication-efficient and have low overhead in terms of the computations that Alice and Bob must perform, when the strings are similar enough. In this paper, we provide simple low-overhead communication-efficient algorithms for such string reconciliation and edit distance problems. In the general case, %where the only assumption we make is that we have an upper bound, $k$, on the edit distance between $X$ and $Y$, we show how to determine the edit distance $k$ between $X$ and~$Y$ using only $O(k^2\log n)$ bits of communication and optimal $O(n)$ time overhead, with high probability. For specialized cases, such as typical English text or DNA sequences, where we can make additional well-justified assumptions about the distribution of the input strings, we show how to achieve possibly better bounds, such as $O(k\log^3 n)$ bits of communication.

Authors: Michael T. Goodrich, Gonzalo Navarro, Claire A. To

Suppose two parties, Alice and Bob, hold long character strings, $X$ and $Y$, respectively, and they are interested in determining how similar $X$ and $Y$ are. {Moreover, they want to exchange the strings with cost proportional to their degree of dissimilarity.} Such problems arise, for example, in database and file system synchronization operations, as well as in DNA sequence comparisons. Since the strings are long, we are interested in methods that are communication-efficient and have low overhead in terms of the computations that Alice and Bob must perform, when the strings are similar enough. In this paper, we provide simple low-overhead communication-efficient algorithms for such string reconciliation and edit distance problems. In the general case, %where the only assumption we make is that we have an upper bound, $k$, on the edit distance between $X$ and $Y$, we show how to determine the edit distance $k$ between $X$ and~$Y$ using only $O(k^2\log n)$ bits of communication and optimal $O(n)$ time overhead, with high probability. For specialized cases, such as typical English text or DNA sequences, where we can make additional well-justified assumptions about the distribution of the input strings, we show how to achieve possibly better bounds, such as $O(k\log^3 n)$ bits of communication.

Thursday, August 20 2026, 00:00

Constant-Time Inverse Suffix Array Queries in Compact Space and Sublinear-Time Construction of Suffix Array Indexes

from arXiv: Data Structures and Algorithms

Authors: Dominik Kempa, Tomasz Kociumaka

For a text $T\in[0..σ)^n$ with $2\leqσ\leq n$, its suffix array orders the suffix starting positions lexicographically, while its inverse suffix array maps each position to its suffix's rank. Since compressed suffix arrays and FM-indexes appeared in 2000, a central goal has been to support both queries in $O(n\logσ)$ bits. Thankachan recently reduced inverse suffix array query time to $O(\log\log n/\log\logσ)$, but constant time remained open. We give the first inverse suffix array structure with optimal space and query time: $O(n\logσ)$ bits and $O(1)$ time. For binary texts, this unconditionally separates the two queries for deterministic structures, since every $O(n)$-bit suffix array structure in the cell-probe model with $Θ(\log n)$-bit cells has worst-case query time $Ω(\log\log n/\log\log\log n)$. Construction is a second challenge: linear time can take $Θ(\log_σ n)$ times as long as reading the input or writing a compact index. Previously, sublinear construction was known for only one such index supporting both queries. In the word RAM with $Θ(\log n)$-bit words, we deterministically construct the new structure and two suffix array families from the packed text in $O(n\min(1,\logσ/\sqrt{\log n}))$ time. For $B\geq2$, the first family uses $O(n\logσ(1+\log_B\log_σn))$ bits and has query time $O(B(1+\log_B\log_σn))$, whereas the second uses $O(Bn\logσ(1+\log_B\log_σn))$ bits and has query time $O(1+\log_B\log_σn)$. Each has peak preprocessing space bounded by its index size. For binary texts, the second family matches the deterministic cell-probe time-space lower bound whenever $B\geq(\log\log n)^{Ω(1)}$, and, outside the slowest-query regimes, improving the deterministic construction time to $o(n/\sqrt{\log n})$ would yield an equally fast Dictionary Matching algorithm.

Authors: Dominik Kempa, Tomasz Kociumaka

For a text $T\in[0..σ)^n$ with $2\leqσ\leq n$, its suffix array orders the suffix starting positions lexicographically, while its inverse suffix array maps each position to its suffix's rank. Since compressed suffix arrays and FM-indexes appeared in 2000, a central goal has been to support both queries in $O(n\logσ)$ bits. Thankachan recently reduced inverse suffix array query time to $O(\log\log n/\log\logσ)$, but constant time remained open. We give the first inverse suffix array structure with optimal space and query time: $O(n\logσ)$ bits and $O(1)$ time. For binary texts, this unconditionally separates the two queries for deterministic structures, since every $O(n)$-bit suffix array structure in the cell-probe model with $Θ(\log n)$-bit cells has worst-case query time $Ω(\log\log n/\log\log\log n)$. Construction is a second challenge: linear time can take $Θ(\log_σ n)$ times as long as reading the input or writing a compact index. Previously, sublinear construction was known for only one such index supporting both queries. In the word RAM with $Θ(\log n)$-bit words, we deterministically construct the new structure and two suffix array families from the packed text in $O(n\min(1,\logσ/\sqrt{\log n}))$ time. For $B\geq2$, the first family uses $O(n\logσ(1+\log_B\log_σn))$ bits and has query time $O(B(1+\log_B\log_σn))$, whereas the second uses $O(Bn\logσ(1+\log_B\log_σn))$ bits and has query time $O(1+\log_B\log_σn)$. Each has peak preprocessing space bounded by its index size. For binary texts, the second family matches the deterministic cell-probe time-space lower bound whenever $B\geq(\log\log n)^{Ω(1)}$, and, outside the slowest-query regimes, improving the deterministic construction time to $o(n/\sqrt{\log n})$ would yield an equally fast Dictionary Matching algorithm.

Thursday, August 20 2026, 00:00

Space-Efficient Hierholzer for Undirected Graphs

from arXiv: Data Structures and Algorithms

Authors: Elena Grigorescu, Ziad Ismaili Alaoui, Tamio-Vesa Nakajima, Shayan Shirazi Mofrad, Sebastian Wild

We present a simple linear-time algorithm that outputs an Eulerian tour of an undirected multigraph with $n$ vertices and $m$ edges, if one exists, in $O(m)$ time and using $O(n)$ words of working memory. The input is given as read-only adjacency lists, and the output is written to an append-only stream in traversal order. Our algorithm first finds a sparse spanning circuit (a skeleton), then traverses the circuit step-by-step, repeatedly outputting further circuits rooted at the current vertex. This solves a problem left open by Ismaili Alaoui, Plump, and Wild (SOSA 2026): their space-efficient variant of Hierholzer's algorithm handles general directed multigraphs, but it is unclear how to generalize it to general undirected multigraphs. Our result completes the picture in the read-only model for space-efficient output of Eulerian tours.

Authors: Elena Grigorescu, Ziad Ismaili Alaoui, Tamio-Vesa Nakajima, Shayan Shirazi Mofrad, Sebastian Wild

We present a simple linear-time algorithm that outputs an Eulerian tour of an undirected multigraph with $n$ vertices and $m$ edges, if one exists, in $O(m)$ time and using $O(n)$ words of working memory. The input is given as read-only adjacency lists, and the output is written to an append-only stream in traversal order. Our algorithm first finds a sparse spanning circuit (a skeleton), then traverses the circuit step-by-step, repeatedly outputting further circuits rooted at the current vertex. This solves a problem left open by Ismaili Alaoui, Plump, and Wild (SOSA 2026): their space-efficient variant of Hierholzer's algorithm handles general directed multigraphs, but it is unclear how to generalize it to general undirected multigraphs. Our result completes the picture in the read-only model for space-efficient output of Eulerian tours.

Thursday, August 20 2026, 00:00

Online Permutation Embedding: Optimal Stopping and Scaling Laws

from arXiv: Data Structures and Algorithms

Authors: Dylan J. Altschuler, Quentin Dubroff, Konstantin Tikhomirov

We study optimal online algorithms for embedding a permutation $π$ of $[k]$ into an iid stream of uniform $[0,1]$ random variables. This problem is a broad generalization of the classical online monotone subsequence selection problem, recovered in the special case $π=\mathrm{Id}_k$. Our first contribution is an efficiently solvable dynamic program for the optimal embedding time of any $k$-permutation $π$. This dynamic program also yields an explicit optimal online embedding algorithm. We then investigate the asymptotic scaling of the optimal embedding time for uniformly random target permutations, as well as the extremal problem of identifying the permutations with largest expected online embedding time. Our second main result shows that, to first order, random permutations are strictly faster to embed than monotone permutations, which in turn are strictly faster to embed than the extremal permutations. This separation stands in sharp contrast to prevailing conjectures and heuristics in the offline theory of permutation embeddings.

Authors: Dylan J. Altschuler, Quentin Dubroff, Konstantin Tikhomirov

We study optimal online algorithms for embedding a permutation $π$ of $[k]$ into an iid stream of uniform $[0,1]$ random variables. This problem is a broad generalization of the classical online monotone subsequence selection problem, recovered in the special case $π=\mathrm{Id}_k$. Our first contribution is an efficiently solvable dynamic program for the optimal embedding time of any $k$-permutation $π$. This dynamic program also yields an explicit optimal online embedding algorithm. We then investigate the asymptotic scaling of the optimal embedding time for uniformly random target permutations, as well as the extremal problem of identifying the permutations with largest expected online embedding time. Our second main result shows that, to first order, random permutations are strictly faster to embed than monotone permutations, which in turn are strictly faster to embed than the extremal permutations. This separation stands in sharp contrast to prevailing conjectures and heuristics in the offline theory of permutation embeddings.

Thursday, August 20 2026, 00:00

Tight Energy Lower Bounds for Distributed Graph Algorithms

from arXiv: Data Structures and Algorithms

Authors: Fabien Dufoulon, Gopal Pandurangan, Peter Robinson

There has been a significant recent interest in designing distributed algorithms in the SLEEPING model that minimize the {energy (a.k.a awake) complexity, which measures the number of rounds a node is awake during the algorithm. A node spends non-trivial resources (messages, energy, etc.) only when it is awake and not while sleeping. Energy complexity has been studied for various fundamental problems with respect to minimizing the maximum (worst-case) or the average number of rounds a node is awake. It has been shown that the energy complexities of several fundamental problems such as leader election (LE), broadcast, Minimum Spanning Tree (MST), Maximal Independent Set (MIS) is exponentially smaller compared to their respective best-possible round complexities in the standard CONGEST model (where nodes can only send messages of small size). This raises a fundamental question of whether such significant energy gains are possible for many other fundamental problems. Our main contribution is a general and powerful technique for showing energy lower bounds using information theory. It gives almost a "plug-in" way to show energy lower bounds for various problems in the standard CONGEST model. Our information-theoretic technique allows us to leverage known lower bounds on communication complexity to obtain new, almost optimal (up to logarithmic factors) polynomial (in $n$) lower bounds on energy complexity --- for both worst-case and average-case --- for fundamental graph problems such as triangle enumeration, All-Pairs Shortest Paths (APSP), diameter computation, minimum weight cycle, Maximum Independent Set (MaxIS), Minimum Dominating Set (MinDS), Minimum Vertex Cover (MinVC). The energy lower bounds of these problems match their respective round lower bounds, implying that one cannot obtain any significant gains in energy complexity.

Authors: Fabien Dufoulon, Gopal Pandurangan, Peter Robinson

There has been a significant recent interest in designing distributed algorithms in the SLEEPING model that minimize the {energy (a.k.a awake) complexity, which measures the number of rounds a node is awake during the algorithm. A node spends non-trivial resources (messages, energy, etc.) only when it is awake and not while sleeping. Energy complexity has been studied for various fundamental problems with respect to minimizing the maximum (worst-case) or the average number of rounds a node is awake. It has been shown that the energy complexities of several fundamental problems such as leader election (LE), broadcast, Minimum Spanning Tree (MST), Maximal Independent Set (MIS) is exponentially smaller compared to their respective best-possible round complexities in the standard CONGEST model (where nodes can only send messages of small size). This raises a fundamental question of whether such significant energy gains are possible for many other fundamental problems. Our main contribution is a general and powerful technique for showing energy lower bounds using information theory. It gives almost a "plug-in" way to show energy lower bounds for various problems in the standard CONGEST model. Our information-theoretic technique allows us to leverage known lower bounds on communication complexity to obtain new, almost optimal (up to logarithmic factors) polynomial (in $n$) lower bounds on energy complexity --- for both worst-case and average-case --- for fundamental graph problems such as triangle enumeration, All-Pairs Shortest Paths (APSP), diameter computation, minimum weight cycle, Maximum Independent Set (MaxIS), Minimum Dominating Set (MinDS), Minimum Vertex Cover (MinVC). The energy lower bounds of these problems match their respective round lower bounds, implying that one cannot obtain any significant gains in energy complexity.

Thursday, August 20 2026, 00:00

Minimizing the Makespan Approximately on Two Identical Parallel Machines with a Loading--Unloading Server

from arXiv: Data Structures and Algorithms

Authors: Keramat Hasani, Frank Werner

We study makespan minimisation on two identical parallel machines that share a single server for both loading and unloading. Each job must be loaded, processed without interruption on its assigned machine, and unloaded immediately after processing, with a common positive integer duration for all loading and unloading operations. We prove that the decision problem is NP-complete for every fixed server-operation duration and strongly NP-complete when this duration is part of the input. We then analyse ordinary list scheduling and the longest-processing-time rule in the non-unit setting. List scheduling has a tight supremum ratio of two. For the longest-processing-time rule, we obtain the exact worst-case ratio when all processing times are at least the server-operation duration, and derive new parameter-dependent lower and upper bounds for unrestricted instances. The results show that both processing-time granularity and blocking generated by short jobs shape the approximation behaviour of the common-server problem.

Authors: Keramat Hasani, Frank Werner

We study makespan minimisation on two identical parallel machines that share a single server for both loading and unloading. Each job must be loaded, processed without interruption on its assigned machine, and unloaded immediately after processing, with a common positive integer duration for all loading and unloading operations. We prove that the decision problem is NP-complete for every fixed server-operation duration and strongly NP-complete when this duration is part of the input. We then analyse ordinary list scheduling and the longest-processing-time rule in the non-unit setting. List scheduling has a tight supremum ratio of two. For the longest-processing-time rule, we obtain the exact worst-case ratio when all processing times are at least the server-operation duration, and derive new parameter-dependent lower and upper bounds for unrestricted instances. The results show that both processing-time granularity and blocking generated by short jobs shape the approximation behaviour of the common-server problem.

Thursday, August 20 2026, 00:00

Decisive Margins in Differentially Private Voting

from arXiv: Data Structures and Algorithms

Authors: Quentin Hillebrand, Pasin Manurangsi, Vorapong Suppakitpaisarn, Phanu Vajanopath

Differential privacy protects individual voting records by injecting randomness into the published outcome, but this noise can lead to erroneous results when an election is close. We study how precise central differential privacy and local differential privacy can be for common voting rules, including Plurality, Condorcet, Maximin, Plurality with Runoff, and Single Transferable Vote (STV). Our measure of precision is the margin of victory needed for a private mechanism to return the same winner as the non-private rule with high probability. We give private algorithms for publishing the winner and prove upper bounds on the required margin for these algorithms. We also prove lower bounds showing that nontrivial margins are necessary; many of these bounds match the corresponding upper bounds up to logarithmic factors. For STV, an information-theoretic upper bound matches the lower bound, but we prove that this guarantee cannot be achieved in polynomial time unless NP $\subseteq$ BPP. This gives a rare example of a computationally tractable task that becomes intractable when one simultaneously requires differential privacy and utility.

Authors: Quentin Hillebrand, Pasin Manurangsi, Vorapong Suppakitpaisarn, Phanu Vajanopath

Differential privacy protects individual voting records by injecting randomness into the published outcome, but this noise can lead to erroneous results when an election is close. We study how precise central differential privacy and local differential privacy can be for common voting rules, including Plurality, Condorcet, Maximin, Plurality with Runoff, and Single Transferable Vote (STV). Our measure of precision is the margin of victory needed for a private mechanism to return the same winner as the non-private rule with high probability. We give private algorithms for publishing the winner and prove upper bounds on the required margin for these algorithms. We also prove lower bounds showing that nontrivial margins are necessary; many of these bounds match the corresponding upper bounds up to logarithmic factors. For STV, an information-theoretic upper bound matches the lower bound, but we prove that this guarantee cannot be achieved in polynomial time unless NP $\subseteq$ BPP. This gives a rare example of a computationally tractable task that becomes intractable when one simultaneously requires differential privacy and utility.

Thursday, August 20 2026, 00:00

An FPRAS for Antiferromagnetic Ising Models on Random Regular Bipartite Graphs

from arXiv: Data Structures and Algorithms

Authors: Zhidan Li, Kuan Yang

We design randomized approximation schemes for the partition function of antiferromagnetic Ising models with uniform external field on random regular bipartite graphs. Our algorithm generalizes the approach of Kocurek, Oveis Gharan and Tjowasi (arXiv, 2026) for hard-core models on the same random graph model beyond the uniqueness threshold. We show that, as long as $λ$ is upper bounded by a constant and $λ(1 - β) \lesssim Δ^{-1/2}$, an efficient randomized algorithm approximates the partition function with high probability. The algorithm first truncates configurations that are large on either side of the bipartition and then samples from Gibbs distributions conditioned on fixed sizes on one or both sides. To choose an optimal truncation bound, we establish concentration properties of the Gibbs distribution on random regular bipartite graphs. Then we apply high-dimensional expansion and prove trickle-down theorems to obtain fast samplers for the conditioned distributions.

Authors: Zhidan Li, Kuan Yang

We design randomized approximation schemes for the partition function of antiferromagnetic Ising models with uniform external field on random regular bipartite graphs. Our algorithm generalizes the approach of Kocurek, Oveis Gharan and Tjowasi (arXiv, 2026) for hard-core models on the same random graph model beyond the uniqueness threshold. We show that, as long as $λ$ is upper bounded by a constant and $λ(1 - β) \lesssim Δ^{-1/2}$, an efficient randomized algorithm approximates the partition function with high probability. The algorithm first truncates configurations that are large on either side of the bipartition and then samples from Gibbs distributions conditioned on fixed sizes on one or both sides. To choose an optimal truncation bound, we establish concentration properties of the Gibbs distribution on random regular bipartite graphs. Then we apply high-dimensional expansion and prove trickle-down theorems to obtain fast samplers for the conditioned distributions.

Thursday, August 20 2026, 00:00

Online Service with Per-Batch Maximum Delay

from arXiv: Data Structures and Algorithms

Authors: Tianhang Lu, Runtian Ren, Shengcai Liu, Ke Tang

We study online service with one maximum-waiting-time charge per service batch. Requests arrive at points of a finite metric, and a mobile server pays for its movement and, for each service walk, the maximum waiting time among the requests served by that walk. We distinguish elective service, where an encountered request may be left pending, from automatic service, where every encounter serves it. Although the two semantics have different optimal schedule structures, we prove that their offline optimal values are equal. On a finite line and on an explicitly represented weighted tree, the common offline value is computable by polynomial-time dynamic programming, whereas exact optimization on arbitrary finite metrics is NP-hard. For the online problem, we prove a metric-independent group-trajectory certificate lemma that charges spatially separated request groups to two parity classes of time windows. It yields deterministic polynomial-time competitive ratios 10 on a line, 12 on a weighted tree, and 20 on an arbitrary finite metric, under both service semantics. With an exact metric-Steiner-tree oracle, the general-metric ratio improves to 12. The polynomial algorithm uses a half-scaled running maximum of terminal-MST weights; the running maximum is necessary because terminal MST weight is not monotone under new arrivals. A fixed two-point line gives a deterministic visible-service lower bound of 3 for every metric class above. Finally, when request locations are hidden until visited, dyadic exploration is 84-competitive on a known finite line. This phenomenon is line-specific: one hidden request gives deterministic and randomized lower bounds 3 and 2 on a line, while a d-leaf unit star gives lower bounds 2d-1 and d.

Authors: Tianhang Lu, Runtian Ren, Shengcai Liu, Ke Tang

We study online service with one maximum-waiting-time charge per service batch. Requests arrive at points of a finite metric, and a mobile server pays for its movement and, for each service walk, the maximum waiting time among the requests served by that walk. We distinguish elective service, where an encountered request may be left pending, from automatic service, where every encounter serves it. Although the two semantics have different optimal schedule structures, we prove that their offline optimal values are equal. On a finite line and on an explicitly represented weighted tree, the common offline value is computable by polynomial-time dynamic programming, whereas exact optimization on arbitrary finite metrics is NP-hard. For the online problem, we prove a metric-independent group-trajectory certificate lemma that charges spatially separated request groups to two parity classes of time windows. It yields deterministic polynomial-time competitive ratios 10 on a line, 12 on a weighted tree, and 20 on an arbitrary finite metric, under both service semantics. With an exact metric-Steiner-tree oracle, the general-metric ratio improves to 12. The polynomial algorithm uses a half-scaled running maximum of terminal-MST weights; the running maximum is necessary because terminal MST weight is not monotone under new arrivals. A fixed two-point line gives a deterministic visible-service lower bound of 3 for every metric class above. Finally, when request locations are hidden until visited, dyadic exploration is 84-competitive on a known finite line. This phenomenon is line-specific: one hidden request gives deterministic and randomized lower bounds 3 and 2 on a line, while a d-leaf unit star gives lower bounds 2d-1 and d.

Thursday, August 20 2026, 00:00

Optimal Deterministic Fully Sparse Matrix Multiplication

from arXiv: Data Structures and Algorithms

Authors: Omar Graia

We give the first deterministic algorithm for fully sparse matrix multiplication that attains the optimal running-time exponent. This result matches the best previously known randomized algorithm running-time exponent. Given compatible matrices $A$ and $B$ over an arbitrary associative ring with identity, with $\operatorname{nnz}(A),\operatorname{nnz}(B)=O(n^{δ_{\mathrm{in}}})$ and $\operatorname{nnz}(AB)=O(n^{δ_{\mathrm{out}}})$, our algorithm finds the support of $AB$ and computes the product exactly in $$O\!\left(n^{β_R(δ_{\mathrm{in}},\min\{δ_{\mathrm{out}},2δ_{\mathrm{in}}\})+\varepsilon}\right)$$ operations, where $β_R(δ_{\mathrm{in}},δ)$ denotes the maximum of $δ_{\mathrm{in}}$ and $ω_{δ_{\mathrm{in}},R}(a,1,b)$ over all $a,b\in[0,1]$ satisfying $a+b=δ$. For dense inputs over a commutative ring, this bound simplifies to $O(n^{ω_R((δ_{\mathrm{out}}-1)_+,1,1)+\varepsilon})$. With the current rectangular matrix multiplication bounds, this is nearly quadratic, namely $O(n^{2+\varepsilon})$, for every $δ_\mathrm{out}\le1.321334$, improving the previous deterministic range of $δ_{\mathrm{out}}\le 0.642668$. To prove this result, we develop a general deterministic recovery technique that finds and fixes sparse parts of an unknown matrix while keeping temporary errors in denser parts under control.

Authors: Omar Graia

We give the first deterministic algorithm for fully sparse matrix multiplication that attains the optimal running-time exponent. This result matches the best previously known randomized algorithm running-time exponent. Given compatible matrices $A$ and $B$ over an arbitrary associative ring with identity, with $\operatorname{nnz}(A),\operatorname{nnz}(B)=O(n^{δ_{\mathrm{in}}})$ and $\operatorname{nnz}(AB)=O(n^{δ_{\mathrm{out}}})$, our algorithm finds the support of $AB$ and computes the product exactly in $$O\!\left(n^{β_R(δ_{\mathrm{in}},\min\{δ_{\mathrm{out}},2δ_{\mathrm{in}}\})+\varepsilon}\right)$$ operations, where $β_R(δ_{\mathrm{in}},δ)$ denotes the maximum of $δ_{\mathrm{in}}$ and $ω_{δ_{\mathrm{in}},R}(a,1,b)$ over all $a,b\in[0,1]$ satisfying $a+b=δ$. For dense inputs over a commutative ring, this bound simplifies to $O(n^{ω_R((δ_{\mathrm{out}}-1)_+,1,1)+\varepsilon})$. With the current rectangular matrix multiplication bounds, this is nearly quadratic, namely $O(n^{2+\varepsilon})$, for every $δ_\mathrm{out}\le1.321334$, improving the previous deterministic range of $δ_{\mathrm{out}}\le 0.642668$. To prove this result, we develop a general deterministic recovery technique that finds and fixes sparse parts of an unknown matrix while keeping temporary errors in denser parts under control.

Thursday, August 20 2026, 00:00

Algorithms for adaptive and heteroskedastic linear regression at the computational threshold

from arXiv: Data Structures and Algorithms

Authors: Spencer Compton, Tselil Schramm

We study finite-sample linear regression in the presence of varied and unknown label noise, focusing on the heteroskedastic and adaptive linear regression models. Heteroskedastic linear regression models settings where the labels are of varying quality. We receive $n$ pairs $(X_i,Y_i)$ with labels $Y_i=X_i^\topβ+\varepsilon_i$, where $\varepsilon_i\sim N(0,σ_i^2)$ and the variances are unknown to the estimator. One natural measurement of the difficulty of this problem is the number of samples $m$ for which $σ_i^2\le1$ (larger $m$ is easier). We obtain a polynomial-time estimator with rate $\tilde{O}((nd^3/m^4)^{1/6})$ when $m\gg d^{3/4}n^{1/4}$, as well as nearly-matching lower bounds. For $d=O(1)$, our estimator achieves error $o(1)$ when $m\gg n^{1/4}$, whereas $L_1$ regression and other traditional approaches require $m\gg n^{1/2}$. In adaptive linear regression, the errors are drawn i.i.d. from an unknown distribution $p$, and our goal is to design a generic estimator that performs nearly as well as the best custom estimator that knows $p$. We introduce a (computationally inefficient) adaptive estimator that, so long as $p$ is a mixture of $k$ symmetric log-concave densities, achieves error comparable with the optimal estimator that knows $p$ and has $\tildeΘ(n/k)$ samples. For $k=1$, we show that $L_q$ regression (with data-dependent $q$) gives a polynomial-time estimator. Finally, to study the computational limits of both problems, we introduce the planted linear regression problem, where $X_i\sim N(0,I_d)$, $m$ unknown samples are noiseless, and the rest have error $\varepsilon_i\sim N(0,1)$. We conjecture that recovering $β$ up to error $\ll\sqrt{d/n}$ (or exactly) may have an information-computation gap between $m=d+1$ and $m\sim d^{3/4}n^{1/4}$, as is suggested by our near-matching polynomial-time estimator and statistical query (SQ) lower bound.

Authors: Spencer Compton, Tselil Schramm

We study finite-sample linear regression in the presence of varied and unknown label noise, focusing on the heteroskedastic and adaptive linear regression models. Heteroskedastic linear regression models settings where the labels are of varying quality. We receive $n$ pairs $(X_i,Y_i)$ with labels $Y_i=X_i^\topβ+\varepsilon_i$, where $\varepsilon_i\sim N(0,σ_i^2)$ and the variances are unknown to the estimator. One natural measurement of the difficulty of this problem is the number of samples $m$ for which $σ_i^2\le1$ (larger $m$ is easier). We obtain a polynomial-time estimator with rate $\tilde{O}((nd^3/m^4)^{1/6})$ when $m\gg d^{3/4}n^{1/4}$, as well as nearly-matching lower bounds. For $d=O(1)$, our estimator achieves error $o(1)$ when $m\gg n^{1/4}$, whereas $L_1$ regression and other traditional approaches require $m\gg n^{1/2}$. In adaptive linear regression, the errors are drawn i.i.d. from an unknown distribution $p$, and our goal is to design a generic estimator that performs nearly as well as the best custom estimator that knows $p$. We introduce a (computationally inefficient) adaptive estimator that, so long as $p$ is a mixture of $k$ symmetric log-concave densities, achieves error comparable with the optimal estimator that knows $p$ and has $\tildeΘ(n/k)$ samples. For $k=1$, we show that $L_q$ regression (with data-dependent $q$) gives a polynomial-time estimator. Finally, to study the computational limits of both problems, we introduce the planted linear regression problem, where $X_i\sim N(0,I_d)$, $m$ unknown samples are noiseless, and the rest have error $\varepsilon_i\sim N(0,1)$. We conjecture that recovering $β$ up to error $\ll\sqrt{d/n}$ (or exactly) may have an information-computation gap between $m=d+1$ and $m\sim d^{3/4}n^{1/4}$, as is suggested by our near-matching polynomial-time estimator and statistical query (SQ) lower bound.

Thursday, August 20 2026, 00:00

New lectures, podcasts, summer school videos

from Turing's Invisible Hand

A bunch of new video content came out over the past couple of months, summarized here in case of interest: First Principles podcast series, featuring interviews with Barbara Liskov, Leslie Lamport, Alvin Roth, Paul Milgrom, Ron Rivest, Shafi Goldwasser, and Noam Nisan. Ergo lecture series on Computation and Its Limits: Series intro; Is There Anything […]

A bunch of new video content came out over the past couple of months, summarized here in case of interest:

First Principles podcast series, featuring interviews with Barbara Liskov, Leslie Lamport, Alvin Roth, Paul Milgrom, Ron Rivest, Shafi Goldwasser, and Noam Nisan.

Ergo lecture series on Computation and Its Limits: Series intro; Is There Anything Computers Can’t Do?; How Algorithms Outsmart Complexity; Easy Problems, Hard Problems; Two Worlds We Might Live In; AI, Quantum Computing, and Beyond. These lectures, aimed at a general audience, focus mostly on the developments in computability and complexity theory from the 1930s through the 1970s.

Videos from the 2026 Summer School on the Theory & Practice of Blockchain Consensus, featuring talks by Ittai Abraham (a16z crypto), Roger Wattenhofer (ETH Zurich/Anza), Dongning Guo (Northwestern University), Maria Apostolaki (Princeton University), Andrew Lewis-Pye (Commonware/London School of Economics), Sasha Spiegelman (Aptos), Francesco d’Amato (Ethereum Foundation), Yann Vonlanthen (Ethereum Foundation), Sourav Das (Category Labs), Guru Vamsi Policharla (Commonware), Alberto Sonnino (Mysten Labs), Patrick O’Grady (Commonware), Joachim Neu (a16z crypto), and Kartik Nayak (Duke University).

By timroughgarden

Wednesday, August 19 2026, 16:07

From legibility to participation

from Ben Recht

An emphasis shift for human-facing computing research

Part of the reason I brought up microconferences on Monday is that I was attending a great one this week on public feedback for AI, organized by Jessica Dai here at Berkeley. In the spirit of creating an archival footprint, Jess and I will have a lot to say about the workshop over the next few days. I’ll kick things off by describing what I talked about.

I opened with a provocation about the trap that policy-minded computer scientists and social scientists so easily fall into. Longtime argmin readers will recognize the pattern. If we want to raise the concerns of a public, we need to convincingly present “evidence” supporting those concerns to policymakers. “Evidence” means cold, hard quantifiable facts that are easy to explain to policymakers, not just anecdotes of harm. I’m sympathetic. If you want to advance an agenda you care about in a complex world, you have to make it simple for those in power to understand. Too many things are happening at once, there’s far too much nuance and ambiguity, policymakers can only keep so many in their heads, and only so many laws can be drafted and passed at any given time.

It makes sense then that people concerned with technocratic solutions spend so much of their time designing architectures of legibility. They focus on the right ways to summarize data, weigh competing interests, and write compelling reports. They build computational frameworks to compile complicated, singular events into useful statistical summaries. A nice chart is worth a thousand testimonies.

These architectures of legibility are what enable the inevitable quantification trap. To make things legible to decision makers, we quantify them. Since we agreed on transparent procedures, the quantified must be objective. Numbers are always objective, right? Objectivity buys analyses authority. And expert authority then becomes a tool of power.

The quantification trap has been a pervasive and mimetic signature of the information age. And it has become progressively invisible as computation has miniaturized and sublimated into ubiquity. Every moment of our lives is now surveilled and quantified, ready to be summarized into new systems of control.

I am not against quantification of social systems. I just want to consistently raise awareness of its hegemony. There are clear benefits to quantification. It buys us a level of intersubjectivity, as anyone can trace the path from evidence to summary statistic. This shared, standardized language lets us collaboratively govern complex societies.

On the other hand, the quantification trap removes discretion, forcing us to abide by rigid rules. Quantification erases individuals in its bucketing and summarization. And quantification enables structural violence, forcing citizens to constantly make themselves legible to those with power to avoid being punished.

The question I always get from technocrats after presenting these critiques of quantification and architectures of legibility is “What else could you do?” My answer is to think about an alternative type of social architecture, architectures of participation. Tim O’Reilly coined this term in the early aughts to describe what makes participatory culture work on the internet. Why do some software systems take off as collaborative efforts? Tim noted that many software and communication systems are designed for contribution. Open source software has countless success stories. We also have the legacy of internet communication, message boards, and the World Wide Web. We have the astounding body of knowledge that is Wikipedia. And we have a powerful public challenge to copyright that was Napster. This last example highlights that not every architecture of participation brings unambiguous good to every stakeholder. The lens of participation helps us think about what elevates voices and values directly through individual actions.

Architecture of participation subsumes many different perspectives on the design of social systems. It includes standard economic mechanism design, the rules of games we play, and the decision-making agreements established by anarchist groups. What distinguishes these systems from architectures of legibility is they aim to cultivate broad expertise from a broad group of people. They are ugly and organic by nature. They are structured agreements for interaction and discussion. They do not suppose a benevolent set of experts at the top will make decisions based on what they see. Mods often write explicit rules, but community patterns are encouraged to be emergent and reflexive. They let the community work together, in small spaces and large ones.

Architectures of participation focus on designing flexible agreements for flexible ends. They accept that there is no clear metric to maximize. Sure, you can build legibility dashboards to make sure your system isn’t crashing. Again, I’m not against quantification. However, the focus of participatory design is not quantification, but broadening engagement and diversifying served ends.

So what does this have to do with AI and public feedback? It is very weird that our contemporary AI took all of human knowledge, made something very interesting and very powerful, and then gave all of the rewards to a small group of people who whine all the time about how they have no power. This is a perversion of participation. Built on the labor and love of individuals, generative AI technology concentrated power. And then those in power convinced themselves they are powerless. San Francisco wants to abdicate all human agency and reduce us to making ourselves legible to an artificial bureaucratic god.

On the other hand, the data center protests are inspirational. Here you have a lot of people who are really upset for a complicated set of reasons about AI. It’s hard to say why they are so mad, and why this issue is so salient, but it’s undeniable that they are driving policy conversations. Their protests and organization have made them not legible, but unignorable.

AI doesn’t have to be exclusionary. We could build an AI that’s a public good. One that invites participation. One that involves known training data, participatory training data. We now know that if you train next-token predictors on collective intelligence, you end up with a quirky piece of software that speaks in natural language, solves impossible math problems, and does all of your coding. We can’t unsee that. But we don’t have to let a small group of whiny, weird people own it. We can use this insight to build a public infrastructure for collective, participatory intelligence.

Subscribe now

By Ben Recht

Wednesday, August 19 2026, 14:14

Centaur Math

from Computational Complexity

In the past, new PhD students would ask how they could succeed when they had to compete with the likes of say, Richard Karp or Avi Wigderson. I would say Karp and Wigderson have limited bandwidth and you can work on problems they don't work on, or think deeper about a problem than Karp or Wigderson has time to.

Now we get the same question but with names like Claude and ChatGPT and it's hard to make the same bandwidth argument. What do we tell them as we get closer to Math AGI?

What even is Math AGI? It's not that every math problem gets solved. I don't expect P vs NP to be solved anytime soon. It would require a completely new approach, and AI doesn't (yet) think outside the box, though it has a very large box.

Math AGI means that with rare exceptions, if AI can't solve a math problem then no human could either. If you need a proof, you'd have to pay for more cycles, or wait for the next new and improved model. Like the Turing test, we'll only truly realize we've reached Math AGI once we've gone well past it.

We haven't reached Math AGI yet and we may never fully get there. We have entered the world of Centaur Math. Mathematicians can still prove theorems AI can't, AI can prove some theorems mathematicians haven't yet proven, but the real strength comes with mathematicians and AI working together. Working with AI today is like having a pretty good PhD student, who has a huge broad base knowledge of mathematics, is a whiz at coding, but still needs direction, encouragement and verification.

Chess had a short centaur moment when humans and AI working together could beat the best human players and AI programs. Now, any human would play worse not following what AI says. Nevertheless, we still enjoy watching two sub-AI humans play chess against each other. I doubt the same would hold for sub-AI mathematicians.

So what do we tell the students? If you love math, do math. Embrace AI, use it to go further, not as a crutch. Challenge yourself and remain agile so you can find success whatever the future might hand us. And remember, math is not ultimately about the theorems we prove but how we understand the principles behind them, and that's a human endeavor not a machine one.

By Lance Fortnow

In the past, new PhD students would ask how they could succeed when they had to compete with the likes of say, Richard Karp or Avi Wigderson. I would say Karp and Wigderson have limited bandwidth and you can work on problems they don't work on, or think deeper about a problem than Karp or Wigderson has time to.

Now we get the same question but with names like Claude and ChatGPT and it's hard to make the same bandwidth argument. What do we tell them as we get closer to Math AGI?

What even is Math AGI? It's not that every math problem gets solved. I don't expect P vs NP to be solved anytime soon. It would require a completely new approach, and AI doesn't (yet) think outside the box, though it has a very large box.

Math AGI means that with rare exceptions, if AI can't solve a math problem then no human could either. If you need a proof, you'd have to pay for more cycles, or wait for the next new and improved model. Like the Turing test, we'll only truly realize we've reached Math AGI once we've gone well past it.

We haven't reached Math AGI yet and we may never fully get there. We have entered the world of Centaur Math. Mathematicians can still prove theorems AI can't, AI can prove some theorems mathematicians haven't yet proven, but the real strength comes with mathematicians and AI working together. Working with AI today is like having a pretty good PhD student, who has a huge broad base knowledge of mathematics, is a whiz at coding, but still needs direction, encouragement and verification.

Chess had a short centaur moment when humans and AI working together could beat the best human players and AI programs. Now, any human would play worse not following what AI says. Nevertheless, we still enjoy watching two sub-AI humans play chess against each other. I doubt the same would hold for sub-AI mathematicians.

So what do we tell the students? If you love math, do math. Embrace AI, use it to go further, not as a crutch. Challenge yourself and remain agile so you can find success whatever the future might hand us. And remember, math is not ultimately about the theorems we prove but how we understand the principles behind them, and that's a human endeavor not a machine one.

By Lance Fortnow

Wednesday, August 19 2026, 13:52

TR26-150 | Private PCPs from Product Expansion | Mitali Bafna, Nikhil Vyas

from ECCC Papers

The quantum analogue of the PCP theorem for QMA remains wide open. A central obstacle is the local indistinguishability of quantum codes: every sufficiently small view of an encoded witness is independent of the witness, seemingly preventing a local verifier from distinguishing YES from NO instances. One approach to this apparent paradox in the work of Anshu, Breuckmann and Nguyen, is to encode the witness in a quantum code and compute on it fault-tolerantly, successively reducing the encoding length until the answer is revealed. We study a classical relaxation of this approach based on the equivalent view of quantum codes as private randomized encodings from multiparty computation. Specifically, we ask whether one can construct circuits that compute on a private encoding of an NP witness, such that every sufficiently small fractional view of the honest computation transcript is independent of the witness (i.e. has quantum distance) and the computation remains correct despite a small fraction of adversarial bit-flip or X-errors in every layer. We construct such circuits and use the classical Cook--Levin theorem to obtain private PCPs for NP: the prescribed PCP encoding is randomized, and for each instance every view below the privacy threshold has the same distribution for all assignments, whether satisfying or not. For Circuit-SAT instances of size $n$, we get $\sqrt{n}$-query private PCPs of size $O(n\log n)$ over alphabet size $\mathrm{poly}(n)$, fractional privacy $\Omega(1/\log n)$ and constant soundness gap. Furthermore, conditional on a high-dimensional product expansion conjecture for Reed-Solomon codes, our PCPs have length $n^{1+o(1)}$, use $n^{o(1)}$ queries, and have fractional privacy and soundness gap $n^{-o(1)}$. Our construction is based on a new family of small-alphabet quantum codes which have near-linear rate, sparse $X$-checks that enable local testability for $X$-errors, support for multiplication (or transversal CCZ gates on the full logical space) and near-linear quantum distance using product expansion. The codes are obtained using tensor products of Reed--Solomon codes, and our key innovation is to choose the evaluation domains as multiplicative subgroups of pairwise coprime orders of $\mathbb{F}_q^\star$. A proof obtained by ChatGPT 5.6 Sol establishes constant 2-dimensional product expansion whenever both rates are bounded away from one, crossing the tight sum-of-rates-below-one barrier in the product expansion theorem of Polishchuk and Spielman. We conjecture the analogous statement in higher dimensions.

Wednesday, August 19 2026, 12:11

An Approximate Cauchy-Schwarz Inequality and Improved Bounds for Sherali-Adams Refutation of Semirandom CSPs

from arXiv: Computational Complexity

Authors: Pravesh K. Kothari, Andrew D. Lin

We formulate an approximate Cauchy-Schwarz inequality and show that it is satisfied by solutions to the Sherali-Adams linear programming hierarchy (interpreted as ``pseudo-distributions''). As a consequence, we resolve a question left open by the work of O'Donnell and Schramm [OS19] that they had explicitly attributed to the lack of such an inequality. A Cauchy-Schwarz inequality is exactly satisfied by pseudo-distributions satisfying the constraints of the sum-of-squares semidefinite programming hierarchy and already has scores of applications. However, the proof there requires global positive semidefiniteness. Our approximate version, on the other hand, relies only on local positive semidefiniteness satisfied by the Sherali-Adams pseudo-distributions. Our formulation loses an additive error that scales with the L1 norm of the coefficients of the constituent polynomials, and this loss is asymptotically tight. Our proof is elementary and relies on a simple sampling argument. As an application, we resolve a question left open in the work of O'Donnell and Schramm that gives a trade-off between constraint density and the Sherali-Adams degree for refuting random constraint satisfaction problems. Specifically, for odd arity CSPs, we show that the constraint density requirement for a given degree can be improved by a polynomial factor in $n$. Along the way, we observe that by a simple extension, the results in their work extend to a more general semirandom setting.

Authors: Pravesh K. Kothari, Andrew D. Lin

We formulate an approximate Cauchy-Schwarz inequality and show that it is satisfied by solutions to the Sherali-Adams linear programming hierarchy (interpreted as ``pseudo-distributions''). As a consequence, we resolve a question left open by the work of O'Donnell and Schramm [OS19] that they had explicitly attributed to the lack of such an inequality. A Cauchy-Schwarz inequality is exactly satisfied by pseudo-distributions satisfying the constraints of the sum-of-squares semidefinite programming hierarchy and already has scores of applications. However, the proof there requires global positive semidefiniteness. Our approximate version, on the other hand, relies only on local positive semidefiniteness satisfied by the Sherali-Adams pseudo-distributions. Our formulation loses an additive error that scales with the L1 norm of the coefficients of the constituent polynomials, and this loss is asymptotically tight. Our proof is elementary and relies on a simple sampling argument. As an application, we resolve a question left open in the work of O'Donnell and Schramm that gives a trade-off between constraint density and the Sherali-Adams degree for refuting random constraint satisfaction problems. Specifically, for odd arity CSPs, we show that the constraint density requirement for a given degree can be improved by a polynomial factor in $n$. Along the way, we observe that by a simple extension, the results in their work extend to a more general semirandom setting.

Wednesday, August 19 2026, 00:00

The Influence of Agent Models on the Complexity of Bus Routing

from arXiv: Computational Complexity

Authors: Eva Deltl, Christian Komusiewicz, Jurek Rostalsky, Johannes Schröder, Luca Pascal Staus

In bus routing, the task is to plan a bus route in a network with several agents, each of whom wants to travel from a starting point to a destination. A bus route should account for several factors, including agents' cost for reaching the bus stops, their travel time, or the energy consumption of the buses. We study the complexity of several variants of this problem, focusing on how the objective function and the models for agents' walking costs influence the problem complexity. After observing that even the simplest agent cost model leads to hardness on general networks, we consider networks with tree structure. Our main findings are as follows. First, allowing agent-specific cost models leads to hardness even on extremely limited trees such as stars. Second, consistent agent models (where agents differ only in their starting points and destinations) make the problem easier in some cases. Finally, allowing agents to choose between using the bus and walking directly can make the problem considerably harder. Most of our hardness results show not only classical NP-hardness but also parameterized intractability for the natural parameter $k$, the number of bus stops.

Authors: Eva Deltl, Christian Komusiewicz, Jurek Rostalsky, Johannes Schröder, Luca Pascal Staus

In bus routing, the task is to plan a bus route in a network with several agents, each of whom wants to travel from a starting point to a destination. A bus route should account for several factors, including agents' cost for reaching the bus stops, their travel time, or the energy consumption of the buses. We study the complexity of several variants of this problem, focusing on how the objective function and the models for agents' walking costs influence the problem complexity. After observing that even the simplest agent cost model leads to hardness on general networks, we consider networks with tree structure. Our main findings are as follows. First, allowing agent-specific cost models leads to hardness even on extremely limited trees such as stars. Second, consistent agent models (where agents differ only in their starting points and destinations) make the problem easier in some cases. Finally, allowing agents to choose between using the bus and walking directly can make the problem considerably harder. Most of our hardness results show not only classical NP-hardness but also parameterized intractability for the natural parameter $k$, the number of bus stops.

Wednesday, August 19 2026, 00:00

A Simple Algebraic Proof of the PCP Theorem

from arXiv: Computational Complexity

Authors: Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan, Madhu Sudan, Sophus Valentin Willumsgaard

We give the simplest known algebraic proof of the PCP theorem, involving only ingredients like code concatenation, polynomial interpolation, and polynomial multiplication. Specifically, we prove that graph 3-coloring has a polynomial-sized proof that can be verified by a verifier tossing logarithmically many coins and querying a constant number of bits in the proof. In particular, our proof does not involve any PCP compositions; notably, it does not invoke the NP-completeness of any fixed problem, such as SAT or 3-coloring, in the construction of the verifier. The main innovation in our work is a clean, coding theoretic, way to encode univariate polynomials that allows us to implement ``low-degree testing'' using just a constant number of bits of queries. Insights from recent attempts to simplify the PCP proof by the authors (STOC 2026) and Goldreich (ECCC 2025) allow us to observe that low-degree was the key bottleneck in converting previous algebraic constructions of the PCP verifier into a constant query PCP. Thus, by overcoming this bottleneck, we get the full PCP verifier using elementary and self-contained steps. As concrete support for the claimed simplicity, we include the full pseudocode of the PCP verifier, assuming finite field arithmetic, and a full description of the completeness (aka ``honest'') prover, assuming multivariate polynomial arithmetic including interpolation and evaluation, that fit in about a page each.

Authors: Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan, Madhu Sudan, Sophus Valentin Willumsgaard

We give the simplest known algebraic proof of the PCP theorem, involving only ingredients like code concatenation, polynomial interpolation, and polynomial multiplication. Specifically, we prove that graph 3-coloring has a polynomial-sized proof that can be verified by a verifier tossing logarithmically many coins and querying a constant number of bits in the proof. In particular, our proof does not involve any PCP compositions; notably, it does not invoke the NP-completeness of any fixed problem, such as SAT or 3-coloring, in the construction of the verifier. The main innovation in our work is a clean, coding theoretic, way to encode univariate polynomials that allows us to implement ``low-degree testing'' using just a constant number of bits of queries. Insights from recent attempts to simplify the PCP proof by the authors (STOC 2026) and Goldreich (ECCC 2025) allow us to observe that low-degree was the key bottleneck in converting previous algebraic constructions of the PCP verifier into a constant query PCP. Thus, by overcoming this bottleneck, we get the full PCP verifier using elementary and self-contained steps. As concrete support for the claimed simplicity, we include the full pseudocode of the PCP verifier, assuming finite field arithmetic, and a full description of the completeness (aka ``honest'') prover, assuming multivariate polynomial arithmetic including interpolation and evaluation, that fit in about a page each.

Wednesday, August 19 2026, 00:00

A Counting Lemma for Somewhat Restricted 3-APs

from arXiv: Computational Complexity

Authors: Amey Bhangale, Subhash Khot, Yang P. Liu, Dor Minzer

For a prime $p\geq 3$, a somewhat restricted $3$-AP in $\mathbb{F}_p^n$ is a triplet $(x,x+a,x+2a)$, where $x\in\mathbb{F}_p^n$ and $a\in \{0,1,2\}^n$. We prove a counting lemma for somewhat restricted $3$-APs in dense sets in $\mathbb{F}_p^n$. More precisely, we prove that for all $α>0$, there exists $β>0$, such that for sufficiently large $n$, if a set $A\subseteq \mathbb{F}_p^n$ has density at least $α$, then it contains at least $β$ fraction of all somewhat restricted $3$-APs. Our proof builds on recently developed machinery from [Bhangale, Khot, Minzer, 2026]. Our main new ingredient is an arithmetic regularity lemma for patterns such as somewhat restricted 3-APs. This result is in the spirit of arithmetic regularity lemmas from the theory of Gowers uniformity norms [Green, Tao, 2010] and may be of independent interest.

Authors: Amey Bhangale, Subhash Khot, Yang P. Liu, Dor Minzer

For a prime $p\geq 3$, a somewhat restricted $3$-AP in $\mathbb{F}_p^n$ is a triplet $(x,x+a,x+2a)$, where $x\in\mathbb{F}_p^n$ and $a\in \{0,1,2\}^n$. We prove a counting lemma for somewhat restricted $3$-APs in dense sets in $\mathbb{F}_p^n$. More precisely, we prove that for all $α>0$, there exists $β>0$, such that for sufficiently large $n$, if a set $A\subseteq \mathbb{F}_p^n$ has density at least $α$, then it contains at least $β$ fraction of all somewhat restricted $3$-APs. Our proof builds on recently developed machinery from [Bhangale, Khot, Minzer, 2026]. Our main new ingredient is an arithmetic regularity lemma for patterns such as somewhat restricted 3-APs. This result is in the spirit of arithmetic regularity lemmas from the theory of Gowers uniformity norms [Green, Tao, 2010] and may be of independent interest.

Wednesday, August 19 2026, 00:00