- talks - lists.cs.princeton.edu

Gödel Centenary Program this Friday
by Moses Charikar 15 Nov '06

15 Nov '06

On Friday, November 17, from 2:00 p.m. to 6:30 p.m. in Wolfensohn Hall, the Institute will host A Program to Mark the Centenary Year of the Birth of Kurt Gödel. The event is free and open to the public; reservations are not required. Seating is on a first come, first served basis. The program will consist of talks aimed at a general audience on the life and work of Kurt Gödel (1906-1978) and his impact on mathematics, philosophy, and computer science. Participants include: John Burgess, Princeton University; John W. Dawson, Jr., The Pennsylvania State University; Solomon Feferman, Stanford University; Juliette Kennedy, University of Helsinki; Karl Sigmund, University of Vienna; and Avi Wigderson, Institute for Advanced Study. For additional information about the program, please visit http://www.ias.edu/SpFeatures/kurt_godel/godel-4.php. There is also background on Gödel's life and work accessible from the IAS homepage, www.ias.edu. An exhibition of posters on Gödel, created by the University of Vienna, will remain on view on the main floor of Fuld Hall through Sunday, December 3. --Moses

1 0

Talk Today, 4pm - CS 105 - Serafim Batzoglou
by Ginny Hogan 07 Nov '06

07 Nov '06

Serafim Batzoglou will present his talk "Models and Algorithms for Genomic Sequences, Proteins, and Networks of Protein Interactions" Wednesday Nov 8th at 4:00pm Computer Science Room 105.

1 0

manfred warmuth talk at 4pm today
by Robert Schapire 25 Oct '06

25 Oct '06

Manfred Warmuth from UC Santa Cruz will be giving today's colloquium at 4pm in CS room 105. See abstract below, or visit http://www.cs.princeton.edu/research/colloquia.php Rob Schapire ------------------------------------------------------------------------ *Leaving the Span* *Manfred K. Warmuth* University of California, Santa Cruz When linear models are too simple then the following "kernel trick" is commonly used: Expand the instances into a high-dimensional feature space and use any algorithm whose linear weight vector in feature space is a linear combination of the expanded instances. Linear models in feature space are typically non-linear in the original space and seemingly more powerful. Also dot products can still be computed efficiently via the use of a kernel function. However we discuss a simple sparse linear problem that is hard to learn with any algorithm that uses a linear combination of the embedded training instances as its weight vector, no matter what embedding is used. We show that these algorithms are inherently limited by the fact that after seeing /k/ instances only a weight space of dimension /k/ can be spanned. Surprisingly the same problem can be efficiently learned using the exponentiated gradient (EG) algorithm: Now the component-wise logarithms of the weights are essentially a linear combination of the training instances. This algorithm enforces "additional constraints" on the weights (all must be non-negative and sum to one) and in some cases these constraints alone force the rank of the weight space to grow as fast as /2^k /. (Joint work with S.V.N. Vishwanathan!) ------------------------------------------------------------------------ -- Princeton University Department of Computer Science 35 Olden Street Princeton, NJ 08540 USA tel: +1 609 258 7726 fax: +1 609 258 1771 Computer Science Building, Room 407 http://www.cs.princeton.edu/~schapire schapire(a)cs.princeton.edu

1 0

talk by Yoav Freund -- Friday, 7/14, 2:30, 402 CS
by Robert Schapire 11 Jul '06

11 Jul '06

Yoav Freund will be giving a talk this Friday, July 14 at 2:30pm in room 402 of the CS building. Title and abstract follow below. ------------------------------------------------------------------------ Title: Using adaptive computer vision to analyze biomedical images Speaker: Yoav Freund Computer Science and Engineering, University of California, San Diego http://www.cse.ucsd.edu/~yfreund Date: Friday, July 14, 2:30pm Place: Room 402, CS building Host: Rob Schapire Abstract: The rapid advancement of biomedical imaging techniques such as fluorescence microscopy, non-linear optics, MRI and ultra-sound make it now possible to observe the time evolution of mechanical and biochemical processes in cells and in the human body at a resolution unimaginable a decade ago. This ability to measure opens up an incredible range of new possibilities for research in biology and in medicine. However, a major challenge along the way is the formidable amount of manual work required to extract meaningful quantitative results from the enormous amounts of collected image data. I suggest a combination of computer vision and machine learning techniques to tackle such problems. In this talk I describe some of my current work applying these ideas in several projects: 1. The study of the dynamics of lamellipodia in spreading cells. 2. The study of regulatory networks in the development of drosophila embryos. 3. Detection of protein micro-crystals for X-ray crystalography. 4. Detection and grading of prostate cancer using microscope images of biopsies. I will conclude with some of the lessons I have learned from these projects and some words on my current approach to automating image analysis tasks. ------------------------------------------------------------------------ -- Princeton University Department of Computer Science 35 Olden Street Princeton, NJ 08540 USA tel: +1 609 258 7726 fax: +1 609 258 1771 Computer Science Building, Room 407 http://www.cs.princeton.edu/~schapire schapire(a)cs.princeton.edu

1 0

Talk starting in five minutes... Wed Jun 14 10:30am talk on overlay networks
by Jennifer Rexford 14 Jun '06

14 Jun '06

-----Original Message----- From: talks-bounces(a)lists.cs.princeton.edu [mailto:talks-bounces@lists.cs.princeton.edu] On Behalf Of Jennifer Rexford Sent: Tuesday, June 13, 2006 7:50 PM To: talks(a)lists.cs.princeton.edu Subject: [talks] Wed Jun 14 10:30am talk on overlay networks Reminder... TALK ANNOUNCEMENT Speaker: Professor John Chi-Shing Lui, Chinese University of Hong Kong Title: On the Interaction of Multiple Overlay Routing Date/time: 10:30am-11:30am on Wednesday June 14 Location: room 105 in the CS building (i.e., the small auditorium) Abstract: In the past few years, overlay networks have received much attention but there has been little study on the ``interaction'' of multiple, co-existing overlays on top of a physical network. In addition to previously introduced concept of overlay routing strategy such as the selfish routing, we introduce a new strategy called ``overlay optimal routing''. Under this routing policy, the overlay seeks to minimize its weighted average delay by splitting its traffic onto multiple paths. We establish that (i) the overlay optimal routing can achieve better delay compared to selfish routing, and (ii) there exists a Nash equilibrium when multiple overlays adopt this strategy. Although an equilibrium point exists for overlay optimal routing and possibly for selfish routing, we show that the interaction of multiple overlay routing may not be Pareto optimal and that some fairness anomalies of resource allocation may occur. This is worthy of attention since overlay may not know the existence of other overlays and they will continue to operate at this sub-optimal point. We explore two pricing schemes to resolve the above issues. We show that by incorporating a proper pricing scheme, the overlay routing game can be led to the desired equilibrium and avoid the problems mentioned above. Extensive fluid-based simulations are performed to support the theoretical claims. The collaborators of this work include Joe W.J. Jiang and Dah-Ming Chiu. Bio: John Chi-Shing Lui was born in Hong Kong. He received his Ph.d. in Computer Science from UCLA. After his graduation, he joined the IBM Almaden Research Laboratory/San Jose Laboratory and participated in various R&D projects on file systems and parallel I/O architectures. He later joined the Department of Computer Science and Engineering at the Chinese University of Hong Kong. His research interests span both in system and in theory/mathematics, with current research interests in theoretic/applied topics in data networks, distributed multimedia systems, network security, OS design issues and mathematical optimization and performance evaluation theory. John's personal interests include films and general reading. _______________________________________________ talks mailing list talks(a)lists.cs.princeton.edu https://lists.cs.princeton.edu/mailman/listinfo/talks

1 0

Wed Jun 14 10:30am talk on overlay networks
by Jennifer Rexford 13 Jun '06

13 Jun '06

Reminder... TALK ANNOUNCEMENT Speaker: Professor John Chi-Shing Lui, Chinese University of Hong Kong Title: On the Interaction of Multiple Overlay Routing Date/time: 10:30am-11:30am on Wednesday June 14 Location: room 105 in the CS building (i.e., the small auditorium) Abstract: In the past few years, overlay networks have received much attention but there has been little study on the ``interaction'' of multiple, co-existing overlays on top of a physical network. In addition to previously introduced concept of overlay routing strategy such as the selfish routing, we introduce a new strategy called ``overlay optimal routing''. Under this routing policy, the overlay seeks to minimize its weighted average delay by splitting its traffic onto multiple paths. We establish that (i) the overlay optimal routing can achieve better delay compared to selfish routing, and (ii) there exists a Nash equilibrium when multiple overlays adopt this strategy. Although an equilibrium point exists for overlay optimal routing and possibly for selfish routing, we show that the interaction of multiple overlay routing may not be Pareto optimal and that some fairness anomalies of resource allocation may occur. This is worthy of attention since overlay may not know the existence of other overlays and they will continue to operate at this sub-optimal point. We explore two pricing schemes to resolve the above issues. We show that by incorporating a proper pricing scheme, the overlay routing game can be led to the desired equilibrium and avoid the problems mentioned above. Extensive fluid-based simulations are performed to support the theoretical claims. The collaborators of this work include Joe W.J. Jiang and Dah-Ming Chiu. Bio: John Chi-Shing Lui was born in Hong Kong. He received his Ph.d. in Computer Science from UCLA. After his graduation, he joined the IBM Almaden Research Laboratory/San Jose Laboratory and participated in various R&D projects on file systems and parallel I/O architectures. He later joined the Department of Computer Science and Engineering at the Chinese University of Hong Kong. His research interests span both in system and in theory/mathematics, with current research interests in theoretic/applied topics in data networks, distributed multimedia systems, network security, OS design issues and mathematical optimization and performance evaluation theory. John's personal interests include films and general reading.

1 0

Wed Jun 14 10:30am talk on overlay networks
by Jennifer Rexford 06 Jun '06

06 Jun '06

TALK ANNOUNCEMENT Speaker: Professor John Chi-Shing Lui, Chinese University of Hong Kong Title: On the Interaction of Multiple Overlay Routing Date/time: 10:30am-11:30am on Wednesday June 14 Location: room 105 in the CS building (i.e., the small auditorium) Abstract: In the past few years, overlay networks have received much attention but there has been little study on the ``interaction'' of multiple, co-existing overlays on top of a physical network. In addition to previously introduced concept of overlay routing strategy such as the selfish routing, we introduce a new strategy called ``overlay optimal routing''. Under this routing policy, the overlay seeks to minimize its weighted average delay by splitting its traffic onto multiple paths. We establish that (i) the overlay optimal routing can achieve better delay compared to selfish routing, and (ii) there exists a Nash equilibrium when multiple overlays adopt this strategy. Although an equilibrium point exists for overlay optimal routing and possibly for selfish routing, we show that the interaction of multiple overlay routing may not be Pareto optimal and that some fairness anomalies of resource allocation may occur. This is worthy of attention since overlay may not know the existence of other overlays and they will continue to operate at this sub-optimal point. We explore two pricing schemes to resolve the above issues. We show that by incorporating a proper pricing scheme, the overlay routing game can be led to the desired equilibrium and avoid the problems mentioned above. Extensive fluid-based simulations are performed to support the theoretical claims. The collaborators of this work include Joe W.J. Jiang and Dah-Ming Chiu. Bio: John Chi-Shing Lui was born in Hong Kong. He received his Ph.d. in Computer Science from UCLA. After his graduation, he joined the IBM Almaden Research Laboratory/San Jose Laboratory and participated in various R&D projects on file systems and parallel I/O architectures. He later joined the Department of Computer Science and Engineering at the Chinese University of Hong Kong. His research interests span both in system and in theory/mathematics, with current research interests in theoretic/applied topics in data networks, distributed multimedia systems, network security, OS design issues and mathematical optimization and performance evaluation theory. John's personal interests include films and general reading.

1 0

[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