Copyright notice
Shuchi's homepage
UW CS
Theory Group
Theory Seminar
|
This page was last updated in 2012. Please see dblp for more recent information.
Recent journal publications
- 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.
Conference publications & working papers
- Auctions with unique
equilibria.
With Jason Hartline. AdAuctions'12.
- A bicriteria approximation for
the reordering buffer problem.
With Siddharth
Barman and William Umboh, arXiv:1204.5823. 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, arXiv:1112.1136. 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.
|