Marek Eliáš, Gautam Kamath, Janardhan Kulkarni, George Z. Li, Jingcheng Liu, Sepideh Mahabadi, Pan Peng, Jakub Tarnawski 等 10 位作者
We give a polynomial-time $(\varepsilon, δ)$-edge-differentially private algorithm that releases a synthetic graph approximately preserving all cut values of a nonnegative weighted input graph $G$. Our algorithm outputs a nonnegative weighted graph $H$ such that, with probability at least $1-β$, simultaneously for all $S\subseteq V$, \[ \left|w_G(S,V\setminus S)-w_H(S,V\setminus S)\right| \leq γw_G(S,V\setminus S) + O\left(\frac{n}{γ\varepsilon} \log^7 \frac{n}{δβγ\varepsilon}\right). \] For fixed $γ, \varepsilon$ and $δ= β= n^{-10}$, the additive error is $n \operatorname{polylog} n$, improving upon the previous efficient bound of $n^{13/12 + o(1)}$. Furthermore, we establish an $Ω(n/γ\varepsilon)$ lower bound for the relevant parameter regime, showing that our result is tight up to polylogarithmic factors. Our algorithm uses a log-det-regularized SDP to generate fractional queries for multiplicative-weights updates and certify accuracy for all cuts. The privacy analysis charges privacy loss only fractionally per mechanism call, based on the amount of mass on edge coordinates retired from subsequent iterations. Our synthetic graph release yields improved error bounds for several downstream tasks in private graph analysis including correlation clustering, Max-Cut, Max-$k$-Cut, constrained cut problems and hierarchical clustering. Most notably, for unweighted complete-graph correlation clustering, we achieve the optimal $\widetilde O(n)$ additive error while reducing the best previously known approximation ratio for this additive error from several thousand to $1.387$. We also provide a formalization of our results in Lean.
We study (non-induced) subgraph counting under interactive local edge differential privacy (LEDP). Given a fixed pattern graph $H$ with $k$ vertices, $\ell\ge1$ edges, and $q$ connected components, our goal is to approximately count its copies in an arbitrary $n$-vertex undirected graph while preserving edge privacy. We give two complementary accuracy guarantees. First, for every $H$, we give Linear Noise Cancellation (LNC), a two-round $\varepsilon$-LEDP algorithm with additive error and root mean square error both $O(n^{k-3/2}/\varepsilon^\ell)$ on every $n$-vertex graph. For fixed sufficiently small $\varepsilon$, this improves the optimal noninteractive additive error for triangles by a factor of $\sqrt n$ and gives the same improvement in worst-case root mean square error for all cliques on at least three vertices. To our knowledge, this is the first separation between interactive and noninteractive LEDP subgraph counting, showing that a single additional round can improve worst-case accuracy polynomially. Second, we determine how accuracy improves when the graph has maximum degree at most a public bound $d$. Our Predict and Correct (PC) framework gives an $(\ell+2)$-round $\varepsilon$-LEDP algorithm with additive error $O(n^{q-1/2}d^{k-q-1}\log^{3\ell-2}n/\varepsilon^\ell)$. For connected patterns, its polynomial factor is $\sqrt n\,d^{k-2}$, giving sublinear error on constant-degree graphs at fixed privacy. We prove matching lower bounds in $n$ and $d$, up to logarithmic factors at fixed privacy, even under arbitrary interaction and approximate privacy with sufficiently small $δ$. At $d=Θ(n)$, the lower bound also establishes the optimality of LNC's dependence on $n$.
We study testing acyclicity of directed graphs in the bounded-degree incidence-lists model, where a tester can query the outneighbors of a vertex but not its inneighbors. Despite significant effort, no tester with $o(n)$ queries is known, while the best established lower bounds are $\widetildeΩ(n^{5/9})$ for one-sided testers (Chen, Randolph, Servedio, and Sun, 2022) and $Ω(n^{1/3})$ for two-sided testers (Bender and Ron, 2002). We show that a query exponent arbitrarily close to one is necessary: for every fixed $η\in(0,1)$, there exists a constant $\varepsilon_η>0$ such that, for every constant $d\ge2$, every randomized adaptive two-sided $\varepsilon_η$-tester for acyclicity of simple $n$-vertex directed graphs whose indegrees and outdegrees are at most $d$ makes $Ω(n^{1-η})$ queries. Our proof overcomes two barriers. First, in previous constructions, the acyclic part of the graph is easy to recognize, which helps an algorithm stay inside the cyclic part. We hide a high-girth cyclic core inside a hierarchy of acyclic masking regions, in which each region imitates the levels below it and can be told apart from them only through rare events, and an iterated information-theoretic argument shows that every exploration observes only small, low-diameter forest components of the core. Second, a two-sided tester may exploit the statistics of collisions without ever seeing a cycle, and at a near-linear budget collisions are unavoidable. We compare complete transcripts with those of an acyclic input built on a fixed core by counting injective embeddings of the observed forest: in high-girth cores, all connected collision patterns of bounded order contribute identically, which makes the two transcript distributions statistically indistinguishable.
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 required to expand: does an $n$-vertex graph of bounded degree contain an induced expander on a constant fraction of its vertices, when the rest of the graph, including the edges leaving the expander, is arbitrary? Let $P_{α,φ}$ denote the property of containing an induced subgraph on at least $αn$ vertices with inner conductance at least $φ$. For every constant $κ\in(0,1)$, we give a tester that accepts graphs in $P_{α,φ}$ and rejects graphs outside $P_{κα,μφ^2}$, where $μ=Θ_{α,κ}(1/\log n)$, using $O_{α,κ}(\sqrt n\,φ^{-2}\log n)$ queries. For fixed $α\in(0,1]$, $κ\in(0,1)$, and $0<φ\le9/20$, we further show that distinguishing these two classes requires $Ω_{α,κ,φ}(n^{1/2+c_{κ,φ}μ})$ queries for every sufficiently large $n$ and every $0<μ\le1$, where $c_{κ,φ}>0$. The bound holds for adaptive algorithms, uniformly in $μ$. Hence, for testers with $\sqrt n\,\mathrm{polylog}(n)$ queries, the logarithmic loss in conductance is necessary up to a $\log\log n$ factor. The same tester also permits distance-based rejection at a weaker conductance while retaining the original core size. Our tester compares the endpoint distributions of random walks from different vertices with each other, rather than with the uniform distribution. Its analysis uses the trace chain, which observes the walk only at its visits to the unknown expanding core. Our lower bound builds on the noisy-parity construction of [CKK+18], using vector-valued parity labels in $\mathbb F_2^r$ to create many hidden classes, each too small to contain a qualifying induced expander.
We establish tight lower bounds on the adaptive and non-adaptive quantum query complexities of Promised $k$-to-one Finding on an exactly $k$-to-one input string $x\in\mathbb Z_q^n$, for every fixed $k\ge2$ and every feasible alphabet size $q\ge n/k$. The lower bounds are $Ω_k(n^{1/2-1/(2(2^k-1))})$ for unrestricted adaptive algorithms and $Ω_k(n^{1-1/k})$ for one-round non-adaptive algorithms. The former matches the adaptive quantum algorithm of Liu and Zhandry [LZ19], whereas the latter matches classical birthday sampling even when the parallel queries are arbitrarily entangled. We also establish the non-adaptive lower bound $Ω_k(\sqrt{n/k})$ for $k$-to-one Testing when $q\ge n$, resolving an open question posed by Koiran, Landes, Portier, and Yao [KLPY10]. Our proofs generate the balanced input from a uniformly random permutation and use compressed permutation oracles to describe the information learned by the algorithm. The adaptive proof bounds the growth of partial collisions through successive queries. The one-round proof instead analyzes the state after the parallel queries directly, bounding the probability that the compressed database contains a full collision. In both proofs, a short verification step accounts for correct outputs that include unrecorded positions. For the decision problem, we also compare one-round states with independent and distinct output labels.
Single-linkage clustering (SLC) is a fundamental method for hierarchical data analysis. In the distance setting, a $k$-clustering produced by SLC can be obtained by computing a minimum spanning tree (MST) and deleting its $k-1$ heaviest edges. This naturally induces a cost profile for the SLC hierarchy: for each $k\in[n]$, we define $\mathrm{cost}_k$ to be the weight of the resulting $k$-component spanning forest, equivalently, the minimum total weight of any spanning forest with exactly $k$ connected components. The corresponding \emph{SLC cost profile} is $(\mathrm{cost}_1,\ldots,\mathrm{cost}_n)$, and the scalar quantity $\mathrm{cost}(G)=\sum_{k=1}^{n}\mathrm{cost}_k$ is the area under this profile. We study the problem of approximating these quantities in sublinear time. We assume that the input is a weighted graph $G$ of average degree $d$ with edge weights in $\{1,\dots,W\}$, accessed through adjacency-list queries; missing edges are treated as having infinite distance. Our main result is a sampling-based algorithm that outputs a succinct sketch of the entire SLC cost profile in the distance setting. The algorithm runs in $\widetilde{O}(d\sqrt{W}/\varepsilon^3)$ time and returns a sketch from which one can derive estimates $(\widehat{\mathrm{cost}}_1,\ldots,\widehat{\mathrm{cost}}_n)$ satisfying $\sum_{k=1}^{n}\bigl|\widehat{\mathrm{cost}}_k-\mathrm{cost}_k\bigr| \le \varepsilon\,\mathrm{cost}(G)$. Thus, we obtain an $\ell_1$ approximation to the full profile whose error is at most an $\varepsilon$-fraction of the area under the true profile. In particular, this yields a $(1\pm\varepsilon)$-approximation to $\mathrm{cost}(G)$ within the same running time. We also prove a nearly matching lower bound of $Ω(d\sqrt{W}/\varepsilon^2)$ queries for estimating $\mathrm{cost}(G)$.