SUNMONTUEWEDTHUFRISAT
Conferences, Lectures, & Seminars
Events for February
-
CS DLS: Prof. Tuomas Sandholm
Thu, Feb 11, 2010 @ 04:00 PM - 05:50 PM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
Talk title: Design and Algorithms for Modern Kidney ExchangesSpeaker: Prof. Tuomas Sandholm (Carnegie Mellon University)Host: Prof. Milind TambeAbstract:
In kidney exchanges, patients with kidney disease can obtain compatible donors by swapping their own willing but incompatible donors. The clearing problem involves finding a social welfare maximizing set of non-overlapping short cycles. We proved this NP-hard. It was one of the main obstacles to a national kidney exchange. We presented the first algorithm capable of clearing these exchanges optimally on a nationwide scale. The key was incremental problem formulation because the formulation that gives tight LP bounds is too large to even store. On top of the branch-and-price paradigm we developed techniques that dramatically improve runtime and memory usage. Furthermore, clearing is actually an online problem where patient-donor pairs and altruistic donors appear and expire over time. We developed trajectory-based online stochastic optimization algorithms (that use our optimal offline solver as a subroutine) for this. I will discuss design parameters and tradeoffs. Our best online algorithms outperform the current practice of solving each batch separately. I will share experiences from using our algorithms as the clearing engine of the largest two kidney exchange networks in the US. We also introduced several design enhancements to the exchanges. For one, we used our algorithms to launch the first never-ending altruistic donor chains. I am also helping UNOS design the nationwide kidney exchange, which will use our algorithms; I will discuss current design considerations.The talk covers material from the following papers:* Online Stochastic Optimization in the Large: Application to Kidney
Exchange. IJCAI-09. (With Awasthi, P.)* A Nonsimultaneous, Extended, Altruistic-Donor Chain. New England
Journal of Medicine 360(11), March 2009. (With Rees, M., Kopke, J., Pelletier, R., Segev, D., Rutter, M., Fabrega, A., Rogers, J., Pankewycz, O., Hiller, J., Roth, A., Ünver, U., and Montgomery, R.)* Clearing Algorithms for Barter Exchange Markets: Enabling Nationwide
Kidney Exchanges. EC-07. (With Blum, A. and Abraham, D.)Bio:
Tuomas Sandholm is Professor in the Computer Science Department at Carnegie Mellon University. He has published over 380 papers on electronic commerce; game theory; artificial intelligence; multiagent systems; auctions and exchanges; automated negotiation and contracting; coalition formation; voting; safe exchange; normative models of bounded rationality; resource-bounded reasoning; machine learning; networks; and combinatorial optimization. He has 19 years of experience building optimization-based electronic marketplaces, and has fielded several of his systems. He is also Founder, Chairman, and Chief Scientist of CombineNet, Inc., which has commercialized over 800 large-scale generalized combinatorial auctions, with over $50 billion in total spend and over $6 billion in generated savings. He received the Ph.D. and M.S. degrees in computer science from the University of Massachusetts at Amherst in 1996 and 1994. He earned an M.S. (B.S. included) with distinction in Industrial Engineering and Management Science from the Helsinki University of Technology, Finland, in 1991. He is recipient of the National Science Foundation Career Award, the inaugural ACM Autonomous Agents Research Award, the Alfred P. Sloan Foundation Fellowship, and the Computers and Thought Award. He is Fellow of the ACM and AAAI.Location: Seaver Science Library (SSL) - 150
Audiences: Everyone Is Invited
Contact: CS Front Desk
-
CS Colloq: Dr. Xi Chen
Tue, Feb 16, 2010 @ 03:30 PM - 05:00 PM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
Talk Title: From Two-Player Games to Markets: On the Computation of Equilibria
Speaker: Xi Chen
Host: Prof. David KempeAbstract:
Recently, there has been tremendous interest in the study of Algorithmic Game Theory. This is a rapidly growing area that lies at the intersection of Computer Science, Game Theory, and Mathematical Economics, mainly due to the presence of selfish agents in highly decentralized systems, the Internet in particular. The computation of Nash equilibria in games and the computation of Market equilibria in exchange markets have received great attention.
Both problems have a long intellectual history. In 1950, Nash showed that every game has an equilibrium. In 1954, Arrow and Debreu showed that under very mild conditions, every market has an equilibrium. While games and Nash equilibria are used to predict the behavior of selfish agents in conflicting situations, the study of markets and market equilibria laid down the foundation of competitive pricing. Other than the fact that both existence proofs heavily rely on fixed point theorems, the two models look very different from each other.
In this talk, we will review some of the results that characterize how difficult it is to compute or to approximate Nash equilibria in two-player games. We will then show how these results also advanced our understanding about market equilibria.
No prior knowledge of Game Theory will be assumed for this talk.Bio:
Dr. Xi Chen received his B.S. degree in Physics from Tsinghua University in 2003 and his Ph.D. in Computer Science from Professor Andrew Chi-Chih Yao's Institute for Theoretical Computer Science at Tsinghua University in 2007. He then became a postdoctoral researcher at the Institute for Advanced Study, hosted by Professor Avi Wigderson. Last year, he was a postdoctoral researcher at Princeton University, hosted by Professor Sanjeev Arora, and this year he is hosted by Professor Shang-Hua Teng at University of Southern California.The research interests of Dr. Chen lie mainly in Algorithmic
Game Theory and Complexity Theory. He is particularly interested in characterizing the intrinsic difficulties of natural and fundamental problems that arise in the game-theoretic study of Internet and e-commerce. His Ph.D. thesis titled "The Complexity of Two-Player Nash Equilibria" won the Silver prize of the New World Mathematics Award, presented by the International Congress of Chinese Mathematicians every three years. He also won the best paper awards of the 47th IEEE Symposium on Foundations of Computer Science and the 20th International Symposium on Algorithms and Computation.
Location: Seaver Science Library (SSL) - 150
Audiences: Everyone Is Invited
Contact: CS Front Desk
-
CS Colloq: Prof. Stella Yu
Thu, Feb 18, 2010 @ 03:30 PM - 05:00 PM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
Talk Title: Art and Vision: A Quest for A Few Simple Right Strokes
Speaker: Prof. Stella Yu (Boston College)
Host: Prof. Shang-Hua TengAbstract:
A Chinese manual of painting instructs art students as follows:
"Figures, even though painted without eyes, must seem to look; without ears, must seem to listen... There are things which ten hundred brushstrokes cannot depict but which can be captured by a few simple strokes if they are right. That is truly giving expression to the invisible."While computer vision research has made fruitful progress with the help of massive data and computing power, I am more interested in an alternative approach: studying art techniques and human vision to discover those few simple right strokes that are essential for visual expression.In this light, visual computation on images needs to address 3 key questions: What are these few simple strokes? Why are they the right ones? How to find them in an image? I have been pursuing answers to these questions in the computation of brightness, space, and attention with simple features, powerful integration, and active selection. In this talk, I will present my progress on these frontiers as well as new ones explored with an artist in an interdisciplinary course on Art and Vision.Bio:
Stella X. Yu got her Ph.D. from the School of Computer Science at Carnegie Mellon University, where she studied robotics at the Robotics Institute and vision science at the Center for the Neural Basis of Cognition. She continued her computer vision research as a postdoc at the Computer Science Department of UC Berkeley. Since she joined the faculty of Boston College, Dr. Yu has been developing an interdisciplinary curriculum and research agenda on Art and Vision, for which she received an NSF CAREER award in 2007. Dr. Yu is currently the Clare Boothe Luce Assistant Professor of Computer Science at Boston College.Location: Seaver Science Library (SSL) - 150
Audiences: Everyone Is Invited
Contact: CS Front Desk
-
CS Colloq: Dr. Frank McSherry
Fri, Feb 19, 2010 @ 10:00 AM - 11:20 AM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
Talk Title: Differential Privacy: Theory and Practice
Speaker: Dr. Frank McSherry, Microsoft Research (SVC)
Host: Prof. David KempeAbstract:
We present an introduction to the recent concept of Differential Privacy, a privacy criterion requiring that a computation not reveal the presence or absence of individual records in an input data set.
After developing the mathematical foundation, we proceed to describe the Privacy Integrated Queries platform, an analysis language and system providing differential privacy guarantees even for users without privacy experience. The platform requires some new mathematics, tasteful language restriction, and careful implementation, but enables a large set of new computations that would otherwise require ad-hoc expert analysis before execution against sensitive data.Bio:
Frank McSherry is a researcher at Microsoft Research's Silicon Valley Campus, where he studies questions related to data analysis and data privacy. His recent interests lie in bringing the theoretical achievements of differential privacy to non-experts, without requiring them to acquire new advanced degrees along the way. Frank received his PhD from the University of Washington, under Anna Karlin, doing research on spectral methods in data analysis.
Location: Seaver Science Library (SSL) - 150
Audiences: Everyone Is Invited
Contact: CS Front Desk
-
CS Colloq: Dr. Shuheng Zhou
Tue, Feb 23, 2010 @ 03:30 PM - 05:00 PM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
Talk Title: High dimensional statistical estimation and modelling
Speaker: Dr. Shuheng Zhou
Host: Prof. Craig KnoblockAbstract:
A line of recent work has demonstrated that sparsity is a powerful technique in signal reconstruction and in statistical estimation.
Given n noisy samples with p dimensions, where n Undirected graphs are often used to describe high dimensional distributions.
Under sparsity conditions, the graph can be estimated using $L_1$ penalization methods. However, most methods prior to our work have assumed that the data are independent and identically distributed.
If the distribution---and hence the graph--- evolves over time, the data are not longer identically distributed. In the second part of the talk, I show how to estimate the sequence of graphs for non-identically distributed data and establish some theoretical results.In the last part of this talk, I will make a brief connection between my research on high dimensional statistical estimation and on statistical privacy, where the general goal is to construct a data release mechanism that protects individual privacy while preserving information content.
Parts of this talk are based on joint work with Professors John Lafferty and Larry Wasserman at Carnegie Mellon University.Bio:
Shuheng Zhou received her Ph.D. from Carnegie Mellon University in August 2006, co-advised by Professors Greg Ganger and Bruce Maggs; Her dissertation work focused on combinatorial optimization problems in network routing. She then continued as a postdoc fellow at CMU, working with Professors John Lafferty and Larry Wasserman on statistical and machine learning algorithms and theory. She has been a postdoc fellow with Seminar for statistics in Department of Mathematics at ETH Z\"urich, since August 2008. She is currently visiting Department of Statistics at UC Berkeley.
Location: Seaver Science Library (SSL) - 150
Audiences: Everyone Is Invited
Contact: CS Front Desk
-
CS Colloq: Dr. Jingrui He
Thu, Feb 25, 2010 @ 03:30 PM - 05:00 PM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
Talk Title: Rare Category Analysis
Speaker: Dr. Jingrui He
Host: Prof. Gaurav SukhatmeAbstract:
Imbalanced data sets are prevalent in many real applications. It is often the case that people are only interested in the minority classes. The focus of my thesis is rare category analysis, which refers to the problem of detecting and characterizing the minority classes in an unlabeled, imbalanced data set. In this talk, I will introduce different aspects of rare category analysis, including rare category detection for detecting examples from new minority classes, rare category characterization for identifying examples from known minority classes, co-selection of relevant features and examples from the minority classes, etc. Along with theoretical analysis, I will also present experimental results showing the effectiveness of the proposed algorithms.Bio:
Jingrui He is a Ph.D candidate in Machine Learning Department at Carnegie Mellon University. She holds an M.S. degree and a B.S. degree from Tsinghua University, P.R. China. Her research interests include statistical learning for rare category analysis, active learning, multimedia, and spam filtering.
Location: Seaver Science Library (SSL) - 150
Audiences: Everyone Is Invited
Contact: CS Front Desk
