Research
      Publications
      Teaching/Service
      Brief biography
      Contact Info


       CS 787


       UW CS
       Theory Group
       Theory Seminar

Research

Interests: design and analysis of algorithms, algorithmic game theory and mechanism design, combinatorial and stochastic optimization. I am also interested in networking (specifically, applications of game theory in networking) and machine learning. Please see my publications for more details.

Publications: recent or complete list.

Advisees: David Malec, Balasubramanian (Balu) Sivan, Seeun (William) Umboh, Chetan Rao, Andrew Morgan
Graduate alumni: Siddharth (Sid) Barman (Ph.D. 2012; first employment: Postdoc at Caltech CMI)
Undergraduate alumni: Huck Bennett (Colorado-Boulder), Boyan Li (CMU)

Sponsors: My research is supported in part by the National Science Foundation and the Alfred P. Sloan Foundation.


Selected recent publications (see complete list here)

Algorithmic mechanism design
• Bayesian mechanisms for scheduling, working paper, 2012.
• Auctions with Unique Equilibria, AdAuctions'12.
• On the impossibility of black-box transformations in mechanism design, STOC'12.
• Optimal Crowdsourcing Contests, SODA'12; invited to Games and Economic Behavior.
• Bayesian mechanism design for budget-constrained agents, EC'11.
• The power of randomness in Bayesian optimal mechanism design, EC'10; to appear in Games and Economic Behavior.
• Sequential posted pricing and multi-parameter mechanism design, STOC'10.
• Pricing randomized allocations, SODA'10; invited to Journal of Economic Theory.
Approximation/online algorithms
• A bicriteria approximation for the reordering buffer problem, ESA'12.
• Secretary problems with convex costs, ICALP'12.
• Traffic-redundancy aware network design, SODA'12.
• Region growing for multi-route cuts, SODA'10.
• Threshold rules for online sample selection, COCOON'10.
• Packing Multiway Cuts in Capacitated Graphs, SODA'09.
Network pricing
• De-Ossifying Internet Routing through Intrinsic Support for End-Network and ISP Selfishness, SIGMETRICS'11 extended abstract.
• The price of anarchy of Bertrand games, EC'09.
• Bertrand Competition in Networks, SAGT'08.


Teaching & Service

Current course:    Advanced Algorithms (CS 787)

Past courses:
     CS 520 Intro to Theoretical Computer Science: Spring 2008
     CS 577 Introduction to Algorithms: Fall 2006, Spring 2010, Fall 2010, Spring 2012, Fall 2012
     CS 787 Advanced Algorithms: Fall 2007, Fall 2009
     CS 880 Topics in Theory: Spring 2007 (Approximation Algorithms), Spring 2011 (Algorithmic Game Theory)
     CMU 15-859 Randomized Algorithms: Fall 2004

Program Committees: FOCS'06, WINE'07, STOC'08, EC'08, EC'09, WINE'09, ICS'11, SODA'11, EC'11, FSTTCS'11, EC'12, APPROX'12, ITCS'13, STOC'13, EC'13

Organization committees: Workshop on Bayesian Mechanism Design (WBMD'11).


Brief Bio

Prior to joining UW as an assistant professor in August 2006, I got my Ph.D. from the Computer Science Department of Carnegie Mellon University defending this in September, 2005. My advisor was Prof. Avrim Blum. Before this I got my undergraduate degree at the Indian Institute of Technology, Delhi. Following my Ph.D., I spent six months doing a postdoc at Stanford University under the advisorship of Prof. Tim Roughgarden, and six months doing a postdoc with the theory group at Microsoft Research, Silicon Valley.


Contact Information

Please note: I get more email every day than I can handle. If you email me and don't receive a response within 2-3 days, please send me a reminder.

Office: 4373 Computer Science
Phone: (608) 890 0027
Fax: (608) 262 9777
Mailing Address:
   Computer Science Department
   University of Wisconsin - Madison
   1210 W. Dayton Street,
   Madison, WI 53706.
Email: shu...@cs.wisc.edu
  (Help digitize books by supporting ReCAPTCHA.)