Final update - August 30th, 2011: I have completed my PhD after defending and writing this thesis. I will be spending the 2011-2012 academic year as a postdoc at Microsoft Research in Redmond, Washington. Starting Fall 2012, I will be an assistant professor of computer science at the University of Southern California.
I will no longer be updating this webpage. Depending on when you are viewing this, you may want to look for my new page either at MSR or at USC. I leave below a snapshot of my homepage as it once stood when I was a grad student, for nostalgia's sake.

Shaddin Dughmi I am a PhD student in the computer science theory group at Stanford University, advised by Professor Tim Roughgarden. My interests include algorithms, game theory, and combinatorial optimization. Recently I have focused on problems in algorithmic mechanism design. I graduated from Cornell University in 2004 with a B.S. in computer science and a minor in applied mathematics. After Cornell, I joined the MITRE Corporation as an Information Security Engineer from 2004 to 2006, where I worked on cryptographic protocol analysis. I enrolled at Stanford in the Fall of 2006, and expect to graduate in June 2011.

Publications

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

• 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

• 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

• Theory Reading Group.

• Theory Lunch.

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

Other

• I enjoy being a Rains CA.

Contact Information

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