Select a calendar:
Filter February Events by Event Type:
SUNMONTUEWEDTHUFRISAT
Events for February 17, 2011
-
IMSC Retreat
Thu, Feb 17, 2011 @ 08:00 AM - 07:00 PM
Thomas Lord Department of Computer Science, Information Sciences Institute, Ming Hsieh Department of Electrical and Computer Engineering, USC Viterbi School of Engineering
Receptions & Special Events
An Overview of Research at the USC Integrated Media Systems Center. An all-day program introduced by Viterbi School Dean Yannis C. Yortsos and IMSC Director Cyrus Shahabi will present overviews of three major IMSC Projects: iCampus ("Intelligent Campus"); iWatch ("Intelligent Surveillance"); and CT Project ("Intelligent Transportation"). Additionally the event will feature demos, posters and a special panel, "The Geo-Social Revolution: Hype or Real?" moderated by Shahabi. A schedule is available at http://imscwww.usc.edu/pdfs/IMSC_Retreat-agenda.pdf
Location: Charlotte S. & Davre R. Davidson Continuing Education Conference Center (DCC) -
Audiences: at capacity; email website contacts if interested in attending
Contact: Eric Mankin
-
CS Colloquium
Thu, Feb 17, 2011 @ 11:00 AM - 12:00 PM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
Speaker: Dr. Craig Boutilier, University of Toronto
Talk Title: Computational Social Choice: A Decision-theoretic Perspective
Abstract: Social choice, an important topic of study for centuries, has recently been the subject of intense investigation and application within computer science. One reason for this is the increasing ease with which preference data from user populations can be derived, assessed, or estimated, and the variety of settings in which preference data can be aggregated for consensus recommendations. However, much work in computational social choice adopts existing social choice schemes rather uncritically. We adopt an explicit decision-theoretic perspective on computational social choice in which an explicit objective function is articulated for the task at hand. With this is place, one can develop new social choice rules suited to that objective; or one can analyze the performance of existing social choice rules relative to that criterion.
We illustrate the approach with two different models. The first is the "unavailable candidate model." In this model, a consensus choice must be selected from a set of candidates, but candidates may become unavailable after agents express their preferences. An aggregate ranking is used as a decision policy in the face of uncertain candidate availability. We define a principled aggregation method that minimizes expected voter dissatisfaction, provide exact and approximation algorithms for optimal rankings, and show experimentally that a simple greedy scheme can be extremely effective. We also describe strong connections to the plurality rule and the Kemeny consensus, showing specifically that Kemeny produces optimal rankings under certain conditions.
The second model is the "budgeted social choice" model. In this framework, a limited number of alternatives can be selected for a population of agents. This limit is determined by some form of budget. Our model is general, spanning the continuum from pure consensus decisions (i.e., standard social choice) to fully personalized recommendation. We show that standard rank aggregation rules are not appropriate for such tasks and that good solutions typically involve picking diverse alternatives tailored to different agent types. In this way, it bears a strong connection to both segmentation problems and multi-winner election schemes. The corresponding optimization problems are shown to be NP-complete, but we develop fast greedy algorithms with theoretical guarantees. Experimental results on real-world datasets demonstrate the effectiveness of our greedy algorithms.
Host: Dr. Milind Tambe, USC
Location: Seeley Wintersmith Mudd Memorial Hall (of Philosophy) (MHP) - 106
Audiences: Everyone Is Invited
Contact: Kanak Agrawal
-
CS Colloquium
Thu, Feb 17, 2011 @ 03:30 PM - 05:00 PM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
Speaker: Virginia Vassilevska Williams, UC Berkeley
Talk Title: Path, matrix and triangle problems -- subcubic algorithms and equivalences
Abstract: Many graph and matrix problems studied in optimization have relatively simple algorithms which run in time cubic in the number of vertices or rows. Some examples include matrix multiplication and all-pairs shortest paths. These problems have widespread applications, and developing more efficient algorithms for them would have a big impact. In 1969, Strassen gave a clever truly subcubic algorithm for matrix multiplication, and this insight has since lead to faster algorithms for many of the graph and matrix problems solvable in cubic time.
Nevertheless, several stubborn problems remain for which the best known running time is essentially cubic. The prototypical of these problems is all-pairs shortest paths. Other stubborn problems include the minimum weight cycle (girth) problem, the replacement paths problem, the second shortest simple path problem, and the simplest of them all, the problem of detecting a negative weight triangle in a graph. We have recently been able to show, perhaps surprisingly, that all these problems are equivalent, in the sense that if one has a truly subcubic algorithm, then all of them do. To accomplish this, we define a new, more refined notion of reduction, preserving "subcubicity" (the notion can easily be extended for any time exponent other than 3 as well).
One of our major goals is to develop a theory of equivalences between problems within P, analogous to that of NP-completeness. One reason P vs NP looks so hard to resolve is that many researchers from different areas have all been working on essentially the same (NP-complete) problem with no success. Our situation is entirely analogous: either these problems require essentially cubic time, or we are missing a fundamental insight which would make all of them simultaneously easier. In this talk I will give an overview of my results in the area, both algorithms and equivalences.
Biography: Virginia Vassilevska Williams is currently a postdoctoral fellow working with Prof. Satish Rao, sponsored by a Computing Innovations Fellowship. She obtained her Bachelor's degree in mathematics and engineering and applied science from the California Institute of Technology in 2003. She completed her Ph.D. in computer science at Carnegie Mellon University in 2008 under the guidance of Prof. Guy Blelloch. She also spent a year as a postdoctoral member at the Institute for Advanced Study in Princeton, in Avi Wigderson's group. Her primary research interests are in graph algorithms and computational social choice.
Host: Prof. Ming-Deh Huang, USC
Location: Seaver Science Library (SSL) - 150
Audiences: Everyone Is Invited
Contact: Kanak Agrawal
