- talks - lists.cs.princeton.edu

[colloquium] special theory lunch: Christos Papadimitriou on Mon March 6
by Sanjeev Arora 06 Mar '06

06 Mar '06

Christos Papadimitriou will speak at a special theory lunch on Monday March 6 in the small auditorium in the CS building. I am sending this announcement to the colloquium mailing list too since the talk should be of wider interest. Lunch will be served shortly before noon and the talk begins at 12:20. We have to be out of the room by 1:25, and food is not allowed in the auditorium so please come early. I apologize for conflicts with other ongoing activities; this time meshed best with the speaker's schedule. His abstract appears below. Sanjeev --------------- Title: COMPUTING EQUILIBRIA Christos H. Papadimitriou UC, Berkeley In 1951 Nash showed that every game has a mixed equilibrium; whether such an equilibrium can be found efficiently has been open since that time. Two decades later Aumann proposed a relaxation called correlated equilibrium, which can be found efficiently by linear programming. These two problems become more interesting and meaningful in the case of succinctly representable multiplayer games. For correlated equilibria, a novel use of the ellipsoid algorithm yields a polynomial-time algorithm in this case; for Nash equilibria a sequence of reductions (discovered in collaboration with Costas Daskalakis and Paul Goldberg) sheds light to the complexity of finding Nash equilibria.

2 1

[colloquium] TALK MONDAY: Computational methods for high-dimensional dynamic programs for discrete resource allocation
by Steven Kleinstein 09 Dec '05

09 Dec '05

TITLE: Computational methods for high-dimensional dynamic programs for discrete resource allocation SPEAKERS: Warren Powell & Hugo Simao Operations Research and Financial Engineering, Princeton University TIME: Monday, December 12, 2005 Seminar begins at 12:30 p.m. (lunch provided ~12:20) LOCATION: Small Auditorium on 1st floor (rm. 105) Computer Science Building ABSTRACT: We will describe a high-dimensional control problem that arises in a transportation setting. The application involves simulating the movements of thousands of drivers and loads in freight transportation. The goal is to build a model that simulates the behavior of the operation, which requires optimizing not only at each point in time, but also over time. The single period control vector involves tens of thousands of dimensions. Formulated as a dynamic program, we obtain a state variable with hundreds of thousands of dimensions. To keep processing times reasonable, we will describe both algorithmic advances and our experience using different computational strategies, including coase-grained and fine-grained parallel decomposition. We will also discuss memory issues that arose as a result of using Java. ** PICASso: ** Program in Integrative Information, Computer and Application Sciences ** www.cs.princeton.edu/picasso SIGN UP FOR THE PICASso MAILING LIST: ===================================== If you would like to be kept informed of computationally-oriented events in (and around) Princeton, please SUBSCRIBE to the PICASso mailing list by visiting https://lists.cs.princeton.edu/mailman/listinfo/picasso. This page also contains information on how to UNSUBSCRIBE. PLEASE FORWARD THIS MESSAGE TO OTHER COMPUTATIONALLY-ORIENTED RESEARCHERS WHO MAY BE INTERESTED IN THIS EVENT, OR FUTURE PROGRAMS. THANKS!

1 0

[colloquium] TODAY: Automatic Generation of Data-Processing Tools
by Steven Kleinstein 14 Nov '05

14 Nov '05

TITLE: Automatic Generation of Data-Processing Tools SPEAKERS: Yitzhak Mandelbaum and David Walker Department of Computer Science, Princeton University TIME: Monday, November 14, 2005 Seminar begins at 12:30 p.m. (lunch provided ~12:20) LOCATION: Room 302 ABSTRACT: An ad hoc data format is any non-standard data format for which parsing, querying, analysis, or transformation tools are not readily available. Despite the increasing use of standard data formats such as XML, ad hoc data sources continue to arise in numerous industries such as finance, health care, transportation, and telecommunications as well as in scientific domains, such as computational biology and chemistry. The absence of tools for processing ad hoc data formats complicates the daily data-management tasks of data analysts, who may have to cope with numerous ad hoc formats even within a single application. Common characteristics of ad hoc data complicate the building of tools to perform even basic data processing tasks. For example, documentation of ad hoc formats, is often incomplete or inaccurate, making it difficult to define a database schema or to build a reliable parser. In addition, the data itself often contains numerous kinds of errors, which can thwart standard database loaders. In this talk we will describe PADS, a system for automatic generation of data processing tools. PADS allows programmers to write simple, high-level descriptions of their data format. Descriptions include information on both the physical layout of the data within a file as well as semantic constraints such as the range of allowed values and correlations between different parts of the data. Once the data has been properly described, the PADS compiler can generate a suite of programming libraries and stand-alone tools. In particular, the PADS compiler generates a parser library capable of detecting and recovering from data errors and a printing library for the format. On top of these basic libraries PADS provides generic tools that can translate ad hoc data into XML, format the data in a canonical form, query the data using the semi-structured query language XQuery as if it were XML (but not actually incur the overhead of translation to XML), and generate a statistical summary of data characteristics such as the range of values in different data fields and the number of errors in each field. ** PICASso: ** Program in Integrative Information, Computer and Application Sciences ** www.cs.princeton.edu/picasso ** Monday, November 14, 2005 SIGN UP FOR THE PICASSO MAILING LIST: If you would like to be kept informed of computationally-oriented events in (and around) Princeton, please SUBSCRIBE to the PICASso mailing list by visiting https://lists.cs.princeton.edu/mailman/listinfo/picasso. This page also contains information on how to UNSUBSCRIBE. PLEASE FORWARD THIS MESSAGE TO OTHER COMPUTATIONALLY-ORIENTED RESEARCHERS WHO MAY BE INTERESTED IN THESE EVENTS, OR FUTURE PROGRAMS. THANKS!

1 0

[colloquium] PICASso Talk today!
by Sandy Barbu 07 Nov '05

07 Nov '05

** PICASso: ** Program in Integrative Information, Computer and Application Sciences ** www.cs.princeton.edu/picasso ** Monday, November 7, 2005 Interdisciplinary Computational Lunchtime Seminars www.cs.princeton.edu/picasso?computational_lunch.html ------------------ TITLE: Computing the Future of Biomedicine SPEAKER: Chris Johnson, Ph.D.,Director, Scientific Computing and Imaging Institute, Distinguished Professor, School of Computing, University of Utah TIME: Seminar begins at 12:30 p.m. (lunch provided at 12:20) LOCATION: Room 105, CS Small Auditorium ABSTRACT: Computers have changed the way we live, work, and even recreate. Now, they are transforming how we think about and treat human disease. Advanced techniques in biomedical computing, imaging, and visualization are already changing the face of biology and medicine in both research and clinical practice. These techniques have the potential to provide comprehensive models and views of the human body in unprecedented depth and detail. As a result, biomedical computing and visualization will help produce exciting new biomedical scientific discoveries and clinical treatments. In this talk, I will discuss the state of the art in biomedical computing, medical imaging, and visualization research and present examples of their vital roles in cardiology, neuroscience, neurosurgery, and radiology. SIGN UP FOR THE PICASSO MAILING LIST: ===================================== If you would like to be kept informed of computationally-oriented events in (and around) Princeton, please SUBSCRIBE to the PICASso mailing list by visiting https://lists.cs.princeton.edu/mailman/listinfo/picasso. This page also contains information on how to UNSUBSCRIBE. PLEASE FORWARD THIS MESSAGE TO OTHER COMPUTATIONALLY-ORIENTED RESEARCHERS WHO MAY BE INTERESTED IN THESE EVENTS, OR FUTURE PROGRAMS. THANKS! PICASso mailing list PICASso(a)lists.cs.princeton.edu https://lists.cs.princeton.edu/mailman/listinfo/picasso

1 0

[colloquium] PICASso Talk for Coloquium news
by Sandy Barbu 26 Oct '05

26 Oct '05

** PICASso: ** Program in Integrative Information, Computer and Application Sciences ** www.cs.princeton.edu/picasso ** Wednesday, October 26, 2005 Computation and Data Analysis in Biology and Information Sciences www.cs.princeton.edu/picasso?bio_info_lunch.html TITLE: A Maximum Entropy Approach to Species Distribution Modeling SPEAKER: Miroslav Dudik, Department of Computer Science, Princeton University TIME: Seminar begins at 12:30 p.m. (lunch provided 12:20) LOCATION: Room 402, Computer Science, Princeton University ABSTRACT: Species distribution modeling is an important problem in ecology and conservation biology. In this problem, we are given a list of locations where a species was observed and a set of environmental variables for the region interest, e.g. elevation, soil type and annual rainfall. Based on these, we would like to predict which conditions are favored by the species. Two main challenges for machine learning are the small number of occurrence localities and a lack of information where the species was NOT found (negative examples). To address both of these in a statistically sound manner, we propose to use the maximum entropy approach. In this talk, we describe the maximum entropy principle (maxent) and how it relates to the maximum likelihood. We describe a relaxation of maxent that gives rise to non-asymptotic performance guarantees which depend very moderately on the number or complexity of environmental variables. We also present a novel coordinate descent algorithm for computing maxent models. Finally, we mention how maxent can be used to address the problem of sample selection bias.

1 0

[colloquium] PICASso Talk TODAY "Aggregating Human Expertise: An Application for Alternating Projection Algorithms"
by Steven Kleinstein 17 Oct '05

17 Oct '05

Thought you might be interested in today's PICASso seminar on "Aggregating Human Expertise: An Application for Alternating Projection Algorithms". An announcement is below. Cheers, -Steve... ** PICASso: ** Program in Integrative Information, Computer and Application Sciences ** www.cs.princeton.edu/picasso ** Monday, October 17, 2005 ** ** Interdisciplinary Computational Lunchtime Seminars ** www.cs.princeton.edu/picasso?computational_lunch.html TITLE: Aggregating Human Expertise: An Application for Alternating Projection Algorithms SPEAKER: Joel B. Predd, Department of Electrical Engineering, Princeton University TIME: Seminar begins 12:30 pm (lunch available at 12:20) LOCATION: Room 302, 3rd Floor, Computer Science Building ABSTRACT: In the panel aggregation problem, each expert on a panel forecasts the chance of a set of events (about, say, the future state of the stock market). The events in question are logically complex and dependent; since the judges are human, the forecasts are plagued by probabilistic incoherence. Several methods have been proposed to fuse the experts' disparate forecasts into a coherent corpus. For problems of interest, these methods are impractical in theory and practice; applications in risk assessment, marketing, and business demand a new approach. What is an efficient algorithm for aggregating the advice of hundreds of judges who provide forecasts for thousands of events? In this talk, we discuss ongoing research aimed at addressing this question using alternating projection algorithms (e.g., the von Neumann-Halperin algorithm). In particular, we show how such classical algorithms can be applied to construct fast and scalable algorithms for aggregating forecasts of chance. We validate the algorithms with experiments in market and geopolitical forecasting. In addition, we discuss how the same methods are useful in other distributed decision making tasks. In particular, we discuss how von Neumann-Halperin can be applied to derive energy and bandwidth efficient training algorithms for distributed kernel regression in wireless sensor networks. Joint work with Professors Sanjeev Kulkarni (EE), Daniel Osherson (Psych), and Vincent Poor (EE). **************** If you would like to be kept informed of computationally-oriented events in (and around) Princeton, please SUBSCRIBE to the PICASso mailing list by visiting https://lists.cs.princeton.edu/mailman/listinfo/picasso. This page also contains information on how to UNSUBSCRIBE. PLEASE FORWARD THIS MESSAGE TO OTHER COMPUTATIONALLY-ORIENTED RESEARCHERS WHO MAY BE INTERESTED IN THESE EVENTS, OR FUTURE PROGRAMS. THANKS!

1 0

[colloquium] PICASso Talk Reminder: Prediction of protein function viagraph-theoretic analysis of interaction maps
by Sandy Barbu 12 Oct '05

12 Oct '05

TALK ANNOUNCEMENT: ------------------ TITLE: Prediction of protein function via graph-theoretic analysis of interaction maps SPEAKER: Elena Nabieva Department of Computer Science TIME: Wednesday, October 12, 2005 LOCATION: Room 402, Computer Science Building ABSTRACT: Determining protein function is one of the most important problems in the post-genomic era. For the typical proteome, there are no functional annotations for one-third or more of its proteins. Traditionally, computational methods to assign protein function have relied largely on sequence homology. Recently, the emergence of high-throughput experimental data sets led to a number of alternative, non-homology based methods for functional annotations. In particular, recent high-throughput experiments have determined proteome-scale protein physical interaction maps for several organisms. These physical interactions are complemented by an abundance of data about other types of functional relationships between proteins, including genetic interactions, knowledge about co-expression and shared evolutionary history. Taken together, these pairwise linkages can be used to build whole-proteome protein interaction maps. We have developed a network-flow based algorithm, FunctionalFlow, that exploits the underlying structure of protein interaction maps in order to predict protein function. In cross-validation testing on the yeast proteome, we show that FunctionalFlow has improved performance over previous methods in predicting the function of proteins with few (or no) annotated protein neighbors. By comparing several methods that use protein interaction maps to predict protein function, we demonstrate that FunctionalFlow performs well because it takes advantage of both network topology and some measure of locality. Finally, we show that performance can be improved substantially as we consider multiple data sources and use them to create weighted interaction networks. SIGN UP FOR THE PICASSO MAILING LIST: ===================================== If you would like to be kept informed of computationally-oriented events in (and around) Princeton, please SUBSCRIBE to the PICASso mailing list by visiting https://lists.cs.princeton.edu/mailman/listinfo/picasso. This page also contains information on how to UNSUBSCRIBE. PLEASE FORWARD THIS MESSAGE TO OTHER COMPUTATIONALLY-ORIENTED RESEARCHERS WHO MAY BE INTERESTED IN THESE EVENTS, OR FUTURE PROGRAMS. THANKS! _______________________________________________ PICASso mailing list PICASso(a)lists.cs.princeton.edu https://lists.cs.princeton.edu/mailman/listinfo/picasso _______________________________________________ announce mailing list announce(a)lists.cs.princeton.edu https://lists.cs.princeton.edu/mailman/listinfo/announce _______________________________________________ PICASso mailing list PICASso(a)lists.cs.princeton.edu https://lists.cs.princeton.edu/mailman/listinfo/picasso

1 0

[colloquium] Helen Berman is giving the CS colloquium on Wednesday
by Thomas A. Funkhouser 10 Oct '05

10 Oct '05

Helen Berman, director of the Protein Data Bank, will be visiting Princeton on Wednesday and giving a talk in the CS colloquium at 4PM in the small auditorium (Room 105). #################################################### The Protein Data Bank: Structure and Function Helen Berman The Protein Data Bank is the international repository for the structures of all biological macromolecules. The ways in which the data are represented, collected, archived, and queried will be described. The ways in which the PDB resource has been designed so as to accommodate a very diverse user community will be discussed.

1 0

[colloquium] TUTORIAL TODAY: Experimental Design and Statistical Analysis for Microarray Experiments
by Steven Kleinstein 07 Oct '05

07 Oct '05

** PICASso: ** Program in Integrative Information, Computer and Application Sciences ** www.cs.princeton.edu/picasso ** Experimental Design and Statistical Analysis ** for Microarray Experiments ** October 7 (1:30 - 5:00 PM) ** Small Auditorium, Computer Science Building (room 105) ** http://www.cs.princeton.edu/picasso?events.html PICASso is pleased to announce an introductory tutorial on "Experimental Design and Statistical Analysis for Microarray Experiments" taught by Thomas J. Downey (President, Partek Inc). Microarray data contains treatment and/or phenotype effects embedded in a sea of technical and biological noise. This mini-course will demonstrate how to use proven statistical methods of experiment design and analysis of variance (ANOVA) to reliably identify biological effects of interest while controlling and removing noise due to biological and technical nuisance effects. Attendees will learn what ANOVA means, what it does, and how it can be used to isolate and remove unwanted technical and biological noise, clearly revealing the signals from the biological factors of interest. In addition, estimates of ratios and fold-changes will be examined from a statistical perspective. The impact of the assumptions of normality, equal variance, and independence will also be addressed for small sample sizes and for large studies as well. Finally, a variety of statistical visualizations will be used to interpret the results of the analysis. This tutorial is designed for researchers performing microarray, or any genomic, or biological studies, but also useful for those wishing to learn more about designing and analyzing experiments in a way that results in substantial noise reduction. It will be held on Princeton's main campus today, October 7th (1:30 - 5:00 PM), Computer Science Building, small auditorium (room 105). All are welcome! Registration is not required.

1 0