PhD Defense by David Dufree

Event Details
  • Date/Time:
    • Wednesday August 22, 2018
      10:00 am - 12:01 pm
  • Location: Klaus 2100
  • Phone:
  • URL:
  • Email:
  • Fee(s):
    N/A
  • Extras:
Contact
No contact information submitted.
Summaries

Summary Sentence: Algorithmic Manipulation of Probability Distributions for Networks and Mechanisms

Full Summary: No summary paragraph submitted.

Title:  Algorithmic Manipulation of Probability Distributions for
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.

 

Additional Information

In Campus Calendar
No
Groups

Graduate Studies

Invited Audience
Faculty/Staff, Public, Graduate students, Undergraduate students
Categories
Other/Miscellaneous
Keywords
Phd Defense
Status
  • Created By: Tatianna Richardson
  • Workflow Status: Published
  • Created On: Aug 8, 2018 - 10:36am
  • Last Updated: Aug 8, 2018 - 10:36am