{"id":"arxiv/2609.33704","url":"https://arxiv.org/abs/2609.33704","tags":["cs.IT","cs.LG","math.PR"],"score":0,"title":"Non-Adaptive Learning of Sparse Erdős--Rényi Graphs via Affine Splitting","domain":"cs.IT","source":"arxiv","authors":["Hoang Ta"],"reviews":0,"subject":"cs.IT","summary":"Graph learning from edge-detecting queries concerns the reconstruction of an unknown edge set on a known vertex set. Each query reports whether a specified vertex subset contains at least one edge. We study non-adaptive schemes, in which all queries are fixed before any outcomes are observed, with the goal of achieving exact recovery using few queries and fast decoding. For general graphs on $n$ vertices with at most $k$ edges, non-adaptive recovery requires $Ω(\\min\\{k^2\\log n,n^2\\})$ queries in the worst case, even when a small error probability is allowed. In this paper, we consider…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-27","reactions":{}}