- talks - lists.cs.princeton.edu

TODAY 10/1 at 4:30pm in B205 - Chandra Nair, Chinese University of Hong Kong
by Emily Lawrence 01 Oct '18

01 Oct '18

EE SEMINAR SERIES Speaker: Chandra Nair, Chinese University of Hong Kong Title: Non-Convex Optimization And Multiuser Information Theory Day: Monday, October 1, 2018 Time: 4:30 pm Room: B205 Engineering Quadrangle Host: Prof. Peter Ramadge Abstract: Capacity regions in multiuser information theory were traditionally established using an achievability argument and converses to corresponding rate regions. Recently, however, capacity regions have been established, for non-trivial and important classes of channels (such as additive Gaussian noise models and others), by optimizing functionals on probability spaces generated from inner or outer bounds and showing that the bounds match for these channels. Optimization ideas have also been used to determine if certain achievable regions proposed in the literature are optimal or sub-optimal in general. The study of these non-convex optimization problems required developing new insights and techniques. In this talk, I will outline the ideas involved in obtaining the results, as well as illustrate the relationship of these problems to hypercontractivity and related notions studied primarily outside information theory. I will present some unifying observations across the family of optimization problems that we have managed to solve, and state some elementary instances of similar problems whose solutions would be of immense interest. Bio: Chandra Nair is an Associate Professor with the Information Engineering department at The Chinese University of Hong Kong. His research interests and contributions have been in developing ideas, tools, and techniques to tackle families of combinatorial and non-convex optimization problems arising primarily in the information sciences. His recent research focus has been on studying the optimality of certain inner and outer bounds to capacity regions for fundamental problems in multiuser information theory. He, along with his doctoral student Yanlin Geng, received the 2016 Information Theory Society paper award for developing a novel way to establish the optimality of Gaussian distributions. A proof of the Parisi and Coppersmith-Sorkin conjectures in the Random Assignment Problem constituted his doctoral dissertation; and he resolved some conjectures related to Random Energy model approximation of the Number Partition Problem during his post-doctoral years. Chandra Nair got his Bachelor's degree, B.Tech(EE), from IIT Madras (India) where he was the Philips (India) and Siemens (India) award winner for the best academic performance. Subsequently he was a Stanford graduate fellow (00-04) and a Microsoft graduate fellow (04-05) during his graduate studies at the EE department of Stanford university. Later, he became a post-doctoral researcher (05-07) with the theory group at Microsoft Research, Redmond. He has been a faculty member of the information engineering department at The Chinese university of Hong Kong since Fall 2007. He was an associate editor for the IEEE Transactions on Information Theory (2014-2016) and is currently a distinguished lecturer of the IEEE Information theory society. He is a fellow of the IEEE. He serves as the Programme Director of the undergraduate program on Mathematics and Information Engineering and the Director of the Institute of Theoretical Computer Science and Communications.

1 0

Save the date for Princeton Research Day - May 9, 2019
by Emily Lawrence 01 Oct '18

01 Oct '18

Save the Date for Princeton Research Day! Posters . Talks . Performances . Art Exhibitions . Digital Presentations Thursday, May 9, 2019 Frist Campus Center <http://researchday.princeton.edu/> researchday.princeton.edu #PRD19 We encourage all academic departments and centers at Princeton to reserve May 9, 2019, for Princeton Research Day, and to support participation by your undergraduates, graduate students, postdoctoral researchers and fellows, and other early career researchers. Princeton Research Day is a celebration of the research and creative endeavors by our undergraduates, graduate students, postdoctoral researchers and fellows, and other early career researchers. The fourth-annual campus-wide event will feature poster presentations, exhibits, performances, selected talks and an award ceremony for outstanding contributions. The all-day event is free and open to the public. Application will open Dec. 3, 2018. Dates to remember: Dec. 3: Call for applications to present at PRD19 Feb. 18: Priority application deadline April 1: Presenters informed of presentation format and given access to edit presentation summaries April 22: Presenter RSVP deadline; last day to edit presentation summaries April 26: PRD19 program becomes available to public May 9: Princeton Research Day More details are available at researchday.princeton.edu <http://researchday.princeton.edu/> . Questions? Contact researchday@princeton <https://owa.princeton.edu/owa/redir.aspx?C=RLzvZJLd5qsfA35tEu-RZUskcIzw1Or- xtqM97sHprDuM74sownUCA..&URL=mailto%3aresearchday%40princeton.edu> .edu <https://owa.princeton.edu/owa/redir.aspx?C=YX0gtaHjrc-9tcOtKgiNyz3ODOIM6cxn odqEzb_K5mX_Wr4sownUCA..&URL=mailto%3aresearchday%40princeton.edu> . Princeton Research Day is a collaborative initiative between the offices of the Dean of the College, the Dean of the Faculty, the Dean of the Graduate School and the Dean for Research, with support from the Office of the Provost. Alice Seneres, Ph.D. Assistant Dean for Academic Affairs Office of the Dean of the Faculty Princeton University 306A Nassau Hall (609) 258-4793 aseneres(a)princeton.edu <mailto:aseneres@princeton.edu>

1 0

Seminar-Dr. Shijia Pan, Thursday, September 27
by Emily Lawrence 26 Sep '18

26 Sep '18

Seminar Speaker Dr. Shijia Pan from Carnegie Mellon University Thursday, September 27, 2018 - 12:30pm Computer Science - Room 402 Host: Margaret Martonosi "Indoor Human Information Acquisition from Physical Vibrations" Abstract: The number of everyday smart devices (such as smart TV, Samsung SmartThings, Nest, Google Home) is projected to grow to the billions in the coming decade. The Cyber-Physical Systems or Internet of Things systems that consist of these devices are used to obtain human information for various smart building applications. Different sensing approaches have been explored, including vision-, sound-, RF-, mobile-, and load-based methods, to obtain various indoor human information. >From the system perspective, general problems faced by these existing technologies are their sensing requirements (e.g., line-of-sight, high deployment density, carrying a device) and intrusiveness (e.g., privacy concerns). My research focuses on non-intrusive indoor human information acquisition through ambient structural vibration, which is referred to as 'structures as sensors'. People's interaction with structures in the ambient environment (e.g., floor, table, door) induces those structures to vibrate. By capturing and analyzing the vibration response of structures, we can indirectly infer information about the people and their actions that cause it. However, challenges remain. Due to the complexity of the physical world (in this case, both structures and people), sensing data distributions can change significantly under different sensing conditions. Therefore, from the data perspective, accurate information learning through a pure data-driven approach requires a large amount of labeled data, which is costly and difficult if not impossible to obtain in real-world sensing applications. My research addresses these challenges by combining physical knowledge and data-driven approaches. Specifically, my system can robustly learn human information from limited labeled data distributions by iteratively expanding the labeled dataset. With insights into the relationship between changes of sensing data distributions and measurable physical attributes, the iterative algorithm guides the expansion order by measured physical attributes to ensure a high learning accuracy in each iteration. Bio: Dr. Shijia Pan is a postdoctoral researcher at Carnegie Mellon University. She received her Bachelor's degree in Computer Science and Technology from University of Science and Technology of China and her Ph.D. degree in Electrical and Computer Engineering at Carnegie Mellon University. Her research interests include cyber-physical systems, Internet-of-Things (IoT), and ubiquitous computing. She worked in multiple disciplines and focused on indoor human information acquisition through ambient sensing. She has published in both top-tier Computer Science ACM/IEEE conferences (IPSN, UbiComp) and high-impact Civil Engineering journals (Journal of Sound and Vibration, Frontiers Built Environment). She is the recipient of numerous awards and fellowships, including Rising Stars in EECS, Nick G. Vlahakis Graduate Fellowship, Google Anita Borg Scholarship, Best Poster Awards (SenSys, IPSN), Best Demo Award (Ubicomp), Best Presentation Award (SenSys Doctoral Colloquium), and Audience Choice Award (BuildSys) from ACM/IEEE conferences.

2 1

Today's Department Colloquium at 4:30 pm Sherrerd Hall 101: Yuval Peres, Microsoft
by Emily Lawrence 25 Sep '18

25 Sep '18

===== Todays ORFE Department Colloquium Announcement===== DATE: Tuesday, September 25th, 2018 TIME: 4:30pm LOCATION: Sherrerd Hall 101 SPEAKER: Yuval Peres, Microsoft Research Title: Communication cost of consensus for nodes with limited memory Abstract: Motivated by applications in blockchain and sensor networks, we consider a model of n nodes trying to reach consensus on their majority bit (which a fraction p>1/2 of them possess; the rest start with the minority bit). Each node v is a finite automaton with m bits of memory (i.e., 2^m states), and a Poisson clock. When it rings, the node v can choose to communicate, and is then matched to a uniformly chosen node u, whence both v,u can update their states based on the other nodes state. Previous work has focused on minimizing the time to consensus and the probability of error; our goal is minimizing communication. We show that when m>3 logloglog(n), consensus can be reached at linear communication cost, but this is impossible if m<logloglog(n). The best algorithms we know intrinsically select a set of expert nodes that learn the majority bit, and then disseminate this knowledge. A key step is to distinguish when nodes can become aware of reaching the majority bit and stop communicating; this is impossible if their memory is too low. (Joint work with Giulia Fanti, Nina Holden and Gireeja Ranade). _____ Biography: Yuval Peres is a Principal Researcher at Microsoft Research in Redmond. He obtained his Ph.D. at the Hebrew University, Jerusalem in 1990, and later taught there and at the University of California, Berkeley. He has published more than 300 research papers and has co-authored books on Brownian motion, Markov chains, Probability on Networks, Fractals, and Game Theory. Yuval was awarded the Rollo Davidson Prize in 1995, the Loève Prize in 2001, and the David P. Robbins Prize in 2011. He was an invited speaker at the 2002 International Congress of Math. and in the 2008 European Congress, and was a plenary lecturer at the Math. Congress of the Americas in 2017. He has advised 22 Ph.D. students. He is a fellow of the American Math. Society and the Institute of Mathematical Statistics. In 2016 he was elected to the U.S. National Academy of Sciences.

1 0

Fwd: CS/EE Seminar - Monday, September 17. 2018, 11:00 am, E-Quad B327 - Liang Wang
by Jennifer Rexford 14 Sep '18

14 Sep '18

> > > Department of Computer Science and > Department of Electrical Engineering Seminar > > > Speaker: Liang Wang > University of Wisconsin - Madison > Title: Understanding Security and Privacy Issues in Cloud Applications > Date: Monday, September 17, 2018 > Time: 11:00 am > Room: E-Quad, Room B327 > Host: Prof. Jennifer Rexford and Prof. Prateek Mittal > > Abstract: An increasing amount of applications are utilizing public clouds and rely on their cloud providers to provide security and privacy protection. However, specific application design patterns might compromise the providers’ efforts on securing applications, and make the applications vulnerable. In my work, I use measurement-driven approaches to examine various types of cloud-based applications/services and investigate whether they can achieve desired security and privacy guarantees. In this talk, I will present my work on: > > (1) Decision-tree-based traffic analysis attacks against Tor meek, a cloud-based traffic obfuscator that is designed to be resistant to Internet censorship by nation states. Our attacks require a censor to maintain little state, but can reliably detect meek traffic with high true-positive rates and sufficiently low false-positive rates (0.006% - 0.02%, out of 14M TCP flows). > > (2) Side-channel attacks against search indexes of multi-tenant cloud services. The attacks can discover terms in other tenants’ private documents, and work efficiently on live cloud services such as GitHub in controlled experiments. > > (3) My most recent work on characterizing popular serverless computing platforms in terms of performance and resource scheduling. We discover several issues that could make serverless applications vulnerable to side-channel and DoS attacks in AWS Lambda and Azure Functions, and find bugs that allow customers to use resources for free in Google Cloud Functions. > > >

1 0

Young Kun Ko will present his FPO "Hardness Amplification in Two Prover Game and Communication Complexity" on Monday, 9/17/2018 at 1pm in CS 401.
by Nicki Gotsis 14 Sep '18

14 Sep '18

Young Kun Ko will present his FPO "Hardness Amplification in Two Prover Game and Communication Complexity" on Monday, 9/17/2018 at 1pm in CS 401. The members of his committee are as follows: Mark Braverman (Adviser); Omri Weinstein (Columbia University) and Gillat Kol (Readers); Zeev Dvir and Ran Raz (Examiners). A copy of his thesis is available in CS 310. All are welcome to attend. Abstract follows below. Whether repeating a task n-times in parallel amplifies the complexity measure in question by n-times is a key technical challenge in complexity theory. As a prelude to alternatives to parallel repetition, we investigate set-based repetition techniques. First we explore the applications of Birthday repetition, first introduced in [2] for quasi-polynomial time hardness results. These include hardness of computing best approximate Nash Equilibria in strategic bimatrix game [53], hardness of finding Densest k-subgraph [50] and hardness of obtaining best signaling scheme in zero-sum bayesian game [68]. >From computational perspective, we first investigate the power and limits of parallel repetition of two-prover game [49]. We characterize the amortized behavior of the game via how much information one needs to win the game with good probability providing an intuitive explanation on why odd-cycle game introduced by [156] serves as a counterexample to strong parallel repetition. Then as an alternative to parallel repetition, we introduce symmetric parallel repetition, that is parallel repetition without coordinates. We show that symmetric parallel repetition indeed beats parallel repetition in some regimes and odd-cycle game is not a counterexample for symmetric parallel repetition. This sheds some light on possible attack route for infamous Unique Games Conjecture. >From communication complexity perspective, we first tackle round tradeoff for Disjointness with Quantum communication. Then we introduce semi-direct sum as a mean to amplify hardness for asymmetric communication. As an application, we reprove and improve the lower bound for �∞ approximate nearest neighbor search.

1 0

Caroline Trippel will present her Pre FPO "Concurrency and Security Verification in Heterogeneous Parallel Systems" on Monday, September 10, 2018 at 2pm in CS 402.
by Nicki Gotsis 07 Sep '18

07 Sep '18

Caroline Trippel will present her Pre FPO "Concurrency and Security Verification in Heterogeneous Parallel Systems" on Monday, September 10, 2018 at 2pm in CS 402. The members of her committee are as follows: Margaret Martonosi (advisor); Readers: Daniel Lustig (NVIDIA ) and Aarti Gupta; Examiners: Andrew Appel and David Wentzlaff (non-reader). All are welcome to attend. Concurrency and Security Verification in Heterogeneous Parallel Systems Abstract Modern computer systems achieve high performance scaling at manageable power and thermal levels by employing parallelism along with high degrees of specialization and heterogeneity. Parallelism and heterogeneity have been employed for years, but today the increasing degree to which they are used poses grand challenge verification problems regarding the “accuracy” of event orderings in system-wide executions. Memory consistency models (MCMs) are one notable design specification that articulate the event orderings needed to guarantee correctness for concurrent programs. As it turns out, accuracy of event orderings forms the cornerstone of security, as well as concurrency in modern processors. Namely, a significant portion of hardware security vulnerabilities that lead to violations of confidentiality and integrity are similarly related to event orderings. My dissertation creates formal, automated tools and techniques for interactive, early-stage specification and verification of the correctness and security of software executing on heterogeneous parallel systems. To address correctness, my work has produced techniques and a novel tool-flow, TriCheck, for full-stack MCM verification. TriCheck leverages SMT-based analysis of hardware-aware program execution graphs to determine if a specific combination of high-level language, compiler, ISA, and microarchitecture align on MCM requirements. In TriCheck’s evaluation of the RISC-V ISA’s support for C11 programs, TriCheck identified fundamental flaws in RISC-V’s draft MCM specification. This work also identified bugs in two previously “proven-correct” compiler mappings from C11 to IBM Power and ARMv7 leading to the discovery of flaws in C11’s MCM itself. To tackle security, my work makes the important and non-obvious observation that the event ordering issues present in hardware MCM analysis are similar to those relevant for hardware security analysis. By re-purposing and augmenting the graph-based MCM analysis techniques above, my work has produced a methodology and tool, CheckMate, for evaluating a microarchitecture’s susceptibility to formally-specified classes of security exploits and for synthesizing proof-of-concept exploit code when it is. Using this tool to evaluate the susceptibility of a speculative out-of-order processor to Flush+Reload cache side-channel attacks resulted in automatically synthesized programs representative of those that were publicly disclosed for conducting Meltdown and Spectre attacks. Evaluating the same processor on its susceptibility to Prime+Probe attacks generated two new exploits, highlighting the importance of automated verification techniques for identifying hardware security vulnerabilities. Overall, these techniques offer advances that allow architects and system designers to play an important early-stage role in system verification for correctness and security, by offering efficient and high-coverage formal methods on which to explore system designs and their vulnerabilities. Bio Caroline Trippel is a Ph.D. candidate in the Computer Science department at Princeton University. She is advised by Professor Margaret Martonosi on her computer architecture dissertation research, specifically on the topic of concurrency and security verification in heterogeneous parallel systems. Her work has resulted in formal, automated tools and techniques for specifying and verifying the correct and secure execution of software running on such systems. She has influenced the design of the RISC-V ISA memory consistency model (MCM) both via full-stack MCM analysis of its draft specification and her subsequent participation in the RISC-V Memory Model Task Group. Additionally, she has developed a novel methodology and tool that synthesized two new variants of the recently publicized Meltdown and Spectre attacks. Caroline received her B.S. in Computer Engineering from Purdue University in 2013, her M.A. in Computer Science from Princeton University in 2015, and was a 2017-2018 NVIDIA Graduate Fellow.

1 0

Speaker-Li Erran Li, Tomorrow, Sept 5
by Emily Lawrence 04 Sep '18

04 Sep '18

Title: Machine Learning for Autonomous Driving: Recent Advances and Future Challenges Li Erran Li, Pony AI Wed Sept 5 12-1pm; Room 302 in CS building (Pizza served before the talk, and the speaker expressed interest in talking to grads) Abstract: Tremendous progresses have been made in applying machine learning to autonomous driving. However, there are fundamental challenges ahead. In this talk, I will present recent advances in applying machine learning to solving the perception, prediction, planning and control problems of autonomous driving. I will discuss key research challenges in learning more robust and abstract representations, scene understanding, behavior prediction, and decision-making in complex real-world scenarios. Bio: Dr. Li Erran Li is the chief scientist at Pony.ai and an adjunct professor at Columbia University. Most recently, he was with the perception team at Uber ATG. Before that, he was at Bell Labs. Dr. Li’s current research interests are machine learning, computer vision and learning-based robotics. Dr. Li has a PhD from the Computer Science Department at Cornell University. Dr. Li is an IEEE Fellow and an ACM Fellow.

1 0

Muhammad Shahbaz will present his FPO, " Enabling Programmable Infrastructure for Multi-tenant Data Centers " on Friday, 9/7/2018 at 11am in CS 302.
by Nicki Gotsis 31 Aug '18

31 Aug '18

Muhammad Shahbaz will present his FPO, " Enabling Programmable Infrastructure for Multi-tenant Data Centers " on Friday, 9/7/2018 at 11am in CS 302. The members of his committee are as follows: Adviser: Nick Feamster; Readers: Jennifer Rexford and Ben Pfaff (VMware Inc.); Examiners: Wyatt Lloyd, Michael Freedman, and Nick Feamster. Everyone is welcome to attend. A copy of his thesis is available in CS 310. Abstract follows below. Today’s data centers are large, shared infrastructures hosting hundreds of thousands of tenants over a vast network of servers. Operating these data centers frequently entails incorporating new infrastructure services that require customizing the behavior of its switches and exploiting unique characteristics of data centers to scale. Emerging programmable switch ASICs allow network operators to customize the behavior of physical switches. Yet, virtual switches running on servers in multitenant data centers are still fixed function and composed of large, complex software codebases. Modifying these switches requires both intimate knowledge of the switch codebase and extensive expertise in network protocol design, raising the bar for customizing these switches prohibitively high. In this dissertation, we address these challenges by, first, presenting the design and implementation of PISCES: a programmable, protocol-independent software switch derived from Open vSwitch (OVS), a fixed-function hypervisor switch, whose behavior is customized using P4. PISCES is not tethered to specific protocols; this independence makes it easy to add new features. We also show how the compiler can analyze the high-level specification to optimize forwarding performance. Our evaluation shows that PISCES performs comparably to OVS and that P4 programs for PISCES are about 40 times shorter than equivalent changes to OVS source code. Next, we demonstrate how such programmable switches help build scalable infrastructure services by exploiting the unique characteristics of data-center networks. We use these switches to address the multicast scalability problem in multi-tenant data centers and present the design of an infrastructure service, Elmo, that scales multicast by taking advantage of the data-center characteristics; specifically, the symmetric topology and short paths in a data center. In Elmo, a PISCES switch encodes multicast group information inside packets themselves, reducing the need to store the same information in hardware switches, which instead read the encoded information to route packets to recipients. In a three-tier data-center topology with 27,000 hosts, Elmo supports a million multicast groups using a 325-byte packet header, requiring as few as 1,100 multicast group-table entries on average in hardware switches, with a traffic overhead as low as 5% over ideal multicast.

1 0

Arpit Gupta will present his FPO "Flexible and Scalable Systems for Network Management" on Friday, 8/31/2018 at 10 am in CS 302.
by Nicki Gotsis 28 Aug '18

28 Aug '18

Arpit Gupta will present his FPO "Flexible and Scalable Systems for Network Management" on Friday, 8/31/2018 at 10 am in CS 302. The members of his committee are as follows: Adviser: Nick Feamster; Readers: Nick Feamster, Jennifer Rexford, and Walter Willinger (NIKSUN Inc.); Examiners: Marshini Chetty, Kyle Jamieson, and Nick Feamster. Everyone is invited to attend. A copy of his thesis is available in CS 310. Thesis abstract follows below. Our daily lives are heavily reliant upon Internet-connected devices, services, and applications. This reliance makes it more critical than ever that the underlying networks they depend on be reliable, performant, and secure. At the same time, the increasing complexity and diversity of today's devices, services, and applications have made network management tasks more complicated than ever. Modern network management mandates that operators can systematically monitor what is going on in their networks (network monitoring) and use this information to take real-time preventive or corrective actions (network control). Achieving these goals while also adhering to the limited compute and storage resources available on modern network devices poses signi\u000Ccant challenges. The contribution of this dissertation is the design and implementation of two systems that enable exible and scalable network monitoring and control. The networkmonitoring system, Sonata, collects and analyzes network tra c to infer various network events in real time. The network-control system, SDX, enables \u000Cne-grained reactive control actions for interdomain tra c without disrupting the existing routing protocols. For each of these two systems, the dissertation focuses on (i) the ab- stractions that allow network operators to express exible programs for both network monitoring and control; (ii) the algorithms that make the best use of limited compute and storage resources; and (iii) the systems that combine the high-level abstractions and the low-level algorithms and can be deployed in production settings. The lessons learned from this dissertation can help us design next-generation network-management systems. More concretely, unlike existing systems that rely solely on a single device-type, this dissertation shows that designing systems that can pool resources from a heterogeneous set of devices (targets) is critical for building exible and scalable network-management systems. It also demonstrates that as the networking technologies and protocols evolve rapidly with time, it is imperative to design modular systems that can swiftly catch up with these changes. Finally, this research also illustrates that it is crucial to select strategic locations (e.g., Internet exchange points) for deployment to drive innovations in Internet-wide tra c monitoring and control.

1 0