A Special Event Celebrating the 10th Anniversary of Georgia Tech's
Algorithms and Randomness Center
Monday, October 24 in Klaus 1116
10:00am: ARC-IDEaS Distinguished Lecture by Jon Kleinberg – Cornell University
Title: Human Decisions and Machine Predictions
11:15am: Josephine Yu - GT Math
Title: Tropical Geometry in Economics
11:50am: Mohit Singh - Microsoft/GT ISyE
Title: New Approaches for Constrained Subset Selection Problem
12:30 Lunch in the Klaus Atrium
(Sponsored by Georgia Tech Colleges of Computing, Engineering, and Sciences, and by Microsoft Research.)
* * * * *
Jon Kleinberg – Cornell University
Human Decisions and Machine Predictions
An increasing number of domains are providing us with detailed trace data on human decisions, often made by experts with deep experience in the subject matter. This provides an opportunity to use machine-learning prediction algorithms to ask several families of questions --- not only about the extent to which algorithms can outperform expert-level human decision-making in specific domains, but also whether we can use algorithms to analyze the nature of the errors made by human experts, to predict which instances will be hardest for these experts, and to explore some of the ways in which prediction algorithms can serve as supplements to human decision-making in different applications. In this talk, I'll explore this theme by drawing on a line of recent projects; all are joint with Sendhil Mullainathan, and include collaborations with Ashton Anderson, Himabindu Lakkaraju, Jure Leskovec, Annie Liang, and Jens Ludwig.
Jon Kleinberg is the Tisch University Professor in the Departments of Computer Science and Information Science at Cornell University. His research focuses on issues at the interface of networks and information, with an emphasis on the social and information networks that underpin the Web and other on-line media. He is a member of the National Academy of Sciences, the National Academy of Engineering, and the American Academy of Arts and Science; and he is the recipient of research fellowships from the MacArthur, Packard, Simons, and Sloan Foundations, as well as awards including the Nevanlinna Prize, the Harvey Prize, the Newell Award, and the ACM-Infosys Foundation Award in the Computing Sciences.
* * * * *
Josephine Yu – Georgia Tech Math
Tropical Geometry in Economics
In a recent and ongoing work, Baldwin and Klemperer explored a connection between tropical geometry and economics. They gave a sufficient condition for the existence of competitive equilibrium in product-mix auctions of indivisible goods. This result, which we call the Unimodularity Theorem, can also be traced back to the work of Danilov, Koshevoy, and Murota. We will introduce product-mix auctions, prove the Unimodularity Theorem, and discuss integer programming formulations of this problem. This is based on a joint work with Ngoc Mai Tran.
Josephine Yu completed her Ph.D. in mathematics at UC Berkeley in 2007. After postdoctoral positions at MIT and the Mathematical Sciences Research Institute in Berkeley, she joined the School of Mathematics at Georgia Tech in 2010. Her research spans combinatorics, computational algebra, and polyhedral and algebraic geometry.
* * * * *
Mohit Singh – Microsoft / Georgia Tech ISyE
New Approaches for Constrained Subset Selection Problem
Selecting a diverse subset of items from a collection occurs as a fundamental problem in various applications including selecting representative documents from a corpus, selecting diverse geographical locations for sensor placement and designing most informative experiments. The problem is modeled by maximizing the entropy of the joint distribution of the selected items and, typically, has additional side constraints. We design approximation algorithms for the subset selection problem with additional partition constraints. Our algorithm relies on efficient polynomial optimization and reveals surprising connections to the problem of counting matchings via the theory of hyperbolic polynomials.
Mohit Singh is a researcher in the theory group at Microsoft Research, Redmond and will be joining ISyE, Georgia Tech in January 2017. His research interests include discrete optimization, approximation algorithms and convex optimization. Previously, he was an Assistant Professor at McGill University from 2010-2011 and a post-doctoral researcher at Microsoft Research, New England from 2008-2009. He obtained his Ph.D. from Tepper School of Business, Carnegie Mellon University and his doctoral thesis received the Tucker prize in 2009 given by the Mathematical Optimization Society. He has also received the best paper award for his work on the traveling salesman problem at the Annual Symposium on Foundations of Computer Science (FOCS) 2011.