Papers

Motivated by recent work of Kocurek, Oveis Gharan, and Tjowasi, which gives an efficient sampling algorithm for the hard-core model on random regular bipartite graphs by decomposing into fixed-size slices, we study the worst-case tractability of approximate counting and sampling of fixed-size slices for bipartite independent set problems. Let $G=(L\sqcup R,E)$ be a bipartite graph with $|L|=|R|=n$ and maximum degree $\Delta$. The fixed-slice problem asks to sample uniformly from independent sets satisfying $|I\cap L|=\alpha_L n$ and $|I\cap R|=\alpha_R n$. We show that if the overall density $\alpha$ lies in the interval $(\frac{1}{\Delta}, \tfrac{1}{2})$, and the densities on the two sides are more balanced than the typical phase densities of a random $\Delta$-regular bipartite graph, then there is no FPRAS or efficient sampling scheme unless $\mathbf{NP}=\mathbf{RP}$. We then study a related fugacity model in which the densities are not fixed, but the independent set is required to be balanced between the two sides of the bipartition. For $\lambda>0$, the balanced hard-core model is the ordinary hard-core model with fugacity $\lambda$, conditioned on the event $|I\cap L|=|I\cap R|$. We prove that this model has the same computational threshold as the hard-core model on general bounded-degree graphs. That is, for every fixed $\Delta\ge 3$, if $\lambda<\lambda_c(\Delta)$, then the balanced partition function admits an FPTAS and the balanced hard-core distribution admits an efficient sampling scheme. Conversely, if $\lambda>\lambda_c(\Delta)$, then no FPRAS or efficient sampler exists on this graph class unless $\mathbf{NP}=\mathbf{RP}$.

We present randomized algorithms for the shortest vector problem (SVP). For the $n$-dimensional lattice $\mathcal L$, our algorithms solve SVP in time $2^{0.6039n+o(n)}$ classically and $2^{0.5411n+o(n)}$ quantumly and space $2^{0.5n+o(n)}$, improving the previous best algorithm running in $2^{n+o(n)}$ time and space of Aggarwal, Dadush, Regev, and Stephens-Davidowitz [STOC'15]. Our algorithms heavily use the property of the Hessian of the periodic Gaussian function at the half shortest vector: For a shortest vector $v \in \mathcal L$, the Hessian at $v/2$ has the eigenvector close to $v$, which can be used to recover $v$ using the (preprocessing) bounded distance decoding algorithm. Given the periodicity modulo $\mathcal L$, the candidate midpoints are indexed by the parity classes in $\mathcal L/2\mathcal L$. Our algorithm searches for the class of a shortest vector by estimating the corresponding Hessians using discrete Gaussian samples. We optimize the algorithm using random sublattice cosets and various sampling technique, achieving the final complexity. The optimization techniques may be of independent interest.

We give a sublinear algorithm for the planted $k$-coloring problem. Given an expander $G$ with a planted coloring, the goal is to efficiently determine the color class of a given vertex. We work in the adversarial planted coloring model of David and Feige [STOC 2016], where an adversary chooses a $d$-regular spectral $\lambda$-expander $G$ on $n$ vertices and plants a balanced $k$-coloring by partitioning the vertices into $k$ equal parts and deleting all edges within each part. This model generalizes the earlier random graph models studied by Blum and Spencer [J. Algorithms 1995] and Alon and Kahale [STOC 1994]. We give the first sublinear-time algorithm for recovering planted colorings in this model. The algorithm has preprocessing time and space $\widetilde O\left(n^{1/2+O(1/\log(d/\lambda))}\right)$, and produces a data structure that answers color queries in time $\widetilde O\left(n^{1/2+O(1/\log(d/\lambda))}\right)$, such that the resulting labeling agrees with the planted coloring on all but an $O(\sqrt{\lambda /d})$ fraction of vertices, up to a permutation of the $k$ colors. The algorithm gives sublinear-time inner product access to the bottom eigenspace of the normalized adjacency matrix, which allows us to adapt the classical spectral approach of Alon and Kahale in sublinear time.

The celebrated $k$-means++ algorithm of Arthur and Vassilvitskii (SODA 2007) achieves an $O(\log k)$ expected approximation for the classical $k$-means problem using $D^2$-sampling, a technique now ubiquitous in clustering algorithm design. Bhattacharya et al. (ESA 2020) introduced $\varepsilon$-noisy $k$-means++, where sampling probabilities may incur an adversarial multiplicative error of $(1\pm\varepsilon)$, but obtained only an $O(\log^2 k)$ guarantee. Grunau et al. (ESA 2023) recovered the asymptotic $O(\log k)$ guarantee, but their analysis loses a constant factor of roughly $147{,}638$ even as $\varepsilon\to0$, leaving open whether $k$-means++ is highly sensitive to even a small amount of noise. They asked whether a bound within $1+O(\varepsilon)$ of the classical guarantee is possible. We resolve this affirmatively, proving an expected approximation guarantee of $8(\ln k+2)\left(\frac{1+\varepsilon}{1-\varepsilon}\right)^4 = (1+O(\varepsilon))\,8(\ln k+2)$. We complement the upper bound with two separations. First, a noisy version of the Arthur and Vassilvitskii lower-bound instance incurs a $1+\Omega(\varepsilon)$ loss over exact $k$-means++, so linear dependence on the noise is necessary. Second, pointwise multiplicative control is qualitatively essential: replacing it with per-round total variation closeness admits no finite approximation guarantee, even for $k=2$.

Temporal networks model dynamic systems in which edges represent interactions and labels specify when these interactions occur. Examples include transportation networks, time-sensitive communication networks, and industrial control systems. In many such applications, an existing temporal network must be transformed into a desired one through a sequence of atomic modifications while maintaining essential functionality throughout the transformation. We formalize the time label reconfiguration problem and provide a theoretical framework for reasoning about such transformation processes. As temporal reachability is a central functionality in many temporal networks, we study a reconfiguration problem on directed temporal graphs subject to temporal reachability constraints. We are given a static graph with a designated set of sources, along with two labeling functions indicating an availability time for every edge. The goal is to transform one labeling into the other by changing the label of a single edge at a time while maintaining temporal reachability of the sources throughout. Our results reveal a sharp complexity transition: the problem is polynomial-time solvable for a single source but becomes PSPACE-hard with two sources. We also show that if the static graph is acyclic or an almost-tournament graph, then all valid labelings can be reconfigured into each other. Our proofs are constructive and yield polynomial-time algorithms.

We study the round complexity of learning a hidden partition $\mathcal{P}$ of an $n$-element universe using PAIR queries: PAIR($x,y$) tells us whether $x$ and $y$ belong to the same part of the partition or not. While it is easy to learn using $n|\mathcal{P}|$ queries using a basic algorithm and this query complexity is optimal, this basic algorithm is highly sequential. Black, Mazumdar, and Saha [COLT 2025] recently gave tight deterministic round/query tradeoffs when the number of parts of $\mathcal{P}$ is known. In particular they prove $\Theta(\log\log n)$ rounds are sufficient and necessary to limit the number of queries to $n|\mathcal{P}|$. They leave proving a randomized lower bound as an open direction. We show that randomization dramatically changes the picture. When the number of parts $k = |\mathcal{P}|$ is known, we give a simple 3-round randomized algorithm using $O(nk\log n)$ queries with high probability, and prove that 2 rounds require $\Omega(n^{4/3}k^{2/3})$ queries – the same as deterministic algorithms. We also study a more general setting where the number of parts is unknown. In this case, we give a 4-round randomized algorithm using $O(n|\mathcal P|\log^2 n)$ queries with high probability, and prove that 3-rounds cannot achieve near-optimal query complexity. Furthermore, we show an even bigger separation in this regime between randomized and deterministic algorithms: for the latter, $\Theta(\log n/\log\log n)$ rounds are necessary and sufficient to obtain near-optimal query complexity.

The Transversal Hypergraph problem is to enumerate (list) all inclusion-wise minimal hitting sets of a given hypergraph $\mathcal{H}$. It is the most important open question in enumeration whether this problem admits an output-polynomial algorithm whose running time scales polynomially with the size of $\mathcal{H}$ and the number of solutions. Currently, Minimal-to-Maximal Conversion Search (MMCS) by Murakami and Uno [DAM 2014] is the most efficient algorithm for real-world instances, but there are no worst-case performance guarantees known for it. We prove that MMCS is in fact not output-polynomial. The lower bound construction motivates a more detailed analysis of how certain heuristic choices in the algorithm design affect the running time. We conduct a thorough analysis of those heuristics and, based on this, propose new extension. We then show in extensive running time experiments that this new heuristic further improves practical performance.

We study the trace distance \[D_{\mathrm{tr}}(\rho,\sigma) =\frac12\|\rho-\sigma\|_1, \rho=\bigotimes_{i=1}^n\rho_i,\quad \sigma=\bigotimes_{i=1}^n\sigma_i, \] when the two exponentially large states are specified by their local factors. We give a deterministic approximation within a universal constant factor for rational product inputs. Its running time is polynomial in the number of factors, the local dimension, and the input bit length. In the opposite direction, exact computation is $\#\mathsf P$-hard even for diagonal qubit states, by the corresponding hardness of total variation distance between product distributions. The proof uses local Uhlmann-optimal purifications to reduce the problem to estimating the product-fidelity defect and the trace norm of a structured first-order operator. Although this operator acts on an exponentially large space, we approximate its trace norm by a local convex surrogate that admits a polynomial-size classical conic formulation. A square-function estimate shows that the surrogate upper-bounds this trace norm. Conversely, duality and local dephasing reduce the reverse comparison to a head–tail inequality for independent centered random variables, showing that the surrogate is at most a dimension-free constant times the same norm.

Competitive analysis is central to the study of online algorithms, but upper bounds are often highly problem-specific. We develop a more unifying methodology via the minimax viewpoint. Guided by Yao's principle, we reduce worst-case competitive analysis to Bayesian online design under an arbitrary correlated prior over arrival sequences. For such a prior, let $X^*$ be the hindsight-optimal fractional solution for the realized instance, and let $X^{(t)}=\mathbb E[X^*\mid \mathcal F_t]$ be its posterior process. Our guiding rule is posterior matching: at each time $t$, choose the feasible online action that tracks the current posterior $X^{(t)}$ as closely as the online constraints permit. We show that this single principle yields optimal or near-optimal guarantees for several classical online fractional problems, including set cover, load balancing, matching and more general resource-allocation problems, recovering or improving state-of-the-art bounds in these settings with norm/concave objectives. Via known rounding reductions, it also yields randomized integral guarantees for weighted paging, MTS on star metrics, and ski-rental. At a technical level, our analysis reduces competitive guarantees to key probabilistic inequalities for the vector martingales generated by the posterior of the offline optimum. The resulting framework gives a reusable route from Bayesian online design under arbitrary correlated priors to information-theoretic worst-case competitive guarantees.