Establishes sharp low-degree estimation thresholds in planted hypergraphs and tensor PCA, resolving open hardness questions and yielding polynomial-time algorithms above thresholds.
A note on Pr\"ufer-like coding and counting forests of uniform hypertrees
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
This note presents an encoding and a decoding algorithms for a forest of (labelled) rooted uniform hypertrees and hypercycles in linear time, by using as few as $n - 2$ integers in the range $[1,n]$. It is a simple extension of the classical Pr\"{u}fer code for (labelled) rooted trees to an encoding for forests of (labelled) rooted uniform hypertrees and hypercycles, which allows to count them up according to their number of vertices, hyperedges and hypertrees. In passing, we also find Cayley's formula for the number of (labelled) rooted trees as well as its generalisation to the number of hypercycles found by Selivanov in the early 70's.
fields
math.ST 1years
2026 1verdicts
UNVERDICTED 1representative citing papers
citing papers explorer
-
Low-degree estimation thresholds in planted hypergraphs and tensor PCA
Establishes sharp low-degree estimation thresholds in planted hypergraphs and tensor PCA, resolving open hardness questions and yielding polynomial-time algorithms above thresholds.