Shaddin Dughmi

I am a Ph.D. student in the Computer Science Department at Stanford University, concentrating in theory. My interests include algorithms, game theory, and combinatorial optimization. Recently I have focused on problems in algorithmic mechanism design. My advisor is Professor Tim Roughgarden. I am currently supported in part by a Siebel Foundation Fellowship.

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.

Publications

• 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 '10. To appear

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

• On the Power of Randomization in Algorithmic Mechanism Design
  Shahar Dobzinski and Shaddin Dughmi, FOCS '09.

• Revenue Submodularity
  Shaddin Dughmi, Tim Roughgarden, and Mukund Sundararajan, EC '09.

• Truthful Approximation Schemes for Single-Parameter Agents
  Peerapong Dhangwatnotai, Shahar Dobzinski, Shaddin Dughmi, and Tim Roughgarden, FOCS '08.
  Journal version in submission.

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

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

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

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

Various Theory Links

• I founded the Theory Reading Group at Stanford. Check it out and join us!

• I organize Theory Lunch. Let me know if you would like to give a talk.

• A mechanism design reading group from Fall '07.

• I learned a lot from TAing Advanced Graph Algorithms . This is stuff every algorithmist should know. The best part is the problem sets.

• 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 greatly enjoy being a Rains CA.

Contact Information

Shaddin Dughmi
460 Gates Building
353 Serra Mall
Stanford, CA 94305

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