March 2012 - talks - lists.cs.princeton.edu

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

Colloquium Speaker, Ira Kemelmacher-Shlizerman, Wed March 14th, 4:30pm
by Nicole E. Wagenblast 12 Mar '12

12 Mar '12

Modeling People from Billions of Photos Ira Kemelmacher-Shlizerman , University of Washington Wednesday, March 14th, 2012, 4:30pm Computer Science Small Auditorium (Room 105) Internet and personal photo collections now add up to over a trillion photos, with people being in most of them. The availability of so many photos presents a unique opportunity to model virtually the whole human population. Modeling humans is key to understanding how people interact with the environment, and to future human machine interfaces. In this talk, I will describe our work on 3D shape and motion estimation of a human face from large photo collections, as well as novel techniques for browsing those collections. This represents an exciting breakthrough towards modeling and visualizing any person just from their available photos. Part of this work is now included in Google’s Picasa. Ira Kemelmacher-Shlizerman is a Postdoctoral researcher in the Department of Computer Science and Engineering at the University of Washington. She received her Ph.D in computer science and applied mathematics at the Weizmann Institute of Science in 2009. Dr. Kemelmacher-Shlizerman works in computer vision and graphics, with a particular interest in developing computational tools for modeling people from Internet and personal photo collections. Ira's recent research was covered by stories in New Scientist, CBS, Discovery News and others. She was also consulting for Google.

1 0

Colloquium Speaker Domagoj Babic Mon March 12th 4:30pm
by Nicole E. Wagenblast 08 Mar '12

08 Mar '12

Software Testing and Verification with Grammatical Inference Domagoj Babic , University of California, Berkeley Recent progress in automated deductive reasoning techniques has triggered a small scientific revolution in automated software testing, verification, and security. Indeed, it is becoming increasingly difficult to find new automated software analysis papers that do not use or assume existence of propositional satisfiability and satisfiability-modulo theories solvers. In this talk, I will discuss the first results of my efforts to answer a simple question: What kind of automated reasoning will trigger the next scientific revolution in automated software analysis? As a potential candidate, I will present grammatical inference (GI), a class of techniques for learning formal languages. By inductively generalizing from examples, GI techniques nicely complement the capabilities of existing (deductive) approaches. Furthermore, the inferred grammars (or automata) are themselves analyzable objects, which can be used as approximations or abstractions of the behavior of the analyzed program. In this talk, I'll analyze several open problems, namely (1) test generation for programs whose inputs have to adhere to complex grammars, and (2) automated verification of web sanitizers, and offer some solutions. The common trait of the above mentioned problems is that they require exact or approximate understanding of the relation between program's input and output. I'll explain how GI techniques can infer such relations and serve as a basis for inventing new powerful software analyses. In particular, I'll show that GI-based automated testing can find six times more vulnerabilities than the state-of-the-art methods, increasing code coverage by up to 58%. The novel symbolic learning technique that I'll present learns input-output relations of web sanitizers (for subsequent verification) in seconds, while construction of the same relations used to take several hours of a human expert's time in the past. Domagoj Babic received his Dipl.Ing. in Electrical Engineering and M.Sc. in Computer Science from the Zagreb University (Faculty of Electrical Engineering and Computing) in 2001 and 2003. He received his Ph.D. in Computer Science in 2008 from the University of British Columbia. After spending a bit more than a year in industry, he joined UC Berkeley, as a research scientist. Domagoj's research focuses on various aspects of software analysis (software verification, testing, and security), decision procedures, grammatical inference, and applied formal methods in general. He is a recipient of the Canada's NSERC PDF Research Fellowship (2010-2012), Microsoft Graduate Research Fellowship (2005-2007), Fulbright Fellowship (declined to attend UBC), and several awards at international programming competitions (1st place at the 2007 Satisfiability Modulo Theories competition in the bit-vector arithmetic category and 3rd place at the 2005 Satisfiability Testing competition in the satisfiable-crafted instances category). For more, see: http://www.domagoj.info/

1 0

4:30pm Thu Mar 8 talk on sparse recovery over networks in B205
by Jennifer Rexford 08 Mar '12

08 Mar '12

DEPARTMENT OF ELECTRICAL ENGINEERING SEMINAR SERIES Speaker: A. Kevin Tang, Cornell University Title: Sparse Recovery over Networks Date/time: 4:30pm Thursday, March 8th Room: E-Quad B-205 Host: Mung Chiang ABSTRACT: Given that large scale networks such as the Internet and power grids have become ever more crucial for our society, it is critical to keep monitoring states of such networks to avoid possible system failure and to optimize performance. The scale and complexity of such systems raise the need to quickly infer component characteristics from a relatively small number of indirect aggregate measurements. Motivated by tomography problems in information networks, we first discuss sparse recovery with graph constraints in the sense that we can take additive measurements over nodes only if they induce a connected subgraph. We provide explicit measurement constructions for several special graphs including line, 2-D grid and tree. A general measurement construction algorithm is also proposed and evaluated. For any given graph G with n nodes, we derive order optimal upper bounds of the minimum number of measurements needed to recover any k-sparse vector over G. Second, to deal with bad data detection in power grids, an iterative mixed L1 and L2 convex programming is used to estimate the true state by locally linearizing the nonlinear measurements. We give conditions under which the solution of the iterative algorithm converges to the true state. We also numerically evaluate our solution to perform bad data detections in nonlinear electrical power networks problems. Besides their clear applications, both formulations significantly generalize the current compressive sensing framework: from complete graph to arbitrary graph (first part of the talk) and from additive linear measurements to nonlinear measurements (second part of the talk). BIO: A. Kevin Tang received his undergraduate degree in electronics engineering from Tsinghua University, Beijing, China, and his Ph.D. in electrical engineering with a minor in applied and computational mathematics from the California Institute of Technology. He is currently an Assistant Professor in the School of Electrical and Computer Engineering at Cornell, where his research interests focus on control and optimization of various networks, including communication networks, power networks, and on-chip networks. His recent awards include a Michael Tien'72 Excellence in Teaching Award from the college of engineering at Cornell in 2011 and a Young investigator award from the US Air Force's Office of Scientific Research in 2012.

1 0

Ari Rabkin talk starting in 5 minutes, room 302
by Mike Freedman 07 Mar '12

07 Mar '12

Using Static Analysis to Diagnose Misconfigured Open Source Systems Software Ariel Rabkin, University of California, Berkeley Ten years ago, few software developers worked on distributed systems. Today, developers often run code on clusters, relying on large open-source software stacks to manage resources. These systems are challenging to configure and debug. Fortunately, developments in program analysis have given us new tools for managing the complexity of modern software. This talk will show how static analysis can help users configure their systems. I present a technique that builds an explicit table mapping a program's possible error messages to the options that might cause them. As a result, users can get immediate feedback on how to resolve configuration errors. --- Ariel Rabkin is a fifth (and final)-year PhD candidate in the RAD Lab at UC Berkeley, working with Randy Katz. He is formerly from Cornell University, AB 2006, MEng 2007). He is interested in software quality and software intelligibility. He expects to graduate in May 2012. His dissertation is about applying program analysis to system management, including automatically describing program configuration options and diagnosing configuration errors. He is a contributor to several open source projects, including Hadoop, the Chukwa log collection framework, and the JChord program analysis toolset.

1 0