Theory of Computing Report

We provide a deterministic polynomial-time list decoding algorithm for Reed-Solomon codes over prime fields that approaches list decoding capacity on every evaluation set in the low (constant) rate regime.

Authors: Chenjian Li, Ji Guan

Exact CNOT synthesis asks for a minimum-size CNOT circuit implementing an invertible linear transformation. Although several related synthesis models have been shown to be computationally hard, their hardness proofs rely on additional structure such as restricted qubit connectivity, encoded inputs, or unrestricted intermediate variables. The complexity of the most basic setting---identity input, a fixed number of labelled qubits, no ancillas, and all-to-all CNOT connectivity---had remained unresolved. In this work, we prove that the decision version of this vanilla exact CNOT synthesis problem is NP-complete, and consequently that its optimization version is NP-hard. Our proof gives a polynomial-time reduction from the Hamiltonian-path problem on grid graphs in two steps. First, we isometrically embed the grid graph into a hypercube via a unary encoding map. We then encode this hypercube Hamiltonian path problem into vanilla exact CNOT synthesis. The main challenge is that CNOT synthesis specifies only the final parity matrix and cannot directly enforce the intermediate vertex visits required by a Hamiltonian path. To overcome this difficulty, we introduce extra recorder qubits that encode the required intermediate vertex visits into the final transformation, forcing any CNOT circuit implementation to realize the intended path structure. Beyond CNOT synthesis, our result directly implies hardness for several related problems, including the shortest word problem over $\mathrm{GL}(n,2)$, distance computation on Cayley graphs over $\mathrm{GL}(n,2)$, minimization of sequential XOR programs, and exact synthesis of phase polynomial circuits.

Authors: Rajmohan Rajaraman, Ravi Sundaram, Amanuel Tesfaye

What can a single layer of self-attention compute? We study head complexity: the minimum number of attention heads required to compute a function in a one-layer attention-only model. We establish an exact hierarchy under this measure: $k$ heads compute $k$-bit parity but cannot compute $(k+1)$-bit parity. The lower bound is unconditional in the two resources a transformer might otherwise exploit; it holds at unbounded embedding dimension and unbounded numerical precision. The proof rests on an alternating-sum obstruction: after clearing the softmax denominators, every monomial in the resulting decision polynomial omits at least one of the $k+1$ input bits, forcing its correlation with parity to vanish. The same obstruction yields lower bounds for related tasks, including the well-studied multi-hop induction-head task. We also establish compactness bounds for embedding dimension and numerical precision. Specifically, a compactness theorem shows that any function computable at all can be computed with embedding dimension and precision bounded by the discrete data of the task, namely, head count, alphabet size, and length. Thus, potentially unbounded dimension or precision provably cannot substitute for heads. Finally, we derive nearly matching universal bounds for general binary functions: $2^n$ heads suffice to compute every $n$-bit binary function, with one head per monomial in its multilinear expansion, while a counting argument shows almost all such functions require $Ω(2^n/n^2)$ heads. This lower bound matches the upper bound to within a $\operatorname{poly}(n)$ factor, even when dimension and precision are unbounded. Together, these results characterize head requirements for Boolean computation in this model.

Authors: Khaled Elbassioni, Rishikesh Gajjala, Saurabh Ray

We give exponential quantum query separations between the standard XOR interface and two forward-only interfaces that supply neither an adjoint nor an inverse oracle. Let $X=\F_2^n$, $N=|X|$, and $f_{h,r}(x)=(h(x),x,r_x)$, where $h:X\to X$ is promised to be either a permutation or a Simon two-to-one function, and $r$ is a fixed table of $n$-bit tags, unrestricted by the promise and reused on every query. The resulting problem is solvable with at most $n+2$ standard XOR queries, but has forward-erasing query complexity $Θ(\sqrt N)$. This answers affirmatively open question 11 in [Scott Aaronson. Open problems related to quantum query complexity. ACM Transactions on Quantum Computing, 2(4):14:1-14:9, 2021] . We also embed these instances into permutations. The detailed construction retains the copy of $x$ in each prescribed output, but for these promises that copy can be replaced by one bit that distinguishes the two inputs in every Simon pair. This gives a permutation domain of size $L=4N^2$ and a permutation problem with the same standard-query upper bound and forward-only in-place query complexity $Θ(\sqrt N)=Θ(L^{1/4})$. Both lower bounds remain valid with a clean coherent bypass. The common lower bound uses an analysis-only recording replacement. In the replacement computation, tracing out the fixed random tag table after $T$ calls gives a sum of positive-semidefinite operator contributions, each depending on $h$ at no more than $T$ addresses. On such a set, the restrictions induced by random permutations and random Simon functions differ only if the set contains a hidden Simon pair, an event of probability $O(T^2/N)$.

Authors: Avinash Bhardwaj

The Semidefinite Programming (SDP) relaxation of the Maximum Cut (Max-Cut) problem is exact when its optimal value equals the integer maximum cut, geometrically corresponding to a rank-1 optimal solution. While the pioneering work of Delorme and Poljak established that recognizing exactness is NP-hard, their reduction relied on exponentially scaling edge weights. This established only weak NP-hardness and explicitly left open the complexity for simple, unweighted graphs. In this paper, we resolve the computational complexity of the exactness property. First, we prove that deciding SDP exactness for weighted graphs is strongly NP-hard by constructing a sum-of-squares dual certificate with polynomially bounded integer weights. Second, we extend this hardness to simple, unweighted graphs via a geometric embedding of restricted Not-All-Equal 4-SAT into edge-disjoint clique structures. Both proofs utilize geometric locking mechanisms that force the continuous SDP relaxation to an absolute global minimum, decoupling the continuous bounds from the underlying combinatorial hardness.

Authors: Nick Jamesson

We study the computational complexity of solving promise systems of equations over finite algebras. Given two algebras $\mathbf{A}$ and $\mathbf{B}$ with a homomorphism from $\mathbf{A}$ to $\mathbf{B}$, the promise system of equations problem is to determine if an input system of equations has a solution in $\mathbf{A}$ or not even in $\mathbf{B}$. We generalize the results of Larrauri, Mottet, and Živný [ACM ToCL'26] to obtain a $\mathbf{P}-\mathbf{NP}$-hard dichotomy result for promise systems of equations over a class of algebras which contains all monoids, and a dichotomy result for promise systems of equations over algebras in a congruence modular variety. We then consider the metaproblem for promise systems of equations over algebras in a congruence modular variety: given finite algebras $\mathbf{A}$ and $\mathbf{B}$ such that $\mathbf{A}$ is in a congruence modular variety, we show there is a quasi-polynomial time algorithm for determining whether or not the associated promise system of equations problem is in $\mathbf{P}$.

Authors: Asad Raza, Jens Eisert, Bill Fefferman

Pseudorandomness is increasingly recognized as a key property of ensembles in quantum information theory, statistical mechanics, and quantum many-body physics. Yet it appears in two conceptually different forms: statistical pseudorandomness, embodied by unitary designs, and computational pseudorandomness captured by pseudorandom unitaries (PRUs). The relationship between these two forms of pseudorandomness remains surprisingly poorly understood. Existing PRU constructions reveal this interplay where a statistically randomizing ingredient, a unitary design, is combined with classical cryptographic primitives to produce computational pseudorandomness. We show that statistical pseudorandomness is not necessary for computationally pseudorandom unitaries. We do this by replacing the unitary $2$-design layer in the existing constructions with ensembles that are not even state $1$-designs, yet are sufficiently {\em distinct}, a property we identify to be necessary for any PRU. This yields new non-adaptively secure PRU ensembles whose computational pseudorandomness is obtained without an underlying statistically pseudorandom quantum ensemble, such as a $2$-design. We characterize distinctness via an entangled analogue of anticoncentration and use it to show that distinctness already captures constraints on coherence and imaginarity of PRUs, while identifying broad classes of inputs for which the latter obstruction disappears, enabling real-valued PRUs even for certain (maximally) entangled states. As an application, we use lack of distinctness to constrain the conjectured pseudorandomness of the random phase-Hadamard ensemble to form a PRU.

Authors: Yuxuan Song, Fan Gao, Yibo Zhao, Jiarui Wen, Youcheng Cai, Ligang Liu

Existing 3D mesh reconstruction methods from Gaussian scene representations predominantly rely on iterative optimization, resulting in slow inference and limited scalability to high-resolution inputs. In this paper, we present AnyGS2Mesh, the first feed-forward framework for directly reconstructing 3D meshes from 3D Gaussian Splatting representations with support for arbitrary input image resolutions. Our approach incorporates a Gaussian-Guided Transformer architecture that exploits explicit 3D geometric priors for efficient mesh generation. We introduce three key components: (1) a Gaussian-Guided Spatial Reasoning Transformer represents Gaussian primitives as structured 3D tokens and jointly reasons over Gaussian and image features; (2) a Streaming and Patchwise Geometry Encoder processes native-resolution views sequentially and aggregates information across variable-length view sets; (3) a Scale-Aligned Hybrid Depth Refiner uses a PatchFusion-style encoder--decoder to fuse RGB-conditioned predicted depth with Gaussian-rendered metric depth, combining fine local structures with globally consistent metric scale. The refined depth maps are integrated through TSDF fusion, followed by Marching Cubes for deterministic mesh extraction. Extensive experiments show that AnyGS2Mesh achieves state-of-the-art reconstruction quality while significantly reducing inference time compared with optimization-based baselines, enabling near-real-time, high-quality mesh reconstruction. Our results demonstrate the potential of combining Gaussian representations and feed-forward Transformer architectures for scalable 3D geometry reconstruction. The code will be made publicly available upon acceptance.

Authors: Tongyang Li, Weiran Ma, Ziyi Yang, Xingyu Zhao

The Knaster-Tarski fixed-point theorem states that every monotone function over a complete lattice has a fixed point. Beyond its fundamental role in order theory, the theorem and its algorithmic variants have found broad applications in areas such as economics, game theory, and programming languages. While the query complexity of finding a Tarski fixed point has been extensively studied in classical models, comparatively little is known in the quantum setting. We prove an $Ω(k\log n)$ quantum query lower bound for finding a fixed point of a monotone function on $[n]^k$, using the nonnegative spectral adversary method. In the two extremal regimes $n = 2$ and $k = 1$, our quantum lower bound matches the previous classical lower bounds $Ω(k)$ and $Ω(\log n)$, respectively. For $n, k\geq 2$, our bound improves the best previous classical lower bound when $n < k$ and is within a factor of $\log n / \log k$ compared to the known classical lower bound when $n \geq k$. To construct the adversary matrix, we develop the Tree--Filtration Adversary Method. Besides yielding our lower bound, the method offers a more transparent combinatorial interpretation of the nonnegative spectral adversary method. When the hard instances of a problem admit a tree-like organization and suggest an intuition analogous to classical decision-tree lower bounds, our method provide a promising approach to establishing quantum complexity lower bounds.

Authors: Yu Liu

We study non-adaptive selection of a feasible set $S$ so as to maximize the expected sum of the $k$ largest realized values among independent nonnegative discrete random variables. The same objective arises when hiring a team of $k$ workers or when computing VCG welfare in an $\ell$-unit auction. The main setting is a fixed-dimensional nonnegative packing family: the natural LP has $d=O(1)$ packing inequalities with binary coefficients. No single algorithm achieves a constant factor on every membership family (already at $k=1$). Given an $α$-approximate max-sum oracle, a decreasing surplus search yields ratio $α/((1+α)(1+\eps))$ for every $k\ge 1$ (cuts included). Every fixed-$d$ packing family already has a deterministic max-sum PTAS, hence inherits that constant. The same signatures that drive the exact-sum scheme---occupancy histograms when $k=O(1/\eps^2)$, and a three-dimensional mixture-quantile type when $k=Ω(1/\eps^2)$---are realized by a packing LP rather than by exact-sum, after enumerating $n^{f(d,1/\eps)}$ heavy items. The result is a PTAS for every $k\ge 1$ on every fixed-$d$ packing family, including binary one- and two-dimensional knapsack. In this packing setting the scheme is essentially optimal as a generic guarantee: there is no FPTAS that works for every such $\F$ unless $P=NP$, and no EPTAS unless $W[1]=FPT$ (two-dimensional knapsack is a witness, already at $k=1$). A separate boundary is query-weight exact-sum, which includes DAG paths and matchings and is incomparable with fixed-$d$ packing. That oracle also yields a PTAS for every $k$, so $d$-dimensional packing is a useful taxonomy, not a partition of every family that admits a PTAS.

Authors: Matthias C. Caro, Natalie McHugh, Sergii Strelchuk

Parameterised graph theory studies how the complexity of graph-theoretic problems depends on structural parameters of the input graph. This perspective has proved useful in analysing tensor-network simulation (Markov and Shi, 2008). Its implications for tensor-network representations and tomography are less well understood. In particular, which graph parameters determine whether a tensor-network state (TNS) admits a tractable matrix product state (MPS) or tree tensor network (TTN) representation, and which control the complexity of learning the state? We address these questions using parameterised graph theory. First, we show that cutwidth and tree-cutwidth bound the bond dimension overhead required to represent a TNS as an MPS or TTN. In the TTN case, tree-cutwidth also bounds the local dimension of the grouped subsystems. The proofs are based on entanglement rerouting, a tensor-network analogue of rerouting information in a classical network. Second, we derive graph-dependent upper bounds on the sample and computational complexity of realisable TNS tomography, with exponents that depend on cutwidth, tree-cutwidth, and a new graph parameter, learning complexity, which we bound in terms of degree and treewidth. We obtain these results by extending the disentangling MPS learner of (Cramer et al., 2010), as analysed further in (Bakshi et al., 2025; Lin et al., 2025), to TTNs and to tensor networks on arbitrary known graphs. Finally, we extend the framework beyond the realisable setting. For an arbitrary input state, our agnostic learner outputs a pure state whose fidelity is within additive error $ε$ of the optimum over tensor-network states on the given graph with a given bond dimension, with explicit graph-dependent bounds on sample and computational complexity.

Authors: Zihong Yi

We give deterministic FPTASes for two dense counting problems on which the known deterministic algorithms, based on zero-free interpolation, run in quasipolynomial time. For fixed $0<γ<1/2$ and $0<θ\leq1$, the first approximates $\mathrm{haf}(A)$ for a symmetric matrix $A$ when its support graph $G$ has minimum degree at least $(1/2+γ)n$ and its nonzero entries lie in $[θ,1]$. It also approximates permanents under the analogous bipartite condition, including full-support matrices in $[θ,1]$. For fixed $β>0$ and $0<κ\leq1$, the second approximates the zero-field Ising partition function $Z(J)$ for zero-diagonal real symmetric matrices $J$ satisfying $\max_{i,j}|J_{ij}|\leqβ/n$ and $λ_{\max}(J)\leq1-κ$. No separate lower-eigenvalue condition is imposed. We further prove $\log\mathrm{haf}(A)=h_A(G)-n/2+O_{γ,θ}(1)$ and $Z(J)=2^n\det(I-J)^{-1/2}(1+O_{β,κ}(1/n))$. Here $h_A(G)$ is the maximum weighted fractional-matching entropy. For unweighted graphs, the first formula improves the Cuckler--Kahn error from $o(n)$ to $O_γ(1)$ on the fixed-margin class and extends it to weights in $[θ,1]$. Both algorithms use a common Gaussian truncation principle. Each problem becomes an integral of a product of a fixed entire function over Gaussian coordinates, with possibly indefinite moment matrix entries of order $1/n$. Cancelling the linear term and exactly resumming the quadratic term leaves a coordinate remainder vanishing to order at least three. Complex dilation handles small supports. For large supports, we bound the recombined tail by a large-deviation rate that beats the entropy of the subsets. The truncation error is at most $(CR/n)^{R/2}+e^{-cn}$. This faster-than-geometric decay permits $R\log(en/R)=O(\log n+\log(1/ε))$ and hence polynomial enumeration.

Authors: Shaddin Dughmi, Yusuf Hakan Kalayci, Vasilis Livanos, Aditya Prasad

Motivated by numerous parallelizable stochastic search problems, most notable and timely among them being LLM inference-time scaling, we propose and study batched versions of the Pandora's Box problem of Weitzman. In particular, boxes are opened in capacity-constrained batches, each batch has a setup cost, and all rewards in a batch are revealed together. We consider two different variants, motivated by different application environments: one where boxes are reusable (i.e., can provide multiple i.i.d.~samples) and another where they are not. For both variants we rule out most ``simple'' natural heuristics, and also formally prove NP-hardness of approximation in the traditional sense. We then relax the problem to allow bi-criteria approximations, with respect to both rewards and setup costs, where we exhibit constant approximation algorithms for both the reusable and non-reusable settings. This is obtained through a linear-programming relaxation of Pandora's Box problem, followed by randomized or Pipage rounding.

Authors: Adam Y. Shavit

Wang and Sitters' 11/6-approximation for graph balancing is not one algorithm but a set of permitted executions: Step 1 may return any feasible solution of the relaxation and Step 3 any of the many ways to match the remaining jobs into the slots the rounding opens. We determine exactly what that latitude permits: ratios arbitrarily close to 11/6, and none reaching it, so 11/6 is the least constant that bounds every permitted run, and no run attains it. We then determine the worst-case guarantee as a function of the big-job threshold beta, measured against the optimum itself. On Wang and Sitters' own range 1/2 < beta < 1 the guarantee is exactly max{3/2 + beta/2, 5/2 - beta}. We then extend the same eligibility rule to 0 < beta <= 1/2 -- outside the range they state, and where a big job's two shares can both reach the threshold, so Step 2 acquires a third choice -- and determine the guarantee there as well: exactly 3/2 + (1-beta)floor(1/beta), hence unbounded as beta falls. The worst-case ratio is therefore known at every threshold in (0,1), and attained at none. Consequently 2/3 is the unique optimal threshold, and the guarantee jumps at one half rather than degrading smoothly. A companion note asks what does not fix the constant.

Authors: Daniël Vos, Sterre Lutz

We present our submission to the IJCAI 2025 'Counterfactual Routing Competition' (CRC 25). The goal of the competition is to find counterfactual explanations for the shortest path problem. This requires deciding what the minimal changes to a road network would make a route chosen by the user the optimal route. This enables explanations such as "Your suggested route would indeed have been optimal, if road X were not a bicycle path." Our solution models the problem as an integer program, iteratively incorporating constraints until an exact solution is found. In the final evaluation on held-out test instances, our method ranked fourth in solution quality and obtained its solution fastest on every instance, with an average runtime of 9.0 seconds compared to 118.8 seconds for the next-fastest submission.

Authors: Rong-Hua Li, Yichun Yang

We study the basic problem of approximating the number of spanning trees of a graph. We propose an algorithm that approximates the number of spanning trees in $\widetilde O(m+n^{7/4}\eps^{-3/2})$ time on a graph with $n$ vertices and $m$ edges. Our algorithm improves upon the previously best known $\widetilde O(m+n^{15/8}\eps^{-7/4})$ time algorithm by Chu, Gao, Peng, Sachdeva, Sawlani, and Wang [FOCS 2018] and the $\widetilde O(m^{1.5}\eps^{-1})$ time algorithm by Liu, Peng and Yang [FOCS 2026] when $m\ge n^{7/6}$. Notably, our algorithm is based on the novel concept of $\ell_1$-regularized resistance. We propose simple and efficient algorithms for computing $\ell_1$-regularized resistance and we show that they can be used to approximate the number of spanning trees by combining with the determinant sparsifier framework of Durfee, Peebles, Peng, and Rao [FOCS 2017].

Authors: Garud Iyengar, Yuanzhe Ma, Jay Sethuraman

We study assortment and procurement design for a digital content platform offering both ad-supported and subscription access. Users are heterogeneous in content preferences and ad tolerance and self-select between the two modes or an outside option. For a fixed common subscription price and ad load, the platform chooses assortment distributions specific to each user type and access mode, together with content-family-level buy-versus-rent decisions to maximize profit. Rental costs scale with realized consumption, whereas buying provides a reusable pool of titles whose cost depends on the largest induced requirement across user types and modes. We show that the resulting problem is NP-hard. We then develop a scalable approximation framework based on a candidate buy set, a relaxation of the procurement coupling, and a decomposition into linear programs with a single equality constraint. These subproblems are solved by dual bisection with cardinality-constrained assortment optimization, followed by restricted-master postprocessing to recover primal feasibility. The method yields computable optimality-gap bounds, an interpretable threshold-based procurement heuristic, and asymptotic optimality under proportional market scaling as market size and grid resolution increase. Numerical experiments show strong performance at moderate market scales and grid sizes.

Hi there, argmin readers! As the fall semester picks up, posting volume will, too. So I’m going to commit to writing short descriptive headers to help you sort through the different threads. Today’s post is a live blog of Lecture 3 of my graduate seminar “Forecasting: A Critical Retrospective.” A table of contents is here.

Since the Great Depression, US law has required financial management companies that offer products like mutual funds to add a disclaimer to all of their advertising:

The thing is, not a single person believes this. The fund managers don’t believe it, and neither do the customers. Why would you buy a mutual fund if you didn’t think its past performance told you something about how much you’ll have upon retirement? We tend to believe that some investments are riskier than others and some managers are more reputable than others. These beliefs are based upon past observations, and we use them to inform our investment decisions.

So what do we need to do to transform past observations into forecasts? We believe that the past can’t perfectly predict the future. We also believe that a forecaster is only as good as their track record. In today’s class, we’ll link these two together, showing how the evaluation metric for forecast track records leads us to particular forecasting algorithms.

Let’s start with the two main examples from Edmond Halley. We believe the past strongly predicts the future when talking about the motions of celestial bodies. We believe it far less when pricing individual insurance policies.

For his comet, Halley paired three observations together using insights about orbital shapes from Isaac Newton. Given the roughly 76-year gaps between these observations, he predicted we’d see the same object again 76 years later. In 1835, by the time we had seen Halley’s comet twice more, astronomers were uniformly convinced Halley was right and were certain we’d see the comet again in 1910 and 1986 (they were proven correct).

For his life table, Halley grouped people by age and used these cohorts to make demographic forecasts. The proportion of the population aged 25 was 1.668%, and the proportion aged 26 was 1.647%. Therefore, he concluded the odds a 25-year-old would live to see 26 were approximately 80 to 1 in favor.

The move in the demography example to consider odds and chance is interesting, and was something in the air at the time. Proto-demographer John Graunt had made similar calculations of hazard and risk in his tabulations thirty years earlier. Probability applied to casino games had only begun to be formalized forty years earlier. The transmutation of frequencies into risk was intuitive once you started assembling databases. Now we just take it for granted, having created a formal structure that hides the intuition.

In today’s lecture, we’ll work out some of the formalism of this map from rates to risks, deriving the mathematical formulas that encode our assumptions. If you assert that a forecaster will be evaluated on their track record, and if you believe that events are effectively the same, then you bind yourself to making future predictions a deterministic function of the observed rates. The assumptions here are usually implicit. We’re assuming a strong level of interchangeability between past and future events with a particular signature. And we tend to use metrics that beg the question: the common scoring rules always return probabilistic forecasts.

The evaluation ties your hands to making a particular form of forecast. Given a set of knowledge and a statistical score, you are forced to make a constant prediction for all future events. If you allow your predictions to be real-valued, they are suboptimal if they don’t obey the rules of probability. The score itself leads us into a probabilistic mindset. I’ve been calling this metrical determinism, and I find myself inserting some variant of this lecture in every class I teach.

Both the comet example and the life table example can be thought of as scoring track records on average. When you have highly predictable events, a perfect score is possible, but it takes a few hits to convince a skeptic that you really have nailed it down. When events are less predictable, you just want to make sure you’re not losing money on your annuity sales, and maximizing future profits again leads you into a particular form of forecasting.

What’s important here is we don’t have to assume some sort of generative model of randomness to buy into probabilistic prediction. Halley did not have to assume that god was playing dice with who lived and died. Instead, probabilities and odds were simply convenient tools for the actuary to price their products. Probability was the logical consequence of assuming past performance was indicative of future results.

Subscribe now

By Ben Recht

The θ(p꜀) = 0 conjecture is solved in all dimensions.

In 2024 Gady Kozma and Shahaf Nitzan showed how to derive the dying percolation conjecture from a proposed conjecture about percolation on general graphs. (I briefly discussed it in this post. Their conjecture was so general that many of us expected a counterexample to be discovered before long.) The dying percolation conjecture asserts that for percolation in at the critical probability, with probability one, there is no infinite cluster. This was known for planar percolation and for percolation in high dimensions. It was a famous open problem in the intermediate dimensions starting with dimension 3. A Claude document, accompanied with a Lean verification, claims a positive solution to the Kozma-Nitzan conjecture. (h/t to Itai Benjamini who told me about it yesterday and also about Hugo’s post.) If verified, this is a remarkable breakthrough. See here and here for the AI’s documents.

There are very interesting related question about three-dimensional percolation.  Is critical percolation in dimension three noise sensitive? Is the total influence of critical finite percolation (for large finite n by n by n box) larger than ? Larger than some ?  (Here are positive.)

I had a long research project around these questions with Gady, in which we managed to prove some interesting lemmas. We hoped to bring influences and Fourier tools to the picture.

Hugo’s Duminil-Copin’s post on “Proofs and Prompts”

There is a very interesting new blog called Proofs and Prompts and Hugo Duminil-Copin wrote a thoughtful post Care for a little more AI? about AI and mathematics, using the θ(p꜀) = 0 problem as a primary example. This was three days before Claude claimed the proof and several commentators remarked about the new AI proof.

I liked Alonso Castillo-Ramirez’ comment: “we can still have great joy and be marvelled by the beauty of mathematics on its own, independently if it was created by a human or an AI.”

And here is a moving Facebook post by another famous researcher in percolation theory – Jeff Steif.

By Gil Kalai

Authors: Surendra Ghentiyala, Pritish Kamath, Ravi Kumar, Pasin Manurangsi

We study the question of answering linear queries with differential privacy using few (expected) random bits. We provide a randomness-efficient analog of the $\| \cdot \|_K$-norm mechanism of Hardt and Talwar [HT10]. For the $\ell_\infty$-error, our algorithm can answer $d$ linear queries with $O(d / \varepsilon)$ error using $O(\log d)$ random bits, improving upon algorithms of Canonne et al. and Ghentiyala [CSV25, Ghe26]; this is optimal when $\varepsilon \le 1/d$. We also provide a computationally efficient version of our algorithm, albeit with an $O(\log d)$ multiplicative increase in the error.

Authors: Vaneet Aggarwal, Yiyang Lu

We study online maximization of nonnegative, non-monotone DR-submodular functions over compact convex down-closed subsets of the $d$-dimensional unit cube. The best known constructive offline approximation factor is $0.401$ under the corresponding meta-solvability assumptions, whereas comparable adversarial online guarantees had remained at $1/e$. We show that this factor is also achievable online. In the post-decision full-information value-oracle model, our algorithm attains factor $0.401$ with sublinear approximate regret when oracle feedback is conditionally unbiased and bounded. The online algorithm does not run the offline construction on a changing objective. Instead, it replaces the offline objective-dependent box step by a weighted online learner that controls the required residual terms cumulatively. An exact asymmetric balance theorem preserves the offline coefficients despite adversarial variation. The direct implementation has $O(T^{3/4})$ regret and uses $O(dT^{1/4})$ oracle calls per round. More generally, for every $δ\in[0,1/4]$, batching gives $O(T^δ)$ calls per round and $O(T^{4/5-δ/5})$ regret, including a one-call $O(T^{4/5})$ endpoint. Under a positive-anchor condition, randomized blocking retains factor $0.401$ with $O(T^{5/6})$ one-point bandit regret.

Authors: Gülce Kardeş, Benjamin Rossman

Classical lower bounds for $\mathrm{AC^0}$ circuits proceed bottom-up by simplifying or approximating gates beginning at the input layer. We introduce a complementary top-down model called the Chopping Game, played by adversaries Spoiler and Duplicator on the sets of $0$- and $1$-inputs of a Boolean function. In each round, Spoiler keeps at least a $1/m$-fraction of one side, and Duplicator arbitrarily restricts the other; Spoiler seeks to minimize (and Duplicator to maximize) the number of rounds until some coordinate separates the two remaining sets. Every depth-$d$, fan-in-$m$ circuit induces a $d$-round winning strategy for Spoiler, while Duplicator strategies that survive $d$ rounds formalize top-down lower-bound arguments. Through the Chopping Game and using the polynomial-approximation method, we first obtain the classical lower bound for depth-$d$ $\mathrm{AC^0}$ circuits in a top-down fashion. We then consider a $k$-local variant of the Chopping Game, which relaxes Spoiler's win condition by requiring a separating coordinate within each Hamming ball of radius $k$, rather than a single coordinate globally. We put forward a conjecture that the $d$-round $k$-local Chopping Game for $\mathrm{PARITY}$ requires $m = n^{ω(1)}$ in the regime $d \ll k \ll n$. We prove such a lower bound $m \ge n^{Ω(k^{1/d}/d)}$ when Spoiler is restricted to so-called affine strategies, a class of strategies that achieves the best known upper bounds. Finally, we formulate a version of the $k$-local Chopping Game on $n$-regular graphs of girth $>2k$, and we conjecture a graph-theoretic analogue of ``$\mathrm{PARITY} \notin \mathrm{AC^0}$''.

Authors: Julia Baligacs, Davide Bilò, Václav Blažej, Maël Dumas, Anna Zych-Pawlewicz

Temporal graphs model dynamic networks by assigning positive integer time labels to the edges, while information propagates along temporal paths, whose edge labels are traversed in nondecreasing order. A temporal $α$-spanner of a temporal graph with $n$ vertices is a temporal subgraph that approximates the minimum-hop temporal distance between every pair of vertices within a factor of $α$. While general temporal graphs may not admit sparse temporal $α$-spanners for any value of $α$, temporal cliques are known to admit temporal $(2k-1)$-spanners of size $\widetilde{\mathcal{O}}(kn^{1+1/k})$ for every positive integer $k$. We present a simple recursive algorithm that computes, for every temporal clique on $n$ vertices, a temporal $3$-spanner of size $n^{1+2/\sqrt{\ln n}}=n^{1+o(1)}$, thereby improving the previous best upper bound of $\widetilde{\mathcal{O}}(n^{3/2})$. We also show that a modified version of our algorithm computes temporal $3$-spanners of size $\mathcal{O}(nL)$ when the lifetime is bounded by $L$, i.e., all time labels are in $\{1,\ldots,L\}$, thus improving the previous bound of $\mathcal{O}(2^Ln\log n)$. Both results are particularly striking in light of the known lower bound of $Ω(n^2)$ on the size of temporal $2$-spanners, which already holds for temporal cliques of lifetime $L\geq 3$. Both algorithms rely on a new simple recursive decomposition that certifies temporal connectivity for a large collection of source-target pairs using only $\mathcal{O}(n)$ carefully selected edges and recursively processes only the remaining pairs. Besides yielding substantially improved upper bounds, this approach is significantly simpler than previous constructions.

Authors: Minki Hhan

This paper presents a new randomized algorithm for solving the exact shortest vector problem. For the $n$-dimensional lattice $\mathcal L$, our algorithm runs in time and space $2^{n/2+o(n)}$. Our algorithm can be viewed as a $q$-ary analogue of the midpoint Hessian for an odd prime $q$; more precisely, we use the fact that, for a shortest vector $v$, the gradient (rather than Hessian) of the periodic Gaussian function at $v/q$ is nearly proportional to $v$ (up to sign), even after aggregation over a relatively large random affine coset. We compute the relevant coset gradient along a chain of intermediate lattices using a combinatorial procedure inspired by Wagner's generalized birthday algorithm, yielding the $2^{n/2+o(n)}$ time and space complexity. A variant of the algorithm solves the exact closest vector problem on every input $(y,\mathcal L)$ with a distance guarantee $\operatorname{dist}(y,\mathcal L)\le 1.039λ_1(\mathcal L)$ within the same time and space complexity. This guarantee holds for a random target and a random lattice drawn according to the Haar-Siegel measure. Thus, this algorithm solves a closest vector problem on such random instances in time and space $2^{n/2+o(n)}$.

Authors: Tomer Waizer, Yoav Danieli

Navigability is a fundamental property of graph-based search structures and plays an important role in the analysis of nearest-neighbor algorithms. Informally, a graph is navigable if, from any current point and toward any desired target, there is always an outgoing edge that moves strictly closer to that target. While this property provides a strong guarantee for greedy search, it can be inherently expensive: in the worst case, navigable graphs require $Ω(n^{3/2})$ edges, where $n$ is the size of the dataset. Recently, Avi and Musco introduced $(1-ε)$-almost navigability, a natural relaxation in which, from every current point, such a progress-making edge is required for almost all targets, while an $ε$ fraction of targets may fail this condition \cite{avimusco2026almost}. They showed that every dataset admits such a graph with $O(n/ε)$ edges. In this work, we prove a matching lower bound, establishing the optimality of their construction and giving a complete characterization of the sparsity achievable by almost-navigable graphs. For most values of $ε$, our hard instances lie in Euclidean spaces of polylogarithmic dimension, across the full worst-case range of $ε$, dimension $d=O(\sqrt{n}\log^{3/2} n)$ suffices. The same construction also sharpens our understanding of ordinary navigability: in the latter dimension, we exhibit datasets for which every navigable graph has $Ω(n^{3/2})$ edges. Our proof reveals a surprising connection between almost navigability and the classical Zarankiewicz problem of constructing dense graphs with limited pairwise neighborhood overlap. This connection lets us translate extremal graph constructions into hard geometric instances for navigation, linking two seemingly different notions of graph sparsity.

Authors: Sayan Bhattacharya, Ermiya Farokhnejad, Thatchaphol Saranurak, Haoze Wang

We study the low-degree Steiner forest decomposition. Given a graph $G=(V,E)$ and a terminal set $U\subseteq V$, the standard decomposition returns a set $X\subseteq V$ of size at most $|U|/2$ and a forest $T\subseteq G-X$ of maximum degree $Δ$ such that, for every connected component $C$ of $G-X$, some connected component of $T$ contains all terminals in $U\cap V(C)$. This is the central decomposition behind several connectivity oracles under vertex failures [DP20, LS22, LW24]. The state-of-the-art algorithms either take $O(mn\log n)$ time with degree bound $4$ [DP20], or take $m^{1+o(1)}$ time with the weaker degree bound $O(\log^{2}n)$ [LW24]. We show that if $T$ is allowed to contain vertices of $X$, then a degree-$4$ decomposition can be computed by a very simple algorithm in $O(mα(n))$ time. Further, we show that this relaxed decomposition is equally useful for constructing connectivity oracles under vertex failures. As a consequence, we obtain a deterministic connectivity oracle under $d$ vertex failures with $\tilde{O}(m)$ space, $\tilde{O}(md_\star)$ preprocessing time ($d_\star$ is an upper bound on the number of failed vertices), $\tilde{O}(d^{2})$ update time, and $O(d)$ query time. Up to polylogarithmic factors, this oracle strictly improves all known oracles; in particular, it removes the $n^{o(1)}$ factors from the preprocessing and update times of [LS22, LW24].

Authors: Sunghyeon Jo, Taekyun Lee

Let $G\in\mathbb{R}^{M\times N}$ have independent standard Gaussian entries. For a fixed margin $κ\in\mathbb{R}$, the asymmetric binary perceptron asks for $σ\in\{\pm1\}^N$ such that $Gσ/\sqrt{N}\geκ\mathbf{1}_M$. We study the online version of this problem, in which the columns of $G$ arrive sequentially and each sign must be chosen irrevocably before future columns are revealed. We determine the exact threshold $α_{\mathrm{on}}(κ)$ for every fixed $κ$: for $M/N\toα$ with $α<α_{\mathrm{on}}(κ)$, there is a deterministic online algorithm, using $O(MN)$ arithmetic operations and polynomial bit complexity, that succeeds with high probability, while for $α>α_{\mathrm{on}}(κ)$, no online algorithm succeeds with high probability. The threshold is characterized by a one-dimensional stochastic control problem for Brownian motion. The main difficulty is to upgrade a single-coordinate Brownian limit to simultaneous feasibility of all $M=Θ(N)$ constraints, which we do with half-line monotonicity and a short final correction block. At zero margin, we give a computer-assisted proof that $0.32747<α_{\mathrm{on}}(0)<0.36664$. In particular, every density below $0.32747$ is achievable online by such an algorithm, more than tripling the best density previously proved attainable by any polynomial-time algorithm, online or offline (the previous bound was $α\le0.1$, due to Li, Schramm, and Zhou). As $κ\to+\infty$, the online threshold agrees to first order with the offline storage capacity. As $κ\to-\infty$, it has the same asymptotic scale as the best known offline polynomial-time guarantee, while the storage capacity is larger by a factor of order $κ^2$.

Authors: Dingding Dong, Vishesh Jain

For an $n\times n$ nonnegative matrix $A$, the Bethe permanent, which is computable in deterministic polynomial time, satisfies the tight universal comparison \[\operatorname{Bethe}(A) \leq \operatorname{per}(A) \leq 2^{n/2}\operatorname{Bethe}(A).\] The lower bound, due to Gurvits, is attained on forests. The upper bound, due to Anari and Rezaei, is attained by the adjacency matrix of a disjoint union of $4$-cycles. Confirming a conjecture of Anari, we provide an optimal girth-dependent refinement of the above comparison. More precisely, we show that if the bipartite support graph of $A$ has girth at least an even integer $g \geq 4$, then \[\operatorname{Bethe}(A) \leq \operatorname{per}(A) \leq 2^{2n/g}\operatorname{Bethe}(A).\] The upper bound is attained by the adjacency matrix of a disjoint union of $g$-cycles.

Authors: Maria Chudnovsky, Daniel Lokshtanov, Eran Nevo

A layout of a graph G is an injective function $f : V(G) \rightarrow Z$, and the bandwidth of a layout f is $bw(G,f) = max_{uv \in E(G)} |f(u) - f(v)|$. The bandwidth bw(G) of G is the minimum bandwidth of a layout of G. Computing the bandwidth of a graph is a notoriously hard problem: assuming P != NP, there is no polynomial time algorithm, even on very restricted classes of trees [Monien, SIAM Journal on Algebraic Discrete Methods, 1986], and no constant factor approximation, even on trees [Dubey et al., JCSS 2011]. Assuming the Exponential Time Hypothesis, there is no algorithm with running time $f(k)n^{o(k)}$ to determine whether an input graph has bandwidth at most k, even on very restricted classes of trees [Dregi and Lokshtanov, ICALP 2014]. In this paper we show that {\sc Bandwidth} on general graphs is FPT-approximable. In particular we give an algorithm that takes as input a graph G and an integer k, runs in time $2^{O(9^k)}n^{O(1)}$, and outputs a subtree T of G such that $bw(T) \geq k$ or a layout of G of bandwidth at most $(10^{85} k^{28})^{4^k}$. This resolves in the affirmative an open problem of Chung and Seymour [Discrete Mathematics, 1989], who asked whether the bandwidth of every graph G is upper bounded in terms of the maximum bandwidth of a subtree of G. Our theorem leads to a forbidden subgraph characterization for graphs of bounded bandwidth, and can be seen as an analog for bandwidth of the classic grid minor theorem for treewidth, the forbidden subtree theorem for pathwidth, and the forbidden subpath theorem for treedepth.

Authors: Diar Heidary

The fully independent SparseStack sketch is a vertical stack of $s$ independent CountSketch matrices, scaled by $s^{-1/2}$, so that every column has exactly $s$ nonzero entries. We prove that it is an oblivious subspace embedding for $d$-dimensional subspaces with distortion $ε$ and failure probability $δ$ when $m = O((d+\log(1/δ))/ε^2)$ and $s = O(\log(d/δ)/ε)$, with explicit constants. These are the parameters conjectured by Nelson and Nguyen (FOCS 2013) for this construction; the row count is optimal by their lower bound. The proof bounds the even moments of the Gram error. A conditional-expectation coupling replaces each signed one-hot column selector by a vector with independent three-point entries, at the cost of a constant factor per moment order. The three-point law has a three-dimensional $L_2$ space, so multiplication by an entry is a $3 \times 3$ Jacobi matrix, and the $2q$-th moment becomes a vacuum matrix element of a deterministic operator on a finite tensor product, graded by total occupation. The operator has three grade bands, and we bound each band on the grade-$ν$ sector by $C(\sqrt{(d+ν+1)/m} + (d+ν+1)/m + (ν+1)/s)$ with $C = 3+\sqrt{2}$. The key step is a shared-factor inequality: each row block of the positive operator attached to one tensor slot is rank one with trace $d$, and the sum over $\ell$ slots sharing the same external factor has norm at most $d+\ell-1$. A $2q$-step expansion and Markov's inequality complete the argument, which is finite-dimensional and does not use Gaussian comparison. The theorem has been formally verified in Lean 4. The proof was developed with AI systems under the author's direction, as disclosed in the paper.

Authors: Dongrun Cai, Xue Chen, Xiaowei Shao

We consider efficient algorithms to learn multiband signals and Fourier-sparse signals. A mutliband signal has a Fourier transform supported by a bounded number of intervals, say $I_1 \cup I_2 \cdots \cup I_n$. There is a long line of research on multiband signals. In particular, Avron et al. showed an efficient reconstructing algorithm whose sample complexity is almost optimal. However, all previous algorithms for multiband signals consider the reconstructing problem in which the locations of $I_1,\ldots,I_n$ are given as a priori knowledge. On the other hand, although the problem of learning Fourier-sparse signals with $k$ arbitrary frequencies dates at least to Prony in 1795, designing efficient and robust learning algorithms is still an open problem. The state-of-the-art is an efficient algorithm of $\tilde{O}(k^3)$ samples and $\tilde{O}(k^{3 ω})$ time from the very recent work by Cai et al., while the statistical upper bound is $\tilde{O}(k^2)$ samples. Let $[-1,1]$ be the time window in which the noise is $\ell_2$ bounded. 1. We show an efficient algorithm to recover the locations of the bands $I_1,\ldots,I_n$ in $\hat{x}$ within $\tilde{O}(n+\sum_i |I_i|)$ samples and $\tilde{O}(n+\sum_i |I_i|)$ time. Furthermore, combining this with the reconstructing algorithm by Avron et al. provides an efficient interpolation algorithm within $\tilde{O}(n+\sum_i |I_i|)$ samples. 2. We show that every $k$-Fourier-sparse signal $x$ admits a multiband approximation $z$ whose Fourier transform is of support size $|\mathrm{supp}(\hat{z})|=\tilde{O}(k^2)$. Furthermore, we show an interpolation algorithm for $k$-Fourier-sparse signals with $\tilde{O}(k^2)$ samples and $\tilde{O}(k^5)$ time.

Ben Brubaker has a new Quanta essay Does Computer Science Need Computers? 

Despite the title (and authors generally don't choose their titles), Brubaker's essay really addresses the question as to whether computer science is about computers. He starts with Dijkstra's apocryphal quote "Computer science is no more about computers than astronomy is about telescopes."

This is the wrong analogy: computers are not the telescopes, they are the stars. You just have to use a broad definition of computer.

The word "computer" goes back to at least 1613. The etymology

1. Latin com- meant “together.”
2. Putāre meant “to reckon” or “calculate”—and originally “to prune” or “clear up.”
3. English added -er, meaning “someone or something that performs an action.”

A Computer

By Lance Fortnow

Akiva Kadari, Pablo Soberon and the cascade conjecture

The cascade conjecture is discussed in this post. I proposed the conjecture back in 1974, inspired by work by Meir Katchalski (though the name “Cascade Conjecture” only came into use over the last decade or two).

Akiva Kadari, a master’s student of Micha Perles, proved the planar case in his M.Sc. thesis. Although the proof was ready in the early-to-mid 1980s, writing the thesis was delayed until 1990, when Micha was on sabbatical and I stepped in as a co-supervisor. (Akiva himself was present in the lecture.)

This is the conjecture

 

Recently. Pablo Soberón proved a remarkable weaker version of the conjecture using topological methods—we will devote a dedicated post to it soon. Very recently, Pablo also disproved the last open case of Grünbaum’s famous mass partition conjecture.

Yaacov Kupitz and Geometric graph theory

 

Yaacov Kupitz once decided to spend a year abroad and got in touch with the famous mathematician John Conway. Just a few weeks before taking off, Yaacov discovered he was going to a different John Conway—also famous, but in an entirely different field! Pivoting quickly, Yaacov instead spent a year in Aarhus, Denmark, where he wrote an influential monograph on geometric graphs (which later became his M.Sc. thesis). Vertices in geometric graphs are points in the plane, and edges are line segments (or sometimes pseudo-line segments) between them. It is a fascinating area, and we have written about it here before. János Pach took Micha Perles’s course on geometric graphs at Rutgers in 1989 and subsequently added the topic to his own research interests. In a previous post, we presented two of Micha’s proofs in geometric graph theory, both related to arthropods: his “proof by Lice” and his “proof for Caterpillars.”

A nice story: Micha was once invited to spend a sabbatical at Rutgers at the newly founded DIMACS. One evening, he received a phone call from Daniel Gorenstein, the founding director of DIMACS, who explained that they needed to lower their offer from $70,000 to $65,000. Micha was quite surprised and responded that when he had originally accepted the offer (also over the phone), he was sure it was $17,000!

Two Helly type problems from the 70s

I thought the proof would come from a certain extension of the Nerve Theorem, but it arrived from a different direction instead. Very recently, the conjecture was proved for  by Giuliamaria Menara in the paper A Helly-Type Theorem for two-component convex sets.

I presented this conjecture in a birthday party of another Micha—Micha Sharir. Shortly afterward, it was settled and since then further extended in various directions.

Meir Katchalski’s theorems about  the dimensions of intersections of convex sets.

 

Meir Katchalski’s beautiful theorems about the dimensions of intersections of convex sets were proved as part of his master’s and doctoral work. He obtained results regarding fractional Helly theorems, common transversals, and various other directions. (In my own doctoral work, I settled a conjecture by Katchalski and Perles.) Meir is the son of Israel’s fourth president, the renowned biologist Ephraim Katzir. I also spoke a bit about Branko Grünbaum, Micha’s doctoral supervisor. In one of the pictures , you can see representatives of five academic generations starting with Branko.

Ido Shemer and neighborly polytopes

Ido Shemer was a Ph.D. student around the same time as Noga Alon, Yaacov Kupitz, and me. His thesis was on neighborly polytopes, and he invented the “sewing” method.

The Kupitz-Perles conjecture

We devoted two posts to this beautiful conjecture (here and here), and Rom Pinchasi talked about it in greater detail in his lecture. When Rom proved his remarkable result, I used to ask him in a friendly way (or so I thought!), as a gesture of appreciation for his abilities: “What about ?” From Rom’s lecture, I learned that he felt uncomfortable about this and regarded it as a form of pressure. To quote Rom: “Gil log-log-logged me every time he saw me in the corridors of the Einstein Institute.”

Four slides from Rom’s lecture.

Ziva Deutsch non convexity and graph homomorphisms

Nonconvexity is a very interesting topic closely related to graph homomorphisms—a subject that was greatly advanced by Perles and his students, as well as by Jarik Nešetřil and his colleagues. Two decades ago, Jarik gave a lecture series in Jerusalem on graph homomorphisms. The shapes in the slide are taken from a 1970 paper by Kay and Guay (see the picture below).

 

Interesting examples of nonconvexity. You can see two interesting extensions of the Magen David symbol, as well as two “dancing rulers.”

Here are Mazi, my mother, and me with Micha and members of his family. The younger daughter in the picture came to the session along with Micha’s oldest daughter. Two of Micha’s grandchildren, Shlomi and Itai, also attended—turns out they participated in our Math + AI project!

Moshe Rosenfeld, Yosi Zaks, and Amos Altshuler

 

I also wanted to mention three contemporaries of Micha: Moshe, Yosi, and Amos. Yosi Zaks and Moshe Rosenfeld were both students of Grünbaum—I mentioned their work and their problems here, here, and here. Amos Altshuler is the same age as Micha, but was unofficially Micha’s doctoral student (officially, he was Furstenberg’s student). Amos’s Ph.D. thesis discussed high-dimensional analogs of Hamiltonian cycles, which he tried to find in the boundary complexes of stacked polytopes.

An anecdote: Ehud, Ziva, and Micha

Michael Kallay and Zeev Smilansky

Michael Kallay (an older academic brother) and Zeev Smilansky (a younger one) studied the decomposition of polytopes. (In Hebrew, Michael’s surname and mine have the exact same spelling.) I was enthusiastic about Zeev’s extensions of cyclic polytopes—though Zeev himself did not share my enthusiasm! Zeev eventually moved into biotech, winemaking, and writing prose and poetry, all while spending decades trying to find an elementary geometric proof and strengthenings for the unimodality of the $h$-vector of simple polytopes. (See this post.)

Kallay’s father was a mathematician who wrote an early Hebrew book on calculus. Zeev Smilansky’s father was the famous writer Izhar Smilansky (S. Izhar).

Micha’s early work on Gale’s transform

Micha Perles used the Gale transform to translate the geometric and combinatorial properties of a -dimensional polytope into a lower-dimensional vector configuration in . This made it possible to study, classify, enumerate and construct complex, higher-dimensional polytopes through lower-dimensional representation. One of the most famous applications was Perles constructions an 8-dimensional polytope with 12 vertices that cannot be realized with rational Cartesian coordinates. Gale transform record the affine dependencies among vertices, and many years ago I conjectured that the space of affine stresses could lead to a similar useful “transform”.  

Enumeration of skeletons of polytopes

This is another beautiful theorem by Micha Perles and a beautiful subsequent theorem by Arnau Padrol.

Jamil Kasem’s thesis

Kasem’s thesis dealt with neighborly families of standard boxes which are described by packing of a complete graph with complete bipartite graphs.

Another anecdote

I cannot translate it to English. Since that telephone call Ehud refers to ChatGPT as “my daughter Chatgi.”

 

By Gil Kalai

Authors: Anurag Anshu, Shankar Balasubramanian, Jonas Haferkamp, Aram W. Harrow, Xinyu Tan

We construct a constant-degree and constant-gap quantum expander on $n$ qubits where each unitary can be implemented by a depth-$1$ and 1D circuit of Pauli or CNOT gates. We provide two applications of this expander. First, we use it to construct a family of frustration-free 1D Hamiltonians whose ground states obey the entanglement-gap relation $S = Θ(Δ^{-1/2})$; this is believed to be optimal, but achieving it had been open. Second, we use it to provide a streaming protocol that tests for closeness to a class of 1D volume-law entangled states. Moreover, we extend our quantum expander to a constant-degree and constant-gap expander on the unitary group where each unitary is a single $T$ gate, a single $T^{\dagger}$ gate, or a depth-$1$ Clifford circuit. This implies that a random sequence of unitaries from the expander yields a gapped walk on a dense subgroup of the unitary group. This improves upon previous work by Bourgain and Gamburd which did not control the dependence of the gap on the dimension.

Authors: Jiaqi Liu, Yansong Feng, Yanbin Pan

Let $q$ range over primes congruent to $3$ modulo $4$. Let $ζ_q$ be a primitive $q$th root of unity, and put $K=\mathbb{Q}(ζ_q)$, with ring of integers $\mathcal{O}_K=\mathbb{Z}[ζ_q]$. We prove that the decision version of the Shortest Vector Problem ($\mathrm{SVP}$) in the $\ell_2$-norm is $\mathrm{NP}$-complete on full-rank free submodules of $\mathcal{O}_K^2$ by a deterministic polynomial-time many-one reduction from Exact Cover by 3-Sets (X3C). The module rank is fixed at two. As a $\mathbb{Z}$-lattice, the module has rank $2(q-1)$, which grows with $q$. The main obstacle is closure under the action of $\mathcal{O}_K$. A module containing a nonzero vector also contains every scalar multiple of that vector by a nonzero element of $\mathcal{O}_K$, and some of these multiples may be shorter. Three ideas overcome this obstacle. First, we map the Bennett--Peikert Reed--Solomon lattice to a principal cyclotomic ideal and use Wan's point-count estimates to prove that a coset of this ideal contains many binary coefficient representatives. Second, a checker based on a quadratic Gauss sum turns the X3C equations into a canonical squared norm. Third, the checker and a second module coordinate combine with a separation bound for ideal cosets to rule out every unintended vector created by the $\mathcal{O}_K$-action. Each constructed instance consists of a prime $q\equiv3\pmod4$, two integral generators whose $2\times2$ generator matrix has nonzero determinant, and an integer squared threshold. The construction also gives $\mathrm{NP}$-hardness of search-$\mathrm{SVP}$ under polynomial-time Turing reductions.

Authors: Anatole Dahan

We investigate the expressive power of fixed-point logics (FP) and their extensions in defining generating sets for accessible subgroups of definable permutation groups. This operation, computable in polynomial time via the Schreier-Sims algorithm, plays a central role in the group-theoretic approach to Graph Isomorphism and Graph Canonisation. In particular, it underpins polynomial-time canonisation for bounded colour-class graphs--a class for which no natural logic capturing P is currently known. We first show that this operation cannot, in general, be expressed in any logic for P. This limitation arises from the fact that accessible subgroups need not admit symmetric generating sets of polynomial size. However, we prove that when the base group admits a definable ordered generating set, the accessible subgroup operation becomes definable in fixed-point logic with the group order operator (FP + ord). This is achieved by partially simulating the Schreier-Sims algorithm within FP + ord. As a corollary, we show that fixed-point logic with counting (FPC) can also define the operation when the base group is abelian. In particular, FPC can define the automorphism group of any graph with abelian colours--despite being unable to canonise such graphs.

Authors: Chenghua Liu, Boning Meng

Friedgut conjectured that an increasing family in the $p$-biased discrete cube with bounded relative boundary can be approximated arbitrarily well by one whose minimal elements have bounded size, with a bound independent of the dimension and the bias (J. Amer. Math. Soc. 12 (1999)). We prove this conjecture by showing that, for $0

Authors: Chenghua Liu, Boning Meng

We prove a complexity dichotomy for Boolean Holant problems defined by arbitrary finite sets of algebraic complex-valued signatures when binary disequality is available. The tractable cases are characterized by an explicit, decidable criterion.

Authors: Sebastien Tchitchek, Julien Tierny

This paper introduces the Sierpiński-Knopp (SK) Wasserstein distance, a fast metric between persistence diagrams. The SK-Wasserstein distance, denoted $d_{\mathrm{SK}}$, maps diagram points and their diagonal projections to the unit interval via the Sierpiński-Knopp space-filling curve on the upper diagonal triangle. The encoded point sets are then efficiently matched via one-dimensional optimal assignment, in \(O(N\log N)\) steps, yielding an explicit diagonal-aware point assignment between the two input persistence diagrams. We show that the SK-Wasserstein distance controls the classical \(2\)-Wasserstein distance between diagrams, admits an explicit isometric embedding into a Hilbert space, and induces a positive-definite Gaussian kernel, making the resulting geometry directly compatible with Euclidean and kernel-based learning methods. A tighter surrogate dissimilarity, noted \(W_Γ\), is also introduced based on the point assignments along the curve. Experiments on 12 scientific collections comprising 227 diagrams show median per-collection speedup of \(d_{\mathrm{SK}}\) over state-of-the-art approximations of \(W_2\) is \(626\times\), while the aggregate speedup over the full benchmark is \(2100\times\). Average-linkage partitions obtained from \(d_{\mathrm{SK}}\) and \(W_Γ\) each exactly match the corresponding \(W_2\) partition on 8 of the 12 collections. Hilbert \(k\)-means and Gaussian spectral clustering, both based on \(d_{\mathrm{SK}}\), achieve mean adjusted Rand indices (ARI) of \(0.756\) and \(0.800\), respectively, with respect to the benchmark reference partitions, compared to \(0.750\) obtained by average linkage on \(W_2\). The Gaussian \(d_{\mathrm{SK}}\) kernel supports other kernel-based analysis tasks, as illustrated by its use for contiguous segmentation of ordered diagram collections in our experiments.

Authors: Yeganeh Bahoo, Roni Sherman

This paper investigates $k$-visibility, where a line of sight can penetrate up to $k$ obstacles. While computing the $k$-visibility polygon from a single query point is well-studied, existing spatial preprocessing approaches rely on full $O(n^2)$ line arrangements through all vertex pairs without characterizing the minimal set of topological boundaries. We present a refined cell decomposition framework that isolates the exact geometric events governing $k$-visibility: primary vertex horizon lines and secondary mutually critical hinge lines. We prove that this minimal set of partition lines yields a spatial decomposition of $Θ(n^4)$ cells within which the combinatorial structure of the $k$-visibility polygon remains strictly invariant. By leveraging a combinatorial $δ$-compression scheme across cell boundaries, we achieve an overall storage complexity of $\mathcal{O}(n^4)$ while supporting optimal $\mathcal{O}(\log n + m)$ query time to reconstruct explicit $k$-visibility polygons of size $m$. Our framework naturally extends to polygons containing holes.

Authors: Filippo Baroni, David Fisac, Mingkun Liu

On the once-punctured torus, we give an exact formula for the number of curves in any given mapping class group orbit of given word length. This settles a conjecture of Chas in [Cha16].

Authors: Marc Alexa

Triangulate a simple quadrilateral by connecting all vertices to an additional point. If the vertices carry values, the piecewise linear function can be assigned a Dirichlet energy. We show that the minimal Dirichlet energy as a function of the location of the inserted point is convex, and the location of the minimum is independent of the values at the corners - a quadrilateral has a discrete harmonic center, characterized by an equilibrium of currents across the inserted edges. It turns out that the fixed points of the Möbius involution swapping opposite corners of the quadrilateral are critical points of this energy, so the discrete harmonic center is Möbius-covariant. For tangential and cyclic quadrilaterals the center admits simple closed forms related to the circle centers. The center and its data-independence generalize to polytopes with d + 2 vertices in dimension d, but the conformal characterizations are special to four points in the plane.

Authors: Boris Aronov, Tsuri Farhana, Matthew J. Katz, Indu Ramesh

Let $P$ be a polygonal curve with $n$ vertices in the plane. We construct a data structure of size $O(n \log n)$ suited for simplification queries of the following kind. Given a query line $\ell$ and an integer $k\ge1$, find a curve $Q$ on $\ell$ with at most $k$ vertices that minimizes the discrete Fréchet distance to $P$, among all such curves. Using our data structure, a query can be handled in $O(k^2 \log^3 n + k\log^4 n)$ time. More generally, a geometric tree $T$ on $n$ vertices in the plane can be preprocessed into a near-linear-size structure so that, given a pair $u$, $v$ of its vertices, a line $\ell$, and an integer $k\ge1$, one can find a curve $Q$ on $\ell$ with at most $k$ vertices that minimizes the discrete Fréchet distance to the path from $u$ to $v$ in $T$, in time $O(k^2 \mathop{polylog} n)$. For the general dimension-reduction problem, where $P$ is a curve in $\mathbb{R}^d$ ($d \ge 3$), $0 < \varepsilon_0 < 1$ is a real parameter, and a query specifies a $g$-flat $h$ ($1 \le g \le d-1$) and an integer $k \ge 1$, we construct a data structure of size $O(n\log n + f(\varepsilon_0) n)$, where $f(\varepsilon_0)=(1+1/\varepsilon_0)^{(d-1)/2}$, that allows us to find a curve $Q$ on $h$ with at most $k$ vertices, whose discrete Fréchet distance to $P$ is at most $1+\varepsilon_0$ times the distance of $Q^*$ to $P$, where $Q^*$ is such a curve that minimizes the distance to $P$. The query handling time is $O(f(\varepsilon_0) k^2 \log^2 n)$.

Authors: Ankan Sadhu

Albertson conjectured that every graph with chromatic number r has crossing number at least cr(K_r). The conjecture was verified for r <= 12 by Albertson, Cranston and Fox, for r <= 16 by Bar'at and T'oth, for r <= 18 by Ackerman, and recently for r <= 24 by Cranston, who reduced the remaining cases r in {25, 26} to three orders. We settle those three orders, so that Albertson's Conjecture holds for all r <= 26. Only published results are used, and an appendix reproves the range 19 <= r <= 24 so that the case r <= 26 does not rest on unpublished work. We also show that if chi(G) = 27 and cr(G) < cr(K_27), then G has a 27-critical subgraph of order 53 or 54 whose complement is connected.

Authors: Hiroki Shibata

The shortest common superstring problem is to find the shortest string that contains every string in a given set as a substring. It is conjectured that the greedy algorithm that repeatedly selects a pair of strings with maximum overlap and merges them is a $2$-approximation algorithm, and this conjecture had remained open for nearly four decades. In this paper, we disprove this conjecture and show that the approximation ratio of this algorithm is at least $9/4$.

Authors: Keerti Choudhary, Amit Kumar, Lakshay Saggi

Sensitivity oracles preprocess a graph so that queries can be answered after any $f$ edge insertions and deletions, without recomputing from scratch. For structural optimization problems the known landscape is limited: for flows and cuts, all known compact oracles handle only $f\le2$ failures; existing oracles for $s$- and global min-cut apply only to undirected graphs; and for matchings, arborescence and spanning-tree packings, and arboricity, no efficient oracle is known for $f>1$. We present a unified algebraic framework based on sensitivity oracles for matroid packing, covering, and parity of sparse linear matroids, yielding the first oracles supporting an arbitrary number $f$ of updates across all of these problems (all constructions randomized Monte-Carlo). Concretely, we obtain efficient oracles for exact $(s,t)$-max-flow/min-cut, resolving an open problem of Baswana, Bhanja, and Pandey (ICALP'22) with near-optimal space; for all-pairs $k$-bounded flow, generalizing the near-optimal reachability oracle of Brand and Saranurak (FOCS'19, the case $k=1$); the first oracles for any $f$ for directed $s$- and global min-cut; oracles for $k$-disjoint arborescences, $k$-disjoint spanning trees, colorful spanning trees, and arboricity; and oracles for the existence of an $α$-factor, with perfect matching as the case $α=1$. We further introduce the \emph{subset sensitivity model}, in which updates are confined to a susceptible edge set of size $σ$ fixed during preprocessing. Here we decouple updates from the matroid representation and eliminate the dependence on $k$ and the matroid density altogether: all of the above are supported with $\widetilde O(f^ω)$ query time and $O(fσ^2)$ space. We also prove a matching $Ω(\min\{σ^2,n^2\})$-bit lower bound when $f\ge2$, establishing optimality.

Authors: Ajinkya Gaikwad

The \emph{$s$-Club Cluster Edge Deletion} problem asks whether, given a graph $G$ and an integer $k$, one can delete at most $k$ edges so that every remaining connected component has diameter at most~$s$. This generalizes the classical \emph{Cluster Edge Deletion} problem by permitting components of bounded diameter instead of requiring cliques. On general graphs, $2$-Club Cluster Edge Deletion is known to be fixed-parameter tractable when parameterized by $k$, but it remains open whether it admits a polynomial kernel, as posed in~\cite{ABUKHZAM2023113864}. Motivated by this question, we study the problem on interval graphs and obtain a polynomial vertex kernel of size $\mathcal{O}(k^{5})$. As a complementary result, we also show that the \emph{$s$-Club Cluster Edge Deletion} problem is polynomial time solvable on unit interval graphs. We also show that $2$-Club Cluster Edge Deletion is NP-hard even on split graphs.

Authors: Krišjānis Petručena

We study path diversification in trusted-node networks, where sensitive material is relayed through intermediate nodes, some of which may be compromised. Our randomized routing rule assigns each vertex an independent random priority and repeatedly expands the highest-priority vertex on the global frontier of the explored region. Let $G$ have $n$ vertices, let $s,t$ be honest endpoints, and let $C$ be a set of $c$ compromised intermediate vertices, called a cartel, whose deletion leaves $s$ and $t$ connected. For every fixed $c$ and every fixed target probability $q\in(0,1)$, we prove that $Θ(n^c)$ independent executions are sufficient in the worst case for some route to avoid $C$ with probability at least $q$.

Authors: Patrick Wong

An LLM application often sells or internally allocates several service products: a small or premium model, a short or long token cap, and possibly multiple posted prices. The operational decision is not merely which model answers a prompt. A price changes purchase probability, a token cap changes both user value and the tail of resource consumption, and accepted requests compete for shared compute and premium-model capacity. Demand and output length are initially uncertain, while an offline model may provide useful but imperfect predictions. We formulate sequential pricing and admission with stochastic resource consumption. Each arriving request belongs to an observable segment. The platform chooses a product--price pair or makes no offer; purchase, revenue, and resource use are then random. An offline predictor supplies a uniform, validated error radius for every segment--product cell. We propose Prediction-Clipped UCB (PCUCB), which intersects the offline prediction interval with an online confidence interval, evaluates products using resource shadow prices, and reserves a sample-path envelope before commitment. The prior gives a fast start when accurate, while online learning protects the platform when predictions are coarse. The analysis is modular. On a simultaneous confidence event, regret against a buffered fluid benchmark is bounded by a pacing term plus the cumulative diameter of the intersected intervals. For $J$ segment-product cells and prediction radius $\varepsilon$, this yields \[ \widetilde O\left( \sqrt{T}+(1+\barΛ) \min\{T\varepsilon,\sqrt{JT}\} \right), \] where $\barΛ$ bounds operational shadow prices. Thus the algorithm smoothly interpolates between an almost full-information regime and learning from scratch. Hard feasibility holds on every sample path through reservation envelopes.

This work studies super-Ramanujan graphs: \(d\)-regular graphs whose spectral expansion lies strictly below the Ramanujan threshold \(2\sqrt{d-1}\). Although this threshold is asymptotically optimal for fixed \(d\) as \(n\) tends to infinity, it leaves open the finer question of how small the spectral expansion can be as a joint function of \(n\) and \(d\). Beyond their fundamental mathematical interest and potential applications to pseudorandomness, super-Ramanujan graphs may also have practical significance, since asymptotic analyses can obscure important finite-size effects. Our first result shows that, for every \(d\geq 3\) and every even \(n\), there exists a \(d\)-regular graph \(G\) on \(n\) vertices satisfying \[ \lambda_2(G) \leq 2\sqrt{d-1} - \frac{\sqrt{d}}{4n^{2/3}}. \] For each fixed \(d\), an asymptotic version of this bound also follows from the recent breakthrough work of Huang, McKenzie, and Yau. Related edge-universality results of Huang and Yau (The Annals of Probability, 2026) imply a bound of the same order in the regime \( n^\varepsilon\leq d\leq n^{1/3-\varepsilon}, \) for any fixed sufficiently small \(\varepsilon>0\), while He (Commun. Math. Phys., 2024) obtains a substantially larger advantage in the denser regime \(d\gg n^{2/3}\). These works provide a much richer probabilistic description of the spectral edge, whereas our proof is considerably simpler and gives a nonasymptotic bound that is uniform in both \(n\) and \(d\). Turning to explicit constructions, it is folklore that the Lubotzky-Phillips-Sarnak graphs are super-Ramanujan, but their guaranteed advantage over the Ramanujan threshold is only exponentially small in \(n\). Our second result gives a polynomial-time construction of bipartite super-Ramanujan expanders with advantage at least \( \frac{\sqrt{d}}{2n} \) over the Ramanujan threshold.