Back to search

Georgia Institute of Technology

Algorithmic manipulation of probability distributions for networks and mechanisms

Abstract

dc:description.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.

Degree

thesis:*
Level thesis:degree_level
Doctoral
Department dc:contributor.department
Computer Science
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2018

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Durfee, David
Advisor dc:contributor.advisor
  • Peng, Richard
Committee members dc:contributor.committeemember
  • Vempala, Santosh
  • Chen, Xi
  • Vigoda, Eric
  • Toriello, Alejandro

Subjects

dc:subject × 4

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1853/62623

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Durfee, David. Algorithmic manipulation of probability distributions for networks and mechanisms. Doctoral thesis, Georgia Institute of Technology, 2018. http://hdl.handle.net/1853/62623