Papers

We describe a simple rejection-sampling-based algorithm to perform length-squared sampling on an $n \times n$ positive-semidefinite (psd) matrix: that is, to sample a column with probability proportional to its squared $\ell_2$-norm. The algorithm runs in just $O(n)$ expected time, which is significantly sublinear in the input matrix size. The runtime is optimal, even when the input is assumed to be diagonal. Our result has several applications. Length-squared sampling is used by a number of sublinear time algorithms for matrix problems, like low-rank approximation and eigenvalue approximation. Often, it is assumed that the algorithm is given access to the matrix column norms, and thus can perform length-squared sampling efficiently. Our result shows that, at least for psd matrices, we can remove this assumption. We also discuss an application to an asymptotically optimal algorithm for estimating the Frobenius norm of a psd matrix to relative error. Finally, we show that our sampling algorithm yields a very simple sublinear time algorithm for the robust psd low-rank approximation problem introduced by Bakshi et al. (FOCS, 2020), which nearly matches the more complex method developed there.

Let $v_1,\ldots,v_T\in B_2^m$ be fixed in advance and revealed sequentially, and assume that $\|v_t\|_\infty\leqslant d^{-1/2}$ for some $d\geqslant 1$ and every $1\leqslant t\leqslant T$. There are absolute constants $L,C,c>0$ and a randomized online signing such that $$\mathbb{P}\left\{\max_{k\leqslant T}\left\|\sum_{t=1}^k\varepsilon_t v_t\right\|_\infty>6L\right\} \leqslant CT\exp\left(-\frac{cd}{\ln^2(ed)}\right).$$ Consequently, constant prefix discrepancy holds with probability at least $1-\varepsilon$ once $d$ is at least $C\ln\frac{3T}{\varepsilon}\left[\ln\left(e+\ln\frac{3T}{\varepsilon}\right)\right]^2$. In particular, every fixed sequence of vectors $a_t\in[-1,1]^m$ with at most $d$ nonzero coordinates admits an online signing with prefix discrepancy $O(\sqrt d)$ and failure probability at most $CT\exp[-cd/\ln^2(ed)]$. We also prove a nonuniform version in which the failure probability depends on the individual parameters $d_t=\|v_t\|_\infty^{-2}$, and a lower bound showing that a universal constant prefix discrepancy is impossible when $d=o(\ln T)$. We identify the corresponding $\ln^2 d$ barrier for the compact-potential method and extend the argument to general symmetric target bodies admitting a quadratic smoothness estimate.

We present a slightly simplified analysis of the asymmetric palette sparsification result by Assadi and Yazdanyar [TheoretiCS, 2026]. The motivation is mainly pedagogical; our approach avoids hypergeometric concentration bounds and extra constant factors in the palette size.

Minimizing the weighted completion times ($P \mid \mid \Sigma w_j C_j$) and weighted number of tardy jobs ($P \mid \mid \Sigma w_j U_j$) on multiple identical machines are two classical NP-hard scheduling problems. As shown by Lenté et al. (2014), both problems can be solved in time ${O}^{\star}(3^n)$. In this paper, we improve these bounds to ${O}(2.755^n)$ and ${O}^{\star}(2^n)$, respectively. Our algorithm for $P \mid \mid \Sigma w_j C_j$ exploits the meet-in-the-middle paradigm and an efficient data structure answering linear programming queries. Additionally, when the number of machines is at most $6$, we show that the running time for $P \mid \mid \Sigma w_j C_j$ can further be improved. Both scheduling problems are generalizations of the classical Bin Packing problem, which can be solved in ${O}^{\star}(2^n)$ time. Improving this running time is an important open question. We show that, when assuming the Asymptotic Rank Conjecture (ARC), Bin Packing can be solved in time ${O}((2-\varepsilon)^n)$ for some $\varepsilon >0$. Our algorithm makes use of two main ingredients: the recent ${O}((2-\varepsilon)^n)$-time algorithm of Nederlof et al. [SICOMP'23] for Bin Packing when the number of bins is a fixed constant, and the ${O}((2-\varepsilon)^n)$-time algorithm of Björklund et al. [SODA'25] for special instances of the $3$-way Partitioning problem when assuming ARC.

We study edge-weighted oblivious bipartite matching. The weight of every potential edge is known, but its existence is revealed only when the edge is probed, and a successful probe between two free vertices must be accepted immediately. We give an explicit randomized algorithm with certified competitive ratio $0.698$, improving the previous best guarantee of $0.659$ (Huang, Sun, Wu, and Zhao, FOCS 2025). The result is computer-assisted and verified by a reproducible exact-integer computation. The same algorithm has a $0.698$-competitive online implementation for the vertex-weighted random-arrival model, improving the previous $0.696$ unweighted guarantee of Mahdian and Yan (STOC 2011) and the $0.686$ vertex-weighted guarantee of Peng and Tang (EC 2025). Our algorithm, Harmonic Ranking, is a role-symmetric generalization of Ranking. It assigns an independent random rank $x_z$ to each vertex and probes a potential edge $uv$ in decreasing order of \[ w_{uv}\frac{h(x_u)h(x_v)}{h(x_u)+h(x_v)}. \] This harmonic priority arises from a budget-balanced gain split and a mutual-proposal interpretation. The analysis lifts two cutoff curves into indicators, reducing the exponential-size factor-revealing problem to a polynomial-size directed minimum-cut instance. A maximum-flow computation with rounded-down integer capacities gives a rigorous certificate. Independently, we observe that the finite-grid unweighted relaxation of our factor-revealing program coincides exactly with a Mahdian–Yan program.

We study the maximum flow problem in directed networks with real capacities in the parallel setting. For a network with $n$ vertices and $m$ arcs, we show that a randomized parallel implementation of a variant of the strongly polynomial max-flow algorithm of Dadush, Orlin, Sidford, and Végh [SODA 2026] runs in $\tilde{O}(mn)$ work and $\tilde{O}(m)$ depth. This improves upon the previously described tradeoffs between work and depth for strongly polynomial parallel maximum flow algorithms: earlier $\tilde{O}(n^3)$-work algorithms have $\tilde{O}(n^2)$ depth [Shiloach and Vishkin, J. Algorithms 1982; Goldberg and Tarjan, J. ACM 1988], while the known $\tilde{O}(m)$-depth approach uses $\tilde{O}(mn^3)$ work [Orlin, Oper. Res. 1993].

This paper investigates a multi-robot search-and-visit problem involving $n$ robots starting at the origin and $k$ unknown treasures hidden on the unit circle $\mathcal{C}$. The robots move independently anywhere in the plane with a maximum speed of 1 and instantly share discovery information. The goal is to determine an algorithm that minimizes the total time needed for all robots to individually visit every treasure. To establish the foundational limits of this task, we first solve an auxiliary optimal routing problem for a single robot on $\mathcal{C}$ that possesses complete prior knowledge of the treasure locations. The exact analysis of this auxiliary problem yields explicit upper and lower bounds for the original search problem.

This paper investigates a parallel machine scheduling problem featuring a single common server responsible for both loading and unloading operations. Each job consists of a unit-time loading operation, non-preemptive processing on one of \(m\) identical machines, and a unit-time unloading operation executed by the same server. The objective is to minimize the makespan. Unlike classical loading-only common-server models, our setting requires the server to handle an unloading operation immediately after a job's processing phase concludes. We prove that the corresponding decision problem is strongly NP-complete when the number of machines is given as part of the input. Furthermore, we analyse the worst-case performance of the List Scheduling (LS) and Longest Processing Time (LPT) heuristics. For three machines, we establish that Algorithm LS achieves an approximation ratio of at most \(5/2\). For an arbitrary fixed \(m \ge 3\), we show that the general LS bound approaches \(4-3/m\) as the number of jobs grows, whereas for Algorithm LPT, we prove the finite-instance ratio $3-\frac{2}{m}+\frac{(m-1)(m-2)}{mn}.$ Thus, for each fixed \(m\), the LPT bound approaches \(3-2/m\) as the number of jobs grows.

Sign-nonsingularity asks whether every real matrix with prescribed entry signs is nonsingular. Polynomial-time algorithms recognize square sign-nonsingular patterns through their connection with even directed cycles, but recognition does not itself produce an exact numerical witness in the negative case. We give a deterministic polynomial-time algorithm that, for any square sign pattern $A$, either reports that $A$ is sign-nonsingular or outputs $B\in\mathbb{Z}^{n\times n}$ and $z\in\mathbb{Z}^n\setminus\{0\}$ such that $\operatorname{sgn}(B)=A$ and $Bz=0$. After normalizing a perfect matching, an even directed cycle yields two determinant terms of opposite signs. Making either term dominant produces endpoint realizations with opposite determinant signs. Changing their magnitudes one coordinate at a time exposes an affine sign-changing step, whose zero is rational; clearing its denominator gives the integer witness. Entries of $B$ have $O(n^2\log n)$ bits, and entries of $z$ have $O(n^3\log n)$ bits. The result settles Conjecture 14.12.4 in the Handbook of Satisfiability.

We give a lower bound for randomized non-adaptive group testing when the goal is to find any $\ell$ defective items but the total number $d$ of defectives is unknown. Bshouty and Haddad-Zaknoon proved an upper bound of $O(\ell\log^2 n)$ tests and a lower bound of $$\Omega\!\left(\frac{\ell\log^2 n}{\log \ell+\log\log n}\right).$$ We prove the matching lower bound. More generally, we show that every randomized non-adaptive algorithm that succeeds with constant probability for every defective set must use $$\Omega\!\left(\ell\log^2(n/\ell)\right)$$ tests. The proof is as follows. At a fixed value of $d$, finding $\ell$ defectives requires about $\ell\log(n/d)$ bits of information. On the other hand, one fixed group test is informative only when its size is tuned to the scale of $d$; across all logarithmic scales of $d$, a single test contributes only $O(1)$ bits. Summing over all scales gives the lower bound. We also record the matching upper bound $$O\!\left(\ell\log^2(n/\ell)\right),$$ obtained by running the known-$d$ algorithm in parallel over dyadic guesses for $d$. Thus the randomized non-adaptive complexity of unknown-$d$ partial detection is $\Theta\!\left(\ell\log^2(n/\ell)\right)$ for constant success probability.

We prove that any distributed quantum algorithm that finds a $3$-coloring with probability $1$ in a cycle of anonymous identical computers has to be global, that is, it needs $\Omega(n)$ communication rounds. It follows that quantum computation and communication does not help with this problem. All prior lower bounds on quantum advantage in distributed graph algorithms use arguments related to physical causality. However, it is known that such arguments cannot rule out fast quantum advantage for $3$-coloring cycles. In particular, any causality-based argument would rule out the existence of finitely dependent coloring, but Holroyd and Liggett (2016) showed that such colorings do exist. Hence to tackle this problem, we need a “genuinely quantum” lower-bound technique that can distinguish between (1) distributions that do not violate physical causality vs. (2) distributions that can be realized with a quantum strategy. We present the first such lower-bound technique in this context. First, we show that $1$-round quantum algorithms cannot break symmetry with probability $1$. Second, we present a wishful teleportation strategy that can be used to turn $T$-round quantum 3-coloring algorithms into $1$-round quantum algorithms breaking symmetry, while preserving success probability $1$. Put together, the lower bound follows.

The matroid secretary problem (MSP) is one of the cleanest, and most captivating open problems in online algorithms. The famous MSP conjecture stipulates that there exists a constant-competitive algorithm, yet to date the best known algorithms are $O(\log \log (\text{rank}))$ competitive. It is widely believed that all information that an algorithm for the MSP should use is information that is available through an independence oracle on the already arrived elements. Despite this, there are natural classes of matroids where a constant-competitive algorithm is known if we are given additional upfront information about the matroid; while no such algorithm is known if all the algorithm can use is an independence oracle on the arrived elements. In this work, we tackle the perhaps most appealing such class of matroids, graphic matroids. We develop an algorithm for the MSP that has access to the independence oracle only. Our algorithm runs in polynomial time, and if the underlying matroid is graphic, it produces an independent set whose weight is at least $1/36$ of the maximum-weight independent set. Ours is the first constant-competitive algorithm for MSP on unknown graphic matroids.

We prove a tight $\Theta(n/\epsilon)$ lower bound on the number of samples required for testing halfspaces over $\mathbb{R}^n$, in the distribution-free sample-based model where the underlying probability distribution is unknown to the algorithm, and the algorithm only receives random samples (i.e., it cannot make queries). This shows that testing is no more efficient than learning for halfspaces. We also show a matching upper bound for one-sided testers, improving on the standard (two-sided) testing-by-learning reduction, establishing that two-sided halfspace testers in this model have no advantage over one-sided testers.

We show that a simple extension of the randomized greedy maximal independent set algorithm yields a constant approximation for the maximum matching problem. The algorithm is a simplification of an algorithm used by Assadi et al. [JACM 2026] in the context of processing data streams in the dynamic setting where edges may be inserted and deleted. In contrast to the previous work, our analysis avoids consideration of fractional matchings and yields a significantly shorter and more direct proof of the approximation factor for the basic algorithm.

We establish new bounds on the Grothendieck constant $K_G$: \[ \frac{6\pi}{11} \le K_G \le \frac{\pi}{2\log(1+\sqrt2)} - 10^{-4}. \] Methodologically, our lower bound approach differs from previous works by establishing limitations on the asymptotically optimal Krivine schemes, rather than giving explicit constructions of gap instances. Our upper bound is obtained by proposing and analyzing the first asymptotic construction of rounding schemes, whereas previous works only consider low-dimensional schemes. Together, these bounds determine the previously unknown tenths digit of $K_G$ to be $7$. The bounds were discovered by a long-running collaborative effort of humans and a long-horizon AI research system that we engineered.

In the undirected Densest Subgraph Problem (DSG) the goal is to output a subset $S$ of vertices of a given graph $G$ that maximizes the quantity $|E(S)|/|S|$, where $E(S)$ is the set of edges in the subgraph induced by $S$. The problem is well studied in both theory and practice, and it admits natural efficient exact algorithms, as well as near-linear time algorithms with a $(1-\varepsilon)$ approximation ratio. However, all previously-known approximation schemes incur logarithmic factors in the size of the graph or other parameters of the graph. This raises the question of whether a linear time $(1-\varepsilon)$-approximation can be obtained for all $\varepsilon>0$. We answer this question affirmatively by providing a $(1-\varepsilon)$-approximation algorithm running in time $O\left(\frac{n+m}{\varepsilon^3}\log \frac{1}{\varepsilon}\right)$, where $m$ and $n$ are respectively the number of edges and vertices of $G$. To the best of our knowledge, this is the first truly linear-time approximation scheme for the problem (when $\varepsilon>0$ is a constant). Our algorithm uses assignments arising from a flow-based formulation together with a structural carving lemma. This lemma allows us to progressively carve "sparse" parts of the graph while nearly preserving the densest subgraph, allowing us to shift heavy computations to smaller instances, which eventually yields the mentioned runtime. Our framework also yields a $(1/2 -\varepsilon)$-approximation for the \emph{Densest At-Least-$k$ Subgraph Problem}, where in addition to maximizing the density, we require the subgraph to have at least $k$ vertices. Our algorithm runs in time $O\left( \frac{(n+m) \log^2 n \log \frac{1}{\varepsilon}}{\varepsilon} \right)$. This nearly matches the known $1/2$ approximation hardness while running in near-linear time.

We study the minimum-weight mixed dominating set problem on threshold graphs. In this problem, vertices and edges have weights, and the goal is to find a mixed set of minimum total weight that dominates every vertex and edge of the graph. We first show that arbitrary weights can be reduced to non-negative weights without changing the asymptotic running time. By adapting a reduction to the minimum-weight edge cover given in Ferrarini, Kober, Lancini, and Yuditsky, we obtain an $\mathcal{O}(n^5)$-time algorithm for the minimum weight mixed dominating set problem on threshold graphs.

We study the graphic $s$-$t$ path TSP on subcubic graphs (maximum degree 3): given distinct vertices $s,t$, find a shortest $s$-$t$ walk that visits every vertex. We prove an upper bound with the asymptotically optimal leading coefficient $5/4$ for every terminal pair, even when $G-\{s,t\}$ is disconnected. Specifically, every simple 2-connected subcubic graph $G$ on $n$ vertices has a spanning $s$-$t$ walk of length at most $\lfloor(5n+n_2(G))/4\rfloor$, where $n_2(G)$ counts its degree-2 vertices. An $O(n^2)$-time algorithm attains this bound. Combining an edge-rooted even-cover theorem of Wigal, Yoo, and Yu (WYY) with an even-cover-to-walk lemma proved here yields this bound for adjacent terminals, a consequence not stated explicitly in their paper. We extend the bound to arbitrary terminal pairs. For cubic graphs, it becomes $\lfloor 5n/4 \rfloor$, to our knowledge the first direct $5/4$ bound for cubic path TSP that does not use the general path-to-tour reduction.

We study the problem of connectivity augmentation of a planar graph, while preserving planarity. This problem is motivated by many real-world settings such as road-networks, power-networks etc. In these settings, it is crucial to preserve the original planar embedding after augmentation. In 2009, Gutwenger and Mutzel gave a constructive algorithm showing that a connected planar graph with a fixed embedding (a plane graph) can be optimally augmented to a biconnected graph without crossings while preserving the embedding. We further this line of research, by giving an algorithm that computes a minimum set of edges that makes a connected plane graph 2-edge-connected in \(O(|V|(1+\alpha(|V|)))\) time and linear space, where \(\alpha\) is the inverse Ackermann function.

Having simple algorithms is important for the practical adoption of new algorithms. However, simplifying existing algorithms is a field that does not usually receive a lot of attention from the theoretical computer science community. It also seems like a task that LLMs might perform well. Thus, in this paper we study how well LLMs can simplify algorithms by evaluating three different LLMs on ten different algorithmic problems. Our study resulted in the discovery of two novel algorithms. The first algorithm is for vertex coloring, and gives a refined bound for the so-called asymmetric palette sparsification proposed by Assadi and Yazdanyar [SOSA 2025] with a very simple proof. The second is a further simplification of the algorithm of Saranurak [SOSA 2021] for deterministically computing a global minimum cut in an unweighted graph using expanders.

The Uhlmann fidelity ${\rm F}(\rho_0,\rho_1) = {\rm tr}|\sqrt{\rho_0}\sqrt{\rho_1}|$ is one of the most fundamental quantities in quantum information theory for quantifying the closeness between two quantum states. Estimating the Uhlmann fidelity to within additive error $\varepsilon$ requires a number of copies of the states, or queries to their state-preparation circuits, that depends at least linearly on the smaller of the ranks of $\rho_0$ and $\rho_1$. Consequently, this rank dependence disappears when either state is pure, in which case the query and sample complexities depend only polynomially on $1/\varepsilon$. However, the known optimal estimator for ${\rm F}(\rho,|\psi\rangle\!\langle\psi|)$ due to Fang and Wang (ESA 2025) requires prior knowledge of which state is pure. In this work, we remove this mathematically unnecessary prior-knowledge requirement and establish an optimal estimator for ${\rm F}(\rho, |\psi\rangle\!\langle\psi|)$ under the sole promise that one of the two states is pure, without knowing which one. Our estimator is obtained by specializing the refined algorithmic Uhlmann transform of Utsumi, Nakata, Wang, and Takagi (2025) to the case where one state is pure. In this setting, the Uhlmann fidelity can be recovered as follows: apply a unitary dilation of ${\rm tr}_{\sf A}(|\psi_0\rangle\!\langle\psi_1|)$ (or its inverse) to the reference register $\sf R$ of the purification $|\psi_1\rangle$ (or $|\psi_0\rangle$) on the registers $\sf A$ and $\sf R$, estimate the corresponding square-root amplitude in each case, and take the maximum of the resulting two estimates.

TensorSketch by~\cite{pham2013fast,kar2012random} provides efficient sketching algorithms for high-dimensional polynomial kernels $\vec{x}^{\otimes p} \in \R^{d^p}$. \cite{kar2012random} uses dense Johnson-Lindenstrauss (JL)-type projections with computational cost $O(pDd)$, where $D$ denotes the sketch dimension, whereas~\cite{pham2013fast} extends the sparse CountSketch~\citep{count_sketch} algorithm, yielding a faster algorithm for high-dimensional sparse inputs with running time $O\big(p(\nnz{\vec{x}} + D \log D)\big)$. However, the variance of both estimators grows exponentially with the polynomial degree $p$, scaling as $3^{p}/D$. Recent work by~\cite{pmlr-v206-wacker23a} showed that using complex-valued distribution reduces this dependence to $2^{p}/D$ for the approach of~\cite{kar2012random}. However, their method relies on dense JL-type projections with computational cost $O(pDd)$ and does not extend to the algorithm of~\cite{pham2013fast}. In this work, we introduce a simple variant of TensorSketch~\citep{pham2013fast} that achieves the same variance bound as~\cite{pmlr-v206-wacker23a}, while retaining its advantage of the input-sparsity running time. We validate our results with supporting experiments on synthetic and real-world datasets.

In this paper, we present a stable mergesort variant, "directional mergesort", that to sort an array of $n$ elements makes no more than $nH+3n$ comparisons and $1.5nH+O(n)$ moves where $H$ is the run-based entropy of the input sequence, matching the best existing algorithms in run-adaptive sorting. However, our algorithm is surprisingly minimalistic: it leverages only skip checks, i.e., bypassing the merge step when both halves are already in order, and dynamically changing the direction of merging based on the state of the subarrays. As dynamic run scanning is avoided, all merge steps remain static and derivable from $n$, enabling a reduction to $O(1)$ words of stack space (i.e. space usage excluding the merge buffer) in "directional mergesort$^{++}$", thus improving over the predecessors' $O(\lg n)$ words. Importantly, as directional mergesort adapts only to non-decreasing runs, directional mergesort$^{++}$ also applies a parallel set of rules for (strictly) decreasing runs, allowing the algorithm to also adapt to decreasing runs whilst retaining the original comparison bounds.

We present a theoretical foundation for inverse-distance attention, from its Euclidean prototype (Resolver) to its non-Euclidean realization (Riemann GeoResolver). The Euclidean part establishes three core theorems: (1) circuit separation—IDA achieves exact retrieval with $\mathcal{O}(1)$ resources while softmax requires $\Omega((\log n)^2)$ width; (2) a Polyak–Lojasiewicz inequality with $\Omega(e^{\Delta^2/\sqrt{d}}/\Delta^2)$ stronger constant than softmax, implying linear convergence, $\mathcal{O}(\log n)$ Lipschitz scaling under a low-rank/clustering assumption, $\Theta(1)$ Hessian spread, and absence of spurious local minima; (3) a width-independent effective rank bound that limits noise memorization—softmax memorizes arbitrary labels when $d_h\ge n$, while IDA limits test error to $\mathcal{O}(\eta^2)$. The non-Euclidean extension then builds upon this prototype, replacing Euclidean distance with hyperbolic geodesic distance for storage and spherical geodesic distance for routing. The Riemann GeoResolver framework comprises ten integrated modules: four HIDA operators spanning $\Theta(n^2)$ to $\Theta(1)$ per token; Hyperbolic Curvature Compression (HCC) with provable error bounds; HyperGate with gradient lower-bound theorem; Spherical Inverse Distance Attention (SIDA) with sphere-analog PL inequalities; Dynamic Memory Genesis (DMG) with $\mathcal{O}(\log T)$ regret bounds; and Geodesic Sparse Routing (GSR) with quality and communication bounds. The Euclidean theorems are proved in full; the non-Euclidean extension theorems are proved with analogous arguments. This work establishes a theoretical arc: from Euclidean attention as a special case, to hyperbolic memory, to spherical retrieval.

A set of intervals $I = \{ I_1, I_2, \dots, I_n \}$ forms a simple chain if, for every $2\leq i \leq n-1$, interval $I_i$ overlaps only with $I_{i-1}$ and $I_{i+1}$. We show that a deterministic memoryless one-directional revoking algorithm achieves a competitive ratio of $2(1 - 1/\sqrt{e}) \approx 0.786$ on the simple chain in the random order model, hence performs worse than the basic greedy algorithm without revoking that has a competitive ratio of $(1 - 1/e^2) \approx 0.864$, but better than any deterministic revoking algorithm in the adversarial model that has a competitive ratio of at most $0.75$. The proof of the latter also leads to a lower bound of $n/4$ for the advice complexity.

For an $n$-vertex graph of maximum degree $\Delta$, an equitable $(\Delta+1)$-coloring is a proper coloring all of whose color classes have size $\sigma = n/(\Delta+1)$ up to rounding. Known algorithms for relaxations of this target aggregate along a spanning structure, at cost scaling with the diameter $D$. We study near-equitable coloring in the LOCAL model and prove that, for deterministic algorithms, exact balance is inherently global: already on the cycle $C_n$, exact balanced free $3$-coloring requires $\Omega(n)$ rounds. More generally, additive imbalance $g$ requires $\Omega(n/g)$ rounds, matching a deterministic $O((n/g)\log^* n)$-round algorithm up to the $\log^* n$ factor, and these problems realize a dense family of intermediate deterministic LOCAL complexities $\tilde\Theta(n^\alpha)$, $\alpha \in (0,1)$, on cycles. The exact bound is sharp in two further senses: the identifier-universe threshold is exactly $N=n+1$, and the $\log^* n$ gap cannot be closed via faster ruling-set anchors. The bound then extends to twisted fiber products, an explicit family realizing, for every $\Delta \ge 3$, every diameter scale from the Moore bound $\Theta(\log n/\log\Delta)$ up to $\Theta(n/\Delta)$. Exact equitable $(\Delta+1)$-coloring requires $\Theta(D)$ rounds deterministically on this family, so exactness costs diameter time already on bounded-degree graphs of logarithmic diameter. In contrast, coarse balance admits local algorithms. On cycles, constant multiplicative equity costs $\Theta(\log^* n)$ rounds. On general graphs with large color classes, all class sizes can be kept within $(1\pm\eta)$ times the average in time independent of the diameter: with palette exactly $\Delta+1$ for $\Delta \le 2^{\sqrt{\log n}/C}$, and with palette $(1+\eta)(\Delta+1)$ for every $\Delta \le n^{1-o(1)}$, the latter in $O(\log n\,(\log\log n)^2)$ rounds.

Adaptive stochastic quantization (ASQ) is a recently introduced quantization approach that optimizes the Mean Squared Error (MSE) for a given input while preserving unbiasedness. It is designed to alleviate the communication and memory bottlenecks of modern data and machine learning workloads, including model, gradient, and KV-cache compression and nearest-neighbor search. Further, practical systems can then compress quantized data with a lossless entropy encoder. However, existing unbiased methods, including ASQ, choose their quantization values without considering this later encoding stage, leaving accuracy on the table. We formulate the Entropy Constrained Adaptive Stochastic Quantization (ECASQ) problem, which jointly selects adaptive quantization values to minimize MSE under an entropy budget and an unbiasedness constraint. We give an optimal dynamic program with $O(sd^2)$ time and $O(d^2)$ space for a length-d vector and at most s quantization values, and a GPU-friendly approximate dynamic program with $O(sd^2)$ time and $O(d)$ space. The approximation guarantees that the solution has an MSE no larger than the optimal solution that uses one fewer bit of entropy per entry. We also provide an iterative refinement procedure for the approximation solution that, in our experiments, yields near-optimal results while retaining a substantial speed advantage over our solver for the optimal solution.

We study envy elimination by adding goods (EEAG) when the additional pool has bounded supply and no separate budget bound. We establish a sharp type-count dichotomy for binary additive valuations. With one additional item type, EEAG is polynomial-time solvable for any number of agents. More generally, our algorithm permits arbitrary nonnegative integer per-copy values. The envy constraints form a system of difference constraints, and Bellman–Ford returns the componentwise least feasible extension. In contrast, with exactly two additional item types, EEAG is NP-complete even when both types have positive finite supply and the approvers of one type form a subset of the approvers of the other. This closes the two-type case left open by Bentert et al. Separately, we prove weak NP-completeness even for two agents with identical additive valuations, one initially endowed good, and a growing number of unit-supply item types. Thus, bounded-supply hardness appears both with two item-types and many agents and with two agents and many item-types.

We prove a necessary and sufficient Hall condition for a family $A=(A_e)_{e\in E(G)}$ of hypergraphs indexed by the edges of a forest \(G\). This restriction on the index graph is sharp. The loop-only case recovers the classical Hall's Theorem with multiplicities for arbitrary finite set systems, while the loopless case shows that full rainbow matching is polynomial time solvable under this forest structure, although the problem is NP-complete in general. As another application, we prove every $5$-tough chordal graph is Hamilton-connected, improving toughness bounds of $18$ for Hamiltonicity (1998) and $10$ for Hamilton-connectedness (2017).

Let $x_1,\ldots,x_n$ be independent standard Gaussian vectors in $\mathbb{R}^d$. An ellipsoid fit is a matrix $S \succeq 0$ such that $x_i^\top S x_i =d$ for every $i$, so that all the points lie on the boundary of the centered ellipsoid $\{ x : x^\top S x = d\}$. Saunderson, Parrilo and Willsky conjectured that, as $n,d \to \infty$, this semidefinite feasibility problem undergoes a sharp transition at $n \sim d^2/4$. We prove this conjecture. If $\lim \sup n/d^2 = \alpha^* <1/4$, then, with probability tending to one, an ellipsoid fit exists; moreover, one can choose $S$ with all eigenvalues in a fixed interval $[\lambda_- , \lambda_+] \subset (0,\infty)$ depending only on $\alpha^*$. Conversely, if $\lim \inf n/d^2 > 1/4$, then, with probability tending to one, no ellipsoid fit exists, without any spectral restriction. Our proof builds on the Gaussian-equivalence framework developed by Bandeira and Maillard (2025) and closes the two gaps left open in their work: establishing exact fitting and removing the operator-norm constraint. On the satisfiable side, the new ingredients are a head-tail decomposition of the dual vector, exact correction of the sparse head constraints, and a Gaussian comparison principle for the low-influence tail. On the unsatisfiable side, we split a candidate into a low-rank spectral head and a Schatten-3 diffuse bulk, Gaussianize the bulk conditionally on the head, and apply a projected Gordon escape argument. The threshold is governed by the statistical dimension $d(d+1)/4$ of the positive semidefinite cone.