Networks and Mechanisms

David Durfee

Algorithms, Combinatorics and Optimization

School of Computer Science

Georgia Institute of Technology

**Date**: Wednesday, Aug 22, 2018

**Time**: 10am (EST)

**Location**: Klaus 2100

**Committee**:

--------------

Dr. Richard Peng (Advisor), School of Computer Science, Georgia Institute of Technology

Dr. Santosh Vempala, School of Computer Science, Georgia Institute of Technology

Dr. Xi Chen, Department of Computer Science, Columbia University

Dr. Eric Vigoda, School of Computer Science, Georgia Institute of Technology

Dr. Alejandro Toriello, School of Industrial and Systems Engineering,

Georgia Institute of Technology

**Abstract**:

--------------

In this thesis we present four different works that solve problems in

dynamic graph algorithms, spectral graph algorithms, computational

economics, and differential privacy. While these areas are not all

strongly correlated, there were similar techniques integral to each of

the results. In particular, a key to each result was carefully

constructing probability distributions that interact with fast

algorithms on networks or mechanisms for economic games and private data

output. For the fast algorithms on networks this required utilizing

essential graph properties for each network to determine sampling

probabilities for sparsification procedures that we often recursively

applied to achieve runtime speedups. For mechanisms in economic games we

construct a gadget game mechanism by carefully manipulating the expected

payoff resulting from the probability distribution on the strategy space

to give a correspondence between two economic games and imply a hardness

equivalence. For mechanisms on private data output we construct a

smoothing framework for input data that allows private output from known

mechanisms while still maintaining certain levels of accuracy.

]]>