Showing 2026Show all
3 papers · 1 filter
cs.DS2026
The Power of Interaction in Locally Edge-Private Subgraph Counting
Xian Chen, Pan Peng
We study (non-induced) subgraph counting under interactive local edge differential privacy (LEDP). Given a fixed pattern graph with vertices, edges, and conn…
cs.DS2026
Testing for a Large Induced Expander: Sublinear Algorithms and Query Lower Bounds
Pan Peng, Ranran Shen
Testing expansion asks to distinguish graphs of large conductance from graphs that are far from having large conductance. We study a relaxation in which only part of the graph is r…
cs.DS2026
Differentially Private Range Subgraph Counting
Xian Chen, Ruobing Bai, Pan Peng
Subgraph counting is a fundamental problem in graph analysis. Motivated by practical scenarios where graph analytics are performed on subgraphs induced by selected vertices -- rath…