Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2604.27651 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of Contents:
- For a connected weighted hypergraph, we give a randomized almost-linear-time solver for the Poisson problem for the cut-based hypergraph Laplacian in the natural input size $P=\sum_{e\in E}|e|$, the sum of hyperedge sizes. For every fixed constant $C>0$, our randomized algorithm runs in $P^{1+o(1)}$ time and, with high probability over its internal randomness, returns a primal point and a dual certificate, with additive optimality gap at most $\exp(-\log^C P)$. A key step is to rewrite the Fenchel dual as a convex-flow problem on an auxiliary $O(P)$-arc graph, yielding a near-optimal dual flow. The main difficulty is primal recovery, because this flow does not by itself determine a primal potential. Our main new ingredient is a recovery theorem showing that, for primal recovery, the detailed routing of the dual flow inside each hyperedge gadget can be discarded: one nonnegative scalar per hyperedge is enough. After the necessary finite-precision rounding, these scalars define a linear-cost min-cost-flow instance on the auxiliary graph, and solving it exactly recovers a primal potential. Finally, a ground-vertex reduction from regularized objectives to the Poisson solver gives randomized almost-linear-time resolvent/proximal primitives for the same cut-based hypergraph Laplacian.