Theory of Computing Report

We consider the worst-case hardness of the gap version of the classic time-bounded Kolmogorov complexity problem—$Gap_pMK^tP[s_1,s_2]$—where the goal is to determine whether for a given string x, $K^t(x) ?s_1(n)$ or $K^{p(t)}(x) > s_2(n)$, where $K^t(x)$ denotes the t-bounded Kolmogorov complexity of x. As shown by Hirahara (STOC’18), if $Gap_pMK^tP[s_1,s_2] \notin prBPP$ for every polynomial p, then (under appropriate derandomization assumption) $Gap_pMK^tP$ is errorless average-case hard with respect to BPP heuristics. The notion of errorless average-case hardness, however, is seemingly insufficient for cryptographic applications where one needs to consider average-case hardness against attacks that simply may err with some probability (i.e., two-sided error hardness). In this work, we present several new consequences of the assumption that $Gap_pMK^tP[s_1,s_2]\notin P/poly$ for all polynomials p, for appropriate choices of $s_1$,$s_2$, and under appropriate (worst-case) derandomization assumptions. In particular, we show that this assumption implies: - The existence of an (inefficient-prover) zero-knowledge proof system for NP with a non-uniform simulator w.r.t. adversaries with a-priori bounded-length auxiliary-input. -  The existence of a hard disjoint NP pair, defined as a promise problem $(Y,N)$ where both $Y,N\in NP$; this provides a barrier towards showing that $Gap_pMK^tP$ is NP-complete. The above results are proven via first showing that the above assumption implies the existence of a so-called conditional PRG—roughly speaking, a cryptographic PRG where indistinguishability only needs to hold for some (potentially not efficiently sampleable) distribution over the seed to the PRG. (In fact, this notion of a PRG also almost directly implies average-case hardness of $Gap_pMK^tP$, and as such, this provides a modular explanation to Hirahara’s results.) Finally, we show that for the results on conditional PRGs and Zero-knowledge Proofs, unconditional results can be obtained (that is, without making any derandomization assumptions), if considering an appropriate version of $Gap_pMK^tP$ concerning randomized $K^t$.

In this paper we study the cryptographic complexity of non-trivial witness-indistinguishable ($WI$) arguments of knowledge. We establish that: - Assuming that $NP\not\subseteq P/poly,$ the existence of a constant-round computational $WI$ argument of knowledge for $NP$ implies that (infinitely-often) auxiliary-input one-way functions exist. - Assuming that $NP\not\subseteq P^{Sam}/poly,$ there is no black-box construction of a constant-round (unbounded-verifier) statistical $WI$ argument of knowledge from one-way permutations. Here, $Sam$ is the collision finder oracle of Haitner, Hoch, Reingold, and Segev [FOCS '07]. Moreover, we identify a natural class of knowledge extractors for which stronger versions of the above implications hold (e.g., even if the protocols have many rounds).

Though I’ve been prefacing my lecture blog posts with italicized disclaimers, I want to single this lecture blog out as being targeted a bit more broadly. Because, in a weird confluence, the topic of this week’s lecture coincides with the topic of an op-ed by Leif Weatherby and me that appears this morning in the New York Times: forecasting and simulation.

We can’t avoid prediction and simulation in a class about feedback systems. Our theories suggest that better predictions and forecasts lead to better plans of action. Additionally, we try to make sense of complex, interconnected systems by simulating their behavior, and simulations often reveal surprising “emergent” behavior of the whole, which wasn’t evident from the modeled behavior of the parts. We also tend to think that the subcomponents of complex, interconnected systems make sense of their surroundings by predicting what other components around them will do.

I was a bit slippery in that paragraph about what the difference is between simulation and prediction. That’s because I’m still not sure how to draw a boundary between the two concepts. The most common axis is opacity: everyone thinks there is a fundamental difference between a model that is “easy to describe” from first principles and one that is purely data-driven. We call the latter “black box” to mark our disdain. The “transparent box” systems might derive from physical laws, and we write down a set of equations that dictate how each step relates to the next. The black box systems might be derived by curve fitting, where we pick a function of convenience, untethered from causal explanation, to describe how inputs have historically mapped to outputs.

I’ll talk more about the opacity slider in later posts this week, but today, I want to ask about the purpose of simulation. That axis is more interesting to me. Simulations can be used in many different ways. You might use a simulation to better understand a system itself. Simulations of mechanical systems can give you a feel for their performance limits. You can use simulations to figure out why something went wrong, deriving causal explanations from plausible mechanisms. And, of course, you can use simulations to predict the future. You can use these simulation forecasts to make a plan of action. Or, in our Draft-Kings-addled culture, you might use them to gamble.

Leif and I talked about this murky simulation landscape in the world of public opinion polling. Specifically, we wrote about the absurdity of silicon sampling. For those unfamiliar with the term, silicon sampling is when you design a social science survey experiment and give the questions to LLMs rather than people. As absurd as this sounds, people are really pushing to do this. There’s a billion-dollar startup called Aaru that is based entirely on this silly idea. And one of their fake polls slipped its way into Axios last week, without Mike Allen realizing that the “poll” he was reporting on was a computer simulation (embarrassed, Axios later edited the story to reflect the phoniness).

But why do silicon samples have so much cachet with pollsters and social scientists? As Leif and I argue in our piece, it’s because polls already rely heavily on simulation methods. Because of remarkably high nonresponse bias, pollsters lean heavily on statistical modeling to tweak their numbers to align with reality. Polls that use multilevel regression and poststratification are already inputting a lot of simulated reality to “correct” their summarization of the data they collected. The number isn’t “percentage of yesses in my sample,” it’s “what I think the percentage of yesses is in the population given my sample and my beliefs about the population.”

Since polling already relies heavily on simulation, tossing out the expensive part of the process—you know, asking actual people questions—feels like a logical conclusion. The Nate Silverization of political coverage turned polling into prediction. In the media, the goal of polls stopped being about understanding what people think and became more about predicting the outcome of elections. If all you need to do is predict, you don’t really need pristine distillations of understanding. You can take your empirical facts and use them solely to predict outcomes. And if the goal is just prediction, you don’t need to bother asking people at all. In fact, you want more reliable data than the fickle behavior of people nagged by pollsters at the end of some modern transmission line. If your goal is only prediction, you’re probably better off not talking to people at all.

But is the purpose of polling prediction? It depends on who you ask, but I’d like to think that the answer is no. At pure face value, the topline numbers of an opinion poll are a summary of a survey. They reduce a list of ones and zeros into two numbers: a mean and a variance.

Now, using a bit more social-scientific reasoning, we might interpret this summarization as a measurement of what a group of people believes. With a rigid methodology, we can consider polling to be quantified opinion. It’s a bit odd to think that you can “objectively” measure opinion in the first place, but this has been a supposition of social science research for a long time.

Unfortunately, statistics has incredibly slippery semantics that lead people to conflate summarization with measurement and measurement with prediction. Is the percentage of “people who answered yes” a summarization of the data? Is it a measured quantity about the opinion of a broader population? Is it a prediction of how people will vote in November? Yes?

I’m interested in this conflation for both political and academic reasons. Leif and I think the polling industry is harmful to the public sphere. But setting those politics aside, I think that being upfront about the purpose of simulations and forecasts helps demystify their outputs. Indeed, this week I’ll describe how purpose dictates forecasts. Prediction of the future is difficult. But if you tell me how my predictions will be evaluated, prediction of the future is trivial. I’ll explain more about why in the next post.

Subscribe now

By Ben Recht

Alice and Bob are given $n$-bit integer pairs $(x,y)$ and $(a,b)$, respectively, and they must decide if $y=ax+b$. We prove that the randomised communication complexity of this Point–Line Incidence problem is $\Theta(\log n)$. This confirms a conjecture of Cheung, Hatami, Hosseini, and Shirley (CCC 2023) that the complexity is super-constant, and gives the first example of a communication problem with constant support-rank but super-constant randomised complexity.

Imagine that every week for twenty years, people message you asking you to comment on the latest wolf sighting, and every week you have to tell them: I haven’t seen a wolf, I haven’t heard a wolf, I believe wolves exist but I don’t yet see evidence of them anywhere near our town.

Then one evening, you hear a howl in the distance, and sure enough, on a hill overlooking the town is the clear silhouette of a large wolf. So you point to it — and all the same people laugh and accuse you of “crying wolf.”

Now you know how it’s been for me with cryptographically relevant quantum computing.

---

I’ve been writing about QC on this blog for a while, and have done hundreds of public lectures and interviews and podcasts on the subject. By now, I can almost always predict where a non-expert’s QC question is going from its first few words, and have a well-rehearsed answer ready to go the moment they stop talking. Yet sometimes I feel like it’s all for naught.

Only today did it occur to me that I should write about something more basic. Not quantum computing itself, but the habits of mind that seem to prevent some listeners from hearing whatever I or other researchers have to tell them about QC. The stuff that we’re wasting our breath if we don’t get past.

Which habits of mind am I talking about?

1. The Tyranny of Black and White. Hundreds of times, I’ve answered someone’s request to explain QC, only to have them nod impatiently, then interrupt as soon as they can with: “So basically, the take-home message is that quantum is coming, and it’ll change everything?” Someone else might respond to exactly the same words from me with: “So basically, you’re saying it’s all hype and I shouldn’t take any of it seriously?” As in my wolf allegory, the same person might even jump from one reaction to the other. Seeing this, I’ve become a fervent believer in horseshoe theory, in QC no less than in politics. Which sort of makes sense: if you think QCs are “the magic machines of the future that will revolutionize everything,” and then you learn that they’re not, why wouldn’t you jump to the opposite extreme and conclude you’ve been lied to and it’s all a scam?
   
2. The Unidimensional Hype-Meter. “So … [long, thoughtful pause] … you’re actually telling me that some of what I hear about QC is real … but some of it is hype? Or—yuk yuk, I bet no one ever told you this one before—it’s a superposition of real and hype?” OK, that’s better. But it’s still trying to project everything down onto a 1-dimensional subspace that loses almost all the information!
   
3. Words As Seasoning. I often get the sense that a listener is treating all the words of explanation—about amplitudes and interference, Shor versus Grover, physical versus logical qubits, etc.—as seasoning, filler, an annoying tic, a stalling tactic to put off answering the only questions that matter: “is Quantum real or not real? If it’s real, when is it coming? Which companies will own the Quantum space?” In reality, explanations are the entire substance of what I can offer. For my experience has consistently been that, if someone has no interest in learning what QC is, which classes of problems it helps for, etc., then even if I answer their simplistic questions like “which QC companies are good or bad?,” they won’t believe my answers anyway. Or they’ll believe my answers only until the next person comes along and tells them the opposite.
   
4. Black-Boxing. Sometimes these days, I’ll survey the spectacular recent progress in fault-tolerance, 2-qubit gate fidelities, programmable hundred-qubit systems, etc., only to be answered with a sneer: “What’s the biggest number that Shor’s algorithm has factored? Still 15 after all these years? Haha, apparently the emperor has no clothes!” I’ve commented that this is sort of like dismissing the Manhattan Project as hopelessly stalled in 1944, on the ground that so far it hasn’t produced even a tiny nuclear explosion. Or the Apollo program in 1967, on the ground that so far it hasn’t gotten any humans even 10% of the way to the moon. Or GPT in 2020, on the ground that so far it can’t even do elementary-school math. Yes, sometimes emperors are naked—but you can’t tell until you actually look at the emperor! Engage with the specifics of quantum error correction. If there’s a reason why you think it can’t work beyond a certain scale, say so. But don’t fixate on one external benchmark and ignore everything happening under the hood, if the experts are telling you that under the hood is where the action now is, and your external benchmark only comes later.
   
5. Questions with Confused Premises. “When is Q-Day?” I confess that this question threw me for a loop the first few times I heard it, because I had no idea what “Q-Day” was. Apparently, it’s the single day when quantum computing becomes powerful enough to break all of cryptography? Or: “What differentiates quantum from binary?” “How will daily life be different once we all have quantum computers in our homes?” Try to minimize the number of presuppositions.
   
6. Anchoring on Specific Marketing Claims. “What do you make of D-Wave’s latest quantum annealing announcement?” “What about IonQ’s claim to recognize handwriting with a QC?” “What about Microsoft’s claim to have built a topological qubit?” These questions can be fine as part of a larger conversation. Again and again, though, someone who doesn’t know the basics will lead with them—with whichever specific, contentious thing they most recently read. Then the entire conversation gets stuck at a deep node in the concept tree, and it can’t progress until we back up about five levels.

---

Anyway—sorry for yet another post of venting and ranting. Maybe this will help:

The wise child asks, “what are the main classes of problems that are currently known to admit superpolynomial quantum speedups?” To this child, you can talk about quantum simulation and finding hidden structures in abelian and occasionally nonabelian groups, as well as Forrelation, glued trees, HHL, and DQI—explaining how the central challenge has been to find end-to-end speedups for non-oracular tasks.

The wicked child asks, “so can I buy a quantum computer right now to help me pick stocks and search for oil and turbocharge LLMs, or is this whole thing basically a fraud?” To this child you answer: “the quantum computing people who seek you as their audience are frauds.”

The simple child asks, “what is quantum computing?” You answer: “it’s a strange new way of harnessing nature to do computation, one that dramatically speeds up certain tasks, but doesn’t really help with others.”

And to the child who doesn’t know how to ask—well, to that child you don’t need to bring up quantum computing at all. That child is probably already fascinated to learn classical stuff.

By Scott

Authors: Jan Krajicek

A propositional proof system $P$ has the strong feasible disjunction property iff there is a constant $c \geq 1$ such that whenever $P$ admits a size $s$ proof of $\bigvee_i α_i$ with no two $α_i$ sharing an atom then one of $α_i$ has a $P$-proof of size $\le s^c$. It was proved by K. (2025) that no proof system strong enough admits this property assuming a computational complexity conjecture and a conjecture about proof complexity generators. Here we build on Ilango (2025) and Ren et al. (2025) and prove the same result under two purely computational complexity hypotheses: - there exists a language in class E that requires exponential size circuits even if they are allowed to query an NP oracle, - there exists a P/poly demi-bit in the sense of Rudich (1997).

Authors: Benedikt Pago

A notorious open question in circuit complexity is whether Boolean operations of arbitrary arity can efficiently be expressed using modular counting gates only. Håstad's celebrated switching lemma yields exponential lower bounds for the dual problem - realising modular arithmetic with Boolean gates - but, a similar lower bound for modular circuits computing the Boolean AND function has remained elusive for almost 30 years. We solve this problem for the restricted model of symmetric circuits: We consider MOD$_m$-circuits of arbitrary depth, and for an arbitrary modulus $m \in \mathbb{N}$, and obtain subexponential lower bounds for computing the $n$-ary Boolean AND function, under the assumption that the circuits are syntactically symmetric under all permutations of their $n$ input gates. This lower bound is matched precisely by a construction due to (Idziak, Kawałek, Krzaczkowski, LICS'22), leading to the surprising conclusion that the optimal symmetric circuit size is already achieved with depth $2$. Motivated by another construction from (LICS'22), which achieves smaller size at the cost of greater depth, we also prove tight size lower bounds for circuits with a more liberal notion of symmetry characterised by a nested block structure on the input variables.

Authors: Chinonso Onah, Kristel Michielsen

We formulate a global-position colored-permutation encoding for the capacitated vehicle routing problem. Each of the $K$ vehicles selects a disjoint partial permutation, and the sum of these $K$ color layers forms a full $n\times n$ permutation matrix that assigns every customer to exactly one visit position. This representation uses $n^2K$ binary decision variables arranged as $K$ color layers over a common permutation structure, while vehicle capacities are enforced by weighted sums over the entries of each color class, requiring no explicit load register and hence no extra logical qubits beyond the routing variables. In contrast, many prior quantum encodings introduce an explicit capacity or load representation with additional qubits. Our construction is designed to exploit the Constraint-Enhanced QAOA framework together with its encoded-manifold analyses. Building on a requirements-based view of quantum utility in CVRP, we develop a routing optimization formulation that directly targets one of the main near-term bottlenecks, namely the additional logical-qubit cost of vehicle labels and explicit capacity constraints. Our proposal shows strong algorithmic performance in addition to qubit efficiency. On a standard benchmark suite, our end-to-end pipeline recovers the independently verified optima. The feasibility oracle may also be of independent interest as a reusable polynomial-time decoding and certification primitive for quantum and quantum-inspired routing pipelines.

Authors: Mark Braverman, Roi Livni, Yishay Mansour, Shay Moran, Kobbi Nissim

Modern machine learning systems, such as generative models and recommendation systems, often evolve through a cycle of deployment, user interaction, and periodic model updates. This differs from standard supervised learning frameworks, which focus on loss or regret minimization over a fixed sequence of prediction tasks. Motivated by this setting, we revisit the classical model of learning from equivalence queries, introduced by Angluin (1988). In this model, a learner repeatedly proposes hypotheses and, when a deployed hypothesis is inadequate, receives a counterexample. Under fully adversarial counterexample generation, however, the model can be overly pessimistic. In addition, most prior work assumes a \emph{full-information} setting, where the learner also observes the correct label of the counterexample, an assumption that is not always natural. We address these issues by restricting the environment to a broad class of less adversarial counterexample generators, which we call \emph{symmetric}. Informally, such generators choose counterexamples based only on the symmetric difference between the hypothesis and the target. This class captures natural mechanisms such as random counterexamples (Angluin and Dohrn, 2017; Bhatia, 2021; Chase, Freitag, and Reyzin, 2024), as well as generators that return the simplest counterexample according to a prescribed complexity measure. Within this framework, we study learning from equivalence queries under both full-information and bandit feedback. We obtain tight bounds on the number of learning rounds in both settings and highlight directions for future work. Our analysis combines a game-theoretic view of symmetric adversaries with adaptive weighting methods and minimax arguments.

Authors: Jarosław Błasiok, Paul Lou, Alon Rosen, Madhu Sudan

In the noisy $k$-XOR problem, one is given $y \in \mathbb{F}_2^M$ and must distinguish between $y$ uniform and $y = A x + e$, where $A$ is the adjacency matrix of a $k$-left-regular bipartite graph with $N$ variables and $M$ constraints, $x\in \mathbb{F}_2^N$ is random, and $e$ is noise with rate $η$. Lower bounds in restricted computational models such as Sum-of-Squares and low-degree polynomials are closely tied to the expansion of $A$, leading to conjectures that expansion implies hardness. We show that such conjectures are false by constructing an explicit family of graphs with near-optimal expansion for which noisy $k$-XOR is solvable in polynomial time. Our construction combines two powerful directions of work in pseudorandomness and coding theory that have not been previously put together. Specifically, our graphs are based on the lossless expanders of Guruswami, Umans and Vadhan (JACM 2009). Our key insight is that by an appropriate interpretation of the vertices of their graphs, the noisy XOR problem turns into the problem of decoding Reed-Muller codes from random errors. Then we build on a powerful body of work from the 2010s correcting from large amounts of random errors. Putting these together yields our construction. Concretely, we obtain explicit families for which noisy $k$-XOR is polynomial-time solvable at constant noise rate $η= 1/3$ for graphs with $M = 2^{O(\log^2 N)}$, $k = (\log N)^{O(1)}$, and $(N^{1-α}, 1-o(1))$-expansion. Under standard conjectures on Reed--Muller codes over the binary erasure channel, this extends to families with $M = N^{O(1)}$, $k=(\log N)^{O(1)}$, expansion $(N^{1-α}, 1-o(1))$ and polynomial-time algorithms at noise rate $η= N^{-c}$.

Authors: Mika Göös, Nathaniel Harms, Florian K. Richter, Anastasia Sofronova

Alice and Bob are given $n$-bit integer pairs $(x,y)$ and $(a,b)$, respectively, and they must decide if $y=ax+b$. We prove that the randomised communication complexity of this Point--Line Incidence problem is $Θ(\log n)$. This confirms a conjecture of Cheung, Hatami, Hosseini, and Shirley (CCC 2023) that the complexity is super-constant, and gives the first example of a communication problem with constant support-rank but super-constant randomised complexity.

Authors: Egor Fokin, Manolis Savva

Physics-based simulation involves trade-offs between performance and accuracy. In collision detection, one trade-off is the granularity of collider geometry. Primitive-based colliders such as bounding boxes are efficient, while using the original mesh is more accurate but often computationally expensive. Approximate Convex Decomposition (ACD) methods strive for a balance of efficiency and accuracy. Prior works can produce high-quality decompositions but require large numbers of convex parts and are sensitive to the orientation of the input mesh. We address these weaknesses with VisACD, a visibility-based, rotation-equivariant, and intersection-free ACD algorithm with GPU acceleration. Our approach produces high-quality decompositions with fewer convex parts, is not sensitive to shape orientation, and is more efficient than prior work.

Authors: Sandro M. Roch

A unique sink orientation (USO) is an orientation of the edges of a polytope in which every face contains a unique sink. For a product of simplices $Δ_{m-1} \times Δ_{n-1}$, Felsner, Gärtner and Tschirschnitz (2005) characterize USOs which are induced by linear functions as the USOs on a $(m \times n)$-grid that correspond to a two-colored arrangement of lines. We generalize some of their results to products $Δ^1 \times\cdots\times Δ^r$ of $r$ simplices, USOs on $r$-dimensional grids and $(r+1)$-signotopes.

Authors: Sariel Har-Peled

We provide a simple algorithm for computing a balanced separator for a set of segments that is $c$-packed, showing that the separator cuts only $O(c)$ segments. While the result was known before, arguably our proof is simpler.

Authors: Mattéo Couplet, Alexandre Chemin, David Bommes, Edward Chien

We present a method for generating orthogonal quadrilateral meshes subject to user-defined feature alignment and sizing constraints. The approach relies on computing integrable orthogonal frame fields, whose symmetries are implicitly represented using orthogonally decomposable (odeco) tensors. We extend the existing 2D odeco integrability formulation to the 3D setting, and define the useful energies in a finite element approach. Our frame fields are shear-free (orthogonal) by construction, and we provide terms to minimize area and/or stretch distortion. The optimization naturally creates and places singularities to achieve integrability, obviating the need for user placement or greedy iterative methods. We validate the method on both smooth surfaces and feature-rich CAD models. Compared to previous works on integrable frame fields, we offer better performance in the presence of mesh sizing constraints and achieve lower distortion metrics.

Authors: Norayr Matevosyan

We introduce eigencone constellations, a hierarchical framework for embedding bounded-degree spatial graphs into concentric spherical shells and partitioning each shell into spectrally weighted, spherical star-shaped territories. Given a connected sparse spatial graph $G$ with a distinguished root vertex (the queen), we assign each vertex to a sphere whose radial position is determined by its graph distance from the queen, then tessellate each sphere into constellation territories whose solid angles are proportional to the spectral mass of the corresponding subgraph. Within each territory, nodes are packed by constrained repulsion, yielding local simplex structures. The resulting geometric representation provides a structural framework for measuring spectral distance between dynamic subgraph states. By combining this eigencone-derived metric with constraints on the domain-specific edit alphabet, we define a forward-only deterministic trajectory -- the isomorphic walk -- which converges graph edits efficiently. We define the notion of spherical star-shaped domains with geodesic visibility, establish their properties under spectral projection, and demonstrate the trajectory convergence on molecular contact graphs.

Authors: Yiming Gao, Yansong Feng, Honggang Hu, Yanbin Pan

We study the \emph{Subset Balancing} problem: given $\mathbf{x} \in \mathbb{Z}^n$ and a coefficient set $C \subseteq \mathbb{Z}$, find a nonzero vector $\mathbf{c} \in C^n$ such that $\mathbf{c}\cdot\mathbf{x} = 0$. The standard meet-in-the-middle algorithm runs in time $\tilde{O}(|C|^{n/2})=\tilde{O}(2^{n\log |C|/2})$, and recent improvements (SODA~2022, Chen, Jin, Randolph, and Servedio; STOC~2026, Randolph and Węgrzycki) beyond this barrier apply mainly when $d$ is constant. We give a reduction from Subset Balancing with $C = \{-d, \dots, d\}$ to a single instance of $\mathrm{SVP}_{\infty}$ in dimension $n+1$, which yields a deterministic algorithm with running time $\tilde{O}((6\sqrt{2πe})^n) \approx \tilde{O}(2^{4.632n})$, and a randomized algorithm with running time $\tilde{O}(2^{2.443n})$ (here $\tilde{O}$ suppresses $\operatorname{poly}(n)$ factors). We also show that for sufficiently large $d$, Subset Balancing is solvable in polynomial time. More generally, we extend the box constraint $[-d,d]^n$ to an arbitrary centrally symmetric convex body $K \subseteq \mathbb{R}^n$ with a deterministic $\tilde{O}(2^{c_K n})$-time algorithm, where $c_K$ depends only on the shape of $K$. We further study the \emph{Generalized Subset Sum} problem of finding $\mathbf{c} \in C^n$ such that $\mathbf{c} \cdot \mathbf{x} = τ$. For $C = \{-d, \dots, d\}$, we reduce the worst-case problem to a single instance of $\mathrm{CVP}_{\infty}$. Although no general single exponential time algorithm is known for exact $\mathrm{CVP}_{\infty}$, we show that in the average-case setting, for both $C = \{-d, \dots, d\}$ and $C = \{-d, \dots, d\} \setminus \{0\}$, the embedded instance satisfies a bounded-distance promise with high probability. This yields a deterministic algorithm running in time $\tilde{O}((18\sqrt{2πe})^n) \approx \tilde{O}(2^{6.217n})$.

Authors: Sarat Moka, Ava Vahedi

We present a new algorithm for the exact uniform sampling of proper \(k\)-colorings of a graph on \(n\) vertices with maximum degree~\(Δ\). The algorithm is based on partial rejection sampling (PRS) and introduces a soft relaxation of the proper coloring constraint that is progressively tightened until an exact sample is obtained. Unlike coupling from the past (CFTP), the method is inherently parallelizable. We propose a hybrid variant that decomposes the global sampling problem into independent subproblems of size \(O(\log n)\), each solved by any existing exact sampler. This decomposition acts as a {\em complexity reducer}: it replaces the input size~\(n\) with \(O(\log n)\) in the component solver's runtime, so that any improvement in direct methods automatically yields a stronger result. Using an existing CFTP method as the component solver, this improves upon the best known exact sampling runtime for \(k>3Δ\). Recursive application of the hybrid drives the runtime to \(O(L^{\log^* n}\cdot nΔ)\), where \(L\) is the number of relaxation levels. We conjecture that \(L\) is bounded independently of~\(n\), which would yield a linear-time parallelizable algorithm for general graphs. Our simulations strongly support this conjecture.

Authors: Huairui Chu, Ajaykrishnan E S, Daniel Lokshtanov, Anikait Mundhra, Thomas Schibler, Xiaoyang Xu, Jie Xue

In the Rectangle Stabbing problem, input is a set ${\cal R}$ of axis-parallel rectangles and a set ${\cal L}$ of axis parallel lines in the plane. The task is to find a minimum size set ${\cal L}^* \subseteq {\cal L}$ such that for every rectangle $R \in {\cal R}$ there is a line $\ell \in {\cal L}^*$ such that $\ell$ intersects $R$. Gaur et al. [Journal of Algorithms, 2002] gave a polynomial time $2$-approximation algorithm, while Dom et al. [WALCOM 2009] and Giannopolous et al. [EuroCG 2009] independently showed that, assuming FPT $\neq$ W[1], there is no algorithm with running time $f(k)(|{\cal L}||{\cal R}|)^{O(1)}$ that determines whether there exists an optimal solution with at most $k$ lines. We give the first parameterized approximation algorithm for the problem with a ratio better than $2$. In particular we give an algorithm that given ${\cal R}$, ${\cal L}$, and an integer $k$ runs in time $k^{O(k)}(|{\cal L}||{\cal R}|)^{O(1)}$ and either correctly concludes that there does not exist a solution with at most $k$ lines, or produces a solution with at most $\frac{7k}{4}$ lines. We complement our algorithm by showing that unless FPT $=$ W[1], the Rectangle Stabbing problem does not admit a $(\frac{5}{4}-ε)$-approximation algorithm running in $f(k)(|{\cal L}||{\cal R}|)^{O(1)}$ time for any function $f$ and $ε> 0$.

Authors: Sobyasachi Chatterjee, Sushmita Gupta, Saket Saurabh, Sanjay Seetharaman, Anannya Upasana

We study a natural generalization of the classical \textsc{Dominating Set} problem, called \textsc{Dominating Set with Quotas} (DSQ). In this problem, we are given a graph \( G \), an integer \( k \), and for each vertex \( v \in V(G) \), a lower quota \( \mathrm{lo}_v \) and an upper quota \( \mathrm{up}_v \). The goal is to determine whether there exists a set \( S \subseteq V(G) \) of size at most \( k \) such that for every vertex \( v \in V(G) \), the number of vertices in its closed neighborhood that belong to \( S \), i.e., \( |N[v] \cap S| \), lies within the range \( [\mathrm{lo}_v, \mathrm{up}_v] \). This richer model captures a variety of practical settings where both under- and over-coverage must be avoided -- such as in fault-tolerant infrastructure, load-balanced facility placement, or constrained communication networks. While DS is already known to be computationally hard, we show that the added expressiveness of per-vertex quotas in DSQ introduces additional algorithmic challenges. In particular, we prove that DSQ becomes \W[1]-hard even on structurally sparse graphs -- such as those with degeneracy 2, or excluding \( K_{3,3} \) as a subgraph -- despite these classes admitting FPT algorithms for DS. On the positive side, we show that DSQ is fixed-parameter tractable when parameterized by solution size and treewidth, and more generally, on nowhere dense graph classes. Furthermore, we design a subexponential-time algorithm for DSQ on apex-minor-free graphs using the bidimensionality framework. These results collectively offer a refined view of the algorithmic landscape of DSQ, revealing a sharp contrast with the classical DS problem and identifying the key structural properties that govern tractability.

Authors: Negin Golrezaei, MohammadTaghi Hajiaghayi, Suho Shin

In the contest design problem, there are $n$ strategic contestants, each of whom decides an effort level. A contest designer with a fixed budget must then design a mechanism that allocates a prize $p_i$ to the $i$-th rank based on the outcome, to incentivize contestants to exert higher costly efforts and induce high-quality outcomes. In this paper, we significantly deepen our understanding of optimal mechanisms under general settings by considering nonconvex objectives in contestants' qualities. Notably, our results accommodate the following objectives: (i) any convex combination of user welfare (motivated by recommender systems) and the average quality of contestants, and (ii) arbitrary posynomials over quality, both of which may neither be convex nor concave. In particular, these subsume classic measures such as social welfare, order statistics, and (inverse) S-shaped functions, which have received little or no attention in the contest literature to the best of our knowledge. Surprisingly, across all these regimes, we show that the optimal mechanism is highly structured: it allocates potentially higher prize to the first-ranked contestant, zero to the last-ranked one, and equal prizes to the all intermediate contestants, i.e., $p_1 \ge p_2 = \ldots = p_{n-1} \ge p_n = 0$. Thanks to the structural characterization, we obtain a fully polynomial-time approximation scheme given a value oracle. Our technical results rely on Schur-convexity of Bernstein basis polynomial-weighted functions, total positivity and variation diminishing property. En route to our results, we obtain a surprising reduction from a structured high-dimensional nonconvex optimization to a single-dimensional optimization by connecting the shape of the gradient sequences of the objective function to the number of transition points in optimum, which might be of independent interest.

Authors: Bernhard Haeupler, Yonggang Jiang, Thatchaphol Saranurak

We show that every directed graph $G$ with $n$ vertices and $m$ edges admits a directed acyclic graph (DAG) with $m^{1+o(1)}$ edges, called a DAG projection, that can either $(1+1/\text{polylog} (n))$-approximate distances between all pairs of vertices $(s,t)$ in $G$, or $n^{o(1)}$-approximate maximum flow between all pairs of vertex subsets $(S,T)$ in $G$. Previous similar results suffer a $Ω(\log n)$ approximation factor for distances [Assadi, Hoppenworth, Wein, STOC'25] [Filtser, SODA'26] and, for maximum flow, no prior result of this type is known. Our DAG projections admit $m^{1+o(1)}$-time constructions. Further, they admit almost-optimal parallel constructions, i.e., algorithms with $m^{1+o(1)}$ work and $m^{o(1)}$ depth, assuming the ones for approximate shortest path or maximum flow on DAGs, even when the input $G$ is not a DAG. DAG projections immediately transfer results on DAGs, usually simpler and more efficient, to directed graphs. As examples, we improve the state-of-the-art of $(1+ε)$-approximate distance preservers [Hoppenworth, Xu, Xu, SODA'25] and single-source minimum cut [Cheung, Lau, Leung, SICOMP'13], and obtain simpler construction of $(n^{1/3},ε)$-hop-set [Kogan, Parter, SODA'22] [Bernstein, Wein, SODA'23] and combinatorial max flow algorithms [Bernstein, Blikstad, Saranurak, Tu, FOCS'24] [Bernstein, Blikstad, Li, Saranurak, Tu, FOCS'25]. Finally, via DAG projections, we reduce major open problems on almost-optimal parallel algorithms for exact single-source shortest paths (SSSP) and maximum flow to easier settings: (1) From exact directed SSSP to exact undirected ones, (2) From exact directed SSSP to $(1+1/\text{polylog}(n))$-approximation on DAGs, and (3) From exact directed maximum flow to $n^{o(1)}$-approximation on DAGs.

Authors: Kemal Mutluergil, Deniz Elbek, Kamer Kaya, Erkay Savaş

Homomorphic encryption (HE) enables computation over encrypted data but incurs a substantial overhead. For sparse-matrix vector multiplication, the widely used Halevi and Shoup (2014) scheme has a cost linear in the number of occupied cyclic diagonals, which may be many due to the irregular nonzero pattern of the matrix. In this work, we study how to permute the rows and columns of a sparse matrix so that its nonzeros are packed into as few cyclic diagonals as possible. We formalise this as the two-dimensional diagonal packing problem (2DPP), introduce the two-dimensional circular bandsize metric, and give an integer programming formulation that yields optimal solutions for small instances. For large matrices, we propose practical ordering heuristics that combine graph-based initial orderings - based on bandwidth reduction, anti-bandwidth maximisation, and spectral analysis - and an iterative-improvement-based optimization phase employing 2OPT and 3OPT swaps. We also introduce a dense row/column elimination strategy and an HE-aware cost model that quantifies the benefits of isolating dense structures. Experiments on 175 sparse matrices from the SuiteSparse collection show that our ordering-optimisation variants can reduce the diagonal count by $5.5\times$ on average ($45.6\times$ for one instance). In addition, the dense row/column elimination approach can be useful for cases where the proposed permutation techniques are not sufficient; for instance, in one case, the additional elimination helped to reduce the encrypted multiplication cost by $23.7\times$ whereas without elimination, the improvement was only $1.9\times$.

Authors: Davi Castro-Silva, Jop Briët, Srinivasan Arunachalam, Arkopal Dutt, Tom Gur

We provide algorithmic versions of the Polynomial Freiman-Ruzsa theorem of Gowers, Green, Manners, and Tao (Ann. of Math., 2025). In particular, we give a polynomial-time algorithm that, given a set $A \subseteq \mathbb{F}_2^n$ with doubling constant $K$, returns a subspace $V \subseteq \mathbb{F}_2^n$ of size $|V| \leq |A|$ such that $A$ can be covered by $2K^C$ translates of $V$, for a universal constant $C>1$. We also provide efficient algorithms for several "equivalent" formulations of the Polynomial Freiman-Ruzsa theorem, such as the polynomial Gowers inverse theorem, the classification of approximate Freiman homomorphisms, and quadratic structure-vs-randomness decompositions. Our algorithmic framework is based on a new and optimal version of the Quadratic Goldreich-Levin algorithm, which we obtain using ideas from quantum learning theory. This framework fundamentally relies on a connection between quadratic Fourier analysis and symplectic geometry, first speculated by Green and Tao (Proc. of Edinb. Math. Soc., 2008) and which we make explicit in this paper.

Authors: Oded Lachish, Amit Levi, Ilan Newman, Felix Reidl

We consider graph property testing in $p$-degenerate graphs under the random neighbor oracle model (Czumaj and Sohler, FOCS 2019). In this framework, a tester explores a graph by sampling uniform neighbors of vertices, and a property is testable with one-sided error if its query complexity is independent of the graph size. It is known that one-sided error testable properties for minor-closed families are exactly those that can be defined by forbidden subgraphs of bounded size. However, the much broader class of $p$-degenerate graphs allows for high-degree ``hubs" that can structurally hide forbidden subgraphs from local exploration. In this work, we provide a complete structural characterization of all properties testable with one-sided error in $p$-degenerate graphs. We show that testability is fundamentally determined by the connectivity of the forbidden structures: a property is testable if and only if its violations cannot be fragmented across disjoint high-degree neighborhoods. Our results define the exact structural boundary for testability under these constraints, accounting for both the connectivity of individual forbidden subgraphs and the collective behavior of the properties they define.

Authors: Hiroki Shibata, Hideo Bannai

Repetitiveness measures quantify how much repetitive structure a string contains and serve as parameters for compressed representations and indexing data structures. We study the measure $χ$, defined as the size of the smallest suffixient set. Although $χ$ has been studied extensively, its reachability, whether every string $w$ admits a string representation of size $O(χ(w))$ words, has remained an important open problem. We answer this question affirmatively by presenting the first such representation scheme. Our construction is based on a new model, the substring equation system (SES), and we show that every string admits an SES of size $O(χ(w))$.

Authors: Oluwatobi Alafin, George B. Mertzios, Paul G. Spirakis

We present a comprehensive analysis of Round-Delayed Amnesiac Flooding (RDAF), a variant of Amnesiac Flooding that introduces round-based asynchrony through adversarial delays. We establish fundamental properties of RDAF, including termination characteristics for different graph types and decidability results under various adversarial models. Our key contributions include: (1) a formal model of RDAF incorporating round-based asynchrony, (2) a proof that flooding always terminates on acyclic graphs despite adversarial delays, (3) a construction showing non-termination is possible on any cyclic graph, (4) a demonstration that termination is undecidable with arbitrary computable adversaries, and (5) the introduction of Eventually Periodic Adversaries (EPA) under which termination becomes decidable. These results enhance our understanding of flooding in communication-delay settings and provide insights for designing robust distributed protocols.

Authors: Ilias Diakonikolas, Chao Gao, Daniel M. Kane, Ankit Pensia, Dong Xie

We study robust regression under a contamination model in which covariates are clean while the responses may be corrupted in an adaptive manner. Unlike the classical Huber's contamination model, where both covariates and responses may be contaminated and consistent estimation is impossible when the contamination proportion is a non-vanishing constant, it turns out that the clean-covariate setting admits strictly improved statistical guarantees. Specifically, we show that the additional information in the clean covariates can be carefully exploited to construct an estimator that achieves a better estimation rate than that attainable under Huber contamination. In contrast to the Huber model, this improved rate implies consistency even when the contamination is a constant. A matching minimax lower bound is established using Fano's inequality together with the construction of contamination processes that match $m> 2$ distributions simultaneously, extending the previous two-point lower bound argument in Huber's setting. Despite the improvement over the Huber model from an information-theoretic perspective, we provide formal evidence -- in the form of Statistical Query and Low-Degree Polynomial lower bounds -- that the problem exhibits strong information-computation gaps. Our results strongly suggest that the information-theoretic improvements cannot be achieved by polynomial-time algorithms, revealing a fundamental gap between information-theoretic and computational limits in robust regression with clean covariates.

Authors: Sujoy Bhore, Hsien-Chih Chang, Jonathan Conroy, Arnold Filtser, Eunjin Oh, Nicole Wein, Da Wei Zheng

Given a weighted digraph $G$, a $(t,g,μ)$-DAG cover is a collection of $g$ dominating DAGs $D_1,\dots,D_g$ such that all distances are approximately preserved: for every pair $(u,v)$ of vertices, $\min_id_{D_i}(u,v)\le t\cdot d_{G}(u,v)$, and the total number of non-$G$ edges is bounded by $|(\cup_i D_i)\setminus G|\le μ$. Assadi, Hoppenworth, and Wein [STOC 25] and Filtser [SODA 26] studied DAG covers for general digraphs. This paper initiates the study of \emph{Steiner} DAG cover, where the DAGs are allowed to contain Steiner points. We obtain Steiner DAG covers on the important classes of planar digraphs and low-treewidth digraphs. Specifically, we show that any digraph with treewidth tw admits a $(1,2,\tilde{O}(n\cdot tw))$-Steiner DAG cover. For planar digraphs we provide a $(1+\varepsilon,2,\tilde{O}_\varepsilon(n))$-Steiner DAG cover. We also demonstrate a stark difference between Steiner and non-Steiner DAG covers. As a lower bound, we show that any non-Steiner DAG cover for graphs with treewidth $1$ with stretch $t<2$ and sub-quadratic number of extra edges requires $Ω(\log n)$ DAGs.

Authors: Nikhil Bansal, Milind Prabhu, Sahil Singla, Siddharth M. Sundaram

In the classic online graph balancing problem, edges arrive sequentially and must be oriented immediately upon arrival, to minimize the maximum in-degree. For adversarial arrivals, the natural greedy algorithm is $O(\log n)$-competitive, and this bound is the best possible for any algorithm, even with randomization. We study this problem in the i.i.d. model where a base graph $G$ is known in advance and each arrival is an independent uniformly random edge of $G$. This model generalizes the standard power-of-two choices setting, corresponding to $G = K_n$, where the greedy algorithm achieves an $O(\log\!\log n)$ guarantee. We ask whether a similar bound is possible for arbitrary base graphs. While the greedy algorithm is optimal for adversarial arrivals and also for i.i.d. arrivals from regular base graphs (such as $G = K_n$), we show that it can perform poorly in general: there exist mildly irregular graphs $G$ for which greedy is $\widetildeΩ(\log n)$-competitive under i.i.d. arrivals. In sharp contrast, our main result is an $O(\log\!\log n)$-competitive online algorithm for every base graph $G$; this is optimal up to constant factors, since an $Ω(\log\!\log n)$ lower bound already holds even for the complete graph $G = K_n$. The key new idea is a notion of log-skewness for graphs, which captures the irregular substructures in $G$ that force the offline optimum to be large. Moreover, we show that any base graph can be decomposed into ``skew-biregular'' pieces at only $O(\log\!\log n)$ scales of log-skewness, and use this to design a decomposition-based variant of greedy that is $O(\log\!\log n)$-competitive.

Authors: Marjan Homayouni-Sangari, Abolfazl Ramezanpour

We find that reinforcement exponentially reduces computation time of the quantum search problem from $\sqrt{D}$ to $\ln D$ in a $D$-dimensional system. Therefor, a reinforced quantum search is expected to exhibit an exponentially larger noise threshold compared to a standard search algorithm in a noisy environment. We use numerical simulations to characterize the level of noise tolerance via reinforcement in the presence of both coherent and incoherent noise, considering a system of $N$ qubits and a single $D$-level (qudit) system. Our results show that reinforcement significantly enhances the algorithm's success probability and improves the scaling of its computation time with system size. These findings indicate that reinforcement offers a promising strategy for error mitigation, especially when a precise noise model is unavailable.

Authors: Ravindran Kannan, Kijun Shin, David Woodruff

We study the Nearest Neighbor Search (NNS) problem in a high-dimensional setting where data lies in a low-dimensional subspace and is corrupted by Gaussian noise. Specifically, we consider a semi-random model in which $n$ points from an unknown $k$-dimensional subspace of $\mathbb{R}^d$ ($k \ll d$) are perturbed by zero-mean $d$-dimensional Gaussian noise with variance $σ^2$ per coordinate. Assuming the second-nearest neighbor is at least a factor $(1+\varepsilon)$ farther from the query than the nearest neighbor, and given only the noisy data, our goal is to recover the nearest neighbor in the uncorrupted data. We prove three results. First, for $σ\in O(1/k^{1/4})$, simply performing SVD denoises the data and provably recovers the correct nearest neighbor of the uncorrupted data. Second, for $σ\gg 1/k^{1/4}$, the nearest neighbor in the uncorrupted data is not even identifiable from the noisy data in general, giving a matching lower bound and showing the necessity of this threshold for NNS. Third, for $σ\gg 1/\sqrt{k}$, the noise magnitude $σ\sqrt d$ significantly exceeds inter-point distances in the unperturbed data, and the nearest neighbor in the noisy data generally differs from that in the uncorrupted data. Thus, the first and third results together imply that SVD can identify the correct nearest neighbor even in regimes where naive nearest neighbor search on the noisy data fails. Compared to \citep{abdullah2014spectral}, our result does not require $σ$ to be at least an inverse polynomial in the ambient dimension $d$. Our analysis uses perturbation bounds for singular spaces together with Gaussian concentration and spherical symmetry. We also provide empirical results on real datasets supporting our theory.

Authors: Kun He

The Sinkhorn--Knopp (SK) algorithm is a cornerstone method for matrix scaling and entropically regularized optimal transport (EOT). Despite its empirical efficiency, existing theoretical guarantees to achieve a target marginal accuracy $\varepsilon$ deteriorate severely in the presence of outliers, bottlenecked either by the global maximum regularized cost $η\|C\|_\infty$ (where $η$ is the regularization parameter and $C$ the cost matrix) or the matrix's minimum-to-maximum entry ratio $ν$. This creates a fundamental disconnect between theory and practice. In this paper, we resolve this discrepancy. For EOT, we introduce the novel concept of well-boundedness, a local bulk mass property that rigorously isolates the well-behaved portion of the data from extreme outliers. We prove that governed by this fundamental notion, SK recovers the target transport plan for a problem of dimension $n$ in $O(\log n - \log \varepsilon)$ iterations, completely independent of the regularized cost $η\|C\|_\infty$. Furthermore, we show that a virtually cost-free pre-scaling step eliminates the dimensional dependence entirely, accelerating convergence to a strictly dimension-free $O(\log(1/\varepsilon))$ iterations. Beyond EOT, we establish a sharp phase transition for general $(\boldsymbol{u},\boldsymbol{v})$-scaling governed by a critical matrix density threshold. We prove that when a matrix's density exceeds this threshold, the iteration complexity is strictly independent of $ν$. Conversely, when the density falls below this threshold, the dependence on $ν$ becomes unavoidable; in this sub-critical regime, we construct instances where SK requires $Ω(n/\varepsilon)$ iterations.

Authors: Stephen Arndt, Benjamin Moseley, Kirk Pruhs, Chaitanya Swamy, Michael Zlatin

We study algorithmic matroid intersection coloring. Given $k$ matroids on a common ground set $U$ of $n$ elements, the goal is to partition $U$ into the fewest number of color classes, where each color class is independent in all matroids. It is known that $2χ_{\max}$ colors suffice to color the intersection of two matroids, $(2k-1)χ_{\max}$ colors suffice for general $k$, where $χ_{\max}$ is the maximum chromatic number of the individual matroids. However, these results are non-constructive, leveraging techniques such as topological Hall's theorem and Sperner's Lemma. We provide the first polynomial-time algorithms to color two or more general matroids where the approximation ratio depends only on $k$ and, in particular, is independent of $n$. For two matroids, we constructively match the $2χ_{\max}$ existential bound, yielding a 2-approximation for the Matroid Intersection Coloring problem. For $k$ matroids we achieve a $(k^2-k)χ_{\max}$ coloring, which is the first $O(1)$-approximation for constant $k$. Our approach introduces a novel matroidal structure we call a \emph{flexible decomposition}. We use this to formally reduce general matroid intersection coloring to graph coloring while avoiding the limitations of partition reduction techniques, and without relying on non-constructive topological machinery. Furthermore, we give a \emph{fully polynomial randomized approximation scheme} (FPRAS) for coloring the intersection of two matroids when $χ_{\max}$ is large. This yields the first polynomial-time constructive algorithm for an asymptotic variant of Rota's Basis Conjecture. This constructivizes Montgomery and Sauermann's recent asymptotic breakthrough and generalizes it to arbitrary matroids.

Authors: Greg Bodwin, Luba Samborska

We prove that the flow-cut gap for $n$-node directed graphs is at most $n^{1/3 + o(1)}$. This is the first improvement since a previous upper bound of $\widetilde{O}(n^{11/23})$ by Agarwal, Alon, and Charikar (STOC '07), and it narrows the gap to the current lower bound of $\widetildeΩ(n^{1/7})$ by Chuzhoy and Khanna (JACM '09). We also show an upper bound on the directed flow-cut gap of $W^{1/2}n^{o(1)}$, where $W$ is the sum of the minimum fractional cut weights. As an auxiliary contribution, we significantly expand the network of reductions among various versions of the directed flow-cut gap problem. In particular, we prove near-equivalence between the edge and vertex directed flow-cut gaps, and we show that when parametrizing by $W$, one can assume unit capacities and uniform fractional cut weights without loss of generality.

August 19-21, 2026 Boston University https://randomconference.com/random-2026-home/ Submission deadline: May 6, 2026 The 30th International Conference on Randomization and Computation (RANDOM 2026) will be held at Boston University, Boston, Massachusetts, USA, on August 19-21, 2026 (together with APPROX 2026 and WOLA 2026). The deadline to submit your papers for RANDOM 2026 is May 6, 2026 (Anywhere … Continue reading RANDOM 2026 Call For Papers

By shacharlovett

Authors: Lucas Gretta, Meghal Gupta, Malvika Raj Joshi

A major open problem in understanding shallow quantum circuits (QAC$^0$) is whether they can compute Parity. We show that this question is solely about the Fourier spectrum of QAC$^0$: any QAC$^0$ circuit with non-negligible high-level Fourier mass suffices to exactly compute PARITY in QAC$^0$. Thus, proving a quantum analog of the seminal LMN theorem for AC$^0$ is necessary to bound the quantum circuit complexity of PARITY. In the other direction, LMN does not fully capture the limitations of AC$^0$. For example, despite MAJORITY having $99\%$ of its weight on low-degree Fourier coefficients, no AC$^0$ circuit can non-trivially correlate with it. In contrast, we provide a QAC$^0$ circuit that achieves $(1-o(1))$ correlation with MAJORITY, establishing the first average-case decision separation between AC$^0$ and QAC$^0$. This suggests a uniquely quantum phenomenon: unlike in the classical setting, Fourier concentration may largely characterize the power of QAC$^0$. PARITY is also known to be equivalent in QAC$^0$ to inherently quantum tasks such as preparing GHZ states to high fidelity. We extend this equivalence to a broad class of state-synthesis tasks. We demonstrate that existing metrics such as trace distance, fidelity, and mutual information are insufficient to capture these states and introduce a new measure, felinity. We prove that preparing any state with non-negligible felinity, or derived states such as poly(n)-weight Dicke states, implies PARITY $\in$ QAC$^0$.

Authors: Vahid R. Asadi, Richard Cleve

The Tree Evaluation Problem ($\mathsf{TreeEval}$) is a computational problem originally proposed as a candidate to prove a separation between complexity classes $\mathsf{P}$ and $\mathsf{L}$. Recently, this problem has gained significant attention after Cook and Mertz (STOC 2024) showed that $\mathsf{TreeEval}$ can be solved using $O(\log n\log\log n)$ bits of space. Their algorithm, despite getting very close to showing $\mathsf{TreeEval} \in \mathsf{L}$, falls short, and in particular, it does not run in polynomial time. In this work, we present the first polynomial-time, almost logarithmic-space algorithm for $\mathsf{TreeEval}$. For any $\varepsilon>0$, our algorithm solves $\mathsf{TreeEval}$ in time $\mathrm{poly}(n)$ while using $O(\log^{1 +\varepsilon}n)$ space. Furthermore, our algorithm has the additional property that it requires only $O(\log n)$ bits of free space, and the rest can be catalytic space. Our approach is to trade off some (catalytic) space usage for a reduction in time complexity.

Authors: Amitai Uzrad

In the dynamic set cover problem, the input is a dynamic universe of elements and a fixed collection of sets. As elements are inserted or deleted, the goal is to efficiently maintain an approximate minimum set cover. While the past decade has seen significant theoretical breakthroughs for this problem, a notable gap remains between theoretical design and practical performance, as no comprehensive experimental study currently exists to validate these results. In this paper, we bridge this gap by implementing and evaluating four greedy-based dynamic algorithms across a diverse range of real-world instances. We derive our implementations from state-of-the-art frameworks (such as GKKP, STOC 2017; SU, STOC 2023; SUZ, FOCS 2024), which we simplify by identifying and modifying intricate subroutines that optimize asymptotic bounds but hinder practical performance. We evaluate these algorithms based on solution quality (set cover size) and efficiency, which comprises update time (the time required to update the solution following each insertion or deletion) and recourse (the number of changes made to the solution per update). Each algorithm uses a parameter $β$ to balance quality against efficiency; we investigate the influence of this tradeoff parameter on each algorithm and then perform a comparative analysis to evaluate the algorithms against each other. Our results provide the first practical insights into which algorithmic strategies provide the most value in realistic scenarios.

Authors: Zhihao Gavin Tang, Yixin Tao, Shixin Wang

We study a single-buyer pricing problem with unreliable side information, motivated by the increasing use of AI-assisted decision-making and LLM-based predictions. The seller observes a private sample that may be either accurate (coinciding with the buyer's valuation), or hallucinatory (an independent draw from the prior), without knowing which case has realized. The buyer does not observe the realized signal, yet knows whether it is accurate or hallucinatory. This creates a higher-order informational asymmetry: the seller is uncertain about the reliability of his own side information, while the buyer has private information about that reliability. Adopting a consistency-robustness framework, we characterize the exact Pareto frontier of tradeoffs between consistency (performance under an accurate signal) and robustness (performance under a hallucinatory signal). We show that keeping the unreliable signal private generates substantial value, yielding tradeoffs that strictly dominate any public-signal benchmark. We further show that perfect consistency does not preclude meaningful protection against hallucination: for every prior, there exists a mechanism achieving perfect consistency together with a nontrivial robustness guarantee of $\frac{1}{2}$. Moreover, if the prior has an infinite mean or a mean of at most its monopoly price, we provide a mechanism that is simultaneously 1-consistent and 1-robust. Our results illustrate a new mechanism design paradigm: rather than relying only on information directly possessed by the designer, mechanisms can be built to leverage the other side's knowledge about the reliability of the designer's information.

Authors: Yuan Chen, Shuai Shao, Ke Shi

We study the zero-free regions of the partition function of the hard-core model on finite graphs and their implications for the analyticity of the free energy on infinite lattices. Classically, zero-freeness results have been established up to the tree uniqueness threshold $λ_c(Δ-1)$ determined by the maximum degree $Δ$. However, for many graph classes, such as regular lattices, the connective constant $σ$ provides a more precise measure of structural complexity than the maximum degree. While recent approximation algorithms based on correlation decay and Markov chain Monte Carlo have successfully exploited the connective constant to improve the threshold to $λ_c(σ)$, analogous results for complex zero-freeness have been lacking. In this paper, we bridge this gap by introducing a proper definition of the connective constant for finite graphs based on a lower bound on the number of $k$-depth self-avoiding walks. We prove that for any graph family with a lower connective constant $μ$, the partition function is zero-free in a complex neighborhood of the interval $[0, λ]$ for all $λ< λ_c(μ)$. As a direct consequence, we establish the uniqueness and analyticity of the free energy density for infinite lattices up to the connective constant threshold, extending the known regions derived from maximum degree bounds. Our proof utilizes a block contraction technique that lifts the correlation decay property from a real interval to a strip-like complex neighborhood.

Authors: Rohan Ghuge, Jai Moondra, Mohit Singh

We study the Stochastic Boolean Function Certification (SBFC) problem, where we are given $n$ Bernoulli random variables $\{X_e: e \in U\}$ on a ground set $U$ of $n$ elements with joint distribution $p$, a Boolean function $f: 2^U \to \{0, 1\}$, and an (unknown) scenario $S = \{e \in U: X_e = 1\}$ of active elements sampled from $p$. We seek to probe the elements one-at-a-time to reveal if they are active until we can certify $f(S) = 1$, while minimizing the expected number of probes. Unlike most previous results that assume independence, we study correlated distributions $p$ and give approximation algorithms for several classes of functions $f$. When $f(S)$ is the indicator function for whether $S$ is the spanning set of a given matroid, our problem reduces to finding a basis of active elements of a matroid by probing elements. We give a non-adaptive $O(\log n)$-approximation algorithm for arbitrary distributions $p$, and show that this is tight up to constants unless P $=$ NP, even for partition matroids. For uniform matroids, we give constant factor $4.642$-approximation ([BBFT20]) that can be further improved to a $2$-approximation if additionally the random variables are negatively correlated for the case of $1$-uniform matroid. We also give an adaptive $O(\log k)$-approximation algorithm for SBFC for $k$-uniform matroids for the Graph Probing problem, where we seek to probe the edges of a graph one-at-a-time until we find $k$ active edges. The underlying distribution on edges arises from (hidden) independent vertex random variables, with an edge being active if at least one of its endpoints is active. This significantly improves over the information-theoretic lower bound on $Ω(\mathrm{poly}(n))$ ([JGM19]) for adaptive algorithms for $k$-uniform matroids with arbitrary distributions.

Authors: Noah Fleming, Max Hopkins, Yuichi Yoshida

Minimum dominating set is a basic local covering problem and a core task in distributed computing. Despite extensive study, in the classic LOCAL model there exist significant gaps between known algorithms and lower bounds. Chang and Li prove an $Ω(\log n)$-locality lower bound for a constant factor approximation, while Kuhn--Moscibroda--Wattenhofer gave an algorithm beating this bound beyond $\log Δ$-approximation, along with a weaker lower bound for this degree-dependent setting scaling roughly with $\min\{\log Δ/\log\log Δ,\sqrt{\log n/\log\log n}\}$. Unfortunately, this latter bound is weak for small $Δ$, and never recovers the Chang--Li bound, leaving central questions: does $O(\log Δ)$-approximation require $Ω(\log n)$ locality, and do such bounds extend beyond LOCAL? In this work, we take a major step toward answering these questions in the non-signaling model, which strictly subsumes the LOCAL, quantum-LOCAL, and bounded-dependence settings. We prove every $O(\logΔ)$-approximate non-signaling distribution for dominating set requires locality $Ω(\log n/(\logΔ\cdot \mathrm{poly}\log\logΔ))$. Further, we show for some $β\in (0,1)$, every $O(\log^βΔ)$-approximate non-signaling distribution requires locality $Ω(\log n/\logΔ)$, which combined with the KMW bound yields a degree-independent $Ω(\sqrt{\log n/\log\log n})$ quantum-LOCAL lower bound for $O(\log^βΔ)$-approximation algorithms. The proof is based on two new low-soundness sensitivity lower bounds for label cover, one via Impagliazzo--Kabanets--Wigderson-style parallel repetition with degree reduction and one from a sensitivity-preserving reworking of the Dinur--Harsha framework, together with the reductions from label cover to set cover to dominating set and the sensitivity-to-locality transfer theorem of Fleming and Yoshida.

Authors: Guy Blanc

We construct algorithms with optimal error for learning with adversarial noise. The overarching theme of this work is that the use of \textsl{randomized} hypotheses can substantially improve upon the best error rates achievable with deterministic hypotheses. - For $η$-rate malicious noise, we show the optimal error is $\frac{1}{2} \cdot η/(1-η)$, improving on the optimal error of deterministic hypotheses by a factor of $1/2$. This answers an open question of Cesa-Bianchi et al. (JACM 1999) who showed randomness can improve error by a factor of $6/7$. - For $η$-rate nasty noise, we show the optimal error is $\frac{3}{2} \cdot η$ for distribution-independent learners and $η$ for fixed-distribution learners, both improving upon the optimal $2 η$ error of deterministic hypotheses. This closes a gap first noted by Bshouty et al. (Theoretical Computer Science 2002) when they introduced nasty noise and reiterated in the recent works of Klivans et al. (NeurIPS 2025) and Blanc et al. (SODA 2026). - For $η$-rate agnostic noise and the closely related nasty classification noise model, we show the optimal error is $η$, improving upon the optimal $2η$ error of deterministic hypotheses. All of our learners have sample complexity linear in the VC-dimension of the concept class and polynomial in the inverse excess error. All except for the fixed-distribution nasty noise learner are time efficient given access to an oracle for empirical risk minimization.

Authors: Stefan Dobrev, Konstantinos Georgiou, Evangelos Kranakis, Danny Krizanc, Lata Narayanan, Jaroslav Opatrny, Denis Pankratov, Sunil Shende

We study a problem of online targets coverage by a drone or a sensor that is equipped with a camera or an antenna of fixed half-angle of view $α$. The targets to be monitored appear at arbitrary positions on a line barrier in an online manner. When a new target appears, the drone has to move to a location that covers the newly arrived target, as well as already existing targets. The objective is to design a coverage algorithm that optimizes the total length of the drone's trajectory. Our results are reported in terms of an algorithm's competitive ratio, i.e., the worst-case ratio (over all inputs) of its cost to that of an optimal offline algorithm. In terms of upper bounds, we present three online algorithms and prove bounds on their competitive ratios for every $α\in [0, π/2]$. The best of them, called \FA is significantly better than the other two for $π/6 < α< π/3$. In particular, for $α=π/4$, its worst case, \FA has competitive ratio $1.25$, while the other two have competitive ratio $\sqrt{2}$. Finally, we prove a lower bound on the competitive ratio of online algorithms for a drone with half-angle $α\in [0, π/4]$; this bound is a function of $α$ that achieves its maximum value at $α= π/4$ equal to $(1+\sqrt{2})/2 \approx 1.207$.

Here are the solutions to the problems I posted last week.

Problem 1

A language \(L\) is commutative if for all \(u\), \(v\) in \(L\), \(uv = vu\). Show that \(L\) is commutative if and only if \(L\) is a subset of \(w^*\) for some string \(w\). The "only if" direction is surprisingly tricky.

Answer

For the "if" direction, suppose \(L \subseteq w^*\). Then every \(u, v \in L\) can be written as \(u = w^i\) and \(v = w^j\), so \(uv = w^{i+j} = vu\).

For the "only if" direction, assume \(L\) is commutative. We may assume \(L\) contains a non-empty string. Let \(u\) be the shortest such string, let \(m\) be the greatest common divisor of the lengths of all non-empty strings in \(L\), and let \(w\) be the prefix of \(u\) of length \(m\). We use the following lemma.

Lemma. If \(xy = yx\) with \(x, y\) non-empty, then both are powers of their common prefix of length \(\gcd(|x|, |y|)\).

Proof of Lemma. By strong induction on \(|x| + |y|\). If \(|x| = |y|\), comparing the first \(|x|\) characters gives \(x = y\), and both equal that string to the first power. If \(|x| < |y|\) (WLOG), comparing the first \(|x|\) characters of \(xy\) and \(yx\) shows \(x\) is a prefix of \(y\). Write \(y = xz\). Then \(x(xz) = (xz)x\) simplifies to \(xz = zx\). Since \(|x| + |z| < |x| + |y|\), the inductive hypothesis gives that \(x\) and \(z\) are powers of their common prefix of length \(\gcd(|x|, |z|) = \gcd(|x|, |y|)\). Since \(y = xz\), \(y\) is a power of this prefix too. \(\square\)

Since \(m\) divides \(|u|\) and, for each \(v \in L\), the lemma gives \(u = r_v^{|u|/\gcd(|u|,|v|)}\), combining these periodicities shows \(u = w^{|u|/m}\). 

Now for any non-empty \(v\neq u \in L\), commutativity gives \(uv = vu\), so by the lemma, \(u\) and \(v\) are both powers of the prefix \(r\) of \(u\) of length \(\gcd(|u|, |v|)\). Since \(m\) divides both \(|u|\) and \(|v|\), it divides \(|r|\), so \(r\) is itself just \(w\) repeated \(|r|/m\) times. Therefore \(v = w^{|v|/m}\). \(\square\)

---

Problem 2

Let an NP machine be sparse if for some \(k\), it has at most \(n^k\) accepting paths for every input of length \(n\). The class FewP is the set of languages accepted by sparse NP machines. Let \(\#N(x)\) be the number of accepting paths of \(N(x)\). Show that if P = FewP then \(\#N(x)\) is polynomial-time computable for any sparse NP machine \(N\).

Answer

The obvious approach is to create a machine \(N'(x, k)\) that accepts if there are at least \(k\) accepting paths of \(N(x)\). But this fails: if \(N(x)\) has \(2n\) accepting paths then \(N'(x, n)\) will have exponentially many accepting paths.

Instead, define \(N'(x, w)\) that accepts if \(N(x)\) has an accepting path starting with \(w\), and use tree search to find all the accepting paths. 

---

Problem 3

Let PERM(\(L\)) be the set of all permutations of the strings in \(L\). For example, PERM(\(\{000, 010\}\)) = \(\{000, 001, 010, 100\}\). Are regular languages closed under PERM? How about context-free languages?

Answer

Regular languages are not closed under PERM. Let \(L = (01)^*\); then \(\mathrm{PERM}(L) \cap 0^*1^* = \{0^n 1^n\}\), which is not regular. Similarly, context-free languages are not closed under PERM in general: \(\mathrm{PERM}((012)^*)\) is not context-free.

However, over a binary alphabet \(\{a, b\}\), if \(L\) is context-free then \(\mathrm{PERM}(L)\) is context-free. Over a binary alphabet, two strings are permutations of each other if and only if they have the same number of each letter, so \(\mathrm{PERM}(L)\) depends only on the Parikh image \(\Pi(L) = \{(|u|_a, |u|_b) : u \in L\}\).

By Parikh's theorem, \(\Pi(L)\) is semilinear for any CFL \(L\), and every semilinear set is the Parikh image of some regular language \(R\). Thus \(\mathrm{PERM}(L) = \mathrm{PERM}(R)\), and it suffices to show \(\mathrm{PERM}(R)\) is context-free for regular \(R\).

Given a DFA \(A\) for \(R\), construct a PDA that, on input \(w\), nondeterministically selects a rearrangement \(u\) of \(w\) while simulating \(A\) on \(u\). The stack tracks the running imbalance \(\Delta_i = |\{a\text{'s in } u_1\cdots u_i\}| - |\{a\text{'s in } w_1 \cdots w_i\}|\) in unary, while the finite control tracks the DFA state and sign of \(\Delta_i\). The PDA accepts iff the DFA reaches a state in \(F\) and the stack is empty (i.e., \(|u|_a = |w|_a\)), establishing \(\mathrm{PERM}(R)\) is context-free.

---

Problem 4

Suppose you have a one-tape Turing machine where we allow the transition function to move the head left, right, or stay put. Show there is an equivalent one-tape Turing machine that only moves the head left or right — and do it without increasing the size of the state space or tape alphabet.

Answer

For each pair \((q, a)\) with \(\delta(q, a) = (p, b, S)\), precompute the stay-closure: keep applying \(\delta\) while the move is \(S\). Since only the scanned cell changes, the process evolves on the finite set \(Q \times \Gamma\). Exactly one of three outcomes occurs: you reach \((p', b', D)\) with \(D \in \{L, R\}\); you enter \(q_{\mathrm{acc}}\) or \(q_{\mathrm{rej}}\); or you fall into an \(S\)-only cycle. Define \(\delta'\) by:

• if the first non-stay step is \((p', b', D)\), set \(\delta'(q, a) = (p', b', D)\);
• if the closure halts, write the last \(b'\) and move (say \(R\)) into \(q_{\mathrm{acc}}\) or \(q_{\mathrm{rej}}\);
• if it \(S\)-loops, write any fixed symbol and move (say \(R\)) into \(q_{\mathrm{rej}}\).

Leave all non-\(S\) transitions unchanged. Then \(Q\) and \(\Gamma\) are unchanged, no \(S\)-moves remain, and the accepted language is preserved.

---

Problem 5

Let E be the set of problems solvable in time \(2^{O(n)}\). Show unconditionally that E \(\neq\) NP.

Answer

EXP, the set of problems solvable in time \(2^{n^{O(1)}}\), has a complete problem that lies in E. So if E = NP then NP = EXP, which gives E = EXP, violating the time hierarchy theorem.

Note this proof does not say anything about whether or not E is contained in NP or vice versa.

---

Problem 6

Show there is a computable list of Turing machines \(M_1, M_2, \ldots\) such that \(\{L(M_1), L(M_2), \ldots\}\) is exactly the set of computable languages.

Answer

This is impossible if the \(M_i\) are all total Turing machines (halt on all inputs). But I never made that requirement.

Let \(N_1, N_2, \ldots\) be the standard enumeration of all Turing machines. Define \(M_i(x)\) to accept if \(N_i(y)\) halts for all \(y < x\) and \(N_i(x)\) accepts. If \(N_i\) is total then \(L(M_i) = L(N_i)\). If \(N_i\) is not total then \(L(M_i)\) is finite and hence computable. Thus \(\{L(M_1), L(M_2), \ldots\}\) contains all computable languages and no non-computable ones. 

By Lance Fortnow

The linear problem specified by an $n \times n$ matrix $M$ over a finite field is the problem of computing the product of $M$ and a given vector $x$. We present optimal error-tolerant random self-reductions (also known as worst-case to average-case reductions) for all linear problems: Given a linear-size circuit that computes $M x$ on an $\varepsilon$-fraction of inputs $x$ for a positive constant $\varepsilon$, we construct a randomized linear-size circuit that computes $M x$ for all inputs $x$ with high probability. This resolves the open problem posed by Asadi, Golovnev, Gur, Shinkar, and Subramanian (SODA'24), who presented quantum $n^{1.5}$-time random self-reductions for all linear problems. Somewhat surprisingly, we also demonstrate the quantum advantage of their quantum reduction over classical uniform algorithms, by proving that any classical subquadratic-time random self-reduction requires the advice complexity of $\Omega(\log(1/\varepsilon) \cdot \log n)$, as long as the field size is at most $1/\varepsilon$. We complement this advice complexity lower bound by presenting (1) a random self-reduction with the optimal advice complexity of $O(\log(1/\varepsilon) \cdot \log n)$ and (2) a uniform random self-reduction over a large finite field.

We resolve the long-standing open problem of Boolean dynamic data structure hardness, proving an unconditional lower bound of $\Omega((\log n / \log\log n)^2)$ for the Multiphase Problem of Patrascu [STOC 2010] (instantiated with Inner Product over $\mathbb{F}_2$). This matches the celebrated barrier for weighted problems established by Larsen [STOC 2012] and closes the gap left by the $\Omega(\log^{1.5} n)$ Boolean bound of Larsen, Weinstein, and Yu [STOC 2018]. The previous barrier was methodological: all prior works relied on ``one-way'' communication games, where the inability to verify query simulations necessitated complex machinery (such as the Peak-to-Average Lemma) that hit a hard ceiling at $\log^{1.5} n$. Our key contribution is conceptual: We introduce a 2.5-round Multiphase Communication Game that augments the standard one-way model with a verification round, where Bob confirms the consistency of Alice's simulation against the actual memory. This simple, qualitative change allows us to bypass technical barriers and obtain the optimal bound directly. As a consequence, our analysis naturally extends to other hard Boolean functions, offering a general recipe for translating discrepancy lower bounds into $\Omega((\log n / \log\log n)^2)$ dynamic Boolean data structure lower bounds. We also argue that this result likely represents the structural ceiling of the Chronogram framework initiated by Fredman and Saks [STOC 1989]: any $\omega(\log^2 n)$ lower bound would require either fundamentally new techniques or major circuit complexity breakthroughs.

A $K$-multi-collision-resistant hash function ($K$-MCRH) is a shrinking keyed function for which it is computationally infeasible to find $K$ distinct inputs that map to the same output under a randomly chosen hash key; the case $K = 2$ coincides with the standard definition of collision-resistant hash function (CRH). A natural question is whether $K$-MCRH implies CRH for $K \geq 3$, as noted by Komargodski, Naor, and Yogev (EUROCRYPT 2018) and also by Jain, Li, Robere, and Xun (FOCS 2024). We resolve this question for all constant $K$, showing that there is no black-box construction of $K$-MCRH from $(K + 1)$-MCRH for all constant $K \geq 2$. We also show that there is no black-box construction of distributional CRH (which is another relaxation of CRH) from 3-MCRH, answering an open question posed by Komargodski and Yogev (CRYPTO 2018) and also by Berman, Degwekar, Rothblum, and Vasudevan (EUROCRYPT 2018). Besides applications in cryptography, our separation also implies black-box separations between TFNP search problems, which are related to problems in proof complexity and other areas.

Can we use ``hardness vs randomness'' techniques to design low-space algorithms? This text surveys a sequence of recent works showing ways to do that. These works designed algorithms for certified derandomization and for catalytic computation (which work unconditionally), derandomization and isolation algorithms from remarkably mild assumptions, and ``win-win'' pairs of algorithms that, for every input, solve either derandomization or another important problem (e.g., $s$-$t$ connectivity) on the input. Underlying these constructions are new, specialized ``hardness vs randomness'' tools for the setting of low-space algorithms. We describe these technical tools, most notably constructions of pseudorandom generators whose reconstruction algorithm (i.e., the security reduction) is a deterministic low-space algorithm. We also explain a key part of obtaining deterministic reconstruction, which is deterministic transformations of distinguishers to bit-predictors. We pose a host of open questions that explore new ways of using hardness vs randomness to design low-space algorithms. These questions address problems in derandomization, catalytic computation, explicit constructions, learning algorithms, and more. This survey appeared in Issue 148 of the Bulletin of the European Association for Theoretical Computer Science.