- talks - lists.cs.princeton.edu

S Comandur preFPO
by Melissa M Lawson 19 Mar '08

19 Mar '08

Seshadhri Comandur will present his preFPO on Wednesday March 26 at 3:30PM in Room 402. The members of his committee are: Bernard Chazelle, advisor; Moses Charikar and Sanjeev Arora, readers; Boaz Barak and Rob Schapire, nonreaders. Everyone is invited to attend his talk. The abstract follows below. --------------------------------------- Title : Dealing with data : Online reconstruction and self-improving algorithms Abstract : With the ubiquity of large data sets, reading the whole input might itself by a luxury. Consider some large dataset that is supposed to (but does not) have some structural property, e.g., a set of numbers should be sorted, a set of points should in convex position, or a graph should be an expander. Let the input be represented by a function f (over a suitable domain and range). Our aim is to output a function g that satisfies the property, and does not differ too much from f. Furthermore, we want to generate g in an online sublinear fashion : given a domain point x, we can output g(x) in sublinear time. This is the problem of online reconstruction, which naturally has connections to property testing and other sublinear slgorithms. We study the reconstruction problem in various settings - monotonicity of functions over lattices, convexity of surfaces, and bounded degree expanders. The results obtained are also interesting in their own right, and provide sublinear algorithmic tools to study these properties. In an interesting aside, we use sublinear tools for online learning problems. We define stronger performance measures for learning problems, and provde very efficient algorithms that attain this performance. One of the key insights is how tools from the sublinear and streaming world allow us to construct efficient learning algorithms. Input in the real world is not always worst-case, and probably comes from some low entropy distribution over the input space. It seems natural that algorithms should run faster given this constraint. Is it possible to learn enough about the input distribution to optimize running time? This is the problem of designing self-improving algorithms, which can tune themselves to the input distribution and cut down their running time. We prove a variety of results for the classic problem of sorting numbers, and then extend these to computational geometry world.

1 0

11am Fri March 14 seminar on road/traffic monitoring in CS 105
by Jennifer Rexford 14 Mar '08

14 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 1

Talk today 3/12 - 4:15PM - Computer Science Room 105 -
by Ginny Hogan 12 Mar '08

12 Mar '08

Reinventing Partially Observable Reinforcement Learning Eyal Amir University of Illinois, Urbana-Champaign Many complex domains offer limited information about their exact state and the way actions affect them. There, autonomous agents need to make decisions at the same time that they learn action models and track the state of the domain. This combined problem can be represented within the framework of reinforcement learning in POMDPs, and is known to be computationally difficult. In this presentation I will describe a new framework for such decision making, learning, and tracking. This framework applies results that we achieved about updating logical formulas (belief states) after deterministic actions. It includes algorithms that represent and update the set of possible action models and world states compactly and tractably. It makes a decision with this set, and updates the set after taking the chosen action. Most importantly, and somewhat surprisingly, the number of actions that our framework takes to achieve a goal is bounded polynomially by the length of an optimal plan in a fully observable, fully known domain, under lax conditions. Finally, our framework leads to a new stochastic-filtering approach that has better accuracy than previous techniques. * Joint work with Allen Chang, Hannaneh Hajishirzi, Stuart Russell, Dafna Shahaf, and Afsaneh Shirazi (IJCAI'03,IJCAI'05,AAAI'06,ICAPS'06,IJCAI'07,AAAI'07).

1 0

Talk by Yaron Lipman today at noon
by Tom Funkhouser 07 Mar '08

07 Mar '08

Yaron Lipman from Tel Aviv University will give a talk today at noon in CS 401. Title: Geometric Deformations. Abstract: Deforming objects in a "shape preserving" manner is a challenging problem with various applications in geometric modeling and computer graphics. In this talk I will examine two geometric-driven approaches to the problem. First, reformulating the problem using the notion of Cartan's moving frames reveals an intriguing relationship between harmonic maps into the group of rotations and shape preserving deformations. The moving frames are known in differential geometry for their ability to simplify some surface theory argumentation. Their employment leads to rather simple algorithms for shape deformation and shape blending of discrete surfaces (meshes). I will present the moving frames as rigid-motion invariant surface representation which is suited for deformations and shape blending. Then I will discuss the optimal rotation field between two isometric surfaces and its use in the context of surface deformation. Second, I will present a recent result demonstrating a closed-form solution to shape preserving space deformations. The new scheme guarantees a pure conformal mapping in 2D and quasi-conformal mappings in 3D. This generalizes recent interesting affine-invariant free form deformation techniques and provides an extremely fast algorithm for shape preserving deformations. Short Bio: Yaron Lipman is a PhD candidate at Tel-Aviv University. He received the BSc degree in mathematics and computer science from Tel Aviv University in 2003. His research interests are in applied geometry, approximations and computer graphics.

1 0

P Shilane FPO
by Melissa M Lawson 06 Mar '08

06 Mar '08

Phil Shilane will present his FPO on Thursday March 13 at 9AM in Room 402. The members of his committee are: Tom Funkhouser, advisor; Szymon Rusinkiewicz and Adam Finkelstein, readers; Andrea LaPaugh and David Dobkin, nonreaders. A copy of his thesis, "Shape Distinction for 3D Object Retrieval", is on display in Room 310. Everyone is invited to attend his talk.

1 0

talk is starting in 10 minuetes
by Ginny Hogan 05 Mar '08

05 Mar '08

Konstantinos Daskalakis talk is starting in 10 minutes - COS 105

1 0

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