Copyright notice
Paper abstracts
Shuchi's homepage


UW CS
Theory Group
Theory Seminar

• Optimal crowdsourcing contests.
  With Jason Hartline and Balu Sivan, invited to Games and Economic Behavior, special issue devoted to AGT papers from 2012.


• The power of randomness in Bayesian optimal mechanism design.
  With David Malec and Balu Sivan, invited to Games and Economic Behavior, special issue devoted to AGT papers from 2010.


• Pricing randomized allocations.
  With Patrick Briest, Robert Kleinberg, and S. Matthew Weinberg, invited to Journal of Economic Theory, special issue on AGT.


• Threshold rules for online sample selection.
  With Eric Bach and William Umboh, invited to Discrete Mathematics: Algorithms and Applications, 2(4):625-642, 2010.

• Auctions with unique equilibria.
  With Jason Hartline. Submitted.


• A bicriteria approximation for the reordering buffer problem.
  With Siddharth Barman and William Umboh. Submitted.


• Bayesian algorithms for scheduling.
  With Jason Hartline, David Malec, and Balu Sivan. Working paper.


• Secretary problems with convex costs.
  With Siddharth Barman, David Malec, and Seeun Umboh. ICALP'12.


• On the impossibility of black-box transformations in mechanism design.
  With Nicole Immorlica and Brendan Lucier, arXiv:1109.2067. STOC'12.


• Traffic redundancy aware network design.
  With Siddharth Barman, arXiv:1110.4150. SODA'12.


• Optimal crowdsourcing contests.
  With Jason Hartline and Balu Sivan, arXiv:1111.2893. SODA'12.


• De-Ossifying Internet Routing through Intrinsic Support for End-Network and ISP Selfishness.
  With Aditya Akella, Holly Esquivel, and Chitra Muthukrishnan. Extended absract in SIGMETRICS'11.


• Bayesian mechanism design for budget-constrained agents.
  With David Malec and Azarakhsh Malekian, arXiv:1103.6280. EC'11.


• Threshold rules for online sample selection.
  With Eric Bach and William Umboh, COCOON'10.


• The power of randomness in Bayesian optimal mechanism design.
  With David Malec and Balu Sivan, EC'10.


• Sequential posted pricing and multi-parameter mechanism design.
  With Jason Hartline, David Malec, and Balu Sivan, STOC'10.


• Region growing for multi-route cuts.
  With Siddharth Barman, SODA'10.


• Pricing randomized allocations.
  With Patrick Briest, Robert Kleinberg, and S. Matthew Weinberg, SODA'10.


• The price of anarchy of Bertrand games.
  With Feng Niu, EC'09.


• Packing Multiway Cuts in Capacitated Graphs. [extended abstract]
  With Siddharth Barman, SODA'09.


• Bertrand Competition in Networks. [extended abstract]
  With Tim Roughgarden, SAGT'08.


• Approximate Pricing via Virtual Valuations.
  With Jason Hartline and Bobby Kleinberg, EC'07.


• Single Source Stochastic Routing.
  With Tim Roughgarden, APPROX'06.


• Optimal Cost Sharing Mechanisms for Steiner Forest Problems.
  With Mukund Sundararajan and Tim Roughgarden, WINE'06.


• Bayesian Optimal No-deficit Mechanism Design.
  With Jason Hartline, Uday Rajan and R. Ravi, WINE'06.


• On the Utility of Privacy-Preserving Histograms.
  With Cynthia Dwork, Frank McSherry and Kunal Talwar, UAI'05.


• On the Hardness of Approximating Multicut and Sparsest-Cut. [extended abstract]
  With Robert Krauthgamer, Ravi Kumar, Yuval Rabani and D. Sivakumar, Computational Complexity (2006), 15(2): 94-114. Preliminary version appeared in CCC'05.


• Towards Privacy in Public Databases.
  With Cynthia Dwork, Frank McSherry, Hoeteck Wee and Adam Smith, TCC'05.


• Embeddings of Negative-type Metrics and An Improved Approximation to Generalized Sparsest Cut. [ps]
  With Anupam Gupta and Harald Racke, ACM Transactions on Algorithms, SODA 2005 Special Issue (2008), 4(2). Preliminary version appeared in SODA'05.


• Approximation Algorithms for Deadline-TSP and Vehicle Routing with Time-Windows. [ps]
  With Nikhil Bansal, Avrim Blum and Adam Meyerson, STOC'04.


• Worst-case Payoffs of a Location Game. [ps]
  With Uday Rajan, R. Ravi and Amitabh Sinha, Operations Research Letters (2006), 34: 499-507. Preliminary version appeared as a poster in EC'04.


• Approximation Algorithms for Orienteering and Discounted-Reward TSP. [ps]
  With Avrim Blum, David Karger, Terran Lane, Adam Meyerson and Maria Minkoff, SIAM Journal on Computing (2007), 37(2): 653-670. Preliminary version appeared in FOCS'03.


• Scaling Properties of the Internet Graph. [ps, extended abstract]
  With Aditya Akella, Arvind Kannan and Srinivasan Seshan, ACM SIGCOMM Computer Communication Review, Special Issue on Science of Network Design (July, 2004), 34(3): 43-56. Preliminary version appeared in PODC'03.


• Scheduling for Flow Time with Admission Control, or, How to Manage your To-Do List. [ps]
  With Nikhil Bansal, Avrim Blum and Kedar Dhamdhere, ESA'03. (A shorter version appeared in MAPSP'03.)


• Profit Maximizing Mechanisms for the Extended Multicasting Game. [ps]
  With David Kitchin, Uday Rajan, Ramamoorthi Ravi and Amitabh Sinha, poster session, EC'03.


• Online Oblivious Routing. [ps]
  With Nikhil Bansal, Avrim Blum and Adam Meyerson, SPAA'03.


• Correlation Clustering. [ps, extended abstract]
  With Nikhil Bansal and Avrim Blum, Machine Learning, Special Issue on Clustering (2004), 56(1-3): 89-113. Preliminary version appeared in FOCS'02.


• Static Optimality and Dynamic Search Optimality in Lists and Trees. [ps]
  With Avrim Blum and Adam Kalai, Algorithmica, Special Issue on Online Algorithms (2003), 36: 249-260. Preliminary version appeared in SODA'02.


• Learning from Labeled and Unlabeled Data using Graph Mincut. [ps]
  With Avrim Blum, ICML'01.


• QoS based Scheduling for Incorporating Variable Rate Coded Voice in BLUETOOTH. [ps]
  With Huzur Saran and Mitali Singh, ICC'01.

Technical Reports

• Bayesian Optimal No-deficit Mechanism Design. [ps]
  With Jason Hartline, R. Ravi and Uday Rajan. CMU-CS-04-153, Aug 2004.


• Scaling Properties of the Internet Graph.
  With Aditya Akella, Arvind Kannan and Srinivasan Seshan. CMU-CS-03-143, May 2003.


• Min-Max Payoffs of a Location Game.
  With Uday Rajan, R. Ravi and Amitabh Sinha. CMU-CS-03-141, May 2003.
  Also appeared as a short paper in ACM EC'04 and published in Operations Research Letters.


• Approximation Algorithms for Orienteering and Discounted-Reward TSP.
  With Avrim Blum, David Karger, Terran Lane, Adam Meyerson and Maria Minkoff. CMU-CS-03-121, March 2003.


• Profit Maximizing Mechanisms for the Extended Multicasting Game.
  With David Kitchin, Uday Rajan, Ramamoorthi Ravi and Amitabh Sinha. CMU-CS-02-164, July 2002.
  Also appeared as a short paper (poster) in ACM EC'03.


• Mechanisms for Internet Routing: A Study.
  With Aditya Akella and Srini Seshan. CMU-CS-02-163, July 2002.