• Login
    View Item 
    •   SMARTech Home
    • Georgia Tech Theses and Dissertations
    • Georgia Tech Theses and Dissertations
    • View Item
    •   SMARTech Home
    • Georgia Tech Theses and Dissertations
    • Georgia Tech Theses and Dissertations
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Algorithmic manipulation of probability distributions for networks and mechanisms

    Thumbnail
    View/Open
    DURFEE-DISSERTATION-2019.pdf (1.353Mb)
    Date
    2018-12-19
    Author
    Durfee, David
    Metadata
    Show full item record
    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.
    URI
    http://hdl.handle.net/1853/62623
    Collections
    • College of Computing Theses and Dissertations [1191]
    • Georgia Tech Theses and Dissertations [23877]

    Browse

    All of SMARTechCommunities & CollectionsDatesAuthorsTitlesSubjectsTypesThis CollectionDatesAuthorsTitlesSubjectsTypes

    My SMARTech

    Login

    Statistics

    View Usage StatisticsView Google Analytics Statistics
    facebook instagram twitter youtube
    • My Account
    • Contact us
    • Directory
    • Campus Map
    • Support/Give
    • Library Accessibility
      • About SMARTech
      • SMARTech Terms of Use
    Georgia Tech Library266 4th Street NW, Atlanta, GA 30332
    404.894.4500
    • Emergency Information
    • Legal and Privacy Information
    • Human Trafficking Notice
    • Accessibility
    • Accountability
    • Accreditation
    • Employment
    © 2020 Georgia Institute of Technology