Last Update: Jun. 23^{rd}, 2013.

**NO UPDATE ANYMORE**: I have recently found a software Mendeley that can systematically maintain the papers I have read, so decided not to update this page anymore. I strongly recommend you to check the Mendeley website.- In this library I present an incomplete list of papers I have carefully read. The major purpose is for a personal record because I keep forgetting the names (and/or) they change over time.
- The number (20xx/xx) in front of the paper title is the year/month I read it.

- (2011/08) "
**From Convex Optimization to Randomized Mechanisms: Toward Optimal Combinatorial Auctions**" by Shaddin Dughmi, Tim Roughgarden and Qiqi Yan.*STOC 2011.* - (2011/08) "
**A Truthful Randomized Mechanism for Combinatorial Public Projects via Convex Optimization**" by Shaddin Dughmi.*EC 2011.* - (2011/08) "
**Black-Box Randomized Reductions in Algorithmic Mechanism Design**" by Shaddin Dughmi and Tim Roughgarden.*FOCS 2010*. - (2011/08) "
**Inapproximability for VCG-Based Combinatorial Auctions**" by Dave Buchfuhrer, Shaddin Dughmi, Hu Fu, Robert Kleinberg, Elchanan Mossel, Christos Papadimitriou, Michael Schapira, Yaron Singer and Chris Umans.*SODA 2010*. - (2009) "
**Simple versus Optimal Mechanisms**" by Jason Hartline and Tim Roughgarden.*EC 2009*.

- (2010) "
**Rationalizable strategic behavior and the problem of perfection**" by David G. Pearce.*Econometrica 1984*. - (2010, complete info) "
**Safe Rationalizability and Safe Mechanism Design**" (Sep 16, 2010) by Jing Chen and Silvio Micali.- with a preliminary version called "Exact Rationalizability and
Safe Mechanism Design".
*Second Brazilian Workshop of the Game Theory Society, Sao Paulo, July 2010*.

- with a preliminary version called "Exact Rationalizability and
Safe Mechanism Design".
- (2010, incomplete info) "
**Conservative Rationalizability and The Second-Knowledge Mechanism**" (Oct 12, 2010) by Jing Chen and Silvio Micali.

- (2011/01) "
**On Optimal Single-Item Auctions**" by Christos Papadimitriou and George Pierrakos. - (2010) "
**Conservative-Bayesian Mechanism Design**" (Dec 12, 2010) by Pablo Azar, Jing Chen and Silvio Micali.*DSpace*.

- (2010, CHM) "
**Perfectly Resilient Mechanisms**" (Jul 26, 2010) by Jing Chen, Avinatan Hassidim and Silvio Micali.- with a preliminary version called "Resilient and Virtually Perfect Revenue From Perfectly Informed Players";
- with a preliminary version called "Robust Perfect Revenue From
Perfectly Informed Players".
*ICS 2010*.

- (2010, MR) "
**Subgame Perfect Implementation**" by John Moore and Rafael Repullo.*Econometrica 1988*. - (2010, AM) "
**Virtual Implementation in Iteratively Undominated Strategies: Complete Information**" by Dilip Abreu and Hitoshi Matsushima.*Econometrica, 1992*. - (2009, GP) "
**Virtual Implementation in Backwards Induction**" by Jacob Glazer and Motty Perry.*Games and Economic Behavior 1996*.

- (2009) "
**Robustly Leveraging Collusion in Combinatorial Auctions**" by Jing Chen, Silvio Micali and Paul Valiant.*ICS 2010.* - (2009) "
**A New Approach to Auctions and Resilient Mechanism Design**" by Jing Chen and Silvio Micali.*STOC 2009.*

- (2010) "
**Revenue Maximization via Nash Implementation**" by Thành Nguyen.*ICS 2011*. - (2010, MV) "
**Generalized Second-Price For Truly Combinatorial Auctions**" (Oct 18, 2010) by Silvio Micali and Paul Valiant.- with a preliminary version called "Resilient Mechanisms For Truly Combinatorial Auctions" (Nov 18, 2008).

- (2011/01) "
**Quantum Strategic Game Theory**" by Shengyu Zhang.*QIP 2011*.

- (2010) "
**Approximate Clustering without the Approximation**" by Maria-Florina Balcan, Avrim Blum and Anupam Gupta.*SODA 2009*. - (2010) "
**On Nash-Equilibria of Approximation-Stable Games**" by Pranjal Awasthi, Nina Balcan, Avrim Blum, Or Sheffet and Santosh Vempala.*SAGT 2010*.

- (2009) "
**Sum of Us: Strategyproof Selection from the Selectors**" by Noga Alon, Felix Fischer, Ariel D. Procaccia and Moshe Tennenholtz.*In submission.* - (2009) "
**Truthful Assignment without Money**" by Shaddin Dughmi and Arpita Ghosh.*EC 2010*. - (2009) "
**Mix and Match**" by Itai Ashlagi, Felix Fischer, Ian A. Kash and Ariel D. Procaccia.*EC 2010.* - (2009) "
**Strategyproof Approximation of the Minimax on Networks**" by Noga Alon, Michal Feldman, Ariel D. Procaccia and Moshe Tennenholtz.*Mathematics of Operations Research 35(3), 2010*.- with a preliminary version called "Strategyproof approximation
mechanisms for location on networks"
*.*

- with a preliminary version called "Strategyproof approximation
mechanisms for location on networks"
- (2009) "
**Approximate mechanism design without money**" by Ariel Procaccia and Moshe Tennenholtz.*EC 2009*.

- (2009) "
**Envy-Free Makespan Approximation**" by Edith Cohen, Michal Feldman, Amos Fiat, Haim Kaplan and Svetlana Olonetsky.*Manuscript 2009*. - (2009) "
**An Optimal Lower Bound for Anonymous Scheduling Mechanisms**" by Itai Ashlagi, Shahar Dobzinski and Ron Lavi.*EC 2009*. - (2009) "
**Randomized Truthful Mechanisms for Scheduling Unrelated Machines**" by Pinyan Lu and Changyuan Yu.*WINE 2008*. - (2009) "
**A $1+\phi$ lower bound for truthful scheduling mechanisms**" by Elias Koutsoupias and Angelina Vidali.*MFCS 2007*. - (2009) "
**A lower bound for scheduling mechanisms**" by George Christodoulou, Elias Koutsoupias and Angelina Vidali.*SODA 2007, Algorithmica*. - (2009) "
**Approximation Algorithms for Scheduling on Multiple Machines**" by V.S. Anil Kumar, Madhav Marathe, Srinivasan Parthasarathy and Aravind Srinivasan.*FOCS 2005*.

- (2010) "
**Optimal Marketing Strategies over Social Networks**" by Jason Hartline, Vahab S. Mirrokni and Mukund Sundararajan.*WWW 2008*. - (2010) "
**Optimal Iterative Pricing over Social Networks**" by Hessameddin Akhlaghpour*et al*.*5th*.

Workshiop on Ad Auctions, Stanford, 2009

- (2011/05) "
**Envy, Truth, and Profit**" by Jason Hartline and Qiqi Yan.*EC 2011*. - (2009) "
**From Optimal Limited To Unlimited Supply Auctions**" by Jason Hartline and Robert McGrew.*EC 2005*. - (2009) "
**A Lower Bound on the Competitive Ratio of Truthful Auctions**" by Andrew Goldberg, Jason Hartline, Anna Karlin and Michael Saks.*STACS 2004*.

- (2012/05) "
**Constant Factor Approximation of Vertex-Cuts in Planar Graphs**" by Eyal Amir, Robert Krauthgamer and Satish Rao.*STOC 2003*. - (2012/03) "
**Finding separator cuts in planar graphs within twice the optimal**" by Naveen Garg, Huzur Saran and Vijay V. Vazirani.*FOCS 1994*. - (2012/02) "
**Finding Minimum-Quetient Cuts in Planar Graphs**" by James K. Park and Cynthia A. Phillips.*STOC 1993*. - (2012/02) "
**Faster Algorithms for Finding Small Edge Cuts in Planar Graphs**" by Satish B. Rao.*STOC 1992*. - (2011/12) "
**Separator Theorems for Minor-Free and Shallow Minor-Free Graphs with Applications**" by Christian Wulff-Nilsen.*FOCS 2011*.

- (2012/02) "
**Improved approximation algorithms for minimum-weight vertex separators**" by Uriel Feige, MohammadTaghi Hajiaghayi and James R. Lee.*STOC 2005*. - (2012/03) "
**Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms**" by Tom Leighton and Satish Rao.*JACM 1999*.

- (2011/01) "
**Finding almost-perfect graph bisections**" by Venkatesan Guruswami, Yury Makarychev, Prasad Raghavendra, David Steurer and Yuan Zhou.*ICS 2011*. - (2011/01) "
**A polylogarithmic approximation of the minimum bisection**" by Uriel Feige and Robert Krauthgamer.*SIAM J. Comput. 31, 2002*.

- (2012/04) "
**Using Petal-Decompositions to Build a Low Stretch Spanning Tree**" by Ittai Abraham and Ofer Neiman.*STOC 2012*. - (2011/09) "
**Electrical Flows, Laplacian Systems, and Faster Approximation of Maximum Flow in Undirected Graphs**" by Paul Christiano, Jonathan Kelner, Aleksander Madry, Daniel Spielman and Shang-Hua Teng.*STOC 2011*.

- (2011/08) "
**Routing in Undirected Graphs with Constant Congestion**" by Julia Chuzhoy. 2011. - (2011/08) "
**Breaking o(n**" by Ken-ichi Kawarabayashi and Yusuke Kobayashi.^{1/2})-approximation algorithms for the edge-disjoint paths problem with congestion two*STOC 2011*.

- (2011) "
**6.896: Sublinear Algorithms**" by Piotr Indyk. - (2009) "
**Space-Efficient Sampling**" by Sudipto Guha and Andrew McGregor.*AISTATS, 2007*.

- (2011) "
**6.896: Probability and Computation**" by Costis Daskalakis. - (2009) "
**Faster generation of random spanning trees**" by Jonathan Kelner and Aleksander Mądry.*FOCS 2009*. - (2009) "
**A Polynomial-time Approximation Algorithm for the Permanent of a Matrix with Non-negative Entries**" by Mark Jerrum, Alistair Sinclair and Eric Vigoda.*JACM 2004.* - (2011/04) "
**Approximating the permanent**" by Mark Jerrum and Alistair Sinclair.*JComp 1989.*

- (2009) Selected chapters of "
**Lower Bound Techniques for Data Structures**" by Mihai Pătraşcu.*MIT Press, 2008*. - (2009) "
**(Data)STRUCTURES**" by Mihai Pătraşcu.*FOCS 2008*. - (2009) "
**Cell probe complexity - a survey**" by Peter Bro Mitersen. 2000. - (2009) "
**New Data Structures for Orthogonal Range Searching**" by Stephen Alstrup, Gerth Stølting Brodal and Theis Rauhe.*FOCS 2000*. - (2009) "
**On Data Structures and Asymmetric Communication Complexity**" by Peter Bro Miltersen, Noam Nisan, Shmuel Safra and Avi Wigderson.*STOC 1995*.

- (2009) "
**Dynamic External Hashing: The Limit of Buffering**" by Zhewei Wei, Ke Yi and Qin Zhang.*SPAA 2009*. - (2009) "
**Lower Bounds for External Memory Dictionaries**" by Gerth Stølting Brodal and Rolf Fagerberg.*SODA 2003*. - (2009) "
**The Buffer Tree: A New Technique for Optimal I/O-Algorithms**" by Lars Arge.*University of Aarhus 1995*. - (2009) "
**A Lower Bound for the Dictionary Problem under a Hashing Model**" by Rajamani Sundar.*FOCS 1991*.

- (2010) "
**Learning Kernel-Based Halfspaces with the Zero-One Loss**" by Shai Shalev-Shwartz, Ohad Shamir and Karthik Sridharan.*COLT 2010*. in theory; in experiment. - (2010) "
**Stochastic Convex Optimization**" by Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro and Karthik Sridharan.*COLT 2009*. - (2009) "
**On the Complexity of Linear Prediction: Risk Bounds, Margin Bounds, and Regularization**" by Sham Kakade, Karthik Sridharan and Ambuj Tewari.*NIPS 2009*. - (2009) "
**Fast Rates for Regularized Objectives**" by Karthik Sridharan, Nathan Srebro and Shai Shalev-Shwartz.*NIPS 2008*.- with a preliminary version called "Fast Convergence Rates for Excess Regularized Risk with Application to SVM"

- (2010) "
**Composite Objective Mirror Descent**" by John Duchi, Shai Shalev-Shwartz, Yoram Singer and Ambuj Tewari.*COLT 2010*. - (2010) "
**Stochastic Methods for $\ell_1$ Regularized Loss Minimization**" by Shai Shalev-Shwartz and Ambuj Tewari.*ICML 2009.* - (2009) "
**Mind the Duality Gap: Logarithmic regret algorithms for online optimization**" by Sham Kakade and Shai Shalev-Shwartz.*NIPS 2009*. - (2009) "
**SVM Optimization: Inverse Dependence on Training Set Size**" by Shai Shalev-Shwartz and Nathan Srebro.*ICML 2008*. - (2009) "
**Online Learning: Theory, Algorithms, and applications**" by Shai Shalev-Shwartz.*The Hebrew University, PhD Thesis 2007*. - (2009) "
**Logarithmic Regret Algorithms for Strongly Convex Repeated Games**" by Shai Shalev-Shwartz and Yoram Singer.*The Hebrew University, Technical Report, 2007*. - (2009) "
**Logarithmic Regret Algorithms for Online Convex Optimization**" by Elad Hazan, Adam Kalai, Satyen Kale and Amit Agarwal.*COLT 2006*. - (2009) "
**Duality**", Chapter 5 of "**Convex Optimization**" by Stephen Boyd and Lieven Vandenberghe.*Cambridge University Press 2004*.

- (2009) "
**Pegasos: Primal Estimated sub-GrAdient SOlver for SVM**" by Shai Shalev-Shwartz, Yoram Singer and Nathan Srebro.*ICML 2007*. - (2009) "
**PSVM: Parallelizing Support Vector Machines on Distributed Computers**" by Edward Y. Chang, Kaihua Zhu, Hao Wang and Hongjie Bai.*NIPS 2007*. - (2009) "
**Training Linear SVMs in Linear Time**" by Thorsten Joachims.*KDD 2006*. - (2009) "
**Efficient SVM Training Using Low-Rank Kernel Representations**" by Shai Fine and Katya Scheinberg.*JMLR 2001*.

- (2009) "
**More Generality in Efficient Multiple Kernel Learning**" by Manik Varma and Bodla Rakesh Babu.*ICML 2009*. - (2009) "
**SimpleMKL**" by Alain Rakotomamonjy, Francis Bach, Stéphane Canu and Yves Grandvalet.*JMLR 2008*. - (2009) "
**Large Scale Multiple Kernel Learning**" by Sören Sonnenburg, Gunnar Rätsch, Christin Schäfer and Bernhard Schölkopf.*JMLR 2006.* - (2009) "
**Multiple Kernel Learning, Conic Duality, and the SMO Algorithm**" by Francis Bach, Gert Lanchriet and Michael Jordan.*ICML 2004*.

- (2009) "
**Fitting a Graph to Vector Data**" by Samuel Daitch, Jonathan Kelner and Daniel Spielman.*ICML 2009*. - (2009) "
**Projected Subgradient Methods for Learning Sparse Gaussians**" by John Duchi, Stephen Gould and Daphne Koller.*UAI 2008*. - (2009) "
**The P-Norm Push: A Simple Convex Ranking Algorithm that Concentrates at the Top of the List**" by Cynthia Rudin.*JMLR 2008*.

- (2009) "
**A Dynamic Bayesian Network Click Model for Web Search Ranking**" by Olivier Chapelle and Ya Zhang.*WWW 2009.* - (2009) "
**Click Chain Model in Web Search**" by Fan Guo, Chao Liu, Anitha Kannan, Tom Minka, Michael Taylor, Yi-Min Wang and Christos Faloutsos.*WWW 2009*. - (2009) "
**Efficient Multiple-Click Models in Web Search**" by Fan Guo, Chao Liu and Yi-Min Wang.*WSDM 2009*. - (2009) "
**Spatio-Temporal Models for Estimating Click-through Rate**" by Deepak Agarwal, Bee-Chung Chen and Pradheep Elango.*WWW 2009*. - (2009) "
**A User Browsing Model to Predict Search Engine Click Data from Past Observations**" by Georges Dupret and Benjamin Piwowarski.*SIGIR 2008*. - (2009) "
**Predicting Clicks: Estimating the Click-Through Rate for New Ads**" by Matthew Richardson, Ewa Dominowska and Robert Ragno.*WWW 2007*.

- (2009) "
**TrueSkill: A Bayesian Skill Rating System**" by Ralf Herbrich and Thore Graepel. Technical Report, MSR 2006. - (2009) "
**A family of algorithms for approximate Bayesian inference**" by Tom Minka.*PhD Thesis, MIT, 2001.*

- (2009) "
**Weakly-Supervised Acquisition of Open-Domain Classes and Class Attributes from Web Documents and Query Logs**" by Marius Paşca and Benjamin Van Durme.*ACL 2008*. - (2009) "
**Organizing and Searching the World Wide Web of Facts - Step Two: Harnessing the Wisdom of the Crows**" by Marius Paşca.*WWW 2007*.

- (2011/04) "
**Derandomizing Polynomial Identity Testing means Proving Circuit Lower Bounds**" by Valentine Kabanets and Russell Impagliazzo.*STOC 2003*.

- (2008) "
**Block sensitivity of weakly symmetric functions**" by Xiaoming Sun.*TCS 2007*. - (2008) "
**On the Sensitivity of Cyclically-Invariant Boolean Functions**" by Sourav Chakraborty.*CCC 2005*. - (2008) Lecture notes "
**Analysis of Boolean Functions**" by Ryan O'Donnell. 2007.