Show simple item record

dc.contributor.advisorPeng, Richard
dc.contributor.authorDurfee, David
dc.date.accessioned2020-05-20T16:46:57Z
dc.date.available2020-05-20T16:46:57Z
dc.date.created2019-05
dc.date.issued2018-12-19
dc.date.submittedMay 2019
dc.identifier.urihttp://hdl.handle.net/1853/62623
dc.description.abstractIn 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.
dc.format.mimetypeapplication/pdf
dc.language.isoen_US
dc.publisherGeorgia Institute of Technology
dc.subjectAlgorithms
dc.subjectSampling
dc.subjectNetworks
dc.subjectMechanisms
dc.titleAlgorithmic manipulation of probability distributions for networks and mechanisms
dc.typeDissertation
dc.description.degreePh.D.
dc.contributor.departmentComputer Science
thesis.degree.levelDoctoral
dc.contributor.committeeMemberVempala, Santosh
dc.contributor.committeeMemberChen, Xi
dc.contributor.committeeMemberVigoda, Eric
dc.contributor.committeeMemberToriello, Alejandro
dc.date.updated2020-05-20T16:46:57Z


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record