Date of Award

Spring 5-18-2026

Document Type

Thesis

Degree Name

Master of Science (MS)

Department

Computer Science

First Advisor

Quanquan Liu

Abstract

This thesis studies two graph algorithmic settings where additional structure gives stronger guarantees than worst-case black-box methods. The paper considers higher order edge connectivity under node differential privacy. We study the minimum k-edge-connected spanning subgraph problem (k-ECSS) and the minimum k-edge-connected component problem (k-ECC). These objectives have large global sensitivity under node privacy, since adding or deleting one vertex and its incident edges can significantly change robust connectivity structure. To address this, we use Propose-Test-Release for locally stable k-ECC instances and a Lipschitz extension framework for k-ECSS, based on bounded-degree complement objectives and the Generalized Exponential Mechanism.

The second part studies sparsification of Cayley graph Laplacians. We show that the leverage score sparsification argument for sums of positive semidefinite matrices can be improved for Cayley graphs using representation theory. Since Cayley graph Laplacians are convolution operators, they decompose into irreducible representation blocks. Applying matrix Chernoff block by block, we can replace the usual log |G| factor by logD, where D = sum  ρ∈bG dρ. This improvement is meaningful for non-abelian groups, where D can be much smaller than |G|.

Download

Share

COinS