Introduction
- 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.
Game Theory
Combinotorial Auctions/Projects
Rationalizability
- (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.
- (2010, incomplete info) "Conservative Rationalizability
and The Second-Knowledge Mechanism" (Oct 12, 2010) by Jing
Chen and Silvio Micali.
Mechanism Design
Bayesian Prior
- (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.
Complete Information
- (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.
Incomplete Information (using external knowledge)
- (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.
Others
- (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).
Quantum Game Theory
- (2011/01) "Quantum Strategic Game Theory" by Shengyu
Zhang. QIP 2011.
Stableness
- (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.
Mechanism Design Without Money
- (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".
- (2009) "Approximate mechanism design without money"
by Ariel Procaccia and Moshe Tennenholtz. EC 2009.
Scheduling Mechanism
- (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.
Social Network
- (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.
Digital Goods (Single Parameter)
- (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.
Algorithm
Planar Separator / Sparcest Cut
General Separator / Cut
- (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.
Electrical Flow
Routing
Streaming
- (2011) "6.896: Sublinear
Algorithms" by Piotr Indyk.
- (2009) "Space-Efficient Sampling" by Sudipto Guha
and Andrew McGregor. AISTATS, 2007.
Counting / Sampling
- (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.
Data Structure
General
- (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.
Hashing
- (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.
Learning Theory
Generalization
- (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"
Stochastic Gradient Descent / Online Optimization
- (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.
Support Vector Machine
- (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.
Multiple Kernel Learning
- (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.
Others
- (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.
Machine Learning
Click Model
- (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.
Bayesian
- (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.
Data Mining
- (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.
Complexity
Hardness and Derandomization
- (2011/04) "Derandomizing Polynomial Identity Testing
means Proving Circuit Lower Bounds" by Valentine Kabanets
and Russell Impagliazzo. STOC 2003.
Boolean Analysis
- (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.
