Theory of Computing Report

All Souls College invites applications for a Post-doctoral Fellowship in Theoretical Computer Science. Those elected will be expected to take up their Fellowship on 1 October 2027. The Fellowship is for five-years, fixed-term, and non-renewable.

Website: https://www.asc.ox.ac.uk/post-doctoral-research-fellowships
Email: pdrf.admin@all-souls.ox.ac.uk

By shacharlovett

Authors: Harshit Goyal, Sudakshina Dutta

This paper studies the computational complexity of verification problems for Binarized Neural Networks (BNNs), where activations (and sometimes weights) are binary. We analyze two problems: satisfiability and robustness under uniform image occlusion. We show that BNN satisfiability is NP-complete via a reduction from Boolean satisfiability problem (SAT), and that uniform occlusion induces a piecewise-constant structure in the network output, enabling a polynomial-time robustness-checking algorithm.

Authors: Neil Krishnan, Elchanan Mossel

We study the role of depth in ReLU networks with discrete (Boolean) inputs and real-valued outputs, complementing two established lines of work. For Boolean inputs, striking depth separation results were proven for $\mathsf{AC}^0$ but with threshold ($\mathsf{TC}^0$) or ReLU gates depth separation is only established for depth two vs. three. On the other hand, for {\em real-valued} functions and ReLU networks, Telgarsky's (2016) constructed a simple one variable class of functions which establishes separation at higher depths. In this paper we are interested to establish an all-depths depth separation for ReLU networks on $\{0,1\}^n$. We do so by exhibiting an explicit family of functions computable exactly by a ReLU network of depth $n+1$ and constant width, such that any ReLU network of depth $d$ and width $w$ computing the function exactly must satisfy $w^d = Ω(2^n)$; in particular, no network of depth $d = o(n/\log n)$ can compute it with width polynomial in $n$. We note that our lower bound relies on \emph{exact, infinite-accuracy} computation as an exponential precision truncation of the output is computable by a polynomial-size $\mathsf{TC}^0$ circuit.

Authors: Tom Hadfield

We define a new measure of intrinsic dimension of a data manifold, which we call the Patnaik-Pearson dimension, and apply this to internal representations of neural networks, in particular transformers. The inspiration for this comes from the HTSR and SETOL work of Martin, Mahoney and Hinrichs, combined with the TwoNN intrinsic dimension estimator of Facco et al. We prove various properties of this intrinsic dimension estimator. Treating weight matrices of neural networks as data manifolds, for weight matrices whose Empirical Spectral Density follows a Pareto (Power Law) distribution, we relate the Patnaik-Pearson dimension to the HTSR and SETOL analysis, and show that critical values of the tail exponent coincide for the two approaches. Using a combination of theoretical and numerical techniques, we study the behaviour of the Patnaik-Pearson dimension of a data manifold under the transformations typical to neural networks. We apply this machinery to the BERT-base and DeepSeek-R1-Distill-Qwen-1 models, to investigate first the Patnaik-Pearson dimension of the initial data manifold of token embeddings, and second the evolution of the Patnaik-Pearson dimension as token embeddings pass through the layers of the model. Code and notebooks used for the numerical results presented here is available at https://github.com/tdhadfield/PatnaikPearson

Authors: Sheng-Gwo Chen, Chen-Chang Peng

The concept of geodesic-like curves was introduced by Chen in 2010 as a method for estimating shortest paths (geodesics) on parametric surfaces, with its convergence established theoretically. However, an efficient numerical computational framework has not yet been developed. In this paper, we propose an elegant and efficient approach for computing geodesic-like curves by leveraging deep learning and Physics-Informed Neural Networks (PINNs). Under the proposed framework, not only can single parametric surfaces be handled efficiently, but a broad class of complex parametric surfaces including multi-surface systems with $C^0$ or higher continuity and surfaces of revolution can also be robustly addressed.

Authors: David Eppstein

The Erdős-Anning theorem states that any point set for which all distances are integers, in a Euclidean space of any dimension, must be either finite or collinear. We prove the same result in hyperbolic space of any dimension. A quantitative form of our result also extends for the first time to Euclidean spaces of dimension greater than two: if a set of points with integer distances in $\mathbb{E}^D$ or $\mathbb{H}^D$ has a subset of $D+1$ points in general position whose diameter is $d$, then the whole set has size $O(D(d+1)^D)$. To prove these results we formulate a lemma that, if the graph of external tangencies of a system of spheres in Euclidean or hyperbolic space contains a $K_{a,b}$ subgraph for $a,b\ge 3$, then the sets of spheres on each side of this biclique have centers that lie on a hyperplane. This lemma also implies that, in multilateration (determining a position from differences of distances to known landmarks), $D+1$ non-coplanar landmarks always suffice to limit the position to two possibilities.

Authors: Huck Bennett, Kyle Fridberg

A recent line of work motivated by cryptographic applications has studied the complexity of the Lattice Isomorphism Problem (LIP). In this work, we study LIP on self-dual lattices $\cal{L} \subset \mathbb{R}^n$, which appear naturally in many applications. Our main results are a $2^{n/2 + o(n)}$-time randomized algorithm for LIP and a $\mathsf{coNP}$ protocol for LIP on a broad class of self-dual lattices. These results extend recent work on ZLIP, the problem of deciding whether a lattice is isomorphic to $\mathbb{Z}^n$. In particular, the former result extends the $2^{n/2 + o(n)}$-time algorithms for ZLIP of Bennett, Ganju, Peetathawachai, and Stephens-Davidowitz (Eurocrypt, 2023) and of Ducas (Des. Codes Cryptogr., 2024). The latter result extends the $\mathrm{ZLIP} \in \mathsf{coNP}$ result of Hunkenschröder (Math. Prog. Series A, 2024). Our results leverage two key structural properties of self-dual lattices $\cal{L} \subset \mathbb{R}^n$: (1) every such lattice $\cal{L}$ is isomorphic to $\cal{L}_0 \oplus \mathbb{Z}^r$ for some self-dual lattice $\cal{L}_0$ with $λ_1(\cal{L}_0)^2 \geq 2$, and (2) every such lattice $\cal{L}$ has \emph{characteristic vectors}, i.e., there exist vectors $\mathbf{w} \in \cal{L}$ such that for every $\mathbf{v} \in \cal{L}$, $\langle\mathbf{v}, \mathbf{w}\rangle \equiv \langle\mathbf{v}, \mathbf{v}\rangle \pmod{2}$. Our results use a line of work by Elkies and Gaulter on lattices with long shortest characteristic vectors, and can be strengthened assuming a positive answer to a related question of Elkies (Math. Res. Lett., 1995). We also study Permutation Code Equivalence (PCE) on self-dual codes, and we observe that similar structural properties imply a polynomial-time algorithm for PCE on certain such codes. This gives a natural class of codes with large hull for which PCE is easy.

Authors: Prashant Gokhale, Piotr Indyk, Yuhao Liu, Sandeep Silwal, Tony Chang Wang, Haike Xu

Computing geometric representations of data is a cornerstone of modern machine learning, typically achieved by training dual encoders which map queries and documents into a shared embedding space. Recent work of You et al. [NeurIPS '25] has extended this approach to hierarchical retrieval, where relevance is determined by the ancestor-descendant relationships in a Directed Acyclic Graph (DAG). While previous work has shown that valid embeddings exist when the number of descendants is small, these bounds degrade significantly for deep hierarchies, requiring dimensions as large as the total number of nodes. In this paper, we investigate compact reachability embeddings for more general graph classes and provide theoretical guarantees for representing hierarchies using embeddings whose dimension depends on structural graph parameters. We prove that for any directed tree, there exists a reachability embedding in constant dimension 3, independent of the tree's size or depth. We generalize this result to graphs characterized by treewidth $t$, constructing embeddings of dimension $O(t \log n)$, where $n$ is the number of nodes. Complementing these upper bounds, we provide matching or near-matching lower bounds, showing that dimension $Ω(n)$ is necessary for general DAGs and $Ω(t/\log(n/t))$ is required for graphs of treewidth $t$. We also obtain upper and lower bounds parameterized by the number of cross-edges in the DAG. We additionally show that our embeddings can be constructed on real world datasets, and that they give much smaller dimensions in high recall regimes compared to prior embeddings with theoretical guarantees.

Authors: Faruk Alpay, Levent Sarioglu

Approximate membership queries in streams often need recent-window semantics rather than membership over all items ever seen. This paper studies guarded epoch Bloom filters, a sliding-window alternative to counting and stable Bloom filters. The structure partitions a fixed bit budget into rotating epochs, inserts only into the current epoch, clears whole segments at epoch boundaries, and keeps one additional guard epoch. This guard yields a deterministic live-window invariant: every item inserted in the last W positions remains represented, while rotation-induced stale retention is bounded by one epoch beyond the target window. We give the construction, prove its live-coverage and bounded-staleness properties, derive a false-positive approximation, and include a blocked variant that improves locality by confining probes to one block per epoch. Experiments cover 225 synthetic streaming configurations and 45 configurations from a timestamp-ordered web-server access-log stream. At 14 bits per live item, the guarded epoch filter reduces median synthetic false positives from 0.191 for a four-bit counting Bloom baseline to 0.02225 while preserving zero measured live-key false negatives. The method is not a replacement for exact deletion; it targets systems where bounded stale positives are acceptable but false negatives inside the live window are not.

Authors: Antoine Amarilli, Florin Manea, Tina Ringleb, Markus L. Schmid

For strings $u, D \in Σ^*$, a subsequence embedding of $u$ in $D$ is a function $e \colon \{1, 2, \ldots, |u|\} \to \{1, 2, \ldots, |D|\}$ with $e(i) < e(i+1)$ for every $i \in \{1, 2, \ldots, |u|-1\}$ and the $i$-th symbol of $u$ equals the $e(i)$-th symbol of $D$. A gap-constraint for $u$ is a triple $(i, j, L)$ with $1 \leq i < j \leq |u|$ and $L$ is a regular language over $Σ$. An embedding $e$ satisfies a gap-constraint $(i, j, L)$ if the factor of $D$ strictly between positions $e(i)$ and $e(j)$ is a word from $L$. We investigate the subsequence matching problem with gap-constraints, which is relevant in the context of complex event recognition (CER): given $u, D \in Σ^*$ and a set $C$ of gap-constraints, find an embedding of $u$ in $D$ that satisfies all gap-constraints from $C$. In general, subsequence matching is NP-complete and the only known tractable variants restrict the interval structure of the gap-constraints. In this work, we show that we can solve subsequence matching with gap-constraints with an arbitrary interval structure rather efficiently (in fact, optimally under SETH) in time $O(|D| (|u| + |C|))$ if the gap-constraint languages satisfy a property which we dub left-convexity: whenever $u v w \in L$ and $v \in L$, then also $uv \in L$. Left-convex languages are sufficiently expressive to model interesting real-world scenarios considered in CER, e.g., length constraints $L = \{w \mid a \leq |w| \leq b\}$ for $a, b \in \mathbb{N}$. We also show how our algorithm can be used in order to efficiently enumerate all satisfying embeddings, which is particularly relevant for possible applications in CER. Finally, we show how non-left-convex languages can lead to intractability, i.e., if in addition to length constraints we allow $\{aa, ε\}$ as the only non-left-convex constraint language, then the problem is NP-complete again.

Authors: Tatiana Belova, Yuriy Dementiev, Danil Sagunov

The field of learning-augmented algorithms has demonstrated that machine-learned predictions can bypass worst-case lower bounds across a wide range of problems. So far, however, the focus has been almost exclusively on polynomial-time algorithms, where predictions improve competitive ratios, approximation guarantees, or running times. In this paper, we raise the question of whether predictions can push the frontier of exact exponential-time algorithms for NP-hard problems. We answer this question affirmatively by proposing a general approach that augments an entire family of state-of-the-art exact algorithms for a variety of subset selection problems. We show that a noisy predictor that is only marginally better than random guessing suffices to provably reduce the search space, and that the resulting runtime speedup scales smoothly with the prediction quality. Importantly, our algorithms require only pairwise independence of predictions or, alternatively, do not require the knowledge of the predictor's accuracy - both strictly weaker and more realistic settings than typically assumed.

Authors: Roman Pauli, Eric Osterkamp, Dominik Köppl

Cartesian tree matching (CTM) is a structural pattern matching approach that identifies sequences with the same Cartesian tree topology, making it suitable for data with natural variability where exact comparisons carry little semantic meaning. While theoretical algorithms for CTM have been studied extensively, systematic empirical evaluations of practical implementations remain rare. This article presents an implementation of the Cartesian Extended Burrows-Wheeler Transform (ceBWT), a BWT-based index structure for CTM. The implementation supports both a dynamically extendable and a statically compressed index variant.

Authors: Christopher En, Yuri Faenza, Andrea Lodi, Gonzalo Muñoz

We study the problem of fair online resource allocation, motivated by applications such as refugee resettlement and airline scheduling, where agents arrive sequentially and must be assigned to facilities with limited capacities. We introduce a model that maximizes the overall welfare subject to resource constraints and a Lipschitz fairness requirement, which ensures that similar agents arriving in the same batch receive similar expected outcomes. We first analyze the offline problem, proving that the value of the optimal fair allocation is at least an $Ω(1/γ)$ fraction of the optimal unfair allocation, where $γ$ is the fairness coefficient, thereby bounding the price of fairness. For the online setting, we propose an algorithm based on dual mirror descent that enforces fairness constraints within batches while estimating optimal dual variables. We prove that this algorithm achieves sublinear regret relative to the optimal offline fluid benchmark. Finally, we validate our theoretical results using real-world data from the Refugee Economies Programme, demonstrating the algorithm's performance and examining the trade-offs between welfare maximization and fairness enforcement.

My latest preprint, “Tangent spheres and integer distances” (arXiv:2606.18569, to appear at CCCG), involves the patterns of external tangencies of circles, spheres or higher-dimensional hyperspheres. You can make a graph whose vertices are a given set of spheres and whose edges are pairs of externally-tangent spheres, and I’d like to understand which graphs are possible. By the circle packing theorem, any planar graph can be represented by interior-disjoint circles in this way, but here I’m not requiring disjointness. So, for instance, you can represent any unit distance graph in the plane (such as the Petersen graph below) by expanding each vertex of the graph into a unit-diameter circle.

In three dimensions, you can produce spheres whose tangencies form arbitrarily large complete bipartite graphs \(K_{n,n}\) by placing \(n\) spheres interior to a torus, like a ball-bearing race or those cat toys with balls rolling around a toroidal track, and another \(n\) spheres tangent to them, centered on the axis of the torus. And by a form of Descartes’ theorem, any four mutually tangent spheres (a \(K_4\) graph of tangencies) can be completed to a \(K_5\) in two different ways, but the two added spheres are not tangent to each other, so one cannot form a \(K_6\) graph.

Given these examples, you might think that it is the high local connectivity of the complete graph \(K_6\) that makes it unrealizable, and the local independence of the complete bipartite graph \(K_{n,n}\) (each vertex has an independent set of neighbors) that makes it realizable. But things are more subtle than that. For every odd \(k\) I can prove the existence of a graph in which each vertex has an independent set of six neighbors, the shortest odd cycle has length \(k\), and there is no realization as a subgraph of external tangencies in \(\mathbb{R}^3\).

This follows from the main lemma in the paper: if a system of spheres or hyperspheres in \(\mathbb{R}^d\) has external tangencies that include a subgraph of the form \(K_{a,b}\), with both \(a\) and \(b\) having at least three spheres, then the sets of spheres on each of the two sides of this bipartite graph have centers that lie on a hyperplane. This is trivial in two dimensions (no such system can exist because it would lead to a planar drawing of \(K_{3,3}\)) but as we have seen, even three-dimensional spheres can have arbitrarily large complete bipartite graphs. Another famous system of spheres, Soddy’s hexlet, has a \(K_{3,6}\) subgraph, and spheres with the tangency graph \(K_{2,2,2,2}\) have many \(K_{4,4}\) subgraphs. (The image below shows Soddy’s hexlet in a form where two of the spheres have degenerated to flat planes.) The lemma applies to these configurations and proves that the subsets of spheres on each side of each bipartition have coplanar centers. The paper then uses this lemma to prove that in localization from differences of distances to landmarks (as used by GPS), any four non-coplanar landmarks suffice, and to generalize the Erdős–Anning theorem, that Euclidean point sets with integer distances are finite or collinear, to arbitrary-dimensional hyperbolic spaces.

So let’s use the same lemma to construct a graph with no short odd cycles and small independent sets of neighbors for each vertex, that cannot be realized by spheres in \(\mathbb{R}^3\). To do so, blow up each vertex of a \(k\)-cycle by replacing it with an independent set of three vertices. Here’s a confluent drawing for \(k=5\) and \(d=3\):

Suppose that this graph had a realization as the external tangencies of spheres in \(\mathbb{R}^3\). No two spheres in a blown-up triple of spheres can be concentric, because concentric spheres could not be tangent to the same neighbors. Each triple \(T\) of spheres (no two concentric), has a unique circle (or degenerate line) \(O_T\) orthogonal to \(T\), the circle or line through the centers of the spheres in \(T\). Any Möbius transformation of space takes circles to circles and spheres to spheres and preserves tangency and orthogonality, so the transformation of the circle \(O_T\) is the circle \(O_{T'}\) for the transformed triple \(T'\). We can perturb the realization by a Möbius transformation so that external tangencies remain external and so that, after this perturbation, the point at infinity does not lie on any \(O_T\). After this perturbation, none of the \(O_T\) degenerate to lines, and therefore the centers of each triple of spheres determine a unique plane. By the lemma from the preprint, each pair of triples two steps along the cycle from each other have centers that lie on the same plane, and because the cycle has odd length, all spheres have coplanar centers. But then this realization would continue to be valid in the plane of all the sphere centers, and we already know that the many \(K_{3,3}\) subgraphs of this graph cannot be realized in the plane. This contradiction means that the supposed three-dimensional realization of our blown-up cycle graph cannot exist.

In four or more dimensions, the second part of the argument still shows that the \(d\)-blowup of a \(k\)-cycle has no realization with sphere centers in each blown-up \(d\)-tuple of spheres in general position. But the first part, where we use a Möbius transformation to perturb everything into general position, stops working. If one blown-up \(d\)-tuple of spheres has cocircular centers, like the ball bearing cat toy example in 3d, its two neighboring \(d\)-tuples can each be placed on lines orthogonal to the circle and through its center, but in four dimensions there is a whole plane orthogonal to a circle and through its center. We can choose two different lines on this plane, and then different circles orthogonal to each of these lines, etc., creating enough flexibility as one progresses around the cycle that a realization might be possible. But my powers of four-dimensional visualization aren’t strong enough for me to be certain that this works, and it might still be possible to prove that other locally independent graphs are unrealizable.

(Discuss on Mastodon)

By David Eppstein

Last week I saw a talk by Northwestern professor Nina Wieda on the history of the Silk Road, a network of trading routes across Asia active from the second century BCE until the mid-15th century. I knew of the Silk Road but was surprised by how much it used and fostered various technologies. 

It started with a technology that allowed for traveling long distances with limited access to water, better known as a camel. Travel was slow, it could take nearly two years to get from one end (modern day Turkey) to the other (China). Cities grew along the way for travelers and their protection, and for trading.

The travelers did not just carry silk and other materials for trade, the routes became an information superhighway of a sort. Religions spread including Buddhism, early Christianity and Manichaeism, an old religion that mostly divided the world into good and evil. Artistic style and influences spread as well with motifs like halos and winged figures appearing across widely separated cultures. Traders needed to converse in several languages, and documents could have several translations. 

The roads carried knowledge about technology itself from astronomy, calendars, medical information, geography and mathematical methods in text translated among the many languages. Travelers brought scribes that created a written language for Mongolian among others. Chinese papermaking made its way west reducing the cost of recording and transmitting information. Gunpowder technology also made its way into Europe from the east. 

A confluence of technologies helped hasten the end of the Silk Road. Marco Polo wrote about his travels along the Silk Road at the end of the 13th century but the account spread more widely with the advent of the printing press in the 15th century. The book inspired explorers who used advances in ship building and navigation to find water routes to the East (and Christopher Columbus to try a western route). These water routes would prove a faster cheaper way to ship goods between Europe and East Asia. The technological revolution shrunk or shuttered cities that used to host traders on the Silk Road. On the other hand, wealthy European traders would help fund and usher in the Renaissance. 

The Silk Road harkens to a time where, for the most part, people, goods and information travelled along the same routes at the same speed. Large cargo still moves fastest by ship, people by airplanes and information via wires and satellite nearly instantaneously.

When we think of technological disruption we think of the industrial revolution or even what's happening today, but the Silk Road reminds us that disruption has always been a part of the world's history, for bad and for good. 

By Lance Fortnow

The meme of the decade is maxximization: looksmaxxing, proteinmaxxing, moneymaxxing, longevitymaxxing. There’s nothing in the world that can’t be maxxed. All the kids are optimizing these days.

Now, it’s easy to tut-tut obsessive maxxers and see them as cautionary tales of culture gone wrong. But why is maxxing culture bad? We all respect people on humble searches for personal “improvement,” “development,” or “betterment” for themselves and their families. But isn’t “making something better” the same as maxxing? I’m coming around to thinking that the answer is no, and I don’t think it’s a matter of degree. The technical language of optimization—embraced by engineers and economists and influencing the rest of society—makes every quest for self-improvement into something grotesque.

In her phenomenal essay “The Ozempicization of the Economy,” Kyla Scanlon juxtaposes two different dietary interventions, the elimination diet vs. GLP-1 agonists, to draw out the limits of the language and mindset of optimization.

I had a bunch of friends who developed stomach issues in their twenties. Many of them went on the elimination diet for relief. For a month, they cut out everything from their diet except a few basic foods, like chicken breast, carrots, and rice. Then, they slowly added things back to their plate, maybe some basic vegetables, maybe some new meats. They journaled how they felt, seeing if they could find clear triggers for their symptoms. Inevitably, they would all find some culprits to avoid, and would establish a good baseline of what they could and couldn’t eat.

Elimination diets are excruciating. It takes months to get to a nearly normal diet that identifies a few problematic foods. And there’s no clear goal other than finding a broad set of accessible foods that you are happy eating.

Is the elimination diet a form of numerical optimization? What is the objective function? Is it “finding the largest array of foods I can eat while not feeling like shit?” How do you quantify “not feeling like shit?” When is it acceptable to stop? I don’t think it’s beneficial to view this process as maximizing a portfolio of food. Most people are far more concerned with the constraints on living a happy, normal life with a healthy relationship to food.

By contrast, GLP-1 agonists do feel like a miraculous optimization tool. If you take them, and you can tolerate the side effects, you’re going to lose weight. The number goes down for everyone.

Scanlon’s essay describes the madness of hoping everything will work like Ozempic. The maxxing community couches its searches for quick fixes in the language of rational science, but they appeal to the postmodern science I discussed last week. It’s a science that conflates “discovery” with a functional demonstration of utility. Interventions are judged by improvement over a baseline. It abandons explanations of how an intervention translates into an effect and replaces them with crude proofs of an impoverished notion of causality. An intervention causes an outcome if (and only if?) some randomized trial demonstrates a statistical difference when the intervention is compared to an appropriate control.

This is precisely the management view of epistemology Lyotard was calling out 50 years ago. A discovery is now a quantitative improvement of an outcome by a discrete move in a complex game. This not only rules out many other forms of discovery and knowledge-making, but it also restricts our attention to interventions that quantitatively improve outcomes for populations.

And it means the only equivocal interventions are the ones that work for everyone. For drugs like GLP-1 agonists, the effect is stark and undeniable. Ozempic is a drug that didn’t need a trial to demonstrate efficacy. It so unambiguously works for almost everyone who takes it. I’ve written about it here before. The p-values are zero. Everyone loses weight. It optimizes for everyone.

So perhaps the grotesque part, the unavoidable part of optimization culture, is the idea that there must be clear rules that work for everyone and guarantee large, measurable, quantified improvements and that every intervention must work like a miracle drug. The rare case of an impressive discovery like Ozempic convinces people that every problem can be solved by one simple trick.

This warps the questions we ask. It forces us into metrics and quantified scores. It warps the process itself. As Scanlon puts it, “The reason we can’t solve our problems is not lack of tools or information - it’s that the dominant method (add, optimize, measure) is the wrong method for the problem (figure out what’s poisoning you).”

Moreover, there is a grotesque endpoint in the shift from trying to be better to trying to be the best. It’s a shift from “as good as I can be” to “better than everyone else.” That doubled x-ed maxx implies there is a maxximum. A perfect destination that is as good as possible. It implies we’re all a peptide stack away from being better than everyone else.

But rejecting the extremes of maxxing culture doesn’t mean abandoning personal improvement. At the population level, bureaucratic pragmatism feels grotesquely crude. At the individual level, we celebrate people who seek to better themselves. Getting better often doesn’t need quantification. A person can get better at writing blogs or playing the guitar without validation from a numerical score. Moreover, we embrace difference at the individual level and acknowledge what works for one individual’s journey might not work for another. We even embrace relativism. Most of us accept that people can find what’s true for them personally by finding what works for them personally.

So what should we call trying to be better? What’s a word that juxtaposes against optimization? Tell me in the comments.

Subscribe now

By Ben Recht

[Guest post by Sam Hopkins]

We invite groups of interested researchers to submit workshop proposals for FOCS 2026 by July 31, 2026.

The FOCS 2026 workshops provide an informal forum for researchers to discuss important research questions, directions, and challenges in the field. Workshops often serve the vital purpose of introducing researchers to new areas and agendas. We also encourage workshops focusing on connections between theoretical computer science and other areas.

Format: Each workshop should be either 2.5 hours or 5 hours. All workshops are in person.

Proposal Submission

Workshop and tutorial proposals should fit within two pages. Please include a list of names and email addresses of the organizers, a brief description of the topic and the goals of the workshop, and the format (overview talks, invited talks, contributed talks, poster session, panel discussion, etc.) and proposed or tentatively confirmed speakers if known. The proposal should specify the desired duration (2.5 or 5 hours).

We encourage proposals to directly address how the topics will fit together and how the format will help researchers outside the particular subarea learn about it. If your proposal is accepted and you wish to solicit contributed talks, we can link to your call for contributions from the FOCS 2026 page. Feel free to contact the workshop co-chairs directly if you have any questions.

Co-chairs: Dakshita Khurana and Sam Hopkins

Submission Instructions

Proposals should be emailed to Dakshita Khurana (dakshita@illinois.edu) and Sam Hopkins (samhop@mit.edu) by July 31, 2026 anywhere on earth (AOE).

Proposers will be notified by August 14, 2026, whether their proposals have been accepted. Here is a sample template for workshop proposals; you may use a different format. The actual workshops will be held on November 8.

By Boaz Barak

Authors: Zhengfeng Ji, Yinchen Liu, Zhe'ou Zhou

Montanaro's polynomial representation expresses amplitudes of quantum circuits over the gates $H$, $Z$, $CZ$, and $CCZ$ as normalized gaps of degree-three polynomials over $\mathbb{F}_2$. The normalization is governed by the circuit width $w(f)$, the minimum number of qubits in any circuit realizing a polynomial $f$. Thus, efficient width minimization would give an approximate-counting route toward a combinatorial characterization of $BQP$. We study the computational complexity of this parameter. For degree-three polynomials with no constant term, deciding whether $w(f)\le k$ is $NP$-complete, resolving Montanaro's open question. We also prove $NP$-hardness of approximation within any factor $49/48-ε$, and show via a twin-copy construction that the exact and approximation hardness results also hold for degree-two polynomials. Under the Exponential Time Hypothesis, the exact problem admits no $2^{o(n)}$-time algorithm when $k=Θ(n)$. Complementing these hardness results, we give a nondeterministic polynomial-time search algorithm using $2\log_2\binom{n}{k}=O(k\log(en/k))$ witness bits, and a constructive fixed-parameter algorithm parameterized by $k$ with running time $k^{6k+o(k)}n+O(m)$.

Authors: Romy Williamson, Niloy Mitra

A surface representation suitable for geometry processing should be compact and explicit, provide global smoothness guarantees, support a wide range of surface topologies, and offer reliable access to differential quantities such as normals and surface energies, while remaining compatible with modern differentiable optimization. Existing neural representations typically sacrifice one or more of these properties: implicit fields typically require iso-surfacing for downstream use, while explicit neural maps are constrained by canonical-domain parametrizations or exhibit seam artifacts between local charts. We introduce Blended Chart Surfaces, a compact, network-free, explicit representation that is smooth by construction and anchored to user-provided topology. Given a coarse proxy mesh encoding the intended surface topology and approximate geometry, Blended Chart Surfaces jointly optimize for a polynomial map at each proxy vertex using an off-the-shelf optimizer to fit to an implicit target shape, avoiding the need for an input parametrization. Neighboring maps are fused using a smooth 'one-ring coordinate' blending scheme, decoupling topology and coarse geometry (carried by the proxy) from geometric details (carried by the local patches). The surface is globally smooth, fully differentiable, and enables stable evaluation of derivatives, making differential quantities and surface energies directly accessible. Additionally, our construction is equivariant to rigid motions and scaling of the proxy mesh. We evaluate Blended Chart Surfaces on various topologies and geometric complexity, and compare against explicit alternatives including interpolating-function baselines and mesh-displacement MLPs. Across these, Blended Chart Surfaces achieve a favorable trade-off among compactness, simplicity, access to differential quantities, and expressivity while remaining smooth across patch boundaries.

Authors: Wojciech Czerwiński, Daniel Dadush, Ekin Ergen, Arka Ghosh, Sławomir Lasota, Łukasz Orlikowski

In online vector balancing, vectors $t_1,\dots,t_n$ arrive one by one from a given set $T$ and the goal is to assign signs $s_1,\dots,s_n\in\{\pm1\}$ in an online manner so as to minimize the largest norm of any signed prefix sum $\sum_{i=1}^ks_i t_i$, $k \in [n]$. In this paper, we analyze the natural Euclidean greedy vector balancing algorithm for this problem: at each step $k$, the sign $s_k\in\{\pm1\}$ is chosen so that $s_k t_k$ has non-positive inner product with $\sum_{i=1}^{k-1} s_i\cdot t_i$. Our main result is the first finite bound, independent of the sequence length $n$, on the performance of greedy whenever $T$ is finite. When $T \subset \mathbb{R}^d$ consists of unit vectors, we prove that the signed sums produced by greedy have Euclidean norm at most $(2/δ_T)^{d-1}$, where $δ_T$ is the minimum non-zero distance between vectors in $T$ and subspaces spanned by vectors in $T$. The same upper bound holds when the sequences are composed of scaled down vectors in $T$. We also provide a simple set $T$ for which $Ω(\sqrt{d}/δ_T)$ is a lower bound. We analyze the greedy algorithm by proving the existence of a bounded convex $K_T$ that is $T$-absorbing: $\forall x\in K_T$ and $t \in\pm T$, $\langle x,t\rangle\leq0\Rightarrow x+t\in K_T$. We give an explicit construction of a set $K_T$ contained in a ball of radius $(2/δ_T)^{d-1}$, based on chains of subspaces spanned by vectors in $T$, which may be of independent interest. We generalize our greedy vector balancing bound to online vector partitioning, where the sequence $t_1,\dots,t_n$ must be partitioned in an online manner into $p$ subsequences. As an application, we prove a special case of a conjecture of Bosman et al. (arxiv:2402.19259), showing that a lexicographic version of total completion time scheduling under scenarios is polynomial time solvable when the number of scenarios is fixed.

Authors: Hui Wang, Xiaowei Li, Chenxin Zhang, Yifan Feng, Jianwei Zuo, Yumeng Tang, Xiuli Sun, Jianliu Wang, Bing Xie, Jiajia Luo

Patient-specific 3D reconstruction of pelvic organ geometry from MRI is important for pelvic floor modeling and downstream patient-specific analysis. However, while previous studies have focused primarily on either image segmentation or downstream use of 3D models, the reconstruction of high-fidelity, high-quality geometries remains labor-intensive and poorly standardized. The study introduced a hybrid deformable shape modeling framework that integrates deep learning prediction with iterative optimization for the reconstruction of the bladder, uterus, and rectum. The framework consists of three core components: a geometry-aware multi-level deep learning architecture that preserves topological consistency of pelvic organs; a two-stage amortized optimization training strategy that balances global shape capture and local surface refinement; and a holistic synergy mechanism--where iterative optimization provides supervision for deep learning during the training phase, and during inference, deep learning rapidly predicts the global organ morphology, followed by iterative optimization to refine local surfaces and mesh quality. This framework demonstrated marked superiority in geometric fidelity than current mainstream deep learning-based organ reconstruction models. For individual anatomical structures, the reconstructed 3D geometries for the bladder, rectum, and uterus achieved significantly lower Chamfer Distance values and higher Dice Similarity Coefficient scores. In addition, while maintaining high computational efficiency, the proposed architecture yielded superior overall volumetric mesh quality. At the patient level, the framework achieved higher mean values for the 10 worst elements for both minSICN and minSIGE compared to traditional geometric post-processing algorithms.

Authors: Matias de Jong van Lier, Shizuo Kaji, Keunsu Kim

We investigate the learning of interpretable bases in non-negative matrix factorisation (NMF) by regularising the topology of the learned basis functions. Our approach is motivated by the observation that many data modalities can be viewed as non-negative functions on a structured domain, where the quality of a basis is intrinsically linked to its topology. However, naive methods for incorporating the topology of the support are often hindered by discreteness and threshold dependence, rendering them unsuitable for continuous optimisation. We address these challenges by employing persistent homology as a stable, threshold-free topological quantifier and by designing topological scores that integrate into the NMF objective as regularisers. The resulting framework encompasses spatially coherent image components, periodic time-series structures, and clique-like graph signals within a unified modelling language.

Authors: Andre N. Costa, Petter Ögren, Carlos H. C. Ribeiro

In this paper, we generalize the concept of Voronoi regions, define agent utility as the integral of a utility density over the corresponding Voronoi region, derive gradients of the utility, and illustrate the approach in a two-team example from soccer. The generalization of Voronoi regions is in the form of so-called Cost-Induced Voronoi (CIV) regions, where the agent state space may differ from the space being partitioned. One example of such regions is when the cost is given by the optimal solution of an LQR control problem. Then the agent states include position as well as velocity, while the partitioned space only includes positions. The agent utility is defined by integrating some utility density over the CIV region of the agent. This utility density might be the probability density of some beneficial event, such as receiving a pass in soccer. The utility is then the overall probability of receiving a pass and the gradient represents a way to improve that probability. We show how this utility gradient can be computed using the Reynolds Transport Theorem from fluid mechanics, and that this approach achieves similar accuracy while reducing computation time by about an order of magnitude compared to a baseline finite-difference approximation.

Authors: Faruk Alpay, Bugra Kilictas

We study dynamic geometric data structures for exact nearest-neighbour maintenance under small motions. For each point we store a certificate consisting of its nearest neighbour and the two smallest neighbour distances, with clearance $c_i=d^i_2-d^i_1$. A triangle-inequality argument gives a sharp validity radius: after a step of maximum displacement $\varepsilon$, every certificate with $c_i>4\varepsilon$ remains valid, so all possible failures are confined to a repair frontier $F_t$. We introduce repair-frontier entropy $H(F_t)$, the normalized Shannon entropy of failed certificates over index cells, as a workload descriptor for choosing between event-driven repair, batched repair, and full rebuild. The resulting maintenance rule repairs only the frontier in $O(|F_t|\log N)$ time under bounded cell occupancy, while a full rebuild costs $Θ(N)$; moreover, entropy lower-bounds the number of frontier cells touched by event-driven repair and shifts the empirical repair-rebuild crossover. We evaluate ten motion families in $d\in{2,3}$, with $N$ up to $16,000$, using an exact tiled GPU oracle and a GPU grid rebuild as ground truth and competitor. Across $2400$ labelled transitions, the validity rule misses no invalid certificate, low-pressure frontiers are usually cheaper to repair incrementally, and diffuse frontiers of the same size are more expensive for event-driven repair but not for batched repair. The released dataset records frontier geometry, certificate audits, per-strategy times, and best-strategy labels.

Authors: Han Huang, Pakawut Jiradilok, Elchanan Mossel

Recent work studied the problem of finding clusters and denoising pairwise distances from noisy distances of points sampled on a manifold. We study the same problems in more general metric measure spaces under \lowerphiregularity{}. We give an algorithm that extracts large localized clusters around every sampled point and uses them to denoise distances to any fixed accuracy, with near-linear running time in the dense fixed-accuracy regime. We also show how to achieve much higher accuracy with a non-efficient algorithm. This suggests that unlike the Riemannian case, denoising to higher accuracy in more general metric spaces has a statistical-computational gap.

Authors: Qi Duan

We study a directed version of the three-terminal reachability-preserving minimum edge cut problem. Given a directed graph $G=(V,A)$ with arc costs and terminals $s_1,s_2,t$, the one-way directed RPMEC problem asks for a minimum-cost set of arcs whose deletion preserves the reachability $s_1\leadsto s_2$ while destroying the reachability $s_1\leadsto t$. We first give a path--cut formulation in terms of a rooted directed cut function. Using a root-linear approximation for the associated polymatroid, we obtain an $O(\sqrt r)$-approximation, where $r$ is the number of relevant vertices with positive singleton cut value. In particular this gives an $O(\sqrt n)$-approximation in general directed graphs. For acyclic directed graphs, we give an additional singleton-length algorithm and obtain an $O(\min\{\sqrt r,h\})$ guarantee, where $h$ is the maximum number of relevant vertices on an $s_1$-$s_2$ path. Finally, we prove that directed planar RPMEC is NP-hard, even on acyclic planar digraphs with nonnegative costs, by reducing from independent set on cubic planar graphs through a finite-bimodal directed node-cut construction and a planar node-to-edge split.

Authors: Deepak Ajwani, Rishikesh Gajjala, Rajiv Raman, Saurabh Ray

In 1965, Wegner conjectured that every finite family \(\mathcal R\) of axis-parallel rectangles in the plane satisfies \(τ(\mathcal R) \le 2ν(\mathcal R)-1\), where \(τ(\mathcal R)\) denotes the minimum number of points needed to pierce all rectangles in \(\mathcal R\), and \(ν(\mathcal R)\) denotes the maximum size of a pairwise disjoint subfamily. Over the last six decades, the conjecture has motivated a long line of work: it has been verified for several special classes of rectangle families, and the best known general upper bounds have been progressively improved, but the conjecture itself had remained open. We give an explicit counterexample. More precisely, we construct a triangle-free rectangle-intersection graph on \(n\) vertices whose independence number is at most \(n/4\). Since the graph is triangle-free, no point of the plane can lie in three rectangles; hence every piercing point hits at most two rectangles. Consequently, \(τ(\mathcal R) \ge n/2 \ge 2ν(\mathcal R)\), contradicting Wegner's conjectured bound. We also give a slightly more general construction for which \(τ(\mathcal R) \ge 2.21ν(\mathcal R)\). This shows that the standard point relaxation, equivalently the clique relaxation, for the Maximum Independent Set of Rectangles problem has integrality gap at least \(2.21\).

Authors: Mohit Garg, Aditya Subramanian

The Connectivity Augmentation Problem (CAP) is a fundamental problem in fault-tolerant network design and has been extensively studied in the context of approximation algorithms. In this work, we consider CAP in the online setting: given a $k$-edge-connected graph $G$ and a set $L$ of additional edges over the vertices of $G$, called links, online requests arrive one by one, each specifying two vertices that need to be $(k+1)$-edge-connected. We start with the graph $G$ and progressively add links to serve these requests. More specifically, upon the arrival of a request $\{u,v\}$, we must immediately and irrevocably add zero or more links from $L$ to the graph so that $u$ and $v$ are $(k+1)$-edge-connected in the resulting augmented graph. The goal is to minimize the total number of links added, and we evaluate an algorithm's performance by its competitive ratio relative to an optimal offline solution. In this work, improving upon previous bounds, we obtain a tight competitive ratio for online CAP, along with other related results.

Authors: Hong Li

The prize-collecting stroll is the path version of the prize-collecting TSP. Given a complete metric graph, two prescribed terminal vertices $s,t$, and nonnegative penalties on vertices, the prize-collecting stroll asks for an $s$-$t$ tour minimizing the length of the tour plus the total penalty of vertices that are not visited by the $s,t$ tour. We study a common generalization of the prize-collecting stroll and several related prize-collecting routing problems, which we call the prize-collecting-$Φ$-TSP. In this model, $Φ$ specifies a set of prescribed vertices alongside their parity and connectivity requirements. We show that, if a $ρ$-approximation algorithm for the prize-collecting TSP is available, then, for any $\varepsilon>0$, there is a polynomial time $(ρ+\varepsilon)$-approximation algorithm for the prize-collecting-$Φ$-TSP when the number of prescribed vertices is bounded by a fixed constant. This yields a better-than-$1.6$-approximation algorithm for the prize-collecting stroll, improving the previous best-known approximation guarantee of $1.6662$.

Authors: Shouzhen Gu, Lily Wang, Aleksander Kubica

Two-dimensional topological translationally invariant (2D TTI) stabilizer codes lie at the heart of fault-tolerant quantum computation, but using them requires solving the decoding problem. Minimum-weight decoding of these codes was recently shown to be NP-hard, even in basic settings, such as the color code with Pauli $Z$ errors and the toric code with Pauli $X$, $Y$ and $Z$ errors. Here, we prove that minimum-weight decoding of 2D TTI codes nonetheless admits a polynomial-time approximation scheme (PTAS), i.e., for any constant $\varepsilon>0$, a recovery operator of weight within a multiplicative factor of $1+\varepsilon$ of the minimum can be found in polynomial time. Our approach builds on Arora's PTAS for Euclidean problems, such as the traveling salesman problem, and applies when decoding can be cast in terms of point-like excitations connected by string-like errors. It therefore extends beyond two dimensions, covering certain higher-dimensional topological codes and quantum memories, including the toric code with phenomenological or circuit-level noise.

Authors: Madhulatha Mandarapu, Sandeep Kunkunuru

Log-structured merge (LSM) trees attach an approximate-membership filter to every run and must split a fixed memory budget across them. The static optimum is known (Monkey); a large systems literature then makes the allocation adaptive, tracking shifting hotness online. We ask a prior question: when is that adaptivity worth its machinery? We give three analytical answers and validate them on synthetic sweeps, real Twitter production cache traces, and a real RocksDB engine. First, a log-law: optimal bits-per-key is affine in the logarithm of access frequency, at a fixed slope. Second, a robustness law: because the workload enters only logarithmically, the excess read cost from a hotness misestimate is half the size-weighted variance of the log error, and a common-factor misestimate is absorbed by the budget multiplier, so coarse estimates lose little. Third, an adaptivity-value frontier: since compaction rebuilds filters for free on its own clock, the value of continuous tracking over an allocation recomputed only at compaction grows quadratically in the within-epoch drift, with a closed-form scale. This yields a three-regime policy (coarse-at-compaction suffices, then track, then at extreme drift fall back to uniform) and predicts that more skew makes fine tracking matter less. On a real cluster, reallocating only at compaction captures 96-99% of tracking's benefit; on RocksDB the false-positive primitive holds within four percent to eight bits per key. The contribution is a characterization of when adaptive tuning pays; we add no new filter and no engine fork. Code and pre-registration are public.

Authors: Abhishek Dhawan, Abhishek Methuku, Minh-Quan Vo

A foundational theorem of Ajtai, Komlós, Pintz, Spencer, and Szemerédi asserts that every $n$-vertex $k$-uniform uncrowded hypergraph with maximum degree $Δ$ contains an independent set of size $c_k n{\left(\frac{\log Δ}Δ\right)^{\frac{1}{k-1}}}$, for some constant $c_k>0$. Determining the optimal leading constant $c_k$ in this bound is a major open problem. A natural target is the so-called shattering-threshold constant $\left(\frac{1}{k-1}\right)^{\frac{1}{k-1}}$, which appears in the solution-space geometry of random constraint satisfaction problems, in average-case complexity theory, and in statistical physics, among other areas. We prove that uncrowded hypergraphs attain this threshold. More precisely, for every $ε>0$ and $k\geq 2$, every $n$-vertex $k$-uniform uncrowded hypergraph of sufficiently large maximum degree $Δ$ contains an independent set of size at least $(1-ε) n {\left(\frac{1}{k-1}\frac{\log Δ}Δ\right)^{\frac{1}{k-1}}}$. Consequently, we obtain the first pseudorandom class of hypergraphs whose guaranteed independence number matches the shattering threshold, resolving a folklore conjecture. Moreover, as another direct consequence, we resolve a conjecture of Verstraëte and Wilson by proving that there exists a constant $c_k=1-o_k(1)$ such that every $n$-vertex $k$-uniform linear hypergraph of maximum degree $Δ$ has independence number at least $c_k n\left(\frac{\log Δ}Δ\right)^{\frac{1}{k-1}}$. Our techniques are constructive yielding efficient algorithms for both static and distributed settings. Specifically, we provide an $\tilde O(nΔ)$-time randomized static algorithm and an $\tilde O(1)$-round randomized $\textsf{LOCAL}$ algorithm to find an independent set in uncrowded hypergraphs at the shattering threshold. These results extend seamlessly to the the setting of linear hypergraphs.

Authors: Sebastian Lüderssen, Stefan Neumann, Pan Peng

We study the problem of $(1+\varepsilon)$-approximating the number of four-cycles in graphs given as arbitrary order edge streams. We propose two new algorithms based on sampling induced subgraphs. Our first contribution is a two-pass algorithm that uses $\widetilde{O}(κm / \sqrt{T})$ space, where $m$ is the number of edges, $T$ is the number of four-cycles, and $κ$ is the graph's degeneracy. This algorithm improves upon existing theoretical bounds and is provably optimal for constant-degeneracy graphs, matching the known $Ω(m/\sqrt{T})$ lower bound up to lower-order factors. Our second contribution is a one-pass algorithm that remains accurate when four-cycles are not highly concentrated around individual nodes, edges, or wedges; this structural property is common in sparse social and collaboration networks. We evaluate both algorithms on a variety of real-world graph streams. The two-pass algorithm consistently outperforms state-of-the-art methods, using substantially less space to achieve a desired accuracy. The one-pass algorithm is competitive when four-cycles are evenly distributed, matching our theoretical analysis. Unlike several recent works, our algorithms perform well even on non-bipartite graphs such as social networks.

Authors: André Ribeiro, Rúben Garrido, Violeta Ramos, António Alberto, Diogo Fernandes, João Varela, Eduardo Lopes, Rodrigo Abreu, Hugo Ribeiro, Tomás Brás, David Pelicano, Afonso Ferreira, Sebastião Teixeira, Maria Linhares, Martim Santos, Rui Machado, Duarte Santos, Gabriel Silva, Guilherme Rosa, João Roldão, Henrique Teixeira, Cláudia Seabra, Ricardo Fonseca, Richard Miranda, Hugo Castro, Ângela Ribeiro, Fouad Bellili, Luís Diogo, André Cardoso, Armando J. Pinho, Diogo Pratas

Lossless data compression remains central to computer science, with direct impact on storage, communication bandwidth, computational cost, and energy consumption. It is also closely related to Algorithmic Information Theory, where compressibility provides an operational measure of structure and non-randomness. This paper presents the 2026 Algorithmic Information Theory Data Compression Challenge, a benchmark for evaluating general-purpose lossless compressors under realistic constraints. Submissions were encouraged to use arithmetic or range coding, limited to at most 8 GB of memory, and required to include a decompressor no larger than 1 MB. The benchmark comprised sixteen heterogeneous files, split into public training and hidden testing datasets. In total, 117 valid submitted compressors were evaluated alongside established reference compressors using compression ratio, compression and decompression time, Weissman score, and Pareto-frontier analysis. The results show that performance depends strongly on the optimization criterion: fast compressors achieved the best speed-oriented scores, whereas modelling-intensive compressors produced smaller outputs at higher computational cost. A Normalized Compression Distance analysis further revealed clusters of related submissions and distinguished incremental variants from more independent implementations. Selected submissions were described for their methodological novelty or competitive performance and further tested on four large external datasets, where several achieved competitive or superior results relative to established compressors. Overall, the challenge confirms the importance of probabilistic modelling, hidden testing, and external datasets for assessing compression performance and generalization. Benchmark resources, leaderboard data, binaries, and selected source code are publicly available at https://aitdcc.github.io.

Authors: Sam van der Poel, Cheng Mao, Benjamin McKenna

Given a simple graph on $n$ vertices and a parameter $k$, the triangle-densest-$k$-subgraph problem is known to be computationally hard in the worst case. To circumvent the computational hardness, we study an average-case model where a triangle-dense subgraph on $k$ vertices is planted in an Erdős-Rényi random graph on $n$ vertices. For the recovery of the planted subgraph, we propose a simple spectral algorithm and a semidefinite program, both of which use a graph matrix whose entries are local signed triangle counts. Theoretical guarantees for these algorithms are established through spectral analysis of the graph matrix. Finally, we provide evidence showing a statistical-to-computational gap analogous to that for the planted clique problem. The computational threshold in terms of the subgraph size $k$ is at least $\sqrt{n}$ in the framework of low-degree polynomial algorithms, while the information-theoretic threshold is at most logarithmic in $n$.

Authors: Wenhao Song

We study exact exponential-time algorithms for Edge Deletion to Cactus. Given a connected graph $G$, the task is to delete a minimum number of edges so that the remaining spanning graph is a connected cactus. Akhtar and Philip (IWOCA 2026) gave an $O^*(3^n)$-time algorithm for the unweighted problem, where $n$ is the number of vertices in the input graph and the $O^*(\cdot)$ notation hides polynomial factors. We improve this bound to $O^*(2^n)$ time and space. More generally, if the deletion costs take at most $q$ distinct nonnegative real values, then the weighted problem can be solved in $O^*(2^n n^{O(q)})$ time and space. Thus every fixed number of distinct costs, and in particular the unweighted case, admits a faster exact algorithm. For nonnegative integer costs of total weight $W$, we obtain an $O^*(2^n(W+1))$ pseudo-polynomial algorithm, while arbitrary nonnegative real costs admit an $O^*(3^n)$ exact algorithm.

Authors: Milind Prabhu, Chris Schwiegelshohn, Sudarshan Shyam

Clustering in a big data setting is an intensively studied problem, with coresets emerging as one of the important paradigms in this line of work. Given a cost function $\text{cost}(P,S)$ mapping input points $P$ and a solution $S$ to an objective value, a coreset is a typically weighted sketch $Ω\subseteq P$ such that $\text{cost}(Ω,S)\approx \text{cost}(P,S)$. In practice, coreset sizes much smaller than those suggested by theoretical guarantees are often found to be sufficient. In this paper, we offer an explanation for this phenomenon. Smaller coreset sizes suffice if we only wish to preserve the costs of \emph{good} solutions, i.e., solutions with low cost. We define and devise \emph{approximation-preserving coresets}, which provide a weaker guarantee than strong coresets, which apply to all solutions, while providing stronger guarantees than weak coresets, which apply only to the optimum solution. We complement this result by showing that even a very small distortion in the approximation factor cannot admit coresets of this size.

Authors: Hagit Attiya, Rotem Oshman, Noa Schiller

Linear probing is one of the simplest and most space-efficient approaches to hash table design, and is widely used in sequential settings due to its compact memory layout. However, designing a concurrent linear-probing hash table with strong liveness guarantees has proved difficult, and only a handful of such algorithms have been proposed, all of which either restrict concurrency or rely on large per-entry metadata, thereby compromising space efficiency. We present a lock-free linear-probing hash table with wait-free lookups that retains the core advantages of sequential linear probing while handling contention gracefully. Our design uses only a small amount of metadata per table entry: a constant number of additional bits when using LL/SC, or a logarithmic number of bits when using CAS. The algorithm is linearizable and lock-free, supports insert, delete, and wait-free lookup operations, and is able to safely reclaim space used by deleted elements without rebuilding the table. We analyze the amortized step complexity of our hash table assuming no concurrent insertions of the same key, and show that each operation has expected amortized step complexity matching that of sequential linear probing, up to the point contention per key.

Authors: Dung Nguyen, Ritwick Mishra, Anil Vullikanti

Counts of $k$-cliques are commonly used metrics in subgraph mining. Since graphs often have sensitive data, there also has been a lot of work on $k$-clique counts with differential privacy. However, these metrics have very high global sensitivity, and so more sophisticated techniques have been developed for counting $k$-cliques with privacy. Smooth sensitivity and ladder functions were developed for reducing the noise magnitude for private estimates of these metrics. However, these are computationally very inefficient to estimate. No polynomial time algorithms are known for smooth sensitivity of $k$-cliques for $k>3$, while the time complexity of ladder functions is lower bounded by the time for exact counts, which does not scale very well. In this paper, we develop a new highly scalable algorithm for estimating $k$-clique counts with differential privacy. Our algorithm adapts the ladder function to serve as a smooth upper bound on its local sensitivity, and utilizes the approximation sensitivity framework to calibrate noise with magnitude proportional to an approximation of the bound. This gives us a significant improvement in the running time. Experiments show that our method is several orders of magnitude faster than the ladder function based estimates of $k$-clique counts, while the accuracy is similar. Our algorithm is the first to scale to graphs with millions of edges, and for larger $k$, for which the ladder function algorithm doesn't complete.

Authors: Miaolan Xie

Many nonsmooth, nonconvex objectives in learning and signal recovery are $ρ$-weakly convex. We minimize such a function in deterministic and stochastic settings when the weak-convexity parameter $ρ$ is unknown. The objective is not required to be globally Lipschitz continuous or smooth. We propose the Adaptive Prox-Guided Scheme (APS), a one-trial proximal algorithm that adapts the proximal parameter online and bidirectionally through a descent test, allowing it to exploit favorable local structure. In the deterministic setting, APS obtains an $O(\varepsilon^{-2})$ iteration complexity for producing an $\varepsilon$-subgradient stationary point. In the stochastic setting, APS achieves a high-probability $O(\varepsilon^{-2})$ iteration bound for driving the Moreau-envelope gradient below $\varepsilon$. This result holds under deliberately weak oracle assumptions: the function-difference estimates may be biased and heavy-tailed, and the stochastic proximal oracle need only be sufficiently accurate with constant probability when the proximal parameter lies below $1/(2ρ)$ (unknown to the algorithm), and can be arbitrary otherwise.

Authors: Xiaoyu Li

A certificate that removes outliers sees the data only through its low-degree moments, and an adversary exploits exactly this, hiding corruption where the clean data already looks typical, in the blind spot no bounded-degree test resolves. That blind spot turns out to have an exact size: the Christoffel function of the clean marginal, the very quantity modern data analysis thresholds to detect outliers, here read from the adversary's side as the corruption a bounded-degree certificate cannot remove. We turn this inversion into the organizing principle of the reweighted-hinge approach to robustly learning $γ$-margin halfspaces under malicious noise (Shen, 2025; Zeng and Shen, 2025): the governing resource is the Sum-of-Squares degree of the outlier-removal certificate, and the resolution principle states that the maximal corruption mass which can hide at a center $c$ from a degree-$2t$ certificate is exactly the Christoffel function $λ_{t+1}(c)$ of the clean marginal. Three consequences follow, all against the certificate method (not information-theoretic). A margin-degree tradeoff: certifying the dense pancake to error $ε$ costs SoS degree $Ω(\log(1/ε))$ or margin $Ω(\sqrt{\log(1/ε)}/\sqrt{d})$, explaining why the $\log(1/ε)$ margin Shen (2025) records is forced, with a weighted-Chebyshev reduction making the threshold $2t=Θ((|c|/s)^2)$ tight modulo one classical weighted-extremal estimate. A degree-$2$ outlier barrier: the resolution principle realized as an explicit instance on which degree $2$ is stuck at $η^{1/2}$ while degree $4$ escapes, locating the method's small breakdown rate in the degree, not the analysis. And a degree-$2t$ algorithm tracing the frontier $η^{1-1/2t}$ (recovering Shen (2025) at $t=1$), whose gain is an explicit constant, capped by the pancake density and shown unimprovable by the degree-$2$ barrier.

Authors: Martino Bernasconi, Matteo Castiglioni, Andrea Celli, Alexandros Hollender

We prove that computing approximate stationary points of min-max optimization over the hypercube is PPAD-hard for quadratic polynomials. This holds even when the polynomials are multilinear, each variable appears in at most three monomials, and the approximation factor is inverse polynomial. As a direct consequence, we obtain the first PPAD-hardness results for two-team zero-sum polymatrix games.

Authors: Min-Hsiu Hsieh, Michael de Oliveira, Sathyawageeswar Subramanian, Xingjian Zhang

Circuit depth is a central resource in complexity theory. While bounded-depth classical circuits admit well-understood hierarchy theorems, the internal structure of constant-depth quantum computation remains comparatively unexplored. We prove an explicit depth hierarchy theorem for $\mathsf{QNC}^0$. For each $d\ge 12$, we construct a family of two-round interactive problems on which no depth-$(d-1)$ quantum circuit can achieve near-perfect success, regardless of gate set, circuit size, or ancillary qubits. In contrast, we prove that our construction admits realizations by simple bounded fan-in quantum circuits of depth larger than $d$ by a small constant factor. Moreover, all bounded fan-in classical circuits of sublogarithmic depth (in the input size) fail to achieve perfect success on these tasks for every $d$, yielding a hierarchy of problems that show unconditional quantum advantage of $\mathsf{QNC}^0$ over $\mathsf{NC}^0$. A key obstacle is the scarcity of lower bound techniques for quantum circuits. To address this, we develop methods to analyze how depth affects a circuit's ability to realize nonlocal correlations amongst its output qubits in a fine-grained manner. Our approach exploits the correspondence between constraint systems and nonlocal games, translating group-theoretic constructions into rigid operator-valued constraint systems and then into non-local games. In particular, we construct constraint systems whose unique faithful operator-valued solutions require every perfect strategy, and every near-perfect strategy to a fixed precision, to implement multi-controlled phase operations. This reduces to a nonlocal unitary-synthesis problem, yielding depth lower bounds for both shallow quantum and classical circuits. These results show that increasing depth strictly increases computational power within $\mathsf{QNC}^0$, establishing a genuinely quantum hierarchy.

Authors: Ioannis Anagnostides, Ioannis Panageas, Tuomas Sandholm, Jingming Yan

A celebrated consequence of the minimax theorem is that two-player zero-sum games admit a tractable equilibrium characterization. In many central applications, however, each side comprises multiple independent agents who share a common objective but cannot perfectly coordinate their actions. Such settings can be modeled as \emph{team zero-sum games}, a natural generalization of both two-player zero-sum games and potential games -- the two most well-studied classes of games in algorithmic game theory. In this paper, we settle the complexity of team zero-sum games by establishing that computing Nash equilibria is \PPAD-complete. As a result, despite the global adversarial structure, team zero-sum games are as hard as general-sum games. Our hardness result holds even when i) the precision is inverse polynomial, thereby ruling out a fully polynomial-time approximation scheme (unless $¶= \PPAD$); ii) each team consists of only two players; and iii) the underlying class of games is polymatrix. As a byproduct, we resolve the complexity of group-wise zero-sum polymatrix games, a class introduced and examined in the seminal work of Cai and Daskalakis (SODA '11), and more recently highlighted by Hollender, Maystre, and Nagarajan (ICLR '25). Moreover, we show that computing a first-order stationary point in min-max optimization is \PPAD-complete even for quadratic (multilinear) objectives. From a technical standpoint, we develop a series of team zero-sum game gadgets that allow us to simulate the breakthrough reduction of Bernasconi and Castiglioni (STOC '26). Moreover, to obtain hardness results for quadratic objectives, we make use of a general technique based on linear local approximation, which is of independent interest.

Authors: Lars Warren Ericson

We describe a Lean~4 formalization revisiting NYU Courant Technical Report TR1995-711 on the average-case complexity of Multilevel Syllogistic (MLS). The development encodes Reischuk--Schindelhauer average-case classes, an axiomatic MLS/EMLS semantics layer, a partial Ferro--Omodeo--Schwartz decision procedure with proved soundness and partial completeness on a membership-free fragment, serialization and step budgets, and conditional NP-average completeness and non-AvP hardness corollaries modulo explicitly documented structural axioms. Full Lean sources are inlined in the appendix modules.

Authors: Héctor Jimenez, Alexander Kozachinskiy, Vicente Opazo

In this note, we introduce a polynomial-time version of the mistake-bounded language generation (MBLG) framework due to Kleinberg, Peale, and Reingold (2026). We observe that the family of parities of variables, and the family of conjunctions of literals, are polynomial-time MBLG. Our main result states that the family of monotone Boolean functions with polynomially-many maxterms is polynomial-time MBLG. This family includes all monotone Boolean functions, computable by polynomial-size decision trees. Our technique can be presented as a new combinatorial game about writing numbers on a board.

Authors: Ali Ahmadi, Kiarash Banihashem, Iman Gholami, Mohammad Taghi Hajiaghayi, Jan Olkowski

Recent work on "quiet planting" in combinatorial optimization aims to generate instances with a hidden solution that is hard to recover, typically by making the planted distribution statistically indistinguishable from uniform for specific algorithms, such as statistical queries. A prominent example is planted $k$-SAT, where $O(n^{k/2})$ clauses can be planted while maintaining indistinguishability from uniform instances, evidenced by prior hardness results which also align with findings in SAT refutation. Despite extensive research and practical use in benchmarking SAT solvers, the challenge of quietly planting multiple solutions while preserving hardness has remained an open problem. This work initiates the study of quiet planting with an arbitrary number of solutions, proposing the first method to construct quiet planting distributions for $k$-SAT formulas that accommodate more than one solution. We provide statistical query lower bounds for distinguishing these planted instances from uniform ones, and our method allows for planting solutions with arbitrary geometric relationships, including varying Hamming distances. A key innovation facilitating multiple solutions is the ability to incorporate arbitrary correlations between variable selection in clauses and their negation patterns, departing from prior approaches. We also investigate the worst-case complexity of SAT by showing the difficulty in distinguishing satisfiable instances with numerous solutions from unsatisfiable ones, addressing an open problem of Hsieh, Mohanty, and Xu (CCC'22). Technically, we generalize $(r-1)$-wise uniformness in clause distributions, proving hardness if marginal negation distributions are $(r-1)$-wise uniform. We also reveal a connection to binary linear codes, showing a $[k, t, r]$ code can guide planting up to $2^t - 1$ solutions on $k$ variables.

Authors: Karthik Sheshadri

We study the polar (conormal) method for determinantal-complexity lower bounds, including the framework used in the companion bound dc(sum_i x_i^N) >= (1/(4e)-o(1))N^2. We obtain quantitative results on both sides of the method: the intersection-theoretic complexity of kernel-incidence constructions and the size of the characteristic-cycle invariants they can detect. For a size-m determinantal representation in N variables, we identify the corank-one kernel incidence with the conormal variety of the generic determinant. An excess-one degeneracy-locus computation yields a closed formula for the associated polar intersection number T(N,m), together with rational generating functions and explicit evaluations including T(3,m)=m(m-1), T(4,m)=m(m-1)^2, and T(5,5)=220. We also compare these counts with the multihomogeneous Bezout estimates used in the companion work and establish asymptotic sharpness at the per-root scale. For an arbitrary degree-d hypersurface X in P^(N-1), possibly singular and reducible, we prove a uniform bound on the conormal multidegrees appearing in its characteristic cycle: m_S delta_i(Con(S-bar)) <= 8(d-1)^(N-1)+O(N). The proof combines bounds on generic-slice Euler characteristics, an explicit analysis of the transform from Euler-characteristic data to conormal multidegrees, and Kashiwara positivity for characteristic cycles. Similar bounds are obtained for vanishing-cycle and Milnor-class variants. Combining these results yields general upper bounds on determinantal-complexity lower bounds obtainable from characteristic-cycle invariants via kernel-corank incidence constructions. In particular, along the diagonal d=N, the resulting lower bounds are at most quadratic in N. We conclude by discussing possible extensions involving scheme-theoretic conormal information and other geometric invariants.

Authors: Qi Duan

We study the three-terminal reachability-preserving minimum node cut problem (\RPMNC). The input is an undirected graph \(G=(V,E)\), nonnegative vertex weights on nonterminal vertices, two protected terminals \(s_1,s_2\), and a target terminal \(t\). The goal is to delete a minimum-weight set of nonterminal vertices so that \(t\) is disconnected from the protected terminals, while \(s_1\) and \(s_2\) remain connected. This problem captures a basic ``separate while preserve'' requirement that arises in biological intervention design, image analysis with connectivity constraints, and cyber-security attack graph mitigation, where deleting or blocking a node represents preventing the corresponding action, state, or biological entity from participating in a harmful pathway. We prove two results. First, the weighted planar version of three-terminal \RPMNC{} is NP-complete. The reduction is from \textsc{Independent Set} on 3-regular Hamiltonian planar graphs and uses a one-sided blocker construction. Second, we give a polynomial-time \(O(\sqrt n)\)-approximation algorithm for general graphs. The algorithm is based on an exact path--separator identity, a directed split-graph representation of rooted vertex separators, and a root-linear approximation of a monotone submodular separator function.

Authors: Qi Duan

We study threshold minimum cut problems with a distinguished root vertex, a set of terminals, and a quota. In the threshold minimum edge cut problem (\TMEC), the goal is to find a minimum-cost edge cut that disconnects at least $k$ terminals from the root. In the threshold minimum node cut problem (\TMNC), the goal is to delete a minimum-cost set of nonterminal, nonroot vertices so that at least $k$ terminals become disconnected from the root. We prove three approximation guarantees. First, undirected general-graph \TMEC{} admits a randomized polynomial-time expected $O(\log n)$ approximation via a Räcke-style cut-dominating tree decomposition and an exact dynamic program on trees. A standard repetition argument gives the same asymptotic ratio with high probability. Second, planar \TMEC{} admits a factor-$2$ approximation by reducing the threshold condition to planar weighted balanced cut. Third, bounded-degree planar \TMNC{} admits a $2Δ$-approximation, where $Δ$ is the maximum degree of a deletable vertex, by reducing the node-cost problem to the planar edge-cut problem on the same graph. The results separate exact-quota guarantees from bicriteria small-set-expansion-type guarantees and identify the unbounded-degree planar node-cut case as the main remaining obstacle.