- talks - lists.cs.princeton.edu

PLOrk performance tonight
by Ge Wang 21 Nov '06

21 Nov '06

Dear all, This event won't be a talk (we hope), but it seemed more relevant to announce here than to [building] or [downtime]. http://ffmup.org/nov_21_06.html --- who/what: The Princeton Laptop Orchestra (PLOrk) presents an evening of new works for computer-mediated chamber music (duo/trio/quartet), composed and performed by members of the Fall 2006 ensemble and seminar: Alan Tormey | Ananya Misra | Andrea Mazzariello | Anne Hege | Ge Wang | John Fontein | Laurie Hollander | Matt Hoffman | Margaret R. Daniel | Michael Hammond | Perry Cook | Rebecca Fiebrink | Samson Young | Scott Elmegreen | Scott Smallwood | Spencer Salazar --- when: tonight 9:00pm (Tuesday) where: Terrace Club (free admission) why: there is usually free beer at ffmup events; new music; free beer! Hope to see you there! Best, Ge!

1 0

Michael J Freedman, Mon Nov 20, 1:30
by Vivek Pai 16 Nov '06

16 Nov '06

Michael J Freedman, the NYU graduate student, will be speaking on Monday at 1:30 in room 402. His talk title and abstract are included below. If you'd like to talk with him, please sign up in /n/fs/department/schedules/visitors/visitfall06/freedman Just to avoid some confusion that occurred the last time he visited, please note that this is not Michael H. Freedman, the Fields Medal winner. =================== RE: Fighting Spam with Reliability and Privacy Mike Freedman NYU / Stanford http://www.scs.stanford.edu/mfreed/ mfreed(a)scs.stanford.edu ----- The explosive growth in unwanted email has prompted the development of techniques for the rejection of email, intended to shield recipients from the onerous task of identifying the legitimate email in their inboxes amid a sea of spam. Unfortunately, widely-used content-based filtering systems have converted the spam problem into a false positive one: Email has become unreliable. We present Reliable Email (RE: [1]), a new whitelisting system that incurs zero false positives among socially-connected users yet populates whitelists automatically by exploiting transitive trust relationships. Further, while RE: permits a recipient to discover whether other users have whitelisted the sender, it preserves the privacy of email contacts with a cryptographic Private Matching [2] protocol. Using real email traces from two sites, we demonstrate that RE: renders a significant fraction of received email reliable. Our evaluation also shows that RE: can prevent up to 88% of the false positives incurred by common email rejection systems. Finally, we propose a more formal definition of security for verifying social connectedness in a privacy-preserving fashion [3]. In the process, we identify a mismatch between RE:'s goals and [2]'s properties, enabling us to construct new cryptographic protocols that are either more efficient (based only on symmetric operations) or achieve stronger guarantees (namely, non-transferability) through bilinear pairings. Using such, RE: can provide privacy-preserving social whitelisting with millisecond overhead. 1. Re: Reliable Email Garriss, Kaminsky, Freedman, Karp, Mazieres, and Yu, NSDI '06 2. Efficient Private Matching and Set Intersection Freedman, Nissim, and Pinkas, EUROCRYPT '04 3. Efficient Private Techniques for Verifying Social Proximity Freedman and Nicolosi, Submitted Nov '06 ----- Michael J. Freedman is a doctoral student at NYU, currently visiting Stanford University. He received his M.Eng. and S.B. degrees from MIT. His research interests broadly focus on security, distributed systems, and cryptography. Among other things, he developed the Coral content distribution network and OASIS anycast service, which serve more than a million users daily (see www.coralcdn.org). In 2006, he co-founded Illuminics Systems, which has been acquired by Quova, Inc.

1 0

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