November 2015 - talks - lists.cs.princeton.edu

PL Seminar- Yaron Minsky, Mon Nov 16, 4:30pm
by Nicole E. Wagenblast 10 Nov '15

10 Nov '15

Programming Languages Seminar Yaron Minsky, Jane Street Capital Monday, November 16, 4:30 p.m Computer Science Room 302 Types and abstractions for concurrent programming This talk describes the design of Async, a monadic concurrency library for the OCaml programming language.

1 0

Colloquium Speaker John Leonard, Tues Nov 10- 12:30pm
by Nicole E. Wagenblast 10 Nov '15

10 Nov '15

Colloquium Speaker John Leonard, Massachusetts Institute of Technology Tuesday, November 10, 2015 - 12:30pm Computer Science 105 Mapping, Localization, and Self-Driving Vehicles This talk will discuss the critical role of mapping and localization in the development of self-driving vehicles. After a discussion of some of the recent amazing progress and open technical challenges in the development of self-driving vehicles, we will discuss the past, present and future of Simultaneous Localization and Mapping (SLAM) in robotics. We will review the history of SLAM research and will discuss some of the major challenges in SLAM, including choosing a map representation, developing algorithms for efficient state estimation, and solving for data association and loop closure. We will also present recent results on object-based mapping in dynamic environments and real-time dense mapping using RGB-D cameras. Joint work with Sudeep Pillai, Tom Whelan, Michael Kaess, John McDonald, Hordur Johannsson, Maurice Fallon, David Rosen, Ross Finman, Paul Huang, Liam Paull, Nick Wang, and Dehann Fourie. John J. Leonard is Samuel C. Collins Professor of Mechanical and Ocean Engineering and Associate Department Head for Research in the MIT Department of Mechanical Engineering. He is also a member of the MIT Computer Science and Artificial Intelligence Laboratory (CSAIL). His research addresses the problems of navigation and mapping for autonomous mobile robots. He holds the degrees of B.S.E.E. in Electrical Engineering and Science from the University of Pennsylvania (1987) and D.Phil. in Engineering Science from the University of Oxford (1994). He was team leader for MIT's DARPA Urban Challenge team, which was one of eleven teams to qualify for the Urban Challenge final event and one of six teams to complete the race. He is the recipient of an NSF Career Award (1998) and the King-Sun Fu Memorial Best Transactions on Robotics Paper Award (2006). He is an IEEE Fellow (2014).

2 4

Soudeh Ghorbani talk Fri Nov 13 11am-11.30am
by Nicole E. Wagenblast 09 Nov '15

09 Nov '15

Soudeh Ghorbani, a PhD student at UIUC working with Brighten Godfrey, is visiting Princeton on November 13 to give a talk. Please see details of her talk below. What: Micro Load Balancing in Data Centers with DRILL When: Friday November 13 from 11am-11.30am Where: COS 302 Speaker: Soudeh Ghorbani, University of Illinois Urbana-Champaign ~~~~~ Micro Load Balancing in Data Centers with DRILL The trend towards simple data center network fabric strips most network functionality, including load balancing capabilities, out of the network core and pushes them to the edge. We investigate a different direction of incorporating minimal load balancing intelligence into the network fabric and show that this slightly smarter fabric significantly enhances performance. We provide a very simple in-network load balancing scheduling algorithm called DRILL which is purely local to each switch. DRILL leverages local load sensing and randomization concepts to distribute load among multiple paths. Through simulation, we show that this simple approach outperforms CONGA, a recent global edge-based load balancing scheme for data centers. We also formally prove the switch-level stability and throughput-efficiency of DRILL’s scheduling algorithm. ~~~~~ Srinivas

1 0

Talk: Kristin J. Dana, Reflectance Gradients for Material Recognition
by Jianxiong Xiao 09 Nov '15

09 Nov '15

Speaker: Prof. Kristin J. Dana http://www.ece.rutgers.edu/~kdana/Home.html Date: Nov 9, 2015 (today) Time: 12:30-13:30 Place: CS 402 Title: Reflectance Gradients for Material Recognition Abstract: We introduce a novel method for using reflectance to identify materials. Reflectance offers a unique signature of a material but is challenging to measure and use for recognizing materials due to its high-dimensionality. Cameras can be used to capture reflectance, but typically from a sparse set of viewing angles. In this work, one-shot reflectance is captured using a unique optical camera measuring dense reflectance disks where the pixel coordinates correspond to surface viewing angles. Angular gradients computed in this reflectance space reveal the material class. These reflectance disks encode discriminative information for efficient and accurate material recognition. We introduce a framework called reflectance hashing that models the reflectance disks with dictionary learning and binary hashing. We demonstrate the effectiveness of reflectance hashing for material recognition with a number of real-world materials.

1 0

Colloquium Speaker Amir Ali Ahmadi Thurs, Nov 12- 4:30pm
by Nicole E. Wagenblast 06 Nov '15

06 Nov '15

Colloquium Speaker Amir Ali Ahmadi, Princeton University, ORFE Thursday, November 12, 2015 - 4:30pm Computer Science 105 Structured Sum of Squares Polynomials in Optimization and Control In recent years, algebraic techniques in optimization such as sum of squares (SOS) programming have led to powerful semidefinite programming relaxations for a wide range of NP-hard problems in computational mathematics. We begin by giving an overview of these techniques, emphasizing their implications for optimization and Lyapunov analysis of dynamical systems, and pointing out some challenges that remain in terms of scalability. We then introduce new algebraic relaxation schemes that are very similar to SOS relaxations in nature but instead of semidefinite programs result in linear or second order cone programs. These are what we call ``DSOS and SDSOS programs.'' We show that these relaxations are orders of magnitude more scalable than SOS relaxations while enjoying many of the same asymptotic theoretical guarantees. (Joint work with Anirudha Majumdar.) Time permitting, we will also present our recently-introduced area of ``robust-to-dynamics optimization'', which has to do with optimizing over invariant sets of dynamical systems. (Joint work with Oktay Gunluk.) Amir Ali Ahmadi ( http://aaa.princeton.edu/ ) is an Assistant Professor at the Department of Operations Research and Financial Engineering at Princeton University and an Associated Faculty member of the Department of Computer Science. Amir Ali received his PhD in EECS from MIT and was a Goldstine Fellow at the IBM Watson Research Center prior to joining Princeton. His research interests are in optimization theory and in computational aspects of dynamics and control. Amir Ali's recent awards include the INFORMS Computing Society Prize (for best series of papers at the interface of operations research and computer science), the AFOSR Young Investigator Program Award, the Goldstine Fellowship of IBM Research, the Best Conference Paper Award of the IEEE International Conference on Robotics and Automation, and the prize for one of two most outstanding papers published in the SIAM Journal on Optimization and Control in 2013-2015. Amir Ali is also a three-time recipient of the NSF Oberwolfach Fellowship and a best student paper award finalist at the 47th IEEE Conference on Decision and Control.

1 0

Srinivas Narayana will present his Pre-FPO on Wednesday, November 11, 2015 at 1:30pm in CS 301
by Nicki Gotsis 04 Nov '15

04 Nov '15

Srinivas Narayana will present his Pre-FPO on Wednesday, November 11, 2015 at 1:30pm in CS 301. The members of his committee are: Jennifer Rexford (adviser), David Walker (reader), Sanjay Rao (Purdue, reader), Nick Feamster (non-reader) and Aarti Gupta (non-reader). Everyone is invited to attend his talk. The talk title and abstract follow below: Title: Declarative Network Path Queries Abstract: Effective management of computer networks by operators is crucial to ensure the availability and performance of "always online" services that we depend on. Towards this goal, programmatic tools can remove slow and expensive human involvement in management. Recently, Software-Defined Networking (SDN) technology has eased programmatic *control* of networks, but there has been relatively little attention on programmatic *measurement* of networks. My thesis focuses on a broad class of network measurement questions that analyze the flow of traffic along network paths. Such questions are crucial for many network management tasks, including traffic engineering, diagnosing congestion, mitigating DDoS attacks, localizing packet loss in networks, and several others. With the current state-of-the-art, network operators measure traffic flow by "synthesizing" multiple data streams from the network---including updates to forwarding rules, traffic observations from counters and packet samples, and changes in network topology. However, this approach has significant limitations: it makes measurements indirect for operators to express, and forces operators to make a difficult trade-off up front between the accuracy and overhead of their measurements. In my thesis, I approach network path measurement with two key principles: (1) Enable operators to specify the measurements they need in a declarative query language; and (2) Drive network measurement according to operator-specified queries. This enables the collection of *exactly* the traffic that satisfies the operator-specified queries, with accurate results for those queries at low overhead. There are three important pieces in my research that realize these principles in practice. First, I will present an declarative query language that enables efficient path-based traffic monitoring. Path queries are specified as regular expressions over predicates on packet locations and header values, with SQL-like ``groupby'' constructs for aggregating results anywhere along a path. Packets can be captured either before or after they traverse a path that satisfies a query, returning results as packet or byte counters, entire packets (mirrored to collectors), or packet and flow sampled records (from commonly deployed packet-sampling technologies). A network operator writes each query indepedently of the forwarding policy in the network, as well as other queries, without worrying about the specifics of switch hardware. We show that she is able to specify several realistic measurement questions corresponding to network resource management, policy enforcement, and fault diagnosis. Second, I will present a query run-time system that translates the operator-specified queries into accurate data plane measurement that runs on commodity switch hardware. The run-time first compiles queries into a deterministic finite automaton. The automaton's transition function is then partitioned, compiled into `match-action' rules (which can run on commodity hardware), and distributed over the switches. Switches stamp packets with automaton states to track their progress towards fulfilling a query. Only when packets satisfy a query are they counted, sampled, or sent to collectors for further analysis. By processing queries in the data plane, users ``pay as they go'', as data-collection overhead is limited to exactly those packets that satisfy the query. Further, storing the automaton state requires only a small amount of extra space (2-4 bytes) on each packet---for example a VLAN or MPLS header. Third, I will present optimizations to our prototype run-time system that is built on top of the Pyretic SDN controller, an open source platform. These optimizations address fundamental bottlenecks in compilation, caused by queries and forwarding policies performing different actions on overlapping sets of packets. Combining such actions into a unified rule set can result in exponential increases in query compile time and the output rule set. The optimizations leverage key insights into the structure of the constituent policies, and recent advances in commodity hardware, to reduce compile times and rule set sizes by 3-4 orders of magnitude. Experiments indicate that the system can enable ``interactive debugging''---compiling multiple queries in a few seconds---while fitting rules comfortably in modern switch rule memories. Together, the query language and run-time system enable expressive measurement specification, as well as accurate and efficient network measurement, furthering the state-of-the-art of network management on commodity hardware.

1 0

Daniel Larkin will present his FPO, "Compressing Trees with a Sledgehammer" on Wednesday, 11/11/2015 at 10am in CS 402
by Nicki Gotsis 04 Nov '15

04 Nov '15

Daniel Larkin will present his FPO on Wednesday, 11/11/2015 at 10:00AM, 402 Computer Science. The members of his committee are: Readers: Robert Sedgewick and Jeff Erickson (University of Illinois at Urbana-Champaign); Examiners: Sanjeev Arora, Zeev Dvir and Robert Tarjan (adviser). A copy of his thesis is available in Room 310. Everyone is invited to attend his talk. The talk title and abstract follow below: Title: "Compressing Trees with a Sledgehammer" Abstract: A variety of problems can be solved more efficiently with the use of compressed trees. The compressed tree method is flexible and can be applied in different ways to solutions for many problems including disjoint set union, nested set union, and path evaluation. The central contribution of this thesis is a unified framework for the analysis of the compressed tree method and a meta-theorem that proves an inverse-Ackermann-type bound for a class of algorithms. The meta-theorem requires only that the compaction method be well-structured and that the other operations maintain a forest structure that admits a well-behaved rank function. These are the weakest known conditions of any analysis to-date that proves such a bound. We use the framework to give a clean, compact alternative analysis of all but one of the known efficient algorithms for disjoint set union; we provide an explicit proof of optimality for the remaining known optimal method, splicing by rank, which was left as an exercise by Tarjan and van Leeuwen [24]; we prove that a new algorithm for disjoint set union called randomized linking is optimal, giving theoretical backing for some recent experimental results; and finally we proceed to explore the nested set union problem, giving an optimal algorithm for any constant number of partitions as well as a few alternatives for the restricted case of two partitions.

1 0