Shaddin Dughmi I am a postdoctoral scholar in the theory group at Microsoft Research in Redmond, Washington. I recently graduated from Stanford University with a PhD in computer science, after defending and writing this thesis. Starting Fall 2012, I will be an assistant professor of computer science at the University of Southern California. My research interests are in algorithms, broadly construed. My recent focus has been on algorithmic problems with economic motivation.

Publications

• Limitations of Randomized Mechanisms for Combinatorial Auctions
  Shaddin Dughmi and Jan Vondrak. FOCS 2011.

• A Truthful Randomized Mechanism for Combinatorial Public Projects via Convex Optimization
  Shaddin Dughmi. EC 2011, co-winner of the Best Student Paper Award.
  proceedings version

• From Convex Optimization to Randomized Mechanisms: Toward Optimal Combinatorial Auctions
  Shaddin Dughmi, Tim Roughgarden, and Qiqi Yan. STOC 2011.
  proceedings version

• Posting Prices with Unknown Distributions
  Moshe Babaioff, Liad Blumrosen, Shaddin Dughmi, and Yaron Singer. ICS 2011.

• Black-Box Randomized Reductions in Algorithmic Mechanism Design
  Shaddin Dughmi and Tim Roughgarden. FOCS 2010.
  proceedings version

• Truthful Assignment without Money
  Shaddin Dughmi and Arpita Ghosh. EC 2010.
  proceedings version

• Inapproximability for VCG-Based Combinatorial Auctions
  Dave Buchfuhrer, Shaddin Dughmi, Hu Fu, Robert Kleinberg, Elchanan Mossel, Christos Papadimitriou, Michael Schapira, Yaron Singer, and Chris Umans. SODA 2010.

• On the Power of Randomization in Algorithmic Mechanism Design
  Shahar Dobzinski and Shaddin Dughmi. FOCS 2009.
  proceedings version

• Revenue Submodularity
  Shaddin Dughmi, Tim Roughgarden, and Mukund Sundararajan. EC 2009.
  proceedings version

• Truthful Approximation Schemes for Single-Parameter Agents
  Peerapong Dhangwatnotai, Shahar Dobzinski, Shaddin Dughmi, and Tim Roughgarden. FOCS 2008 and SICOMP Special issue for FOCS 2008.
  proceedings version | journal version

• Completeness of the Authentication Tests
  Shaddin Dughmi, Joshua D. Guttman, and F. Javier Thayer. ESORICS 2007.

• Searching for Shapes in Cryptographic Protocols
  Shaddin Dughmi, Joshua D. Guttman, and F. Javier Thayer. TACAS 2007.

• Skeletons and the Shapes of Bundles
  Shaddin Dughmi, Joshua D. Guttman, and F. Javier Thayer. WITS 2007.

• Skeletons, Homomorphisms and Shapes: Characterizing Protocol Executions
  Shaddin Dughmi, Joshua D. Guttman, and F. Javier Thayer. MFPS 2007.

Technical Reports and Working Papers

• Randomization and Computation in Strategic Settings
  Shaddin Dughmi. PhD Thesis, Stanford University, August 2011.

• Succinct Coverage Oracles
  Ioannis Antonellis, Anish Das Sarma, and Shaddin Dughmi.

• Submodular Functions: Extensions, Distributions, and Algorithms. A Survey.
  Shaddin Dughmi. PhD Qualifying Exam Report, Department of Computer Science, Stanford University.
  arXiv:0912.0322v3 [cs.DS].

• Amplified Hardness of Approximation for VCG-Based Mechanisms
  Shaddin Dughmi, Hu Fu, and Robert Kleinberg. Merged with two closely related, independent discoveries into Inapproximability for VCG-Based Combinatorial Auctions above.
  arXiv:0907.1948v2 [cs.GT].

Various Theory Links

• A mechanism design reading group from Fall '07.

• I learned a lot from TAing Advanced Graph Algorithms .

• A very useful two-course introduction to approximation algorithms: cs261 and cs361b. The lecture notes are particularly handy.

• My favorite course from undergrad.

Contact Information

Email: "first name"@cs.stanford.edu
Phone: (650)387-9265