Theory of Computing Report

We show that for any unsatisfiable CNF formula $\varphi$ that requires resolution refutation width at least $w$, and for any $1$-stifling gadget $g$ (for example, $g=MAJ_3$), (1) every resolution-over-parities (Res($\oplus$)) refutation of the lifted formula $\varphi \circ g$ of size at most $S$ has depth at least $\Omega(w^2/\log S)$; (2) every Res($\oplus$) refutation of the lifted formula $\varphi \circ g$ has size $\Omega(w^2)$. The first result substantially extends and simplifies all previously known lifting theorems for bounded-depth Res($\oplus$). The lifting result of Itsykson and Knop [IK, ITCS'26] requires gadgets of logarithmic size and applies only to refutations of depth at most $O(n\log n)$, whereas our result applies to nearly quadratic depth. The liftings of Bhattacharya and Chattopadhyay [BC, ECCC'25] and of Byramji and Imagliazzo [BI, arXiv'25] apply to nearly quadratic depth as well, but rely on a much stronger assumption of $(\Omega(n),\Omega(n))$-DT-hardness, which is far less standard than large resolution width. Our proof combines the random-walk-with-restarts method of Alekseev and Itsykson [AI, STOC'25] with a new idea: the random walk is defined relative to the structure of the refutation graph, rather than by a distribution on inputs induced by the formula. Using this technique, we substantially strengthen the supercritical size-depth tradeoff of Itsykson and Knop [IK, ITCS'26], both by improving the depth lower bound and by reducing the size of the separating formulas to polynomial in the number of variables, with the latter resolving an open question. In particular, we construct a family of polynomial-size formulas that admit polynomial-size resolution refutations, while any Res($\oplus$) refutation of depth $o(n^2/\log^4 n)$ necessarily has superpolynomial size. Our second result yields a pure quadratic lower bound on the size of Res($\oplus$) refutations, improving upon the previously known near-quadratic lower bound of [BI, arXiv'25].

The following are prepared remarks that I delivered by Zoom to a student group at my old stomping-grounds of MIT, and which I thought might interest others (even though much of it will be familiar to Shtetl-Optimized regulars). The students asked me to share my “optimistic vision” for the year 2050, so I did my best to oblige. A freewheeling discussion then followed, as a different freewheeling discussion can now follow in the comments section.

---

I was asked to share my optimistic vision for the future. The trouble is, optimistic visions for the future are not really my shtick!

It’s not that I’m a miserable, depressed person—I only sometimes am! It’s just that, on a local level, I try to solve the problems in front of me, which have often been problems in computational complexity or quantum computing theory.

And then, on a global level, I worry about the terrifying problems of the world, such as climate change, nuclear war, and of course the resurgence of populist, authoritarian strongmen who’ve turned their backs on the Enlightenment and appeal to the basest instincts of humanity. I won’t name any names.

So then my optimistic vision is simply that we survive all this—“we” meaning the human race, but also meaning communities that I personally care about, like Americans, academics, scientists, and my extended family. We survive all of it so that we can reach the next crisis, the one where we don’t even know what it is yet.

---

But I get the sense that you wanted more optimism than that! Since I’ve spent 27 years working in quantum computing, the easiest thing for me to do would be to spin an optimistic story about how QC is going to make our lives so much better in 2050, by, I dunno, solving machine learning and optimization problems much faster, curing cancer, fixing global warming, whatever.

The good news is that there has been spectacular progress over the past couple years toward actually building a scalable QC. We now have two-qubit gates with 99.9% accuracy, close to the threshold where quantum error-correction becomes a net win. We can now do condensed-matter physics simulations that give us numbers that we don’t know how to get classically. I think it’s fair to say that all the key ideas and hardware building blocks for a fault-tolerant quantum computer are now in place, and what remains is “merely” the staggeringly hard engineering problem, which might take a few years, or a decade or more, but should eventually be solved.

The trouble for the optimistic vision is that the applications, where quantum algorithms outperform classical ones, have stubbornly remained pretty specialized. In fact, the two biggest ones remain the two that we knew about in the 1990s:

1. simulation of quantum physics and chemistry themselves, and
2. breaking existing public-key encryption.

Quantum simulation could help with designing better batteries, or solar cells, or high-temperature superconductors, or other materials, but the road from improved understanding to practical value is long and uncertain. Meanwhile, breaking public-key cryptography could help various spy agencies and hackers and criminal syndicates, but it doesn’t obviously help the world.

The quantum speedups that we know outside those two categories—for example, for optimization and machine learning—tend to be either modest or specialized or speculative.

Honestly, the application of QC that excites me the most, by far, is just disproving all the people who said QC was impossible!

So much for QC then.

---

And so we come to the elephant in the room—the elephant in pretty much every room nowadays—which is AI. AI has now reached a place that exceeds the imaginations of many of the science-fiction writers of generations past—excelling not only at writing code and solving math competition problems but at depth of emotional understanding. Many of my friends are terrified of where this is leading us—and not in some remote future but in 5 or 10 or 20 years. I think they’re probably correct to be terrified. There’s an enormous range of possible outcomes on the table, including ones where the new superintelligences that we bring into being treat humans basically as humans treated the dodo bird, or the earlier hominids that used to share the earth with us.

But, within this range of outcomes, I think there are also some extremely good ones. Look, for millennia, people have prayed to God or gods for help, life, health, longevity, freedom, justice—and for millennia, God has famously been pretty slow to answer their prayers. A superintelligence that was aligned with human values would be nothing less than a God who did answer, who did deliver all those things, because we had created it to do so. Or for religious people, perhaps such an AI would be the means by which the old God was finally able to deliver all those things into the temporal world. These are the stakes here.

To switch metaphors, people sometimes describe the positive AI-enabled future as “luxury space communism.” AI would take care of all of our material needs, leaving us to seek value in our lives through family, friendships, competition, hobbies, humor, art, entertainment, or exploration. The super-AI would give us the freedom to pursue all those things, but would not give us the freedom to harm each other, to curtail each others’ freedoms, or to build a bad AI capable of overthrowing it. The super-AI would be a singleton, a monotheistic God or its emissary on earth.

Many people say that something would still be missing from this future. After all, we humans would no longer really be needed for anything—for building or advancing or defending civilization. To put a personal fine point on it, my students and colleagues and I wouldn’t needed any more to discover new scientific truths or to write about them. That would all be the AI’s job.

I agree that something would be lost here. But on the other hand, what fraction of us are needed right now for these things? Most humans already derive the meaning in their lives from family and community and enjoying art and music and food and things like that. So maybe the remaining fraction of us should just get over ourselves! On the whole, while this might not be the best future imaginable, I would accept it in a heartbeat given the realistic alternatives on offer. Thanks for listening.

By Scott

July 6-10, 2026 Okinawa, Japan https://www.oist.jp/conference/information-theory-modern-science Submission deadline: May 17, 2026 Registration deadline: June 15, 2026 We are excited to announce the opening of registration for the Information Theory in Modern Science (ITMS) Workshop, hosted at the Okinawa Institute of Science and Technology (OIST), Japan This workshop brings together researchers from information theory, probability, statistics, … Continue reading Information Theory in Modern Science 2026

By shacharlovett

A reader worried about the future.

I am writing this email as a young aspiring researcher/scientist. We live in a period of uncertainty and I have a lot of doubts about the decisions I should make. I've always been interested in mathematics and physics and I believe that a career in this area would be a fulfilling one for me. However, with the development of AI I'm starting to have some worries about my future. It is difficult to understand what is really happening. It feels like everyday these models are improving and sooner rather than later they will render us useless.

I know that the most important objective of the study of mathematics/science is understanding and that AI will not take that pleasure away from us. But still I feel that it will be removing something fundamental to the discipline. If we have a machine that is significantly better than us at solving problems doesn't science lose a part of its magic? The struggle that we face when trying to tackle the genuinely difficult questions is perhaps the most fascinating part of doing research.

I would very much like to read about your opinion on this subject. Will mathematicians/scientists/researchers still have a role to play in all of this? Will science still be an interesting subject to pursue?

There are two questions here, the future of mathematics and the future of mathematicians. Let's take them separately.

Looks like the same letter went to Martin Hairer and highlighted in a recent NYT article about the state of AI doing math and the too-early First Proof project. According to Hairer, "I believe that mathematics is actually quite ‘safe', I haven’t seen any plausible example of an L.L.M. coming up with a genuinely new idea and/or concept."

I don't disagree with Hairer but the state of the art can quickly change. A few months ago I would have said that AI had yet to prove a new theorem, no longer true.

It's too early to tell just how good AI will get in mathematics. Right now it is like an early career graduate student, good at literature search, formalizing proofs, writing paper drafts, exploring known concepts and simple mathematical discussions. But no matter how good it gets, mathematics is a field of infinite concepts, there will always be more to explore as Gödel showed. I do hope AI gets strong at finding new concepts and novel proofs of theorems, and see new math that might not have happened while I'm still here to see it.

For mathematicians the future looks more complicated. AI may never come up with new ideas and Hairer might be right. Or AI could become so good at theorem proving that if you give a conjecture to AI and it can't resolve it, you might as well not try. The true answer is likely in-between and we'll get there slower rather than faster. 

People go into mathematics for different reasons. Some find joy in seeing new and exciting ideas in math. Some like to create good questions and models to help us make sense of mathematical ideas. Some enjoy the struggle of proving new theorems, working against an unseen force that seems to spoil your proofs until you finally break through, and impressing their peers with their prowess. Some take pleasure in education, exciting others in the importance and excitement of mathematics. These will all evolve with advances in AI and the mathematician's role will evolve with it.

My advice: Embrace mathematics research but be ready to pivot as AI evolves. We could be at the precipice of an incredible time for mathematical advances. How can you not be there to see it? And if not, then math needs you even more.

By Lance Fortnow

The hardness vs. randomness paradigm aims to construct pseudorandom generators (PRGs) based on complexity theoretic hardness assumptions. A seminal result in this area is a PRG construction by \cite{NW,IW97}. A sequence of works \cite{KvM,SU01,Umans02,SU05} generalized the result of \cite{NW,IW97} to nondeterministic circuits. More specifically, they showed that if $\E=\DTIME(2^{O(n)})$ requires nondeterministic circuits of size $2^{\Omega(n)}$, then for every sufficiently large $s$, and every $\eps \ge \frac{1}{s}$, there is an $\eps$-PRG $G:\B^{r=O(\log s + \log \frac{1}{\eps})} \to \B^s$ that runs in time $\poly(s)$, and fools size $s$ nondeterministic circuits. In particular, for every size $s$ nondeterministic circuit $C$, \[\Pr[C(G(U_r))=1] \le \Pr[C(U_s)=1] + \eps.\] Applebaum et al. \cite{AASY15} showed that ``black-box techniques'' cannot achieve such results for $\eps=s^{-\omega(1)}$. In order to circumvent this problem, Artemenko et al. \cite{AIKS16} suggested a ``multiplicative'' version of PRGs, which requires that: \[\Pr[C(G(U_r))=1] \le 2 \cdot \Pr[C(U_s)=1] + \eps.\] This still gives that $\Pr[C(G(U_r))=1]$ is very small, if $\Pr[C(U_s)=1]$ is very small, and is therefore suitable for applications that only require this consequence. \cite{AIKS16} constructed such multiplicative PRGs for $\eps=s^{-\omega(1)}$ (based on very strong hardness assumptions). In this paper, we give an optimal construction of multiplicative PRGs for nondeterministic circuits. More specifically, under the same hardness assumption used for (standard) PRGs for nondeterministic circuits, we show that for every $\eps \ge \frac{1}{2^{s}}$, there is a multiplicative PRG $G:\B^{r=O(\log s + \log \frac{1}{\eps})} \to \B^s$ that runs in time $\poly(s)$ and fools size $s$ nondeterministic circuits. This gives the optimal seed length under a hardness assumption that is necessary, and provides improvements in several applications of multiplicative PRGs. Our result improves upon the previous multiplicative PRG construction of \cite{AIKS16}, which uses a stronger hardness assumption against $\Sigma_3$-circuits, and where the seed length is the suboptimal $r=O(\log s) + O(\log \frac{1}{\eps})^2$. Our result also improves upon the recent multiplicative PRG of Shaltiel \cite{ShaltielCCC25} that only achieves very small stretch (the output length in \cite{ShaltielCCC25} is less than twice the seed length). \smallskip We also show that black-box techniques cannot give a version of our result where ``nondeterministic'' is replaced by ``deterministic''. This justifies the current situation where hardness for nondeterministic circuits is used even if one only wants low error multiplicative PRGs that fool \emph{deterministic} circuits. \smallskip Our PRG construction borrows ideas from the recent ``low stretch'' PRG of Shaltiel \cite{ShaltielCCC25}, and the (standard) PRG construction of Shaltiel and Umans \cite{SU01}. Loosely speaking, we aim to get the ``multiplicativity'' of the former, and the ``large stretch'' of the latter. While both approaches generalize the list-decoding results of Sudan, Trevisan and Vadhan \cite{STV}, the two results are tailored to two very different parameter regimes, and we introduce several new ideas to make the two approaches co-exist.

Authors: Changryeol Lee

While prior work established a verifier-based polynomial time framework for NP, explicit deterministic machines for concrete NP-complete problems have remained elusive. In this paper, we construct fully specified deterministic Turing Machines (DTMs) for SAT and Subset-Sum within a polynomial-time NP verifier simulation framework. We show that both machines operate in polynomial time and, for satisfiable instances, deterministically generate valid witnesses, thereby extending the framework to deterministic FNP computation without increasing the degree of polynomial complexity. Furthermore, we provide a complete implementation of the framework, including the dynamic computation graph, feasible-graph construction, verification walks, and Turing-machine simulation via edge extensions. The implementation behaves in accordance with the predicted polynomial-time bounds. To ensure transparency and reproducibility, the complete Python implementation and source code are made available in a public online repository.

Authors: Katarína Cechlárová, Ildikó Schlotter

Consider an election where the set of candidates is partitioned into parties, and each party must choose exactly one candidate to nominate for the election held over all nominees. The Necessary President problem asks whether a candidate, if nominated, becomes the winner of the election for all possible nominations from other parties. We study the computational complexity of Necessary President for several voting rules. We show that while this problem is solvable in polynomial time for Borda, Maximin, and Copeland$^α$ for every $α\in [0,1]$, it is $\mathsf{coNP}$-complete for general classes of positional scoring rules that include $\ell$-Approval and $\ell$-Veto, even when the maximum size of a party is two. For such positional scoring rules, we show that Necessary President is $\mathsf{W}[2]$-hard when parameterized by the number of parties, but fixed-parameter tractable with respect to the number of voter types. Additionally, we prove that Necessary President for Ranked Pairs is $\mathsf{coNP}$-complete even for maximum party size two, and $\mathsf{W}[1]$-hard with respect to the number of parties; remarkably, both of these results hold even for constant number of voters.

Authors: Guangyan Zhou

We study the algorithmic decidability of the domination number in the Erdos-Renyi random graph model $G(n,p)$. We show that for a carefully chosen edge probability $p=p(n)$, the domination problem exhibits a strong irreducible property. Specifically, for any constant $0

Authors: Colin Cleveland, Bart de Keijzer, Maria Polukarov

We study the computational complexity of strategic behaviour in primary elections. Unlike direct voting systems, primaries introduce a multi-stage process in which voters first influence intra-party nominees before a general election determines the final winner. While previous work has evaluated primaries via welfare distortion, we instead examine their game-theoretic properties. We formalise a model of primaries under first-past-the-post with fixed tie-breaking and analyse voters' strategic behaviour. We show that determining whether a pure Nash equilibrium exists is $Σ_2^{\mathbf P}$-complete, computing a best response is NP-complete, and deciding the existence of subgame-perfect equilibria in sequential primaries is PSPACE-complete. These results reveal that primaries fundamentally increase the computational difficulty of strategic reasoning, situating them as a rich source of complexity-theoretic challenges within computational social choice.

Authors: Michaela Borzechowski, Sebastian Haslebacher, Hung P. Hoang, Patrick Schnider, Simon Weber

The famous Ham-Sandwich theorem states that any $d$ point sets in $\mathbb{R}^d$ can be simultaneously bisected by a single hyperplane. The $α$-Ham-Sandwich theorem gives a sufficient condition for the existence of biased cuts, i.e., hyperplanes that do not cut off half but some prescribed fraction of each point set. We give two new proofs for this theorem. The first proof is completely combinatorial and highlights a strong connection between the $α$-Ham-Sandwich theorem and Unique Sink Orientations of grids. The second proof uses point-hyperplane duality and the Poincaré-Miranda theorem and allows us to generalize the result to and beyond oriented matroids. For this we introduce a new concept of rainbow arrangements, generalizing colored pseudo-hyperplane arrangements. Along the way, we also show that the realizability problem for rainbow arrangements is $\exists \mathbb{R}$-complete, which also implies that the realizability problem for grid Unique Sink Orientations is $\exists \mathbb{R}$-complete.

Authors: Palash Dey, Anubhav Dhar, Ashlesha Hota, Sudeshna Kolay, Aritra Mitra

In this paper, we study the Maximum Common Vertex Subgraph problem: Given two input graphs $G_1,G_2$ and a non-negative integer $h$, is there a common subgraph $H$ on at least $h$ vertices such that there is no isolated vertex in $H$. In other words, each connected component of $H$ has at least $2$ vertices. This problem naturally arises in graph theory along with other variants of the well-studied Maximum Common Subgraph problem and also has applications in computational social choice. We show that this problem is NP-hard and provide an FPT algorithm when parameterized by $h$. Next, we conduct a study of the problem on common structural parameters like vertex cover number, maximum degree, treedepth, pathwidth and treewidth of one or both input graphs. We derive a complete dichotomy of parameterized results for our problem with respect to individual parameterizations as well as combinations of parameterizations from the above structural parameters. This provides us with a deep insight into the complexity theoretic and parameterized landscape of this problem.

Authors: Joshua Brakensiek, Lorenzo Ciardo, Venkatesan Guruswami, Aaron Potechin, Stanislav Živný

In this paper, we continue the study of robust satisfiability of promise CSPs (PCSPs), initiated in (Brakensiek, Guruswami, Sandeep, STOC 2023 / Discrete Analysis 2025), and obtain the following results: For the PCSP 1-in-3-SAT vs NAE-SAT with negations, we prove that it is hard, under the Unique Games conjecture (UGC), to satisfy $1-Ω(1/\log (1/ε))$ constraints in a $(1-ε)$-satisfiable instance. This shows that the exponential loss incurred by the BGS algorithm for the case of Alternating-Threshold polymorphisms is necessary, in contrast to the polynomial loss achievable for Majority polymorphisms. For any Boolean PCSP that admits Majority polymorphisms, we give an algorithm satisfying $1-O(\sqrtε)$ fraction of the weaker constraints when promised the existence of an assignment satisfying $1-ε$ fraction of the stronger constraints. This significantly generalizes the Charikar--Makarychev--Makarychev algorithm for 2-SAT, and matches the optimal trade-off possible under the UGC. The algorithm also extends, with the loss of an extra $\log (1/ε)$ factor, to PCSPs on larger domains with a certain structural condition, which is implied by, e.g., a family of Plurality polymorphisms. We prove that assuming the UGC, robust satisfiability is preserved under the addition of equality constraints. As a consequence, we can extend the rich algebraic techniques for decision/search PCSPs to robust PCSPs. The methods involve the development of a correlated and robust version of the general SDP rounding algorithm for CSPs due to (Brown-Cohen, Raghavendra, ICALP 2016), which might be of independent interest.

Authors: Xi Chen, Yuhao Li, Mihalis Yannakakis

We study the problem of finding an $ε$-fixed point of a contraction map $f:[0,1]^k\mapsto[0,1]^k$ under both the $\ell_\infty$-norm and the $\ell_1$-norm. For both norms, we give an algorithm with running time $O(\log^{\lceil k/2\rceil}(1/ε))$, for any constant $k$. These improve upon the previous best $O(\log^k(1/ε))$-time algorithm for the $\ell_{\infty}$-norm by Shellman and Sikorski [SS03], and the previous best $O(\log^k (1/ε))$-time algorithm for the $\ell_{1}$-norm by Fearnley, Gordon, Mehta and Savani [FGMS20].

Authors: Jean Cardinal, Micha Sharir

Semialgebraic graphs are graphs whose vertices are points in $\mathbb{R}^d$, and adjacency between two vertices is determined by the truth value of a semialgebraic predicate of constant complexity. We show how to harness polynomial partitioning methods to construct compact adjacency labeling schemes for families of semialgebraic graphs. That is, we show that for any family of semialgebraic graphs, given a graph on $n$ vertices in this family, we can assign a label consisting of $O(n^{1-2/(d+1) + \varepsilon})$ bits to each vertex (where $\varepsilon > 0$ can be made arbitrarily small and the constant of proportionality depends on $\varepsilon$ and on the complexity of the adjacency-defining predicate), such that adjacency between two vertices can be determined solely from their two labels, without any additional information. We obtain for instance that unit disk graphs and segment intersection graphs have such labelings with labels of $O(n^{1/3 + \varepsilon})$ bits. This is in contrast to their natural implicit representation consisting of the coordinates of the disk centers or segment endpoints, which sometimes require exponentially many bits. It also improves on the best known bound of $O(n^{1-1/d}\log n)$ for $d$-dimensional semialgebraic families due to Alon (Discrete Comput. Geom., 2024), a bound that holds more generally for graphs with shattering functions bounded by a degree-$d$ polynomial. We also give new bounds on the size of adjacency labels for other families of graphs. In particular, we consider semilinear graphs, which are semialgebraic graphs in which the predicate only involves linear polynomials. We show that semilinear graphs have adjacency labels of size $O(\log n)$. We also prove that polygon visibility graphs, which are not semialgebraic in the above sense, have adjacency labels of size $O(\log^3 n)$.

Authors: Nathaniel K. Brown, Ben Langmead

The move structure represents permutations with long contiguously permuted intervals in compressed space with optimal query time. They have become an important feature of compressed text indexes using space proportional to the number of Burrows-Wheeler Transform (BWT) runs, often applied in genomics. This is in thanks not only to theoretical improvements over past approaches, but great cache efficiency and average case query time in practice. This is true even without using the worst case guarantees provided by the interval splitting balancing of the original result. In this paper, we show that an even simpler type of splitting, length capping by truncating long intervals, bounds the average move structure query time to optimal whilst obtaining a superior construction time than the traditional approach. This also proves constant query time when amortized over a full traversal of a single cycle permutation from an arbitrary starting position. Such a scheme has surprising benefits both in theory and practice. We leverage the approach to improve the representation of any move structure with $r$ runs over a domain $n$ to $O(r \log r + r \log \frac{n}{r})$-bits of space. The worst case query time is also improved to $O(\log \frac{n}{r})$ without balancing. An $O(r)$-time and $O(r)$-space construction lets us apply the method to run-length encoded BWT (RLBWT) permutations such as LF and $φ$ to obtain optimal-time algorithms for BWT inversion and suffix array (SA) enumeration in $O(r)$ additional working space. Finally, we provide the RunPerm library, providing flexible plug and play move structure support, and use it to evaluate our splitting approach. Experiments find length capping results in faster move structures, but also a space reduction: at least $\sim 40\%$ for LF across large repetitive genomic collections.

Authors: Anouk Duyster, Tomasz Kociumaka

A Random Access query to a string $T\in [0..σ)^n$ asks for the character $T[i]$ at a given position $i\in [0..n)$. In $O(n\logσ)$ bits of space, this fundamental task admits constant-time queries. While this is optimal in the worst case, much research has focused on compressible strings, hoping for smaller data structures that still admit efficient queries. We investigate the grammar-compressed setting, where $T$ is represented by a straight-line grammar. Our main result is a general trade-off that optimizes Random Access time as a function of string length $n$, grammar size (the total length of productions) $g$, alphabet size $σ$, data structure size $M$, and word size $w=Ω(\log n)$ of the word RAM model. For any $M$ with $g\log n 0$ [Belazzougui et al.; ESA'15], [Ganardi, Jeż, Lohrey; J. ACM 2021]. The only tight lower bound [Verbin and Yu; CPM'13] was $Ω(\frac{\log n}{\log\log n})$ for $w=Θ(\log n)$, $n^{Ω(1)}\le g\le n^{1-Ω(1)}$, and $M=g\log^{Θ(1)}n$. In contrast, our result yields tight bounds in all relevant parameters and almost all regimes. Our data structure admits efficient deterministic construction. It relies on novel grammar transformations that generalize contracting grammars [Ganardi; ESA'21]. Beyond Random Access, its variants support substring extraction, rank, and select.

Authors: Frederik Glitzner

Stable matching is a fundamental area with many practical applications, such as centralised clearinghouses for school choice or job markets. Recent work has introduced the paradigm of near-feasibility in capacitated matching settings, where agent capacities are slightly modified to ensure the existence of desirable outcomes. While useful when no stable matching exists, or some agents are left unmatched, it has not previously been investigated whether near-feasible stable matchings satisfy desirable properties with regard to their stability in the original instance. Furthermore, prior works often leave open deviation incentive issues that arise when the centralised authority modifies agents' capacities. We consider these issues in the Stable Fixtures problem model, which generalises many classical models through non-bipartite preferences and capacitated agents. We develop a formal framework to analyse and quantify agent incentives to adhere to computed matchings. Then, we embed near-feasible stable matchings in this framework and study the trade-offs between instability, capacity modifications, and computational complexity. We prove that capacity modifications can be simultaneously optimal at individual and aggregate levels, and provide efficient algorithms to compute them. We show that different modification strategies significantly affect stability, and establish that minimal modifications and minimal deviation incentives are compatible and efficiently computable under general conditions. Finally, we provide exact algorithms and experimental results for tractable and intractable versions of these problems.

Authors: Christian Bertram, Mads Vestergaard Jensen

Given an undirected graph $G=(V, E)$, the Personalized PageRank (PPR) of $t\in V$ with respect to $s\in V$, denoted $π(s,t)$, is the probability that an $α$-discounted random walk starting at $s$ terminates at $t$. We study the time complexity of estimating $π(s,t)$ with constant relative error and constant failure probability, whenever $π(s,t)$ is above a given threshold parameter $δ\in(0,1)$. We consider common graph-access models and furthermore study the single source, single target, and single node (PageRank centrality) variants of the problem. We provide a complete characterization of PPR estimation in undirected graphs by giving tight bounds (up to logarithmic factors) for all problems and model variants in both the worst-case and average-case setting. This includes both new upper and lower bounds. Tight bounds were recently obtained by Bertram, Jensen, Thorup, Wang, and Yan for directed graphs. However, their lower bound constructions rely on asymmetry and therefore do not carry over to undirected graphs. At the same time, undirected graphs exhibit additional structure that can be exploited algorithmically. Our results resolve the undirected case by developing new techniques that capture both aspects, yielding tight bounds.

Authors: Ernestine Großmann, Christian Schulz, Darren Strash, Antonie Wagner

This work addresses the well-known Maximum Independent Set problem in the context of hypergraphs. While this problem has been extensively studied on graphs, we focus on its strong extension to hypergraphs, where edges may connect any number of vertices. A set of vertices in a hypergraph is strongly independent if there is at most one vertex per edge in the set. One application for this problem is to find perfect minimal hash functions. We propose nine new data reduction rules specifically designed for this problem. Our reduction routine can serve as a preprocessing step for any solver. We analyze the impact on the size of the reduced instances and the performance of several subsequent solvers when combined with this preprocessing. Our results demonstrate a significant reduction in instance size and improvements in running time for subsequent solvers. The preprocessing routine reduces instances, on average, to 22% of their original size in 6.76 seconds. When combining our reduction preprocessing with the best-performing exact solver, we observe an average speedup of 3.84x over not using the reduction rules. In some cases, we can achieve speedups of up to 53x. Additionally, one more instance becomes solvable by a method when combined with our preprocessing.

Authors: Bernhard Haeupler, Antti Roeyskoe, Zhijun Zhang

All parallel algorithms for directed connectivity and shortest paths crucially rely on efficient shortcut constructions that add a linear number of transitive closure edges to a given DAG to reduce its diameter. A long sequence of works has studied both (efficient) shortcut constructions and impossibility results on the best diameter and therefore the best parallelism that can be achieved with this approach. This paper introduces a new conceptual and technical tool, called certified shortcuts, for this line of research in the form of a simple and natural structural criterion that holds for any shortcut constructed by an efficient (combinatorial) algorithm. It allows us to drastically simplify and strengthen existing impossibility results by proving that any near-linear-time shortcut-based algorithm cannot reduce a graph's diameter below $n^{1/4-o(1)}$. This greatly improves over the $n^{2/9-o(1)}$ lower bound of [HXX25] and seems to be the best bound one can hope for with current techniques. Our structural criterion also precisely captures the constructiveness of all known shortcut constructions: we show that existing constructions satisfy the criterion if and only if they have known efficient algorithms. We believe our new criterion and perspective of looking for certified shortcuts can provide crucial guidance for designing efficient shortcut constructions in the future.

Authors: Vijay K. Garg, Rohan Garg

We present methods to compute least fixed points of multiple monotone inflationary functions in parallel and distributed settings. While the classic Knaster-Tarski theorem addresses a single function with sequential iteration, modern computing systems require parallel execution with overwrite semantics, non-atomic updates, and stale reads. We prove three convergence theorems under progressively relaxed synchronization: (1) Interleaving semantics with fair scheduling, (2) Parallel execution with update-only-on-change semantics (processes write only on those coordinates whose values change), and (3) Distributed execution with bounded staleness (updates propagate within $T$ rounds) and $i$-locality (each process modifies only its own component). Our approach differs from prior work in fundamental ways: Cousot-Cousot's chaotic iteration uses join-based merges that preserve information. Instead, we use coordinate-wise overwriting. Bertsekas's asynchronous methods assume contractions. We use coordinate-wise overwriting with structural constraints (locality, bounded staleness) instead. Applications include parallel and distributed algorithms for the transitive closure, stable marriage, shortest paths, and fair division with subsidy problems. Our results provide the first exact least-fixed-point convergence guarantees for overwrite-based parallel updates without join operations or contraction assumptions.

Authors: Kishen N Gowda, Willem Fletcher, MohammadHossein Bateni, Laxman Dhulipala, D Ellis Hershkowitz, Rajesh Jayaram, Jakub Łącki

Hierarchical Agglomerative Clustering (HAC) is a widely-used clustering method based on repeatedly merging the closest pair of clusters, where inter-cluster distances are determined by a linkage function. Unlike many clustering methods, HAC does not optimize a single explicit global objective; clustering quality is therefore primarily evaluated empirically, and the choice of linkage function plays a crucial role in practice. However, popular classical linkages, such as single-linkage, average-linkage and Ward's method show high variability across real-world datasets and do not consistently produce high-quality clusterings in practice. In this paper, we propose \emph{Chamfer-linkage}, a novel linkage function that measures the distance between clusters using the Chamfer distance, a popular notion of distance between point-clouds in machine learning and computer vision. We argue that Chamfer-linkage satisfies desirable concept representation properties that other popular measures struggle to satisfy. Theoretically, we show that Chamfer-linkage HAC can be implemented in $O(n^2)$ time, matching the efficiency of classical linkage functions. Experimentally, we find that Chamfer-linkage consistently yields higher-quality clusterings than classical linkages such as average-linkage and Ward's method across a diverse collection of datasets. Our results establish Chamfer-linkage as a practical drop-in replacement for classical linkage functions, broadening the toolkit for hierarchical clustering in both theory and practice.

Authors: Anders Aamand, Justin Y. Chen, Sandeep Silwal

We study differentially private continual release of the number of distinct items in a turnstile stream, where items may be both inserted and deleted. A recent work of Jain, Kalemaj, Raskhodnikova, Sivakumar, and Smith (NeurIPS '23) shows that for streams of length $T$, polynomial additive error of $Ω(T^{1/4})$ is necessary, even without any space restrictions. We show that this additive error lower bound can be circumvented if the algorithm is allowed to output estimates with both additive \emph{and multiplicative} error. We give an algorithm for the continual release of the number of distinct elements with $\text{polylog} (T)$ multiplicative and $\text{polylog}(T)$ additive error. We also show a qualitatively similar phenomenon for estimating the $F_2$ moment of a turnstile stream, where we can obtain $1+o(1)$ multiplicative and $\text{polylog} (T)$ additive error. Both results can be achieved using polylogarithmic space whereas prior approaches use polynomial space. In the sublinear space regime, some multiplicative error is necessary even if privacy is not a consideration. We raise several open questions aimed at better understanding trade-offs between multiplicative and additive error in private continual release.

Authors: Mateusz Basiak, Marcin Bienkowski, Guy Even, Agnieszka Tatarczuk

The online bisection problem requires maintaining a dynamic partition of $n$ nodes into two equal-sized clusters. Requests arrive sequentially as node pairs. If the nodes lie in different clusters, the algorithm pays unit cost. After each request, the algorithm may migrate nodes between clusters at unit cost per node. This problem models datacenter resource allocation where virtual machines must be assigned to servers, balancing communication costs against migration overhead. We study the variant where requests are restricted to edges of a ring network, an abstraction of ring-allreduce patterns in distributed machine learning. Despite this restriction, the problem remains challenging with an $Ω(n)$ deterministic lower bound. We present a randomized algorithm achieving $O(\varepsilon^{-3} \cdot \log^2 n)$ competitive ratio using resource augmentation that allows clusters of size at most $(3/4 + \varepsilon) \cdot n$. Our approach formulates the problem as a metrical task system with a restricted state space. By limiting the number of cut-edges (i.e., ring edges between clusters) to at most $2k$, where $k = Θ(1/\varepsilon)$, we reduce the state space from exponential to polynomial (i.e., $n^{O(k)}$). The key technical contribution is proving that this restriction increases cost by only a factor of $O(k)$. Our algorithm follows by applying the randomized MTS solution of Bubeck et al. [SODA 2019]. The best result to date for bisection with ring demands is the $O(n \cdot \log n)$-competitive deterministic online algorithm of Rajaraman and Wasim [ESA 2024] for the general setting. While prior work for ring-demands by Räcke et al. [SPAA 2023] achieved $O(\log^3 n)$ for multiple clusters, their approach employs a resource augmentation factor of $2+\varepsilon$, making it inapplicable to bisection.

Authors: Robert Ganian, Viktoriia Korchemna

We investigate the parameterized complexity of Bayesian Network Structure Learning (BNSL), a classical problem that has received significant attention in empirical but also purely theoretical studies. We follow up on previous works that have analyzed the complexity of BNSL w.r.t. the so-called superstructure of the input. While known results imply that BNSL is unlikely to be fixed-parameter tractable even when parameterized by the size of a vertex cover in the superstructure, here we show that a different kind of parameterization - notably by the size of a feedback edge set - yields fixed-parameter tractability. We proceed by showing that this result can be strengthened to a localized version of the feedback edge set, and provide corresponding lower bounds that complement previous results to provide a complexity classification of BNSL w.r.t. virtually all well-studied graph parameters. We then analyze how the complexity of BNSL depends on the representation of the input. In particular, while the bulk of past theoretical work on the topic assumed the use of the so-called non-zero representation, here we prove that if an additive representation can be used instead then BNSL becomes fixed-parameter tractable even under significantly milder restrictions to the superstructure, notably when parameterized by the treewidth alone. Last but not least, we show how our results can be extended to the closely related problem of Polytree Learning.

The Faculty of Science at the University of Calgary invites applications for a Tenure-Track Assistant Professor in Computer Science position with a focus on Theoretical Foundations of Computer Science.

Website: https://careers.ucalgary.ca/jobs/17169318-tenure-track-assistant-professor-research-in-computer-science-faculty-of-science
Email: cpsc.hiring@ucalgary.ca

By shacharlovett

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

I could teach an entire semester-long graduate class on gradient descent. First, I’d present gradient descent. Then I’d move to accelerated gradient descent. Then I could teach stochastic gradient descent, coordinate descent, projected gradient descent, proximal gradient descent… This would get us to Spring break. We could wrap up the semester with other assorted gradient potpourri. Indeed, Steve Wright and I packaged this course into a textbook: Optimization for Data Analysis.

Steve and I were inspired by the thousands of machine learning and optimization papers of the 2010s that made minor extensions in this gradient zoo. All of these papers proved their methods worked in the same way. They set up a Lyapunov function. They showed that it decreased as the algorithm evolved. QED.

Those Lyapunov functions were sometimes easy to come by. You’d always start with the function value itself. If it significantly decreased every iteration, then the algorithm would converge. You could also study the distance of the current iterate to the optimal solution. It took me a decade of beating my head against Nesterov’s inscrutable estimate sequences to realize that he was actually using a Lyapunov function too. In Nesterov’s accelerated method, this Lyapunov function has the form:

Showing functions like this were Lyapunov functions required pages of calculations, but all of these were manipulating exactly two inequalities. The most important assumption when analyzing gradient descent is that the gradients are Lipschitz. This means that the slope of the gradient function is bounded. Oftentimes, we also assume that the functions are strongly convex. This is equivalent to assuming the slope of the gradient function is bounded below.

Together, we had that the following two inequalities were true for any x and z.

Here, L is the Lipschitz constant of the gradient. m is the strong convexity parameter. Sometimes we’d use the second inequality with m=0. You might call those functions weakly convex. Convergence proofs cleverly sum up these two inequalities evaluated at different points in space to show that some Lyapunov function decreases. After enough Tetris-like puzzling, you surely prove that the Lyapunov function decreases.

These analyses appear to be assessing the stability of a dynamical system. That’s because they are. Gradient methods control a nonlinear system that takes a vector as input and outputs the gradient of a convex function evaluated at that vector.

The algorithm feeds “x” into the black box. The black box spits out “g.” The algorithm does some thinking and spits out another x. Eventually, the g emitted by the black box is always equal to zero.

In fact, all of the gradient-based algorithms are equivalent to PID controllers. Gradient descent is literally an integral controller. It is even after the same goals: gradient descent wants to find a point where the derivative is zero. Integral control seeks zero steady-state error. Accelerated methods are PID controllers. Projected gradient is a PI controller.

What if we just relabel that picture to align with control theory notation:

The slope bound assumption on the gradients is equivalent to assuming the black box has gain bounded between an upper and lower bound. This is the sort of thing control theorists have studied for a century. They call such nonlinear functions “sector bounded” and have a variety of tools to verify control algorithms when such uncertain nonlinearities are in the feedback loop.

In the paper “Analysis of Optimization Algorithms by Integral Quadratic Constraints,” Laurent Lessard, Andy Packard, and I translated these techniques to optimization algorithms. This let us search for Lyapunov-like proofs that your algorithm converges. With these tools, we could derive the same convergence rates and get novel robustness arguments. And the analyses were automatable, in the sense that we derived our proofs using other optimization algorithms.

A complementary approach to this problem developed by optimizers is the PEP framework, which uses a language more native to optimization. Both proof systems work because positive linear combinations of positive things are positive. Thus, you try to show a Lyapunov function decreases by writing this statement as an equality, and showing it’s the linear combination of a bunch of these inequalities. The computer can do this for you.

Lots of interesting insights come from this parallel between optimization and control. For instance, it shows there is no way to “fix” simple momentum methods like the Heavy Ball Method to prove they converge globally. The automated proof framework also helped us identify perturbations to the methods that could sometimes yield faster convergence rates or greater numerical stability.

But one thing I haven’t been able to do is turn this around: I want to teach a semester-long graduate course on PID control that would feel like my optimization class. I was hoping to get a start during this graduate seminar. I wanted to make it clear that most of the analysis could be done by Lyapunov functions. I wanted to move beyond sector-bounded nonlinear maps to more common dynamical system models in which people apply PID controllers. And I want to do all of this without ever taking a Laplace transform.

If there are any control theorists out there reading this with ideas for putting such a course together, please let me know! I know many would argue that PID controllers are solved, and the interesting stuff happens at a higher level. But to push the limits of what modern learning-control systems do, we have to understand the PID controls at the innermost loops of the complex system. Explaining this part of the architecture in a clean, modern way is a good pedagogical challenge for my control theory friends.

Subscribe now

By Ben Recht

The Algorithms group at IISc Bengaluru invites posdoc applications. Areas include Approximation/Online Algorithms, Game Theory, Computational Geometry, Optimization, Learning, and more. Fellowship: ₹80,000–1,30,000/month + travel/research grant.

Faculty: Siddharth Barman, Arindam Khan, Anand Louis, Rahul Saladi.

𝗔𝗽𝗽𝗹𝗶𝗰𝗮𝘁𝗶𝗼𝗻 𝗟𝗶𝗻𝗸: https://forms.gle/moz2vx7tiNFCbXmS6

Website: https://www.linkedin.com/posts/arindam-khan-445ab615_postdoc-jobs-algorithms-activity-7427285529886580736-6tUk?utm_source=share&utm_medium=member_desktop&rcm=ACoAAAMwLfUBJutL4b0gGJNLzdNG9Zwai-rt7_M
Email: ARINDAMKHAN@IISC.AC.IN

By shacharlovett

Authors: Ismael Rodriguez

We identify a few conditions $X$ such that $(P=NP \wedge X) \;\Rightarrow\; P=PSPACE$.

Authors: Gil Cohen, Dean Doron, Noam Goldgraber

Pseudorandom generators (PRGs) for low-degree polynomials are a central object in pseudorandomness, with applications to circuit lower bounds and derandomization. Viola's celebrated construction gives a PRG over the binary field, but with seed length exponential in the degree $d$. This exponential dependence can be avoided over sufficiently large fields. In particular, Dwivedi, Guo, and Volk constructed PRGs with optimal seed length over fields of size exponential in $d$. The latter builds on the framework of Derksen and Viola, who obtained optimal-seed constructions over fields of size polynomial in $d$, although growing with the number of variables $n$. In this work, we construct the first PRG with optimal seed length for degree-$d$ polynomials over fields of polynomial size, specifically $q \approx d^4$, assuming sufficiently large characteristic. Our construction follows the framework of prior work and reduces the required field size by replacing the hitting-set generator used in previous constructions with a new pseudorandom object. We also observe a threshold phenomenon in the field-size dependence. Specifically, we prove that constructing PRGs over fields of sublinear size, for example $q = d^{0.99}$ where $q$ is a power of two, would already yield PRGs for the binary field with comparable seed length via our reduction, provided that the construction imposes no restriction on the characteristic. While a breakdown of existing techniques has been noted before, we prove that this phenomenon is inherent to the problem itself, irrespective of the technique used.

Authors: Alexey Barsukov, Santiago Guzmán-Pro

We present a structural classification of constraint satisfaction problems (CSP) described by reflexive complete $2$-edge-coloured graphs. In particular, this classification extends the structural dichotomy for graph homomorphism problems known as the Hell--Nešetřil theorem (1990). Our classification is also efficient: we can check in polynomial time whether the CSP of a reflexive complete $2$-edge-coloured graph is in P or NP-complete, whereas for arbitrary $2$-edge-coloured graphs, this task is NP-complete. We then apply our main result in the context of matrix partition problems and sandwich problems. Firstly, we obtain one of the few algorithmic solutions to general classes of matrix partition problems. And secondly, we present a P vs. NP-complete classification of sandwich problems for matrix partitions.

Authors: Joseph Dorfer

We study the reconfiguration of odd matchings of combinatorial graphs. Odd matchings are matchings that cover all but one vertex of a graph. A reconfiguration step, or flip, is an operation that matches the isolated vertex and, consequently, isolates another vertex. The flip graph of odd matchings is a graph that has all odd matchings of a graph as vertices and an edge between two vertices if their corresponding matchings can be transformed into one another via a single flip. We show that computing the diameter of the flip graph of odd matchings is $Π_2^p$-hard. This complements a recent result by Wulf [FOCS25] that it is~$Π_2^p$-hard to compute the diameter of the flip graph of perfect matchings where a flip swaps matching edges along a single cycle of unbounded size. Further, we show that computing the radius of the flip graph of odd matchings is $Σ_3^p$-hard. The respective decision problems for the diameter and the radius are also complete in the respective level of the polynomial hierarchy. This shows that computing the radius of the flip graph of odd matchings is provably harder than computing its diameter, unless the polynomial hierarchy collapses. Finally, we reduce set cover to the problem of finding shortest flip sequences. As a consequence, we show $\log$-\APX-hardness and that the problem cannot be approximated by a sublogarithmic factor. By doing so, we answer a question asked by Aichholzer, Brenner, Dorfer, Hoang, Perz, Rieck, and Verciani [GD25].

Authors: John Bostanci, Andrew Huang, Vinod Vaikuntanathan

We show an unconditional classical oracle separation between the class of languages that can be verified using a quantum proof ($\mathsf{QMA}$) and the class of languages that can be verified with a classical proof ($\mathsf{QCMA}$). Compared to the recent work of Bostanci, Haferkamp, Nirkhe, and Zhandry (STOC 2026), our proof is conceptually and technically simpler, and readily extends to other oracle separations. In particular, our techniques yield the first unconditional classical oracle separation between the class of languages that can be decided with quantum advice ($\mathsf{BQP}/\mathsf{qpoly}$) and the class of languages that can be decided with classical advice ($\mathsf{BQP}/\mathsf{poly}$), improving on the quantum oracle separation of Aaronson and Kuperberg (CCC 2007) and the classically-accessible classical oracle separation of Li, Liu, Pelecanos and Yamakawa (ITCS 2024). Our oracles are based on the code intersection problem introduced by Yamakawa and Zhandry (FOCS 2022), combined with codes that have extremely good list-recovery properties.

Authors: Lijie Chen, Jiatu Li, Igor C. Oliveira, Ryan Williams

In this work, we propose a new bounded arithmetic theory, denoted $APX_1$, designed to formalize a broad class of probabilistic arguments commonly used in theoretical computer science. Under plausible assumptions, $APX_1$ is strictly weaker than previously proposed frameworks, such as the theory $APC_1$ introduced in the seminal work of Jerabek (2007). From a computational standpoint, $APX_1$ is closely tied to approximate counting and to the central question in derandomization, the prBPP versus prP problem, whereas $APC_1$ is linked to the dual weak pigeonhole principle and to the existence of Boolean functions with exponential circuit complexity. A key motivation for introducing $APX_1$ is that its weaker axioms expose finer proof-theoretic structure, making it a natural setting for several lines of research, including unprovability of complexity conjectures and reverse mathematics of randomized lower bounds. In particular, the framework we develop for $APX_1$ enables the formulation of precise questions concerning the provability of prBPP=prP in deterministic feasible mathematics. Since the (un)provability of P versus NP in bounded arithmetic has long served as a central theme in the field, we expect this line of investigation to be of particular interest. Our technical contributions include developing a comprehensive foundation for probabilistic reasoning from weaker axioms, formalizing non-trivial results from theoretical computer science in $APX_1$, and establishing a tailored witnessing theorem for its provably total TFNP problems. As a byproduct of our analysis of the minimal proof-theoretic strength required to formalize statements arising in theoretical computer science, we resolve an open problem regarding the provability of $AC^0$ lower bounds in $PV_1$, which was considered in earlier works by Razborov (1995), Krajicek (1995), and Muller and Pich (2020).

Authors: Yang P. Liu, Shachar Lovett, Kunal Mittal

We prove that for any 3-player game $\mathcal G$, whose query distribution has the same support as the GHZ game (i.e., all $x,y,z\in \{0,1\}$ satisfying $x+y+z=0\pmod{2}$), the value of the $n$-fold parallel repetition of $\mathcal G$ decays exponentially fast: \[ \text{val}(\mathcal G^{\otimes n}) \leq \exp(-n^c)\] for all sufficiently large $n$, where $c>0$ is an absolute constant. We also prove a concentration bound for the parallel repetition of the GHZ game: For any constant $ε>0$, the probability that the players win at least a $\left(\frac{3}{4}+ε\right)$ fraction of the $n$ coordinates is at most $\exp(-n^c)$, where $c=c(ε)>0$ is a constant. In both settings, our work exponentially improves upon the previous best known bounds which were only polynomially small, i.e., of the order $n^{-Ω(1)}$. Our key technical tool is the notion of \emph{algebraic spreadness} adapted from the breakthrough work of Kelley and Meka (FOCS '23) on sets free of 3-term progressions.

Authors: Alexander Firbas

A graph is geometric 1-planar if it admits a straight-line drawing where each edge is crossed at most once. We provide the first systematic study of the parameterized complexity of recognizing geometric 1-planar graphs. By substantially extending a technique of Bannister, Cabello, and Eppstein, combined with Thomassen's characterization of 1-planar embeddings that can be straightened, we show that the problem is fixed-parameter tractable when parameterized by treedepth. Furthermore, we obtain a kernel for Geometric 1-Planarity parameterized by the feedback edge number $\ell$. As a by-product, we improve the best known kernel size of $O((3\ell)!)$ for 1-Planarity and $k$-Planarity under the same parameterization to $O(\ell \cdot 8^{\ell})$. Our approach naturally extends to Geometric $k$-Planarity, yielding a kernelization under the same parameterization, albeit with a larger kernel. Complementing these results, we provide matching lower bounds: Geometric 1-Planarity remains \NP-complete even for graphs of bounded pathwidth, bounded feedback vertex number, and bounded bandwidth.

Authors: Lotte Blank

Given two polygonal curves $P$ and $Q$ defined by $n$ and $m$ vertices with $m\leq n$, we show that the discrete Fréchet distance in 1D cannot be approximated within a factor of $2-\varepsilon$ in $\mathcal{O}((nm)^{1-δ})$ time for any $\varepsilon, δ>0$ unless OVH fails. Using a similar construction, we extend this bound for curves in 2D under the continuous or discrete Fréchet distance and increase the approximation factor to $1+\sqrt{2}-\varepsilon$ (resp. $3-\varepsilon$) if the curves lie in the Euclidean space (resp. in the $L_\infty$-space). This strengthens the lower bound by Buchin, Ophelders, and Speckmann to the case where $m=n^α$ for $α\in(0,1)$ and increases the approximation factor of $1.001$ by Bringmann. For the discrete Fréchet distance in 1D, we provide an approximation algorithm with optimal approximation factor and almost optimal running time. Further, for curves in any dimension embedded in any $L_p$ space, we present a $(3+\varepsilon)$-approximation algorithm for the continuous and discrete Fréchet distance using $\mathcal{O}((n+m^2)\log n)$ time, which almost matches the approximation factor of the lower bound for the $L_\infty$ metric.

Authors: Zhengding Hu, Jingwen Sun, Le Jiang, Yuhao Wang, Junqing Lin, Yi Zong, Guangzhong Sun

As one of the most fundamental problems in graph processing, the Single-Source Shortest Path (SSSP) problem plays a critical role in numerous application scenarios. However, existing GPU-based solutions remain inefficient, as they typically rely on a single, fixed queue design that incurs severe synchronization overhead, high memory latency, and poor adaptivity to diverse inputs. To address these inefficiencies, we propose MultiLevelMultiQueue (MLMQ), a novel data structure that distributes multiple queues across the GPU's multi-level parallelism and memory hierarchy. To realize MLMQ, we introduce a cache-like collaboration mechanism for efficient inter-queue coordination, and develop a modular queue design based on unified Read and Write primitives. Within this framework, we expand the optimization space by designing a set of GPU-friendly queues, composing them across multiple levels, and further providing an input-adaptive MLMQ configuration scheme. Our MLMQ design achieves average speedups of 1.87x to 17.13x over state-of-the-art implementations. Our code is open-sourced at https://github.com/Leo9660/MLMQ.git.

Authors: Diptarka Chakraborty, Rudrayan Kundu, Nidhi Purohit, Aravinda Kanchana Ruwanpathirana

Given a set of strings over a specified alphabet, identifying a median or consensus string that minimizes the total distance to all input strings is a fundamental data aggregation problem. When the Hamming distance is considered as the underlying metric, this problem has extensive applications, ranging from bioinformatics to pattern recognition. However, modern applications often require the generation of multiple (near-)optimal yet diverse median strings to enhance flexibility and robustness in decision-making. In this study, we address this need by focusing on two prominent diversity measures: sum dispersion and min dispersion. We first introduce an exact algorithm for the diameter variant of the problem, which identifies pairs of near-optimal medians that are maximally diverse. Subsequently, we propose a $(1-ε)$-approximation algorithm (for any $ε>0$) for sum dispersion, as well as a bi-criteria approximation algorithm for the more challenging min dispersion case, allowing the generation of multiple (more than two) diverse near-optimal Hamming medians. Our approach primarily leverages structural insights into the Hamming median space and also draws on techniques from error-correcting code construction to establish these results.

Authors: T. R. Avila, Lars Rohwedder, Leo Wennmann

Recent concurrent work by Dupré la Tour and Fujii and by Hollender, Manurangsi, Meka, and Suksompong [ITCS'26] introduced a generalization of classical discrepancy theory to non-additive functions, motivated by applications in fair division. As many classical techniques from discrepancy theory seem to fail in this setting, including linear algebraic methods like the Beck-Fiala Theorem [Discrete Appl. Math '81], it remains widely open whether comparable non-additive bounds can be achieved. Towards a better understanding of non-additive discrepancy, we study coverage functions in a sparse setting comparable to the classical Beck-Fiala Theorem. Our setting generalizes the additive Beck-Fiala setting, rank functions of partition matroids, and edge coverage in graphs. More precisely, assuming each of the $n$ items covers only $t$ elements across all functions, we prove a constructive discrepancy bound that is polynomial in $t$, the number of colors $k$, and $\log n$.

Authors: Yaniv Sadeh, Haim Kaplan

We study the maintenance of a $(Δ+C)$-edge-coloring ($C\ge 1$) in a fully dynamic graph $G$ with maximum degree $Δ$. We focus on minimizing \emph{recourse} which equals the number of recolored edges per edge updates. We present a new technique based on an object which we call a \emph{shift-tree}. This object tracks multiple possible recolorings of $G$ and enables us to maintain a proper coloring with small recourse in polynomial time. We shift colors over a path of edges, but unlike many other algorithms, we do not use \emph{fans} and \emph{alternating bicolored paths}. We combine the shift-tree with additional techniques to obtain an algorithm with a \emph{tight} recourse of $O\big( \frac{\log n}{\log \frac{Δ+C}{Δ-C}}\big)$ for all $C \ge 0.62Δ$ where $Δ-C = O(n^{1-δ})$. Our algorithm is the first deterministic algorithm to establish tight bounds for large palettes, and the first to do so when $Δ-C=o(Δ)$. This result settles the theoretical complexity of the recourse for large palettes. Furthermore, we believe that viewing the possible shifts as a tree can lead to similar tree-based techniques that extend to lower values of $C$, and to improved update times. A second application is to graphs with low arboricity $α$. Previous works [BCPS24, CRV24] achieve $O(ε^{-1}\log n)$ recourse per update with $C\ge (4+ε)α$, and we improve by achieving the same recourse while only requiring $C \ge (2+ε)α- 1$. This result is $Δ$-adaptive, i.e., it uses $Δ_t+C$ colors where $Δ_t$ is the current maximum degree. Trying to understand the limitations of our technique, and shift-based algorithms in general, we show a separation between the recourse achievable by algorithms that only shift colors along a path, and more general algorithms such as ones using the Nibbling Method [BGW21, BCPS24].

Authors: Shinsaku Sakaue, Yuichi Yoshida

We study online learning in the random-order model, where the multiset of loss functions is chosen adversarially but revealed in a uniformly random order. Building on the batch-to-online conversion by Dong and Yoshida (2023), we show that if an offline algorithm admits a $(1+\varepsilon)$-approximation guarantee and the effect of $\varepsilon$ on its average sensitivity is characterized by a function $\varphi(\varepsilon)$, then an adaptive choice of $\varepsilon$ yields a small-loss regret bound of $\tilde O(\varphi^{\star}(\mathrm{OPT}_T))$, where $\varphi^{\star}$ is the concave conjugate of $\varphi$, $\mathrm{OPT}_T$ is the offline optimum over $T$ rounds, and $\tilde O$ hides polylogarithmic factors in $T$. Our method requires no regularity assumptions on loss functions, such as smoothness, and can be viewed as a generalization of the AdaGrad-style tuning applied to the approximation parameter $\varepsilon$. Our result recovers and strengthens the $(1+\varepsilon)$-approximate regret bounds of Dong and Yoshida (2023) and yields small-loss regret bounds for online $k$-means clustering, low-rank approximation, and regression. We further apply our framework to online submodular function minimization using $(1\pm\varepsilon)$-cut sparsifiers of submodular hypergraphs, obtaining a small-loss regret bound of $\tilde O(n^{3/4}(1 + \mathrm{OPT}_T^{3/4}))$, where $n$ is the ground-set size. Our approach sheds light on the power of sparsification and related techniques in establishing small-loss regret bounds in the random-order model.

Authors: Prathamesh Dharangutte, Jingcheng Liu, Pasin Manurangsi, Akbar Rafiey, Phanu Vajanopath, Zongrui Zou

We study approximation algorithms for Maximum Constraint Satisfaction Problems (Max-CSPs) under differential privacy (DP) where the constraints are considered sensitive data. Information-theoretically, we aim to classify the best approximation ratios possible for a given privacy budget $\varepsilon$. In the high-privacy regime ($\varepsilon \ll 1$), we show that any $\varepsilon$-DP algorithm cannot beat a random assignment by more than $O(\varepsilon)$ in the approximation ratio. We devise a polynomial-time algorithm which matches this barrier under the assumptions that the instances are bounded-degree and triangle-free. Finally, we show that one or both of these assumptions can be removed for specific CSPs--such as Max-Cut or Max $k$-XOR--albeit at the cost of computational efficiency.

Pseudorandom generators (PRGs) for low-degree polynomials are a central object in pseudorandomness, with applications to circuit lower bounds and derandomization. Viola’s celebrated construction (CC 2009) gives a PRG over the binary field, but with seed length exponential in the degree $d$. This exponential dependence can be avoided over sufficiently large fields. In particular, Dwivedi, Guo, and Volk (RANDOM 2024) constructed PRGs with optimal seed length over fields of size exponential in $d$. The latter builds on the framework of Derksen and Viola (FOCS 2022), who obtained optimal-seed constructions over fields of size polynomial in $d$, although growing with the number of variables $n$. In this work, we construct the first PRG with optimal seed length for degree-$d$ polynomials over fields of polynomial size, specifically $q \approx d^4$, assuming, as in [DGV], sufficiently large characteristic. Our construction follows the framework of [DV, DGV] and reduces the required field size by replacing the hitting-set generator used in prior work with a new pseudorandom object. We also observe a threshold phenomenon in the field-size dependence. Specifically, we prove that constructing PRGs over fields of sublinear size, for example $q = d^{0.99}$ where $q$ is a power of two, would already yield PRGs for the binary field with comparable seed length via our reduction, provided that the construction imposes no restriction on the characteristic. While a breakdown of existing techniques has been noted before, we prove that this phenomenon is inherent to the problem itself, irrespective of the technique used.

This is just a quick announcement that I’ll be hosting Nate Soares—who coauthored the self-explanatorily titled If Anyone Builds It, Everyone Dies with Eliezer Yudkowsky—tomorrow (Tuesday) at 5PM at UT Austin, for a brief talk followed by what I’m sure will be an extremely lively Q&A about his book. Anyone in the Austin area is welcome to join us.

By Scott

Authors: Jonah Brown-Cohen, Geoffrey Irving, Simon C. Marshall, Ilan Newman, Georgios Piliouras, Mario Szegedy

AI safety via debate uses two competing models to help a human judge verify complex computational tasks. Previous work has established what problems debate can solve in principle, but has not analysed the practical cost of human oversight: how many queries must the judge make to the debate transcript? We introduce Debate Query Complexity}(DQC), the minimum number of bits a verifier must inspect to correctly decide a debate. Surprisingly, we find that PSPACE/poly (the class of problems which debate can efficiently decide) is precisely the class of functions decidable with O(log n) queries. This characterisation shows that debate is remarkably query-efficient: even for highly complex problems, logarithmic oversight suffices. We also establish that functions depending on all their input bits require Omega(log n) queries, and that any function computable by a circuit of size s satisfies DQC(f) <= log(s) + 3. Interestingly, this last result implies that proving DQC lower bounds of log(n) + 6 for languages in P would yield new circuit lower bounds, connecting debate query complexity to central questions in circuit complexity.

Authors: Matthias Christandl, Aram W. Harrow, Greta Panova, Pietro M. Posta, Michael Walter

Some representation-theoretic multiplicities, such as the Kostka and the Littlewood-Richardson coefficients, admit a combinatorial interpretation that places their computation in the complexity class #P. Whether this holds more generally is considered an important open problem in mathematics and computer science, with relevance for geometric complexity theory and quantum information. Recent work has investigated the quantum complexity of particular multiplicities, such as the Kronecker coefficients and certain special cases of the plethysm coefficients. Here, we show that a broad class of representation-theoretic multiplicities is in #BQP. In particular, our result implies that the plethysm coefficients are in #BQP, which was only known in special cases. It also implies all known results on the quantum complexity of previously studied coefficients as special cases, unifying, simplifying, and extending prior work. We obtain our result by multiple applications of the Schur transform. Recent work has improved its dependence on the local dimension, which is crucial for our work. We further describe a general approach for showing that representation-theoretic multiplicities are in #BQP that captures our approach as well as the approaches of prior work. We complement the above by showing that the same multiplicities are also naturally in GapP and obtain polynomial-time classical algorithms when certain parameters are fixed.

Authors: Sandip Das, Sk Samim Islam, Daniel Lokshtanov

A multipacking in an undirected graph $G=(V,E)$ is a set $M\subseteq V$ such that for every vertex $v\in V$ and for every integer $r\geq 1$, the ball of radius $r$ around $v$ contains at most $r$ vertices of $M$, that is, there are at most $r$ vertices in $M$ at a distance at most $r$ from $v$ in $G$. The Multipacking problem asks whether a graph contains a multipacking of size at least $k$. For more than a decade, it remained an open question whether the Multipacking problem is NP-complete or solvable in polynomial time. Whereas the problem is known to be polynomial-time solvable for certain graph classes (e.g., strongly chordal graphs, grids, etc). Foucaud, Gras, Perez, and Sikora [Algorithmica 2021] made a step towards solving the open question by showing that the Multipacking problem is NP-complete for directed graphs and it is W[1]-hard when parameterized by the solution size. In this paper, we prove that the Multipacking problem is NP-complete for undirected graphs, which answers the open question. Moreover, the problem is W[2]-hard for undirected graphs when parameterized by the solution size. Furthermore, we have shown that the problem is NP-complete and W[2]-hard (when parameterized by the solution size) even for various subclasses: chordal, bipartite, and claw-free graphs. Whereas, it is NP-complete for regular, and CONV graphs (intersection graphs of convex sets in the plane). Additionally, the problem is NP-complete and W[2]-hard (when parameterized by the solution size) for chordal $\cap$ $\frac{1}{2}$-hyperbolic graphs, which is a superclass of strongly chordal graphs where the problem is polynomial-time solvable. On the positive side, we present an exact exponential-time algorithm for the Multipacking problem on $n$-vertex general graphs, which breaks the $2^n$ barrier by achieving a running time of $O^*(1.58^n)$.

Authors: Yaé U. Gaba

The complexity quasi-metric, introduced by Schellekens, provides a topological framework where the asymmetric nature of computational comparisons -- stating that one algorithm is faster than another carries different information than stating the second is slower than the first -- finds precise mathematical expression. In this paper we develop a comprehensive theory of expansive homeomorphisms on complexity quasi-metric spaces. Our central result establishes that the scaling transformation $ψ_α(f)(n)=αf(n)$ is expansive on the complexity space $(\C,d_\C)$ if and only if $α\neq 1$. The $δ$-stable sets arising from this dynamics correspond exactly to asymptotic complexity classes, providing a dynamical characterisation of fundamental objects in complexity theory. We prove that the canonical coordinates associated with $ψ_α$ are hyperbolic with contraction rate $λ=1/α$ and establish a precise connection between orbit separation in the dynamical system and the classical time hierarchy theorem of Hartmanis and Stearns. We further investigate unstable sets, conjugate dynamics, and topological entropy estimates for the scaling map. Throughout, concrete algorithms and Python implementations accompany the proofs, making every result computationally reproducible. SageMath verification snippets are inlined alongside the examples, and the full code is available in the companion repository.

Authors: Pin-Hsian Lee, Te-Cheng Liu, Meng-Tsung Tsai

We give a short, self-contained, and easily verifiable proof that determining the outerthickness of a general graph is NP-hard. This resolves a long-standing open problem on the computational complexity of outerthickness. Moreover, our hardness result applies to a more general covering problem $P_F$, defined as follows. Fix a proper graph class $F$ whose membership is decidable. Given an undirected simple graph $G$ and an integer $k$, the task is to cover the edge set $E(G)$ by at most $k$ subsets $E_1,\ldots,E_k$ such that each subgraph $(V(G),E_i)$ belongs to $F$. Note that if $F$ is monotone (in particular, when $F$ is the class of all outerplanar graphs), any such cover can be converted into an edge partition by deleting overlaps; hence, in this case, covering and partitioning are equivalent. Our result shows that for every proper graph class $F$ whose membership is decidable and that satisfies all of the following conditions: (a) $F$ is closed under topological minors, (b) $F$ is closed under $1$-sums, and (c) $F$ contains a cycle of length $3$, the problem $P_F$ is NP-hard for every fixed integer $k\ge 3$. In particular: For $F$ equal to the class of all outerplanar graphs, our result settles the long-standing open problem on the complexity of determining outerthickness. For $F$ equal to the class of all planar graphs, our result complements Mansfield's NP-hardness result for the thickness, which applies only to the case $k=2$. It is also worth noting that each of the three conditions above is necessary. If $F$ is the class of all eulerian graphs, then cond. (a) fails. If $F$ is the class of all pseudoforests, then cond. (b) fails. If $F$ is the class of all forests, then cond. (c) fails. For each of these three classes $F$, the problem $P_F$ is solvable in polynomial time for every fixed integer $k\ge 3$, showing that none of the three conditions can be dropped.