Papers

We study the cost-minimization prophet inequality problem, in which a decision-maker sequentially observes $n$ independent and identically distributed (IID) random variables. After each observation, the decision-maker must either accept the current realization and stop, or reject it and continue with the next variable. The goal is to minimize the selected value. Unlike the classical maximization setting, if none of the first $n-1$ values is accepted, the final realization must be selected. Esfandiari et al. (SIDMA 2017) showed that this problem does not admit constant-competitive online algorithms in general, which motivates subsequent work on restricted distribution classes, such as entire distributions (Livanos and Mehta, SODA 2024) and distributions with bounded extreme values (Livanos and Mehta, EC 2025). In this work, we focus on distributions with bounded support. For distributions supported on $[1,b]$, we characterize the competitive ratio of online algorithms as a function of both $b$ and $n$. We consider both distribution-aware and distribution-oblivious settings. In the distribution-aware case, we provide a nearly tight characterization of the optimal online algorithm, showing that its competitive ratio is at most $b^{(1-1/n)^n}$ for all $n\geq 2$. More significantly, we design a distribution-oblivious algorithm that achieves the same guarantee, with a sequence of predetermined thresholds that depend only on $b$ and $n$. Furthermore, we extend our analysis to the non-IID setting, where we show that a simple single-threshold algorithm attains an asymptotically optimal competitive ratio of $\Theta(\sqrt{b})$.

Fast Fourier transforms on parallel machines incur two forms of data movement: processor-local transfers through the memory hierarchy and global redistribution between processors. Four-step FFT organizations switch the active transform dimension with one global transpose-like exchange, but this alone does not yield cache-efficient local computation. Cache-oblivious FFTs achieve asymptotically optimal local memory traffic through recursive layout transformations, whose direct materialization can require extra data-rearrangement passes and global exchanges. We present PACO, a fully cache-oblivious parallel FFT framework that reconciles these objectives. PACO executes LocalFFT -> OneGlobalPermutation -> LocalFFT. Its local stages recursively partition both transform and batch dimensions without knowledge of the cache parameters. Rather than materializing the transpose-like layouts induced by this recursion, PACO defers them, showing that they compose into a base-b digit-reversal permutation that is fused with the redistribution already required to change the local transform dimension. The resulting middle stage is a perfectly balanced parallel cache-oblivious digit-reversal permutation in which each source-destination processor pair exchanges exactly $N/p^2$ elements. Under an exact base-b slab decomposition in a hybrid ideal-cache/BSP model, PACO computes an N-point DFT exactly with maximum per-processor work $\Theta((N/p) \log N)$ and maximum per-processor cache complexity $\Theta((N/(pB))(1 + \log_M N))$, using exactly one global redistribution round. PACO returns canonical logical DFT coefficients under a factor-swapped target slab ownership. The single redistribution is necessary under the stated no-replication ownership model, while its communication volume is optimal for the prescribed fused permutation and source-target slab distributions.

This thesis investigates Euclidean-space and $\ell_p$-norm representations of different forms of data, with a focus on efficient algorithms for computing these representations in settings where the amount of data is very large. The applications of such representations are also discussed: they may be used to summarize the data in a more compact form for downstream tasks while preserving its most salient properties; and further, they may also be used to extract insights about the data that may not be apparent in its original form. This thesis presents novel algorithms for computing Euclidean representations in the case where the data comes with linear structure, as well as in the case where the data comes only with metric, or distance structure. In addition, we give algorithms for computing $\ell_p$-norm representations in linear structured cases. The analyses of these algorithms use tools from geometry, probability, and optimization, and these tools are used to illuminate other algorithms for similar problems.

A query-oblivious coreset for a softmax-attention head is a subset of the key-value pairs whose attention output is within $\varepsilon$ of the full one for every query in a ball. Liberty, Andoni and Kleiner proved that unweighted coresets of size $O(\sqrt d e^{\rho+\frac12\log\rho+o(\log\log\rho)}/\varepsilon)$ exist, $\rho$ the query radius times the centred key radius, against a lower bound $\Omega(\sqrt d e^{\rho}/\varepsilon)$, and conjectured that closing the gap needs new techniques. It does not: a spherical lift of both balls into one exponential-kernel instance lets the Bozzai-Rothvoss chaining bound apply, and Chevet's inequality splits key from value dimension, giving coresets of size $O(e^{\rho}(\sqrt{d_v}+\sqrt{d_k\log(1+\rho)})/\varepsilon)$ in randomised polynomial time, the first constructive whole-ball guarantee within $\sqrt{\log(1+\rho)}$ of the lower bound. A sampling cap $O(e^{2\rho}/\varepsilon^{2})$ completes the envelope; in fixed dimension Tai's diameter-free bound removes the logarithm, settling the Gaussian-restriction case of a Bozzai-Rothvoss question for the kernels. We give theLiberty-Andoni-Kleiner lower boud transfer the one-waycommunication bounds of Chen et r is the price of one signing forall queries. A census of every head of Qwen2.5-7B-Instruct and Llama-3-8B-Instruct finds $\rho$ at least 23.877, so everyactor $e^{\rho}/\varepsilon$prescribes a coreset larger than the cache: the algorithmic contribution is asymptotic on these models.

Fixed shipment costs encourage large orders, while inventory and customer backlog costs favor frequent replenishment. In a serial system, the stages must also coordinate their lot sizes and material availability. We study the classical echelon stock $(R,nQ)$ policy: the downstream stage requests a fixed lot, the upstream stage orders an integer multiple of that lot, and transfers contain complete lots. For unit Poisson demand, deterministic lead times, setup and holding costs at both stages, and full backlogging, we prove that the optimized cost in this class is at most $5/3\approx1.667$ of the optimal admissible system cost, uniformly over all nonnegative cost rates, demand rates, and lead times. The guarantee holds even when the selected policy pays a setup charge for every lot while the optimal benchmark pays only once per aggregate shipment. To obtain the guarantee, we use a common inventory calculation that allows independently chosen replenishment frequencies while respecting upstream material availability. We compare its optimized value, an upper bound on the best integer-ratio policy cost, with a novel lower bound on the optimal system cost that combines allocated single-stage costs with the minimum inventory cost when setup costs are zero. We also show that no uniform factor below $(1+\sqrt{3})/2\approx1.366$ is possible for the classical class. Existing numerical experiments place best-found classical policies within $22.7\%$ of an evaluated lower bound across three broad grids. The results quantify both the reliability and the limits of a simple operating rule and explain how shipment consolidation, replenishment timing, and flexibility affect its value.

Interprocedural dominance asks which program points every matched call-and-return execution must pass on its way to a target. An analysis that writes out immediate dominance pays for the transitive reduction of this order, the minimal dominator graph. Measured instances of that graph look near-linear, with edge-to-node ratios around 1.1–1.26~\cite{DeSutter2007}, but no program property is known to force this: it is unclear which structural restrictions imply sparse output, and whether dense output also rules out cheap queries. This paper answers both through calling contexts. A static node stands for the group of its reachable configurations; write $\kappa$ for the largest group size and $\alpha$ for how many nodes have more than one configuration. One context per node keeps the tree with $n-1$ edges. Two already allow $\Theta(n^2)$ cover edges in a sparse, loop-free, recursion-free ICFG with total degree three, constant-size procedures, and logarithmic stack depth, while the reachable configuration graph itself stays linear, so the blowup comes from grouping, not from many configurations. Three keep $\Theta(n^2)$ covers even when the explicit call/return graph is acyclic: all target-reaching runs visit the mandatory procedures in the same order, and extra runs that stop short of any target remove the comparabilities that would otherwise kill the covers. Complementing the lower bounds, $\alpha$ ambiguous nodes admit at most $\min\{\floor{n^2/4},(\alpha+1)(n-1)\}$ cover edges, with $\Omega(\alpha n)$ attainable at stack depth one. And for every ICFG with at most two contexts per node, deleting a context group reduces dominance to dual-failure reachability, giving $O(n)$-word, $O(1)$-query representation after polynomial preprocessing. Explicit cover size, context ambiguity, and query-space cost are three separate quantities.

Horner's rule evaluates a monic degree-$n$ polynomial using $n-1$ multiplications. We show that with rational preprocessing of the coefficients, any such polynomial can be evaluated using only $\lfloor n/2 \rfloor + 1$ multiplications over fields of characteristic zero or of characteristic $p>n$. This resolves the multiplication side of a conjecture of Rabin and Winograd (Comm. Pure Appl. Math 1972), who achieved $n/2 + 2\lceil\log_2 n\rceil$ multiplications and conjectured the logarithmic overhead was necessary. We show that this multiplication count can't be beaten in general, proving that three multiplications do not suffice for degree~$6$. This strengthens the lower bound of Pan (STOC 1978), who proved a tight bound for general, complex preprocessing. In characteristic~2, for every $n>1$ and every finite field of size at least $2n$, we prove that an $n$-multiplication chain cannot parametrize all value vectors at $2n$ distinct evaluation points, even with arbitrary preprocessing. We give $\lfloor n/2 \rfloor + 1$ multiplication schedules over characteristic~2, each with an explicit inverse, for every odd degree $n\le 25$ and conjecture that this is possible for all $n$. We also give an injective polynomial construction for universal hashing that uses $N$ multiplications to hash $2N$ values with a single random key. This improves the best previous construction by Daniel J. Bernstein (cryp.to).

The constructive diagonal Ramsey problem asks, given adjacency-oracle access to an $N$-vertex graph, for a clique or independent set of the order guaranteed by Ramsey's theorem. We give a bounded-error quantum algorithm that, for every $K\ge2$ and $N\ge4^{K-1}$, finds and verifies a homogeneous $K$-set using $O\!\left(2^K K\log\frac K\eta\right)$ edge queries with failure probability at most $\eta$. At the Ramsey scale $N=2^n$, this yields a homogeneous set of order $\lfloor n/2\rfloor+1$ using $O(\sqrt N\log N\log(\log N/\eta))$ queries, improving on the $O(N)$ queries of the explicit classical recursion and giving, to our knowledge, the first sublinear worst-case algorithm for the Ramsey relation. We also derive an $\Omega(N^{1/12})$ quantum lower bound by a reduction from collision finding. The algorithm runs the constructive recursion over implicit candidate sets. Each set is represented by a short conjunction of adjacency constraints and sampled using capped unknown-solution quantum search, and a scale-aware concentration schedule balances estimation accuracy against the increasing cost of sampling deeper sets. We complement the upper bound with an $\Omega(N^{1-1/\sqrt2})$ randomized lower bound, transported from the random-Painter analysis of online Ramsey numbers, which holds on the uniform distribution $G(N,1/2)$. On that distribution a greedy quantum search uses only $\widetilde O(N^{1/4})$ queries, giving a provable polynomial quantum speedup for Ramsey search on random graphs. We also give an estimation-free size-biased recursion and extend it to every fixed number of edge colours.

We present the first polynomial lower bounds for several fundamental problems in the distributed graph sketching model in the tiny-error regime, which includes deterministic algorithms as a special case. In the graph sketching model, every node sends a single message to the referee who does not have any prior knowledge of the graph and must output the answer. While the work of Nelson and Yu (SODA 2019) and Yu (SODA 2021) showed that $\Theta( \log^3n )$ is optimal for constructing a spanning forest or deciding whether the graph is connected with error at most $\frac{1}{\text{poly}(n)}$ , their approach does not yield any stronger bounds for significantly smaller error probabilities. Our main result is to show that solving either connectivity or spanning tree construction with error at most $\delta$ requires messages of length $\Omega( \min\{n, \log_2 \frac{1}{\delta}\}^{1/3} )$, which implies that algorithms with exponentially small error must send messages of $\Omega( n^{1/3} )$ bits in the worst case. Our results significantly narrows the current gap between the Jelani-Yu threshold of $\Theta( \log^3n )$ and the trivial upper bound of sending $O(n)$ bits per node for deterministic graph sketching. We also extend our results to $k$-edge connectivity. For any $k=O(n^{1/7})$, we recover the same bound of $\Omega( k )$ on the message length for algorithms with exponentially small error that was shown by Robinson and Tan (PODS 2026) only for deterministic algorithms. Finally, for $k=n^{o(1)}$, our result implies a stronger lower bound of $\Omega_\epsilon( n^{\epsilon} )$ bits, for any constant $\epsilon<\tfrac{1}{3}$.

We (the author and the AI systems that did the heavy lifting) show that the quantum query complexity of minimizing a convex function over a convex subset of $\mathbb{R}^n$ with evaluation and membership queries is $\tilde\Omega(n)$, nearly matching the best known upper bound. In particular, we show this even for quadratic minimization, which is equivalent to inverting an $n \times n$ real matrix using matrix-vector queries. We also show linear or nearly linear lower bounds on the quantum query complexity of computing the trace, the sign of the determinant, and the magnitude of the determinant of a real matrix in the matrix-vector query model. We use a novel quantum lower bound technique, the determinantal witness method, based on identifying a witness whose Fourier transform vanishes on low-rank matrices and that correlates well with the function being computed.

We give a deterministic algorithm for single-source shortest paths in directed graphs with integral edge weights at least $-W$ that runs in time $$O((m+n\log\log n)\log^2 n \log(nW)).$$ This improves the previous fastest deterministic bound of Li by a factor of $\log n$.

In the uniform sparsest cut problem we are asked to find a vertex set that cuts few edges relative to the number of vertex pairs it separates. The Goemans-Linial SDP coupled with the Arora-Rao-Vazirani rounding gives an $\mathcal{O}(\sqrt{\log n})$ approximation on arbitrary graphs on $n$ vertices. We study this relaxation on finite Abelian Cayley graphs. First we show that when the second normalized Laplacian eigenvalue of $G= \mathrm{Cayley}(\Gamma, S)$ is realized by a Fourier character with image size at most four then $\lambda_2(G)=\mathrm{SDP}_{\mathrm{GL}}(G)=\psi(G)$. Geometrically, a character maps the vertices onto a regular polygon where the squared chord distance satisfies the triangle inequalities exactly when the polygon has at most four vertices. Grouping equal character fibers gives a cyclic quotient where the optimal cut can be found exactly and so the relaxation is exact on finite Abelian Cayley graphs on groups of exponent at most four. Second, we replace each generator $s$ of $S$ by a uniformly random element of its cyclic subgroup (including identity). If $r_s$ is the order of $s$, we let $\alpha(r_s)$ to be the average number of $\pm s$ steps needed to simulate such a move, and let $\rho(S)=\max_{s\in S}\alpha(r_s)$ be its worst case. Full cyclic averaging eliminates character phases and choosing a nontrivial character $\chi^*$ minimizing the auxiliary eigenvalue and taking $K=\mathrm{ker}\chi^*$ gives \[ \psi(G)\leq\psi_G(K)\leq\frac{q^*}{q^*-1} \cdot\rho(S)\cdot\mathrm{SDP}_{\mathrm{GL}}(G)\leq 2\rho(S)\cdot\mathrm{SDP}_{\mathrm{GL}}(G), \] where $q^*=|\chi^*(\Gamma)|$. If all generator orders are at most $R$, this is an $R/2$ approximation. Finally, we construct an infinite family of finite Abelian Cayley graphs with Goemans-Linial integrality gap exactly $16/15$.

Machine unlearning typically aims to emulate retraining from scratch: upon a deletion request, the unlearning algorithm should produce an outcome that would have been obtained had the deleted point never been included. Recent work has shown that this emulation requirement carries no meaningful privacy semantics against an adversary who observes a sequence of releases. Machine unlearning is thus not a privacy question per se, but rather a data maintenance question, which is precisely the subject of retroactive algorithms. These are algorithms supporting modifications of past operations, guaranteeing that all subsequent answers reflect the revised history as if it had always been in force. We put forward a definition of private retroactive algorithms, combining the retroactivity requirement with differential privacy under continual observation. We present constructions achieving both privacy and retroactivity at no asymptotic cost over privacy alone for linear statistics, clustering, and histograms, alongside impossibility results.

The strategic facility location problem is defined as follows: $n$ agents report their location in a metric space, and the objective is to design a mechanism deciding the (possibly randomized) location of a facility such that agents have no incentive to lie about their position. We focus on the egalitarian cost, which means that the goal of the mechanism is to minimize the expected maximal facility-agent distance. Meanwhile, mechanisms must be truthful (or strategyproof): no agent may decrease their expected distance to the facility via lying on their location. Designing truthful mechanisms minimizing the approximation ratio is a well-studied problem, and the optimal solution is known for the real line. We focus in this paper on higher dimension Euclidean spaces, for which gaps remain between the best known lower and upper bounds. We first show that, maybe counter-intuitively, the problem is easier for two agents on the plane rather than on the line: the mechanism can exploit the additional dimension to prevent more efficiently agent lies. Based on this intuition, we devise lower bounds for $\mathbb R^d$ asymptotically matching the best known approximation factor of $2$ for large $d$. We also provide novel mechanism ideas, improving over the best known algorithms on the plane, and when the agents belong to $\mathbb R^d$ but the facility may use an additional dimension.

Online resource-allocation systems, like outpatient scheduling and spectrum allocation, often assign sequentially arriving requests to an ordered pool of scarce resources, where each request accepts a contiguous interval of feasible options. We study the resulting online matching problem on convex bipartite graphs under irrevocable decisions and adversarial arrivals. We first show that convexity alone does not improve the classic worst-case guarantee of 1-1/e, achieved by Ranking. We then consider the uniform-length model, in which every online request has exactly d consecutive offline neighbors. We propose Flip, which uses one random bit to commit ex-ante to either earliest-feasible assignment or latest-feasible assignment. Although either natural deterministic policy can waste capacity and be asymptotically only 1/2-competitive, we show that their randomized mixture is 2/3-competitive. This guarantee is tight for Flip and remains valid against a semi-adaptive adversary that observes the selected policy before choosing the arrival order. We also prove that no randomized online algorithm can achieve a competitive ratio strictly larger than 3/4 in the uniform-length model.

We study linear codes for insertion and deletion (insdel) errors through the lens of evaluation codes. We develop a general framework for analyzing random puncturings of evaluation codes, where the edit distance is controlled by only the size of the evaluation domain and the maximum number of zeros of a nonzero function in the underlying function space. Our proof generalizes the results of Con, Guo, Li, and Zhang (ICALP 2025), and simultaneously simplifies their arguments by avoiding an in-depth analysis of longest common subsequences. We demonstrate the applicability of our core theorem by instantiating it with random puncturings of Reed–Muller codes. We then recover the result that random Reed–Solomon codes approach the half-Singleton bound over linear-sized fields while also improving the dependence on the additive gap $\varepsilon$ from $2^{O(1/\varepsilon^2)}$ to $2^{O(1/\varepsilon)}$. Finally, by applying the framework to algebraic geometry codes arising from asymptotically good towers of function fields, we show that there exist randomized families of structured linear codes over constant-sized fields that approach the half-Singleton bound.

We consider the problem of approximately maximizing a weakly submodular function using the standard greedy algorithm, which is known to give tight approximation results for such functions under a cardinality constraint. We show that this is not the case for general matroid constraints. For any $\gamma < 1$, we give a family of $\gamma$-weakly submodular functions and a simple partition matroid constraint and show that the standard greedy algorithm provides no constant approximation for the resulting constrained maximization problem.

Graphs are a standard representation for data in the social sciences, cybersecurity, computer infrastructure, bioinformatics, and more. Typical real-world graphs are sparse, meaning the average degree is small (in the tens, while the number of vertices is more than millions). When graph data is collected from a source, a major task is to perform data exploration. Thus, any region of “density" is of interest, since it indicates special structure. An important goal is to cover a significant portion of the graph using dense subgraphs. Existing algorithms that find many dense subgraphs do not have overlapping output, and hence provide limited coverage. Other methods that produce overlapping clusters do not generate dense subgraphs. The main goal of this paper is to develop provable and practical methods that can provide overlapping dense subgraphs that can cover large portions of real-world networks. Our contribution is an algorithm CohortRecovery that achieves this goal. We first develop a mathematical framework of triadic cohorts that captures the notion of “detectable dense subgraphs” that potentially overlap. We prove that CohortRecovery can output a set of dense subgraphs, such that each triadic cohort is almost completely contained in some dense subgraph. We give a practical implementation of CohortRecovery and demonstrate it on a variety of datasets. It typically runs in under ten minutes on a commodity machine even on graphs with tens of millions of edges. For numerous datasets, CohortRecovery is able to cover more than 25% of the vertices in non-trivial subgraphs of density more than 0.8, and is significantly better than a wide variety of scalable graph clustering/community detection algorithms. Moreover, we demonstrate that output of CohortRecovery captures ground truth clusters obtained by manual curation.

We study exact single-source shortest paths when the output is only the materialized labeled distance vector ($\mathrm{DIST}$), rather than a distance order. In the full deterministic comparison-addition model, the minimum worst-case number of additions on every fixed directed topology is exactly the maximum number $\rho_{\mathrm{fwd}}$ of forward nonsource endpoint classes over rooted vertex orders; the lower bound permits adaptive control, literals, and arbitrary mixed sums. This arithmetic law aligns with the comparison optimum on DAGs, where the full resource region is an exact rectangle. Cycles destroy that alignment: a two-spoke shared-hub graph has coordinatewise optima $(4,2)$ but requires five comparisons at the two-addition budget. Its $k$-spoke extension forces $k\log_2 k+O(k)$ comparisons at the addition optimum and has an entropy-tight deterministic tradeoff $C_{k+r}^*(H_k)=\Theta(k+\Lambda_{k,r})$, where $\Lambda_{k,r}=\log_2(k!/[r!(r+1)^{k-r}])$, with leading constant one when $\Lambda_{k,r}/k\to\infty$. Because the two coordinatewise minima need not belong to one program, these conflicts lead to the same-program benchmark $\operatorname{OPT}_{\mathrm{DIST}}=\inf_A\sup_w(C_A(w)+P_A(w))$. An exact transcript-cone game yields one uniform interpreter whose charged addition-comparison cost equals $\operatorname{OPT}_{\mathrm{DIST}}$ on every topology; its optimal actions are synthesizable in polynomial space but may require exponential time. Finally, an active-core reduction and the current deterministic directed-SSSP bound give an efficient uniform $O\!\bigl(\operatorname{OPT}_{\mathrm{DIST}}\sqrt{\log(2+\operatorname{OPT}_{\mathrm{DIST}})\log\log(4+\operatorname{OPT}_{\mathrm{DIST}})}\bigr)$ charged-operation bound. Thus optimal numerical policies exist uniformly, while efficient constant-competitive navigation remains open.

Learning-augmented algorithms use fallible predictions while retaining formal performance guarantees. This survey synthesizes prediction interfaces, error measures, consistency–robustness trade-offs, and five representative construction mechanisms across online optimization, caching, learned data structures, graph problems, and mechanism design. An orthogonal theorem-level axis distinguishes achieved upper bounds from matched asymptotic dependence. Formal guarantees are separated from empirical systems evidence, with explicit treatment of prediction cost, feedback, and composition. The resulting synthesis states sufficient conditions for limited end-to-end reasoning and delineates open problems in cost-aware prediction, endogenous error, semantic predictors, and benchmarking.

Karger's elegant random contraction algorithm for finding a global mincut in a graph has been highly influential. More recent work has obtained several different (nonuniform) random contraction algorithms for mincut in hypergraphs and hedgegraphs. Motivated by the conceptual goal of understanding these algorithms in a unified fashion, we study random contraction algorithms for finding a minimum quotient of a polymatroid. We introduce the notion of quotient-bounded polymatroids and show that several existing results can be derived and understood under a common algorithmic framework for quotient-bounded polymatroids.

In this paper, we study several statistical problems on similarity graphs in the node-arrival streaming model, including degree moments, diversity index, degree-moment sampling, and diversity sampling. We develop constant-pass, sublinear-space streaming algorithms for these problems and establish space lower bounds that nearly match the upper bounds in their dependence on the stream length.

We consider the Feedback Vertex Set problem (FVS): the input is an undirected graph $G=(V,E)$ and the goal is to find a minimum-cardinality (or a min-cost in the weighted case) subset $S \subseteq V$ of vertices such that $G-S$ has no cycles. A $2$-approximation via the local-ratio method was developed in the mid 90's by Bafna, Berman and Fujito (1995) and by Becker and Geiger (1996), and this approximation ratio is tight under UGC. The local-ratio algorithms were later interpreted as primal-dual algorithms via an LP relaxation by Chudak, Goemans, Hochbaum, and Williamson (1998). All known $2$-approximation algorithms for FVS have been via local-ratio and primal-dual methods, and in a quest to obtain a new LP rounding algorithm, it was conjectured (Fiorini 2021) that the Strong-Density polyhedron developed by Chudak, Goemans, Hochbaum, and Williamson has an extreme point property: every basic feasible solution to the LP has a variable with value at least $1/2$. We prove this conjecture. We also consider a related Strong-Edge-Density polyhedron and show the same extreme point property. The advantage of this polyhedron is that it admits a polynomial-time separation oracle and also a compact extended formulation. These results lead to polynomial-time iterative rounding $2$-approximation algorithms. The proof of the extreme point property is of independent technical interest and key ideas in the proof were suggested by AI tools.

We study the multiobjective hypergraph min-cut problem: Given a hypergraph $H=(V,E)$ and $k$ cost functions $c_1, c_2, \ldots, c_k:E\to\mathbb{Z}_{\ge 0}$, the goal is to find a non-empty proper subset $U\subsetneq V$ of vertices with minimum $\max_{i\in [k]} c_i(\delta(U))$. When $k$ is part of input, the problem is NP-hard (even in graphs). We focus on fixed-constant $k$ setting (e.g., $k=1, 2, 3, \ldots$). Single-objective hypergraph min-cut as well as multiobjective graph min-cut for a constant number of objectives admit polynomial-time algorithms. In contrast to these special cases, the complexity of multiobjective hypergraph min-cut remains open even for $k=2$. Known techniques fail to extend due to structural differences between graphs and hypergraphs. For $k$-objective hypergraph min-cut when $k$ is a fixed constant, we design a randomized PTAS, and two different randomized quasi-polynomial time algorithms. As an application of our $2$-objective hypergraph min-cut results, we obtain a quasi-polynomial time approximation scheme (QPTAS) for hypergraph connectivity interdiction. AI tools were used to iterate and refine the algorithmic ideas underlying this work.

The $\ell_p$-Lewis weights of a matrix are defined by a fixed-point equation. For $p<4$, Cohen and Peng [CP15] showed that iterating an equivalent rearrangement of this equation computes Lewis weights to high precision; for $p\geq4$, prior high-precision methods instead use optimization-based approaches. We show that the direct Lewis fixed-point iteration, appearing in the thesis of Lee [Lee16], computes Lewis weights to high precision for every $p>2$. For a matrix $\mathbf{A}\in\mathbb{R}^{m\times n}$ partitioned into row blocks $\mathbf{A}_{[1]},\ldots,\mathbf{A}_{[k]}$, we compute, for $p>2$, coordinatewise $\varepsilon$-approximate $\ell_p$ block Lewis weights in $O\left(p\log\frac{p\sqrt{\sum_{i=1}^k\operatorname{rank}(\mathbf{A}_{[i]})}}{\varepsilon}\right)$ rounds of exact leverage-score-vector computations. For ordinary Lewis weights, this becomes $O\left(p\log\frac{p\sqrt{m}}{\varepsilon}\right)$, improving the $O\left(p^2\log(m/\varepsilon)\right)$ bound of Gribling, Sidford, and Zhang [GSZ26] for $p\geq4$. Our main observation is that each direct Lewis update contracts the KL divergence to the true weights by a factor of $1-\frac{2}{p}$. We also give an alternate explanation of this contraction through volume sampling and entropic independence. Synthetic experiments closely match our predicted local contraction rates and iteration counts grow approximately linearly with $p$; real-data experiments illustrate the information-concentration tradeoff of finite-$p$ block Lewis designs.

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 $\epsilon$ 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.

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<\gamma<1/2$ and $0<\theta\leq1$, the first approximates $\mathrm{haf}(A)$ for a symmetric matrix $A$ when its support graph $G$ has minimum degree at least $(1/2+\gamma)n$ and its nonzero entries lie in $[\theta,1]$. It also approximates permanents under the analogous bipartite condition, including full-support matrices in $[\theta,1]$. For fixed $\beta>0$ and $0<\kappa\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\beta/n$ and $\lambda_{\max}(J)\leq1-\kappa$. No separate lower-eigenvalue condition is imposed. We further prove $\log\mathrm{haf}(A)=h_A(G)-n/2+O_{\gamma,\theta}(1)$ and $Z(J)=2^n\det(I-J)^{-1/2}(1+O_{\beta,\kappa}(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_\gamma(1)$ on the fixed-margin class and extends it to weights in $[\theta,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/\epsilon))$ and hence polynomial enumeration.

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.

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.

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 $\Omega(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 $\Omega(k)$ and $\Omega(\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.