Maria-Florina Balcan

Assistant Professor  School of Computer Science  Georgia Institute of Technology   Office: KACB 2144   Email:

---

My main research interests are computational and statistical machine learning, computational aspects in economics and game theory, and algorithms. For more information on my research, see the publications and presentations links below.

I am a recipient of a Microsoft Faculty Research Fellowship and of an NSF CAREER Award. My research is also funded by AFOSR/MURI, ONR, and a Google Research Award.
Prior to Georgia Tech, I was a postdoc at Microsoft Research New England and before that I graduated from the Computer Science Department at Carnegie Mellon University. My Ph.D. thesis New Theoretical Frameworks for Machine Learning received the CMU SCS Distinguished Dissertation Award. Additional information is in my resume.

Publications by year, or by topic. Selected presentations.

---

Teaching

• Current course
• Design and Analysis of Algorithms (Spring 2013).

• Past courses
• Design and Analysis of Algorithms: Fall 2012, Spring 2011.
• Machine Learning Theory: Fall 2011, Spring 2010.
• Connections between Learning, Game Theory, and Optimization. Fall 2010.
• Machine Learning Theory. Spring 2007, CMU.
• Artificial Intelligence (Spring 2002, University of Bucharest)

---

Service

• Board member of the International Machine Learning Society


• Program committees
• Main PC/Area Chair: FOCS 2013, COLT 2013, ICML 2013, COLT 2012, WINE 2012, UAI 2012, NIPS 2011,COLT 2011, ICS 2011, NIPS 2010, ALT 2010, FOCS 2009, COLT 2009.
• Extended PC: ICML 2012, EC 2011, ECML PKDD 2010, WWW 2010, ICML 2008, ICML 2007.


• Organizer
  • ARC Workshop on Modern Aspects of Submodularity.
  • Invited Session Chair: INFORMS Annual Meeting 2009.
  • Invited Session Chair: The 20th International Symposium on Mathematical Programming, ISMP 2009.
  • NIPS 2008 Workshop on Learning with Data-dependent Concept Spaces.

---

Selected papers

Recent papers

• Active and passive learning of linear separators under log-concave distributions. Phil Long. COLT 2013.
• Finding Endogenously Formed Communities. With Christian Borgs, Mark Braverman, Jennifer Chayes, and Shang-Hua Teng. SODA 2013.
• Efficient Semi-Supervised and Active Learning of Disjunctions. With Chris Berlind, Steven Ehrlich, and Yingyu Liang. ICML 2013.
• Clustering under Approximation Stability. With Avrim Blum and Anupam Gupta. Journal of the ACM 2013.
  Earlier version Approximate Clustering without the Approximation in SODA 2009. See related talk.
• Learning Valuation Functions. With Florin Constantin, Satoru Iwata, and Lei Wang. COLT 2012.
  See COLT talk. See related talk.
• Robust Interactive Learning. With Steve Hanneke. COLT 2012. See COLT talk.
• Distributed Learning, Communication Complexity, and Privacy. With Avrim Blum, Shie Fine, and Yishay Mansour. COLT 2012.
• Active Clustering of Biological Sequences. With Heiko Roglin, ShangHua Teng, Konstantin Voevodski, and Yu Xia. Journal of Machine Learning Research 2012.
  Earlier version in UAI 2010.
• Learning Submodular Functions. With Nick Harvey. STOC 2011. See related talk
  Also a NECTAR track paper at ECML-PKDD 2012 (for "significant machine learning results"). See short abstract.
  See also Submodular Functions: Learnability, Structure, and Optimization (expanded version, 2012).
• Robust Hierarchical Clustering. With Pramod Gupta. COLT 2010.

 Older papers

• The True Sample Complexity of Active Learning. With Steve Hanneke and Jennifer Wortman. Machine Learning Journal 2010 (special issue, invited).
  Earlier version in COLT 2008.
• A Discriminative Model for Semi-Supervised Learning. With Avrim Blum. Journal of the ACM 2010.
  Earlier version in COLT 2005. Also a book chapter. See related talk.
• Agnostic Active Learning. With Alina Beygelzimer and John Langford. Journal of Computer and System Sciences 2009 (special issue, invited).
  Earlier version in ICML 2006.
• A Discriminative Framework for Clustering via Similarity Functions. With Avrim Blum and Santosh Vempala. STOC 2008.
  See also long version.
• Reducing Mechanism Design to Algorithm Design via Machine Learning. With Avrim Blum, Jason Hartline, and Yishay Mansour. Journal of Computer and System Sciences 2008 (special issue, invited).
  Earlier version in FOCS 2005.
• On a Theory of Learning with Similarity Functions. With Avrim Blum. ICML 2006. See related talk.
  Combined with subsequent paper by Nathan Srebro in journal version, Machine Learning Journal 2008 (special issue, invited).