- talks - lists.cs.princeton.edu

Dominic Kao MSE thesis talk
by Melissa M. Lawson 10 Apr '12

10 Apr '12

Dominic Kao will present his MSE thesis talk on Monday April 16 at 2PM in room 402. The members of his committee are: Yael Niv (PSY), her postdoc Carlos Diuk, and Adam Finkelstein, reader. Everyone is invited to attend his talk. His abstract follows below. --------------------- The world has already spent 5.93 million years playing the video game World of Warcraft. What makes video games rewarding? We suggest that one important factor in a player's enjoyment of a game is the schedule of rewards, specifically, we hypothesized that variable rewards are more interesting and enticing than a fixed reward size. To test this hypothesis we studied several variable reward schedules contrasted with a fixed reward schedule in a custom-built video game. We found that variable reward schedules were preferred, except when the schedule’s range included very small or non-existent (zero) rewards. Participants consistently mischaracterized the variable reward schedule as having a higher mean than the fixed schedule. We further hypothesized that reward schedule preference is an indicator for game genre preference. Ultimately, the conclusions made can be applied more broadly to the now ubiquitous game mechanics that surround us in both the real and virtual world.

1 0

J Huang preFPO
by Melissa M. Lawson 05 Apr '12

05 Apr '12

Jialu Huang will present her preFPO on Monday April 9 at 1PM in Room 301 (note room!!) The members of her committee are: David August, advisor; David Walker and Kai Li, readers; Doug Clark and JP Singh, nonreaders. Everyone is invited to attend her talk. Her abstract follows below. ========================================================================================= Abstract: Automatic parallelization is a promising approach to deliver scalable multi-threaded programs for multi-core architectures. Most existing techniques parallelize independent loops and insert global synchronizations at the end of each loop invocation. For programs with few loop invocations, these global synchronizations do not limit parallel execution performance. However, for programs with many loop invocations, those synchronizations can easily become the performance bottleneck since they frequently force all threads to wait, losing potential parallelization opportunities. Some automatic parallelization techniques apply static analyses to enable cross-invocation parallelization. Instead of waiting, threads can execute iterations from follow-up invocations if they do not cause any conflict. However, static analyses must be conservative, and therefore cannot handle programs with irregular dependence patterns. In order to enable more parallelization across loop invocations, this thesis presents two novel automatic parallelization techniques: BLISS and SBS. Unlike existing techniques relying on static analyses, these two techniques take advantage of runtime information to achieve much more aggressive parallelization. BLISS constructs a custom runtime engine which non-speculatively observes dependences at runtime and synchronizes iterations only when necessary; while SBS applies software speculative barriers to permit some of the threads to execute past the invocation boundaries. The two techniques are complimentary in the sense that they can parallelize programs with potentially very different characteristics. SBS is most effective when a program's cross-invocation dependences rarely cause a runtime conflict. BLISS' runtime engine imposes a marginal amount of overhead, but it also enables the technique to effectively parallelize programs whose dependences can cause frequent conflicts. Preliminary implementation and evaluation demonstrate that both techniques can achieve much better scalability compared to existing automatic parallelization techniques. ==============================================================================================

1 0

J Terrace preFPO
by Melissa M. Lawson 05 Apr '12

05 Apr '12

Jeff Terrace will present his preFPO on Thursday April 12 at 4PM in Room 302 (note room!). The members of his committee are: Michael Freedman, advisor; Adam Finkelstein and Phil Levis (Stanford), readers; Vivek Pai and Szymon Rusinkiewicz, nonreaders. Everyone is invited to attend his talk. His abstract follows below. --------------------- Metaverses are three-dimensional virtual worlds where anyone can add and script new objects. Metaverses today, such as Second Life, are dull, lifeless, and stagnant because users can see and interact with only a tiny region around them, rather than a large and immersive world. Current metaverses impose this distance restriction on visibility and interaction in order to scale to large worlds, as the restriction avoids appreciable shared state in underlying distributed systems. We present a brief summary of the design and implementation of the Sirikata metaverse server. The Sirikata server scales to support large, complex worlds, even as it allows users to see and interact with the entire world. It achieves both goals simultaneously by leveraging properties of the real world and 3D environments in its core systems, such as a novel distributed data structure for virtual object queries based on visible size. A virtual-world environment becomes a truly engaging platform when users have the ability to insert 3D content into the world. However, arbitrary 3D content is often not optimized for real-time rendering, limiting the ability of clients to display large scenes consisting of hundreds or thousands of objects. We present the design and implementation of an automatic, unsupervised conversion process that transforms 3D content into a format suitable for real-time rendering while minimizing loss of quality. The resulting progressive format includes a base mesh, allowing clients to quickly display the model, and a progressive portion for streaming additional detail as desired. Sirikata’s public, open-source content repository is currently using this method and has processed over 700 3D models. 3D meshes are large--often several megabytes in size. When a client enters a scene containing many objects, it can take a long time to download meshes, resulting in poor visual fidelity. A progressive mesh format allows a client to download a low-resolution version of a mesh at a much lower cost in bandwidth, but deciding how to order downloads has a huge impact on performance. Should a client download a higher texture resolution for one model, or stream additional vertices for another? Worse, underpowered clients might not be able to display a high resolution mesh, resulting in wasted time downloading unneeded content. We present the design and implementation of a framework for evaluating scheduling algorithms for progressive meshes and we perform this evaluation on several different algorithms. The result is a mesh scheduling algorithm that optimizes for visual fidelity given a fixed bandwidth constraint.

1 0

W Clarkson FPO
by Melissa M. Lawson 03 Apr '12

03 Apr '12

Will Clarkson will present his FPO on Monday April 9 at 8:30AM in the 3rd Floor Conference Room in Sherrerd Hall. Note time and location! The members of his committee are: Ed Felten, advisor; Andrew Appel and Adam Finkelstein, readers; Brian Kernighan and Rebecca Fiebrink, nonreaders. A copy of his thesis, "Breaking Assumptions: Distinguishing Between Seemingly identical Items Using Cheap Sensors", is on display in Room 310. Everyone is invited to attend his talk.

1 0

11am Fri Mar 30 talk on smart energy in CS 105
by Jennifer Rexford 30 Mar '12

30 Mar '12

Speaker: Shivkumar Kalyanaraman, IBM Research Title: Smarter Energy: The Promise of Cyber-Physical Systems Location: 105 Computer Science Building (a.k.a. the "small auditorium") Date/time: 11am-noon on Friday March 30 Abstract: This talk will review how the climate change problem is linked to the fossil-fuel energy problem, and overview various options for sustainable energy and their relative contributions. We then discuss smarter energy, and how sensing, networking, real-time analytics, actuation and control come together in a "cyber-physical" system. The talk will discuss key IBM Research and some commercial initiatives worldwide -- ranging from deep rainforest microgrids in Brunei, smart grid tomography in Australia, integration of fickle wind energy and plug-in hybrid electric vehicles (PHEV) in Denmark, context-sensitive "smart" demand-response systems for residential use. Bio: Shivkumar Kalyanaraman is a Senior Technical Staff Member (STSM) & Senior Manager of the Next Gen Systems & Smarter Planet Solutions Department at IBM India Research Labs, Bangalore. He was previously a Manager of the Next Generation Telecom Research group and a Research Staff Member since 2008. He was a full Professor at the Department of Electrical, Computer and Systems Engineering at Rensselaer Polytechnic Institute in Troy, NY. He received a B.Tech degree in Computer Science from the Indian Institute of Technology, Madras, India in July 1993, followed by M.S. and Ph.D. degrees at the Ohio State University in 1994 and 1997 respectively. He also holds an Executive M.B.A. (EMBA) degree from Rensselaer Polytechnic Institute (2005). His current research in IBM is at the intersection of emerging wireless technologies and IBM middleware and systems technologies with applications to large-scale smarter planet problems (grids, traffic, finance etc). He was selected by MIT's Technology Review Magazine in 1999 as one of the top 100 young innovators for the new millenium. He served as the TPC Co-chair of IEEE INFOCOM 2008, and General co-chair of ACM SIGCOMM 2010 in New Delhi. He is on the editorial board of IEEE/ACM Transactions of Networking. He is a Fellow of the IEEE, and an ACM Distinguished Scientist.

1 0

A Bhaskara preFPO
by Melissa M. Lawson 28 Mar '12

28 Mar '12

Aditya Bhaskara will present his preFPO on Monday April 2 at 1PM in Room 301. His committee is: Moses Charikar, advisor; Sanjeev Arora and Zeev Dvir, readers; Bernard Chazelle and Amit singer (Math), nonreaders. Everyone is invited to attend his talk. His abstract follows below. Title: Finding Dense Sub-structures in Graphs and Matrices A basic primitive in graph optimization is that of finding small induced subgraphs of a given graph with ``many'' edges. Questions of this nature arise often in practice, for instance in finding ``communities'' in social networks, and in clustering type problems. From the theory side, this captures questions such as ``small-set expansion'', which has proved to be an intriguing open problem. A simple formalization we study is the Densest-k-subgraph problem, where the objective, given a graph G, is to find an induced subgraph on k vertices with as many edges as possible. There is a vast gap in our understanding of this problem in terms of the approximation ratio we can achieve. I will discuss the state of the art in approximation algorithms, and try to point out why it is difficult to write convex programming relaxations for the problem. This is akin to difficulties that arise in other problems which have a ``small-support'' constraint, such as those arising in compressed sensing. An interesting aspect of the densest-k-subgraph problem is that random instances seem to be the hardest for obtaining approximation algorithms. A question related to this is that of computing the q->p (operator) norm of a matrix. Such norms are generalizations of singular values, and in general, computing them is not a convex optimization problem. We will see conditions under which it is possible to compute them efficiently, and attempt to obtain a `characterization', by complementing this with hardness results. We also study generalizations of singular values to three-dimensional tensors, a problem which arises in applications involving 3D data. The question is believed to be very hard (even to approximate) in general. We study the following `planted' variant: suppose we know that the tensor is "rank-k + small noise" (but we do not have access to such a decomposition), then can we solve the tensor analog of largest singular value? We show that this can be done in time exponential in $k$ (but almost linear in the size of the tensor). Results in the talk will be based on joint works with Sanjeev Arora, Moses Charikar, Eden Chlamtac, Uriel Feige, Ravi Kannan, and Aravindan Vijayaraghavan.

1 0

Colloquium Speaker Umesh Vazirani, Tues March 27- 4:30pm
by Nicole E. Wagenblast 26 Mar '12

26 Mar '12

Certifiable Quantum Dice Umesh Vazirani , University of California, Berkeley Tuesday, March 27 4:30pm Computer Science Small Auditorium (Room 105) A source of independent and uniform random bits is a basic resource in many computational tasks, such as cryptography, game theoretic protocols, algorithms and physical simulations. In the classical world it is impossible to construct a random number generator whose output can be certified to be a uniformly random n-bit string, since there seems to be no basis on which to reject any particular output in favor of any other. Quantum mechanics allows for a remarkable random number generator: its output is certifiably random in the sense that if the output passes a simple statistical test, and a no-signaling condition is met between the two boxes in the randomness generating device (based, say, on the speed of light limit imposed by special relativity), even a quantum skeptic (viz Einstein's famous quote ``God does not play dice with the Universe''), would be convinced that the output is truly random, independent of the validity of quantum mechanics. Based on joint work with Thomas Vidick.

1 1

R Manokaran preFPO
by Melissa M. Lawson 26 Mar '12

26 Mar '12

Rajsekar Manokaran will present his preFPO on Wednesday March 28 at 1:30PM in Room 402. The members of his committee are: Sanjeev Arora, advisor; Moses Charikar and Zeev Dvir, readers; Mark Braverman and Bernard Chazelle, nonreaders. Everyone is invited to attend his talk. His abstract follows below. ------------------- Title: Approximability using Mathematical Relaxations A standard approach to coping with the NP-hardness of a combinatorial optimization problem involves designing algorithms that guarantee a solution within a factor p of the optimum (a.k.a an p-approximation algorithm). We study the approximability of various fundamental graph optimization problems using linear programming~(LP) relaxations. In the first part of the thesis, we study simple LP relaxations for Metric Labeling, and a variety of Packing and Covering problems. For all these problems, we show that the relaxation already obtains the best approximation, upto known algorithmic barriers. The novelty here is the generality of the technique: the proof only uses simple "local" properties of the relaxation, oblivious of the actual approximation factor, p, obtained thus. In the second part, we use insights obtained from the above in studying the approximability of a large class of ordering problems, including the Maximum Acyclic Subgraph problem. Here, we show that a trivial algorithm, that outputs a random ordering irrespective of the instance in hand, already achieves the best appromximation factor upto known algorithmic techniques. In the final part, we study implications of "average-case" algorithmic barriers. In particular, we show that the densest-k-subgraph problem is hard to approximate to within any constant factor assuming random k-AND formulas are hard to distinguish from well satisfiable ones. These results are based on joint works with Noga Alon, Sanjeev Arora, Moses Charikar, Venkatesan Guruswami, Johan Hastad, Amit Kumar, Dana Moshkovitz, Joseph Naor, Prasad Raghavendra, Roy Schwartz, Madhur Tulsiani, Nisheeth Vishnoi and Omri Weinstein

1 0

Yun Zhang FPO
by Melissa M. Lawson 23 Mar '12

23 Mar '12

Yun Zhang will present her FPO on Thursday March 29 at 2PM in Room 402. The members of her committee are: David August, advisor; David Walker and Scott Mahlke (Michigan), readers; Doug Clark and Jen Rexford, nonreaders. A copy of her thesis, "Runtime Speculative Software-Only Fault Tolerance", is on display in Room 310. Everyone is invited to attend her talk.

1 0

Colloquium speaker Shyamnath Gollakota, Mon March 26th 4:30pm
by Nicole E. Wagenblast 23 Mar '12

23 Mar '12

Embracing Interference in Wireless Systems Shyamnath Gollakota , Massachusetts Institute of Technology Monday, March 26, 4:30pm Computer Science Small Auditorium (Room 105) The wireless medium is a shared resource. If nearby devices transmit at the same time, the transmitted signals interfere, resulting in a collision. In traditional networks, collisions cause the loss of the transmitted information. For this reason, wireless systems have been designed with the assumption that interference is intrinsically harmful and must be avoided. My research takes an alternate approach: Instead of viewing interference as an inherently counterproductive phenomenon that should to be avoided, I design practical systems that can successfully reconstruct the transmitted information even in the presence of collisions; hence, rendering the interference harmless. Moreover, these new systems can exploit interference constructively to increase throughput and improve security. In the talk, I will present the first WiFi receiver that decodes colliding packets, rendering WiFi interference harmless. I will also show how to inject useful interference that increases network throughput using a system called analog network coding. Then, I will talk about the role of interference in improving security. I will use interference to secure insecure medical implants, and establish secure wireless connections without having users enter passwords or use pre-shared secret keys. Shyamnath Gollakota is a PhD candidate in Electrical Engineering and Computer Science at the Massachusetts Institute of Technology. His research in networking focuses on addressing wireless interference and security. He has been awarded the ACM SIGCOMM 2008 Best paper award for ZigZag decoding, ACM SIGCOMM 2011 Best Paper Award for securing medical implants, and AT&T Applied Security Award for password-free wireless security. His work has appeared in venues like Slashdot, BBC Radio, Forbes, and Network World. He received his masters in Electrical Engineering and Computer Science at MIT, and a bachelors degree in Computer Science and Engineering at IIT Madras.

1 1