Selected Publications in Chronological Order - (by research area)

(Papers are ordered in reverse chronological order of first publication.)

• I Like Her more than You: Self-determined Communities.
  With Christian Borgs, Mark Braverman, Jennifer Chayes, and Shang-Hua Teng. See arXiv:1201.4899 version.
  

• Learning Valuation Functions.
  With Florin Constantin, Satoru Iwata, and Lei Wang. See arXiv:1108.5669 version.
  

• Approximate Nash Equilibria under Stability Conditions.
  With Mark Braverman. See arXiv:1008.1827 version.
  

• Learning Submodular Functions.
  With Nick Harvey. STOC 2011.
  

• The Snowball Effect of Uncertainty in Potential Games.
  With Florin Constantin and Steven Ehrlich. WINE 2011.

• Game-theoretic Couplings and Applications.
  With Florin Constantin, Georgios Piliouras, and Jeff Shamma. CDC 2011.
  

• Leading Dynamics to Good Behavior.
  SIGecom Exchanges, Vol. 10.2, 2011 (Invited).
  

• Min-Sum Clustering of Protein Sequences with Limited Distance Information.
  With With Heiko Roglin, ShangHua Teng, Konstantin Voevodski, and Yu Xia. SIMBAD 2011.
  

• Combining Self Training and Active Learning for Video Segmentation.
  With Alireza Fathi, Xiaofeng Ren, and James M. Rehg. BMVC 2011.
  

• Robust Hierarchical Clustering.
  With Pramod Gupta. COLT 2010.
  

• Efficient Clustering with Limited Distance Information.
  With Heiko Roglin, ShangHua Teng, Konstantin Voevodski, and Yu Xia. UAI 2010.
  
  An extended version appears under the title Active Clustering of Biological Sequences in Journal of Machine Learning Research 2012.
  

• Sequential Item Pricing for Unlimited Supply.
  With Florin Constantin. WINE 2010.

• On Nash-Equilibria of Approximation-Stable Games.
  With Pranjal Awasthi, Avrim Blum, Or Sheffet, and Santosh Vempala. SAGT 2010.
  

• Circumventing the Price of Anarchy: Leading Dynamics to Good Behavior.
  With Avrim Blum and Yishay Mansour. ICS 2010.
  

• On the Equilibria of Alternating Move Games.
  With Aaron Roth, Adam Kalai, and Yishay Mansour. SODA 2010.
  

• Finding Low Error Clusterings.
  With Mark Braverman. COLT 2009.

• Agnostic Clustering.
  With Heiko Roeglin and Shang-Hua Teng. ALT 2009.
  

• Better Guarantees for Sparsest Cut Clustering
  Open Problem. COLT 2009.
  

• The Price of Uncertainty
  With Avrim Blum and Yishay Mansour. EC 2009.
  

• Improved Equilibria via Public Service Advertising.
  With Avrim Blum and Yishay Mansour. SODA 2009.
  

• Approximate Clustering without the Approximation.
  With Avrim Blum and Anupam Gupta. SODA 2009.
  
  See also journal submission (2010).

• A Discriminative Framework for Clustering via Similarity Functions.
  With Avrim Blum and Santosh Vempala. STOC 2008.
  
  See also journal submission (2009).

• Item Pricing for Revenue Maximization.
  With Avrim Blum and Yishay Mansour. ACM Conference on Electronic Commerce, 2008.
  
  A related note appears in SIGecom Exchanges, Issue 7.3, 2008 (Invited).

• Improved Guarantees for Learning via Similarity Functions.
  With Avrim Blum and Nathan Srebro. COLT 2008.
  
  A related note on Similarity-Based Theoretical Foundation for Sparse Parzen Window Prediction.
  With Avrim Blum and Nathan Srebro. ICML/UAI/COLT 2008 Workshop on Sparse Optimization and Variable Selection.

• The True Sample Complexity of Active Learning.
  With Steve Hanneke and Jennifer Wortman. COLT 2008.
  Winner of the Mark Fulk Best Student Paper Award.
  
  An extended version appears in Machine Learning Journal, 80(2-3):111-139, 2010. Special issue for COLT 2008 (Invited).
  

• Clustering with Interactive Feedback.
  With Avrim Blum. ALT 2008.
  

• New Theoretical Frameworks for Machine Learning.
  Thesis Proposal, May 2007.
  
  
• Margin Based Active Learning.
  With Andrei Broder and Tong Zhang. COLT 2007.
  
  
• A Theory of Loss-leaders: Making Money by Pricing below Cost.
  With Avrim Blum, Hubert Chan, and MohammadTaghi Hajiaghayi. WINE 2007. Also available as Technical Report, CMU-CS-07-143.
  
  
• Robust Reductions from Ranking to Classification.
  With Nikhil Bansal, Alina Beygelzimer, Don Coppersmith, John Langford, and Greg Sorkin. COLT 2007.
  
  An extended version appears in Machine Learning Journal, 72(1-2):139-153, 2008. Special issue for COLT 2007 (Invited).
  
  
• Asymptotic Active Learning.
  With Eyal Even-Dar, Steve Hanneke, Michael Kearns, Yishay Mansour, and Jennifer Wortman. NIPS 2007 Workshop on Principles of Learning Design Problem.
  
  
• Open Problems in Efficient Semi-Supervised PAC Learning.
  With Avrim Blum. COLT 2007.
  
  
• Mechanism Design, Machine Learning, and Pricing Problems.
  With Avrim Blum. SIGecom Exchanges 2007, special issue on Combinatorial Auctions (Invited).
  
  
• Random Sampling Auctions for Limited Supply.
  With Nikhil Devanur, Jason D. Hartline, and Kunal Talwar. Technical Report, CMU-CS-07-154, 2007.
  

• An Augmented PAC Model for Semi-Supervised Learning.
  With Avrim Blum. Book Chapter in Semi-Supervised Learning, Chapelle, O., Zien, A., and Scholkopf, B. (Eds.), MIT Press, 2006.
  
  
• On a Theory of Learning with Similarity Functions.
  With Avrim Blum. ICML 2006.
  
  Combined with subsequent paper by Nathan Srebro in journal version, Machine Learning Journal, 72(1-2):89--112, 2008. DOI 10.1007/s10994-008-5059-5. Special issue for COLT 2007 (Invited).
  
  
• Agnostic Active Learning.
  With Alina Beygelzimer and John Langford. Journal of Computer and System Sciences, 75(1):78--89, 2009. Special issue on Learning Theory for best papers in 2006 (Invited).
  
  A preliminary version of this paper appears in the Proceedings of the 23rd International Conference on Machine Learning (ICML) 2006.
  
  
• Approximation Algorithms and Online Mechanisms for Item Pricing.
  With Avrim Blum. ACM Conference on Electronic Commerce, 2006.
  
  An extended version appears in Theory of Computing, 3/9 : 179--195, 2007.
  
  

• A PAC-style Model for Learning from Labeled and Unlabeled Data.
  With Avrim Blum. COLT 2005.
  
  Extended version appears under the title A Discriminative Model for Semi-Supervised Learning in Journal of the ACM, 2010.
  
  
• Search and Knowledge Representation in Artificial Intelligence. Theory and Applications.
  With Florentina Hristea. University of Bucharest Publishing House, 2005 (in Romanian).
  
  
• Mechanism Design via Machine Learning.
  With Avrim Blum, Jason D. Hartline, and Yishay Mansour. Proceedings of the 46th Annual Symposium on Foundations of Computer Science (FOCS) 2005.
  
  Extended version appears under the title Reducing Mechanism Design to Algorithm Design via Machine Learning in Journal of Computer and System Sciences, 74:1245--1270, 2008. Special issue on Learning Theory for best papers in 2005 (Invited).
  
  A related paper on Sponsored Search Auction Design via Machine Learning appears in the Workshop on Sponsored Search Auctions, 2005.
  
  
• Person Identification in Webcam Images: An Application of Semi-Supervised Learning.
  With Avrim Blum, Pakyan Choi, John Lafferty, Brian Pantano, Mugizi Rwebangira, and Xiaojin Zhu. ICML 2005 Workshop on Learning with Partially Classified Training Data.
  
  

• On Kernels, Margins, and Low-dimensional Mappings.
  With Avrim Blum and Santosh Vempala. Proceedings of the 15th International Conference on Algorithmic Learning Theory (ALT) 2004.
  
  Extended version appears under the title Kernels as Features: On Kernels, Margins, and Low-dimensional Mappings in Machine Learning Journal, 65(1):79--94, 2006.
  
  
• Co-Training and Expansion: Towards Bridging Theory and Practice.
  With Avrim Blum and Ke Yang. NIPS 2004.
  
  

• Handwritten Text Localization in Skewed Documents.
  With Ergina Kavallieratou, Doru Balcan, and Nikos Fakotakis. International Conference on Image Processing (ICIP) 2001.
  
  
• An Adaptive Resonance Theory (ART) Based Approach to Handwritten/ Machine-Printed Text Discrimination.
  With Doru Balcan. ICC&IE 2001.