Selected Publications in Chronological Order - (by research area)

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

• Random Sampling Auctions for Limited Supply.
  With Nikhil Devanur, Jason D. Hartline, and Kunal Talwar. Technical Report, CMU-CS-07-154, 2007.
  
  

• 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.
  

• 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. Invited to appear in a special issue of Machine Learning Journal for COLT 2008.
  Winner of the Mark Fulk Best Student Paper Award.
  

• 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, August 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).
  
  

• 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, August, 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 2007.
  
  

• A PAC-style Model for Learning from Labeled and Unlabeled Data.
  With Avrim Blum. COLT 2005.
  
  See also journal submission (2008).
  
  
• 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 '04).
  
  Extended version appears under the title Kernels as Features: On Kernels, Margins, and Low-dimensional Mappings in Machine Learning Journal 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.