2025-05-20 | | Total: 2
The problem of counting subgraphs or graphlets under local differential privacy is an important challenge that has attracted significant attention from researchers. However, much of the existing work focuses on small graphlets like triangles or $k$-stars. In this paper, we propose a non-interactive, locally differentially private algorithm capable of counting graphlets of any size $k$. When $n$ is the number of nodes in the input graph, we show that the expected $\ell_2$ error of our algorithm is $O(n^{k - 1})$. Additionally, we prove that there exists a class of input graphs and graphlets of size $k$ for which any non-interactive counting algorithm incurs an expected $\ell_2$ error of $\Omega(n^{k - 1})$, demonstrating the optimality of our result. Furthermore, we establish that for certain input graphs and graphlets, any locally differentially private algorithm must have an expected $\ell_2$ error of $\Omega(n^{k - 1.5})$. Our experimental results show that our algorithm is more accurate than the classical randomized response method.
In this paper, we give a quadratic Goldreich-Levin algorithm that is close to optimal in the following ways. Given a bounded function $f$ on the Boolean hypercube $\mathbb{F}_2^n$ and any $\varepsilon>0$, the algorithm returns a quadratic polynomial $q: \mathbb{F}_2^n \to \mathbb{F}_2$ so that the correlation of $f$ with the function $(-1)^q$ is within an additive $\varepsilon$ of the maximum possible correlation with a quadratic phase function. The algorithm runs in $O_\varepsilon(n^3)$ time and makes $O_\varepsilon(n^2\log n)$ queries to $f$, which matches the information-theoretic lower bound of $\Omega(n^2)$ queries up to a logarithmic factor. As a result, we obtain a number of corollaries: - A near-optimal self-corrector of quadratic Reed-Muller codes, which makes $O_\varepsilon(n^2\log n)$ queries to a Boolean function $f$ and returns a quadratic polynomial $q$ whose relative Hamming distance to $f$ is within $\varepsilon$ of the minimum distance. - An algorithmic polynomial inverse theorem for the order-3 Gowers uniformity norm. - An algorithm that makes a polynomial number of queries to a bounded function $f$ and decomposes $f$ as a sum of poly$(1/\varepsilon)$ quadratic phase functions and error terms of order $\varepsilon$. Our algorithm is obtained using ideas from recent work on quantum learning theory. Its construction deviates from previous approaches based on algorithmic proofs of the inverse theorem for the order-3 uniformity norm (and in particular does not rely on the recent resolution of the polynomial Fre\uıman-Ruzsa conjecture).