- talks - lists.cs.princeton.edu

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

Friday Feb 22 noon: Ian Buck->John Danskin, nVidia, "GPU Computing"
by Adam Finkelstein 22 Feb '08

22 Feb '08

The talk is as planned at noon; however, due to a canceled flight we have a change of speaker and slight change in emphasis: Speaker: John Danskin Title: NVIDIA GeForce 8800 Graphics Processor: development and direction Time/Place: Today, noon, Computer Science Bldg, room 302 Abstract: The GeForce 8800 and its derivative architectures are the fastest available graphics processors. In an architectural departure, they are significantly more flexible than previouos processors. In this talk Dr. Danskin will discuss our goals for the 8800, the decision making process, new architectural features, performance, and some challenges for the future. Dr. Danskin is Vice President of GPU Architecture at NVIDIA, Chief Architect for the GeForce 8800 GPU, and holds a PhD in Computer Science from Princeton University. On Wed, Feb 20, 2008 at 10:58 PM, Adam Finkelstein <af(a)cs.princeton.edu> wrote: > Talk announcement: > > Speaker: Ian Buck, nVidia > Title: GPU Computing > Time/Place: Friday, noon, Computer Science Bldg, room 302 > > Abstract: > > Many researchers have observed that general purpose computing with > programmable graphics hardware (GPUs) has shown promise to solve many of > the world's compute intensive problems, many orders of magnitude faster > the conventional CPUs. The challenge has been working within the > constraints of a graphics programming environment to leverage this huge > performance potential. GPU computing with CUDA is a new approach to > computing where hundreds of on-chip processor cores simultaneously > communicate and cooperate to solve complex computing problems, > transforming the GPU into a massively parallel processor. The NVIDIA > C-compiler for the GPU provides a complete development environment gives > developers the tools they need to solve new problems in > computation-intensive applications such as product design, data > analysis, technical computing, and game physics. In this talk, I will > provide a brief history of computing with GPUs, how CUDA can solve > compute intensive problems, and where GPU computing will be going in the > future. > > Bio: > > Ian Buck completed his Ph.D. at the Stanford Graphics Lab in 2004. His > thesis was titled "Stream Computing on Graphics Hardware," researching > programming models and computing strategies for using graphics hardware > as a general purpose computing platform. His work included developing > the "Brook" software toolchain for abstracting the GPU as a general > purpose streaming coprocessor. Ian received is B.S.E from Princeton and > was a proud member of the Princeton CS Graphics Group. He currently > works for NVIDIA as the GPU-Compute software manager. >

1 0

Z Barutcuoglu preFPO
by Melissa M Lawson 21 Feb '08

21 Feb '08

Zafer Barutcuoglu will present his preFPO on Thursday February 28 at 1:30 PM in Room 402. The members of his committee are: Rob Schapire (advisor); Olga Troyanskaya and David Blei (readers); Mona Singh and Fei-Fei Li (non-readers). Everyone is invited to attend his talk. His abstract follows below. ---------------------------------- Classification problems encountered in real-life applications often have domain-specific structural information available on the measured data, which cannot be readily accommodated by conventional machine learning algorithms. Ignoring the structure and blindly running a conventional algorithm on the numerical data can compromise the quality of solutions. This thesis provides answers to two such complementary settings; one where there is a hierarchy among multiple class labels (output structure), and one where the input features are known to be sequentially correlated (input structure). Probabilistic graphical models are used to encode the dependencies, and efficient Bayesian inference algorithms are used for parameter estimation. While both scenarios are motivated by real bioinformatics problems, namely gene function prediction and aneuploidy-based cancer classification, they have applications in other domains as well, such as computer graphics, music, and text classification.

1 0

Friday Feb 22 noon: Ian Buck, nVidia, "GPU Computing"
by Adam Finkelstein 20 Feb '08

20 Feb '08

Talk announcement: Speaker: Ian Buck, nVidia Title: GPU Computing Time/Place: Friday, noon, Computer Science Bldg, room 302 Abstract: Many researchers have observed that general purpose computing with programmable graphics hardware (GPUs) has shown promise to solve many of the world's compute intensive problems, many orders of magnitude faster the conventional CPUs. The challenge has been working within the constraints of a graphics programming environment to leverage this huge performance potential. GPU computing with CUDA is a new approach to computing where hundreds of on-chip processor cores simultaneously communicate and cooperate to solve complex computing problems, transforming the GPU into a massively parallel processor. The NVIDIA C-compiler for the GPU provides a complete development environment gives developers the tools they need to solve new problems in computation-intensive applications such as product design, data analysis, technical computing, and game physics. In this talk, I will provide a brief history of computing with GPUs, how CUDA can solve compute intensive problems, and where GPU computing will be going in the future. Bio: Ian Buck completed his Ph.D. at the Stanford Graphics Lab in 2004. His thesis was titled "Stream Computing on Graphics Hardware," researching programming models and computing strategies for using graphics hardware as a general purpose computing platform. His work included developing the "Brook" software toolchain for abstracting the GPU as a general purpose streaming coprocessor. Ian received is B.S.E from Princeton and was a proud member of the Princeton CS Graphics Group. He currently works for NVIDIA as the GPU-Compute software manager.

1 0