Optimization-based approaches for graph analytics and secure private distributed protocols

Abstract

Mathematical optimization is a study that focuses on finding the best solution, with regards to certain criteria, from all feasible solutions. It is the core of applying mathematical principles in real-world problems, with wide applications in the field of mechanical engineering, economics, and data science. In this thesis, we study optimization-based algorithms for graph analytics and private secure distributed protocols.

For the problem of finding subgraphs with maximum total density and limited overlap in weighted hypergraphs, we apply techniques from linear program in devising algorithms for large real-world datasets, and experiments are included to show the efficiency of our methods. For the problem of privacy amplification by iteration for alternating direction method of multipliers, we focus on improving the privacy guarantee for alternating direction method of multiplier and recover the factor of $\frac{1}{T}$ in the $\Dz$-divergence as number $T$ of iteration increases. For the problem of game-theoretically secure protocols for the ordinal random assignment, we devise secure protocol that achieves maximin secure, strong equal treatment and stability; at the same time we show an impossibility result stating that no maximin secure protocol can realizing a mechanism that is strong equal treatment and ordinal efficiency, excluding the possibility of realizing the well-known probabilistic serial mechanism in a maximin secure distributed protocol.