{"ID":2851799,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.19725","arxiv_id":"2510.19725","title":"CommonSense: Efficient Set Intersection (SetX) Protocol Based on Compressed Sensing","abstract":"In the set reconciliation (\\textsf{SetR}) problem, two parties Alice and Bob, holding sets $\\mathsf{A}$ and $\\mathsf{B}$, communicate to learn the symmetric difference $\\mathsf{A} Δ\\mathsf{B}$. In this work, we study a related but under-explored problem: set intersection (\\textsf{SetX})~\\cite{Ozisik2019}, where both parties learn $\\mathsf{A} \\cap \\mathsf{B}$ instead. However, existing solutions typically reuse \\textsf{SetR} protocols due to the absence of dedicated \\textsf{SetX} protocols and the misconception that \\textsf{SetR} and \\textsf{SetX} have comparable costs. Observing that \\textsf{SetX} is fundamentally cheaper than \\textsf{SetR}, we developed a multi-round \\textsf{SetX} protocol that outperforms the information-theoretic lower bound of \\textsf{SetR} problem. In our \\textsf{SetX} protocol, Alice sends Bob a compressed sensing (CS) sketch of $\\mathsf{A}$ to help Bob identify his unique elements (those in $\\mathsf{B \\setminus A}$). This solves the \\textsf{SetX} problem, if $\\mathsf{A} \\subseteq \\mathsf{B}$. Otherwise, Bob sends a CS sketch of the residue (a set of elements he cannot decode) back to Alice for her to decode her unique elements (those in $\\mathsf{A \\setminus B}$). As such, Alice and Bob communicate back and forth %with a set membership filter (SMF) of estimated $\\mathsf{B \\setminus A}$. Alice updates $\\mathsf{A}$ and communication repeats until both parties agrees on $\\mathsf{A} \\cap \\mathsf{B}$. On real world datasets, experiments show that our $\\mathsf{SetX}$ protocol reduces the communication cost by 8 to 10 times compared to the IBLT-based $\\mathsf{SetR}$ protocol.","short_abstract":"In the set reconciliation (\\textsf{SetR}) problem, two parties Alice and Bob, holding sets $\\mathsf{A}$ and $\\mathsf{B}$, communicate to learn the symmetric difference $\\mathsf{A} Δ\\mathsf{B}$. In this work, we study a related but under-explored problem: set intersection (\\textsf{SetX})~\\cite{Ozisik2019}, where both pa...","url_abs":"https://arxiv.org/abs/2510.19725","url_pdf":"https://arxiv.org/pdf/2510.19725v1","authors":"[\"Jingfan Meng\",\"Tianji Yang\",\"Jun Xu\"]","published":"2025-10-22T16:08:39Z","proceeding":"cs.DC","tasks":"[\"cs.DC\",\"cs.NI\"]","methods":"[]","has_code":false}