- talks - lists.cs.princeton.edu

Speaker Today 4:15pm COS 105
by Ginny Hogan 05 Mar '08

05 Mar '08

Konstantinos Daskalakis, UC Berkeley, will present his talk "Computing Equilibria in Games" at 4:15pm Computer Science Room 105.

1 0

11am Wed Mar 5 talks on overlays and P2P in room CS 401
by Jennifer Rexford 04 Mar '08

04 Mar '08

Speaker: Taekyoung Kwon, Seoul National University Time: 11:00am - 12:15pm, Mar/5, Wednesday Room: CS 401 Talk #1: A Decentralized and Autonomous Content-centric Overlay Networking (DACON) Architecture for Pervasive Services (1) More and more wireless technologies are emerging for Internet access. However, end users who want pervasive connectivity cannot afford to subscribe to all the wireless Internet services. To provide content access services for the users without additional Internet access cost, we pay attention to user-deployable devices such as IEEE 802.11 access points and cellular home base stations. Exploiting these devices, we propose a decentralized autonomous content-centric overlay networking (DACON) architecture for pervasive content access. To encourage individuals to participate in DACON, we discuss how to incorporate financial incentive issues, so that those who deploy DACON hosts can profit by content distribution. Talk #2: Climber: An Incentive-based Resilient Peer-to-Peer System for Live Streaming Services (2) P2P systems are cost-effective and can be easily deployed only by leveraging the participating peers' resources (i.e., upload link bandwidth) to distribute contents. In this paper, we propose Climber, an incentive-based resilient P2P system, for live streaming services. Climber encourages each peer to provide more upload link bandwidth to the system, and embodies an incentive mechanism that improves resilience under high churning rate. The structure of Climber is a hybrid of a tree and a mesh,which self-improves and adapts to network churning rate. Simulation results are given to evaluate the performance of the proposed protocol. Short bio Taekyoung Kwon is an assistant professor at the School of Computer Science and Engineering, Seoul National University (SNU) since 2004. Before joining SNU, he was a Postdoctoral Research Associate at University of California, Los Angeles (UCLA), and at City University New York (CUNY). He obtained BS, MS and PhD degrees from the Department of Computer Engineering, SNU, South Korea, in 1993, 1995 and 2000, respectively. During his graduate program, he was a visiting student at IBM T.J. Watson Research Center and at University of North Texas. His research interest lies in wireless networks, mobile networks, P2P networking, and ubiquitous computing.

1 0

last reminder: talk today at 1:30pm by Prof. Jianbo Shi
by Fei-Fei Li 03 Mar '08

03 Mar '08

Visual Thinking with Graph Network Jianbo Shi Assistant Professor Computer and Information Science University of Pennsylvania Time/Location: 1:30pm Mon Mar 3, CS 301 Many visual perception tasks are fundamentally NP-hard computational problems. Solving these problems robustly requires thinking through combinatorially many hypothesis. Despite this, our human visual system performs these tasks effortlessly. How is this done? I would like to make two points on this topic. First, formulating visual thinking as NP-hard computation tasks has an important advantage: visual routines can be analyzed precisely to identify their behaviors independently of their implementations. Second, I will show there is a class of graph optimization problems which can be implemented using a distributed network system with physical (and plausible biological) interpretation. I will demonstrate this graph based approach for: 1) image segmentation using Normalized Cuts with explanations for illusory contours, visual pop out and attention; 2) salient contour grouping using Untangling Cycle; and 3) contour context selection for shape detection. -- --------------------------------------------- Li, Fei-Fei Ph.D. (publish under L. Fei-Fei) Assistant Professor Computer Science Dept. Princeton University 35 Olden St. Princeton, NJ 08540 Tel: (609)258-8130 Office: Room 211, CS Building Website: http://vision.cs.princeton.edu ---------------------------------------------

1 0

Talk on Wed. 3/5/2008 4:15PM
by Ginny Hogan 03 Mar '08

03 Mar '08

Konstantinos Daskalakis, UC Berkeley, will present his talk "Computing Equilibria in Games" Wed 3/5/2008 at 4:15pm Computer Science Room 105 - Abstract - Game Theory is important for the study of large competitive environments, such as the Internet, the market, and even social and biological systems. A key tool in analyzing such systems (games) is the study of their stable states, that is, their equilibria. Understanding the properties of equilibria can give insights into the effectiveness of economic policies, engineering decisions, etc. However, due to the large scale of most interesting games, the problem of computing equilibria cannot be separated from complexity considerations. Motivated by this challenge, I will discuss the problem of computing equilibria in games. I will show first that computing a Nash equilibrium is an intractable problem. It is not NP-complete, since, by Nash's theorem, an equilibrium is always guaranteed to exist, but it is at least as hard as solving any fixed point computation problem, in a precise complexity-theoretic sense. In view of this hardness result, I will present algorithms for computing approximate equilibria. In particular, I will describe algorithms that achieve constant factor approximations for 2-player games and give a quasi-polynomial time approximation scheme for the multi-player setting. Finally, I will consider a very natural and important class of games termed anonymous games. In these games every player is oblivious to the identities of the other players; examples arise in auction settings, congestion games, and social phenomena. I will introduce a polynomial time approximation scheme for the anonymous setting and provide surprising connections to Stein's method in probability theory. Bio: Constantinos (or Costis) Daskalakis grew up in Athens, Greece, where he received his undergraduate degree in Electrical and Computer Engineering from the National Technical University of Athens. In 2004 he moved to California to pursue a Ph.D. in Computer Science at U.C. Berkeley under the supervision of Professor Christos H. Papadimitriou. Costis's work has focused on computational game theory and applied probability, in particular the computation of equilibria in games, the study of social networks, and computational problems in biology. His research is motivated by two questions: "How does the algorithmic perspective influence economics, biology, physics, and the social sciences?" And, "how does the study of computational problems arising from areas outside computer science transform the theory of computation?"

1 0

Prof. Jianbo Shi on graph theories @ 1:30pm CS 301, Mon Mar 3
by Fei-Fei Li 02 Mar '08

02 Mar '08

Visual Thinking with Graph Network Jianbo Shi Assistant Professor Computer and Information Science University of Pennsylvania Time/Location: 1:30pm Mon Mar 3, CS 301 Many visual perception tasks are fundamentally NP-hard computational problems. Solving these problems robustly requires thinking through combinatorially many hypothesis. Despite this, our human visual system performs these tasks effortlessly. How is this done? I would like to make two points on this topic. First, formulating visual thinking as NP-hard computation tasks has an important advantage: visual routines can be analyzed precisely to identify their behaviors independently of their implementations. Second, I will show there is a class of graph optimization problems which can be implemented using a distributed network system with physical (and plausible biological) interpretation. I will demonstrate this graph based approach for: 1) image segmentation using Normalized Cuts with explanations for illusory contours, visual pop out and attention; 2) salient contour grouping using Untangling Cycle; and 3) contour context selection for shape detection. -- --------------------------------------------- Li, Fei-Fei Ph.D. (publish under L. Fei-Fei) Assistant Professor Computer Science Dept. Princeton University 35 Olden St. Princeton, NJ 08540 Tel: (609)258-8130 Office: Room 211, CS Building Website: http://vision.cs.princeton.edu ---------------------------------------------

1 0

11am Fri Mar 14 talk on road/traffic monitoring by Venkat Padmanabhan from MSR
by Jennifer Rexford 01 Mar '08

01 Mar '08

Hi folks, On Friday March 14, Venkat Padmanabhan -- who leads the Mobility, Networks, and Systems group at Microsoft Research India -- will be visiting. See http://research.microsoft.com/research/mns/default.aspx His talk is at 11am in the small auditorium (CS 105), with the title/abstract below. He'd also like to give interested folks an overview of the MSR lab in Bangalore, and to discuss career opportunities for internships, research positions, and visiting researchers. That session will start run from 2:15-3:30pm, in a room to-be-announced later. Please let me know if you'd like to meet with Venkat and/or join for lunch at noon. -- Jen Speaker: Venkat Padmanabhan Title: TrafficSense: Rich Road and Traffic Monitoring Using Mobile Smartphones Abstract: We consider the problem of monitoring road and traffic conditions in a city. Prior work in this area has required the deployment of dedicated sensors on vehicles and/or on the roadside, or the tracking of mobile phones by service providers. Furthermore, prior work has largely focused on the developed world, with its relatively simple traffic flow patterns. In fact, traffic flow in cities of the developing regions, which comprise much of the world, tends to be much more complex owing to varied road conditions (e.g., potholed roads), chaotic traffic (e.g., a lot of braking and honking), and a heterogeneous mix of vehicles (2-wheelers, 3-wheelers, cars, buses, etc.). To monitor road and traffic conditions in such a setting, we present TrafficSense, a system that piggybacks on smartphones that users carry around with them. Each participating smartphone performs rich sensing using its communication radios, GPS, accelerometer, and microphone, scans for and exchanges information from other participating phones in its neighbourhood, and reports processed information back to a central server for aggregation and reporting. We discuss key technical challenges, including energy optimization and the need for hands-free operation, present the design of TrafficSense, including how information from multiple sensors is combined to make inferences, and evaluate it in various road and traffic settings in Bangalore. (Joint work with Prashanth Mohan and Ram Ramjee.) Bio: Venkat Padmanabhan is a Senior Researcher and Research Manager at Microsoft Research India in Bangalore, where he founded and now leads the Mobility, Networks, and Systems group. Venkat was previously with Microsoft Research Redmond for 8.5 years. His research interests are in networked systems and his current projects focus on mobile and sensor systems, and network management. His professional service has included serving as program (co-)chair for ACM NOSSDAV 2004, ACM IMC 2005, and IEEE HotWeb 2008, and as an affiliate faculty member at the University of Washington, where he has taught and served in student thesis committees. Venkat holds a B.Tech. from IIT Delhi and an M.S. and Ph.D. from UC Berkeley, all in Computer Science.

1 0

talk is starting in 5 minutes
by Ginny Hogan 27 Feb '08

27 Feb '08

Christiane Fellbaum's talk is starting in 5 minutes - 4:15pm - cos 105

1 0

talk today 2/27
by Ginny Hogan 27 Feb '08

27 Feb '08

Christiane Fellbaum, Princeton, will present her talk "A lexical resource for Natural Language Processing" at 4:15pm today - Computer Science Room 105 -

1 0

E Chlamtac preFPO
by Melissa M Lawson 26 Feb '08

26 Feb '08

Eden Chlamtac will present his preFPO on Tuesday, March 4, at 4:30PM in Room 402. The members of his committee are Sanjeev Arora (advisor), Moses Charikar and Bernard Chazelle (readers), and Boaz Barak and Ken Steiglitz (non-readers). Everyone is invited to attend his talk. His abstract follows below. ------------------------------------------------- Title: Non-Local Analysis of SDP-Based Approximation Algorithms Abstract: Semidefinite Programming (SDP) has been at the core of many approximation algorithms since the seminal work of Goemans and Williamson on MAX-CUT. Analysis of the approximation guarantee afforded by SDP-based approximation algorithms has traditionally relied on a comparison of local random events to corresponding local structures in the input. A marked departure from this approach was demonstrated recently in the work of Arora, Rao, and Vazirani on SPARSEST CUT, where a more nuanced probabilistic argument was used to combine local random events, thus yielding an improved approximation guarantee. I will describe a number of SDP-based algorithms which admit a non-local analysis of their approximation guarantee. In one case, the analysis is inspired by the approach of Arora-Rao-Vazirani, while in other cases, both the algorithm and the analysis make novel use of SDP hierarchies. These hierarchies give progressively tighter relaxations of combinatorial problems. Previously they had been shown not to yield any significant improvement in the approximation of various important problems, thus the results I will discuss mark a first positive use of these hierarchies. In particular, I will describe the following results: 1. A proof that the algorithm of Blum and Karger for coloring 3-colorable graphs yields a legal coloring using at most O(n^0.2130) colors (as opposed to the original guarantee of O(n^0.2142)). 2. An algorithm for coloring 3-colorable graphs which yields a legal coloring using at most O(n^0.2072) colors. This algorithm extends that of Blum-Karger, and uses the third level of the Lasserre SDP hierarchy. 3. An approximation algorithm which finds an independent set of size n^poly(gamma) in any 3-uniform hypergraph which contains an independent set of size gamma*n (previous algorithms were known only for gamma>1/2). This algorithm uses n^(1/poly(gamma)) levels of the Lasserre SDP hierarchy.

1 0

Speaker Wed 2/27 -
by Ginny Hogan 25 Feb '08

25 Feb '08

Christiane Fellbaum, Princeton, will present her talk "WordNet: A lexical resource for Natural Language Processing" at 4:15pm Computer Science Room 105 -

1 0