Shaddin Dughmi Assistant Professor Department of Computer Science University of Southern California Research interests: Algorithms, broadly construed. My recent focus has been on algorithmic problems with economic motivation. Bio: I graduated from Stanford University with a PhD in computer science in 2011, after defending and writing this thesis. I then spent the 2011-2012 academic year as a postdoc at Microsoft Research. I started at USC in the Fall of 2012. Email: "first name"@usc.edu Office Hours: by appointment. Office Address: SAL 234, 941 Bloom Walk, Los Angeles, CA 90089.

Teaching

• CS599, Fall 2012: Algorithm Design in Strategic Settings

• Randomization and Computation in Strategic Settings
  Shaddin Dughmi. PhD Thesis, Stanford University, August 2011.
  Winner of the Arthur L. Samuel Thesis Award, given in recognition of the best PhD thesis in the computer science department at Stanford University.

Conference and Journal Publications

• Combinatorial Auctions with Restricted Complements
  Ittai Abraham, Moshe Babaioff, Shaddin Dughmi, and Tim Roughgarden. EC 2012.
  proceedings version

• Dynamic Pricing with Limited Supply
  Moshe Babaioff, Shaddin Dughmi, Robert Kleinberg, and Aleksandrs Slivkins. EC 2012.

• 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.

Manuscripts and Technical Reports

• Mechanisms for Risk Averse Agents, Without Loss
  Shaddin Dughmi and Yuval Peres. Presented at the workshop on risk aversion in algorithmic game theory and mechanism design, held in conjunction with EC 2012.

• 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.0322v4 [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].

Miscellany

Various Theory Links

• A mechanism design reading group from Fall '07.

• I learned a lot from TAing Advanced Graph Algorithms .

• My favorite course from undergrad.

Interests and Hobbies