{"ID":2874980,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.03215","arxiv_id":"2509.03215","title":"Triangle Detection in Worst-Case Sparse Graphs via Local Sketching","abstract":"We present a non-algebraic, locality-preserving framework for triangle detection in worst-case sparse graphs. Our algorithm processes the graph in $O(\\log n)$ independent layers and partitions incident edges into prefix-based classes where each class maintains a 1-sparse triple over a prime field. Potential witnesses are surfaced by pair-key (PK) alignment, and every candidate is verified by a three-stage, zero-false-positive pipeline: a class-level 1-sparse consistency check, two slot-level decodings, and a final adjacency confirmation. \\textbf{To obtain single-run high-probability coverage, we further instantiate $R=c_G\\log n$ independent PK groups per class (each probing a constant number of complementary buckets), which amplifies the per-layer hit rate from $Θ(1/\\log n)$ to $1-n^{-Ω(1)}$ without changing the accounting.} A one-shot pairing discipline and class-term triggering yield a per-(layer,level) accounting bound of $O(m)$, while keep-coin concentration ensures that each vertex retains only $O(d^+(x))$ keys with high probability. Consequently, the total running time is $O(m\\log^2 n)$ and the peak space is $O(m\\log n)$, both with high probability. The algorithm emits a succinct Seeds+Logs artifact that enables a third party to replay all necessary checks and certify a NO-instance in $\\tilde O(m\\log n)$ time. We also prove a $Θ(1/\\log n)$ hit-rate lower bound for any single PK family under a constant-probe local model (via Yao)--motivating the use of $Θ(\\log n)$ independent groups--and discuss why global algebraic convolutions would break near-linear accounting or run into fine-grained barriers. We outline measured paths toward Las Vegas $O(m\\log n)$ and deterministic near-linear variants.","short_abstract":"We present a non-algebraic, locality-preserving framework for triangle detection in worst-case sparse graphs. Our algorithm processes the graph in $O(\\log n)$ independent layers and partitions incident edges into prefix-based classes where each class maintains a 1-sparse triple over a prime field. Potential witnesses a...","url_abs":"https://arxiv.org/abs/2509.03215","url_pdf":"https://arxiv.org/pdf/2509.03215v1","authors":"[\"Hongyi Duan\",\"Jian'an Zhang\"]","published":"2025-09-03T11:07:35Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.CG\"]","methods":"[]","has_code":false}