- talks - lists.cs.princeton.edu

Colloquium Speaker: Lester Mackey Monday Dec 14, 12:30pm
by Nicole E. Wagenblast 14 Dec '15

14 Dec '15

Colloquium Speaker- Joint talk with CSML Lester Mackey, Stanford University Monday, December 14, 12:30pm Computer Science 105 Matrix Completion and Matrix Concentration The goal in matrix completion is to recover a matrix from a small subset of noisy entries. Web-scale instances of this problem include collaborative filtering for recommendation and link prediction in social networks. Many modern matrix completion algorithms provide strong recovery guarantees but scale poorly due to the repeated and costly computation of truncated SVDs. To address this deficiency, in the first part of this talk, I will introduce Divide-Factor-Combine (DFC), a parallel divide-and-conquer framework for boosting the scalability of a matrix completion algorithm while retaining its theoretical guarantees. Our experiments demonstrate the near-linear to super-linear speed-ups attainable with this approach, and our analysis shows that DFC enjoys high-probability recovery guarantees comparable to those of its base algorithm. Fundamental to our analysis – and to the analyses of many matrix completion procedures – are matrix concentration inequalities that characterize the fluctuations of a random matrix about its mean. In the second part of this talk, I will show how Stein’s method of exchangeable pairs can be used to derive concentration inequalities for matrix-valued random elements. When applied to a sum of independent random matrices, this approach yields matrix generalizations of the classical inequalities due to Hoeffding, Bernstein, Khintchine, and Rosenthal. The same technique delivers bounds for sums of dependent random matrices and more general matrix functionals of dependent random elements.

1 2

ACM/IEEE celebrates Computer Science Education week- Speaker: Robert Sedgewick
by Nicole E. Wagenblast 10 Dec '15

10 Dec '15

All ACM / IEEE-CS meetings are open to the public. Students and their parents are welcome. There is no admission charge. Princeton ACM/IEEE- CS Chapters The following "computer science in education" talk is part of our celebration of Computer Science Education Week (December 7 -13, http://csedweek.org ). Computer Science for the Masses Robert Sedgewick, Princeton University, Computer Science Thursday, December 10, 8pm Friend Center, 101 Colleges and universities need a good "introduction to computer science" for their students. What should we teach and how should we teach it? How should we use technology in an introductory course? This talk describes a introductory computer science course at Princeton University. The course has been under development for 25 years. It is the highest-enrolled course at Princeton, attracting two-thirds of all students, preparing them all for further study in computer science (nearly 40% of all Princeton students are taking a CS course at any point in time). The content is broad and deep, building on a solid foundation in programming to address fundamental issues in theoretical computer science and to also provide an overview of computer architecture, all in the context of interesting applications in science, engineering, and commerce. The course is currently using a new textbook, extensive online content, and studio-produced lecture videos. Robert Sedgewick is the founding chair and the William O. Baker Professor in the Department of Computer Science at Princeton and a member of the board of directors of Adobe Systems. His research interests revolve around algorithm design, including mathematical techniques for the analysis of algorithms. Prof. Sedgwick is the author of the very popular textbook "Algorithms, Fourth Edition" and other books on algorithms that have been best-sellers for decades. On-line meeting notice: http://PrincetonACM.acm.org/meetings/mtg1512.pdf

1 1

Colloquium Speaker- Gillat Kol, Today, 12:30pm
by Nicole E. Wagenblast 10 Dec '15

10 Dec '15

Colloquium Speaker Gillat Kol, Institute for Advanced Study Thursday, December 10, 12:30pm Computer Science 105 Interactive Information Theory In a profoundly influential 1948 paper, Claude Shannon introduced information theory and used it to study one-way data transmission problems over different channels, both noisy and noiseless. That paper initiated the study of error correcting codes and data compression, two concepts that are especially relevant today with the rise of the internet and data-intensive applications. In the last decades, interactive communication protocols are used and studied extensively, raising the fundamental question: To what extent can Shannon's results be generalized to the interactive setting, where parties engage in an interactive communication protocol? In this talk we will focus on the interactive analog of data compression in an attempt to answer the above question.

1 0

Colloquium Speaker- Gillat Kol, Thurs Dec 10, 12:30pm
by Nicole E. Wagenblast 09 Dec '15

09 Dec '15

Colloquium Speaker Gillat Kol, Institute for Advanced Study Thursday, December 10, 12:30pm Computer Science 105 Interactive Information Theory In a profoundly influential 1948 paper, Claude Shannon introduced information theory and used it to study one-way data transmission problems over different channels, both noisy and noiseless. That paper initiated the study of error correcting codes and data compression, two concepts that are especially relevant today with the rise of the internet and data-intensive applications. In the last decades, interactive communication protocols are used and studied extensively, raising the fundamental question: To what extent can Shannon's results be generalized to the interactive setting, where parties engage in an interactive communication protocol? In this talk we will focus on the interactive analog of data compression in an attempt to answer the above question.

1 0

Xiaozhou Li will present his Pre-FPO on 12/9/15 in CS 401 at 10am
by Nicki Gotsis 08 Dec '15

08 Dec '15

Xiaozhou Li will present his Pre-FPO on 12/9/15 in CS 401 at 10am. The members of his committee are: Mike Freedman (adviser), Kyle Jamieson, Michael Kaminsky (Intel Labs), Jennifer Rexford, and Kai Li. Below are the title and abstract of his talk. Title: Towards High-performance and Cost-effective Key-Value Storage Abstract: Key-value storage is one of the fundamental building blocks for today’s large-scale, high-performance data-intensive applications. In this talk, I will present my research on improving the performance and scalability of key-value storage in a cost effective manner, with a particular focus on combining new hardware and infrastructure capabilities with carefully-crafted algorithmic techniques. I will first present the design, implementation, and evaluation of a high-throughput and memory-efficient concurrent hash table. The design arises from careful attention to systems-level optimizations such as minimizing critical section length and reducing interprocessor coherence traffic through algorithm re-engineering. We exploited Intel’s recent hardware transactional memory (HTM) for concurrency control, and found that HTM provides software engineering benefits by reducing the intellectual complexity of locking more than it provides performance benefits. Algorithmic optimizations that benefit both HTM and designs for fine-grained locking are needed to achieve high performance. In the second part of this talk, I will present SwitchKV, a new scalable key-value store system design that combines high-performance cache nodes with resource constrained backend nodes to provide load balancing in the face of unpredictable workload skew. The cache nodes absorb the hottest queries so that no individual backend node is over-burdened. Compared with previous designs, SwitchKV exploits SDN techniques and deeply optimized switch hardware to enable efficient content based routing. Programmable network switches keep track of cached keys and route requests to the appropriate nodes at line speed, based on keys encoded in packet headers. A new hybrid caching strategy keeps cache and switch forwarding rules updated with low overhead and ensures that system load is always well-balanced under rapidly changing workloads. We demonstrate SwitchKV can meet the service-level objectives for many cloud services more efficiently than traditional systems.

1 0

Nanxi Kang will present her FPO, "Flexible Enterprise Network Management on Commodity Switches" on Monday, 12/14/2015 at 3pm - 5pm, 301 COS.
by Nicki Gotsis 07 Dec '15

07 Dec '15

Nanxi Kang will present her FPO, "Flexible Enterprise Network Management on Commodity Switches" on Monday, 12/14/2015 at 3pm - 5pm, 301 COS. The members of her committee are, Jennifer Rexford (adviser), readers: Nicholas Feamster and Sanjay Rao (Purdue University); nonreaders: David Walker and Michael Freedman A copy of her thesis is available in Room 310. Everyone is invited to attend her talk. The talk abstract follows below: Enterprise networks interconnect heterogeneous hosts, requiring careful management to provide secure, reliable and high-performance network communication. Today, the operators have to manually configure individual network devices, while considering the host address assignments and devices constraints (e.g., limited memory). These approaches are too complicated and inefficient for enterprise networks with growing numbers of hosts and devices. The rise of Software Defined Networks (SDN) offers opportunities to simplify the management of enterprise networks. Leveraging the logically-centralized control plane and the programmable switch rule-tables in SDN, we design a novel network management system that supports flexible policies and reduces configuration complexity. We argue that the operators should focus on defining network-wide policies rather than grappling with low-level details, such as switch memory sizes, individual switch configurations and host addresses. It is the controller’s job to compile the high-level policies into rules for individual switches while staying within the rule-table sizes. In this thesis, we present a flexible enterprise network management system that assigns addresses based on host attributes, distributes network-wide policies across multiple switches and computes switch rules to achieve high-level load balancing policies. Specifi-cally, • we propose the “Attribute-Carrying IPs” (ACIPs) abstraction, where the attributes of a host are encoded in the IP addresses to enable flexible policy specification. We present Alpaca, algorithms for realizing ACIPs under practical constraints of limited length IP addresses and constraint switch rule-tables. • we propose the “One Big Switch” abstraction, which consists of an endpoint policy that views all hosts connected to a single switch, a hop-by-hop routing policy that defines paths between endpoints and a compiler that synthesizes switch rules that iii obey policies and adhere to the resource constraints. We present efficient algorithms that distribute policies across networks while managing rule-space constraints. • we propose the “One Big Server” abstraction, where a switch load balances incoming service requests to multiple equivalent servers based on their capacities. We present Niagara, an SDN-based traffic-splitting scheme that achieves accurate traffic splits while being extremely efficient in using the rule-table space.

1 0

Yiming Liu will present his FPO on Wednesday, 12/9/2015 at 10am, 402 Computer Science.
by Nicki Gotsis 02 Dec '15

02 Dec '15

Yiming Liu will present his FPO on Wednesday, 12/9/2015 at 10am, 402 Computer Science. The members of his committee are Szymon Rusinkiewicz (advisor), readers: Aseem Agarwala (Google) and Adam Finkelstein; nonreaders: Jianxiong Xiao and Thomas Funkhouser. 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: Internet-Data-Driven Image Creation and Enhancement. Traditional systems for image creation and enhancement are completely reliant on user input, either to generate content directly or to evaluate and tune algorithms. The input must be generated by talented artists, and it is applicable only to the image for which it was originally intended. This poses scalability challenges for such traditional image generation and editing systems. An alternative paradigm, which is being researched in a variety of contentgeneration domains, is to exploit the large amount of data made available by users over the Internet. This data may take many forms: images, image keywords, and even judgments about image quality. Although the data is noisy and was not originally intended for the task at hand, it nevertheless serves as a useful source of “prior information.” These priors make it possible to build image creation and enhancement systems that require only a small amount of user input, and do not require the users to be professional artists or designers. This thesis describes three such systems, including low-level image-processing (motion deblurring), high-level editing (keyword-based image stylization), and image creation (sketch-driven iconification). First, by learning based on a massive online user study, we develop a metric for automatically predicting the perceptual quality of images produced by motion deblurring algorithms, without access to the original images. Second, by leveraging online image search engines, we investigate an approach to photo filtering that only requires the user to provide one or more keywords. Third, we develop a system that synthesize a variety of pictograms by remixing portions of icons retrieved from a large online repository.

1 0

Colloquium Speaker- Gillat Kol, Thurs Dec 10, 12:30pm
by Nicole E. Wagenblast 02 Dec '15

02 Dec '15

Colloquium Speaker Gillat Kol, Institute for Advanced Study Thursday, December 10, 12:30pm Computer Science 105 Interactive Information Theory In a profoundly influential 1948 paper, Claude Shannon introduced information theory and used it to study one-way data transmission problems over different channels, both noisy and noiseless. That paper initiated the study of error correcting codes and data compression, two concepts that are especially relevant today with the rise of the internet and data-intensive applications. In the last decades, interactive communication protocols are used and studied extensively, raising the fundamental question: To what extent can Shannon's results be generalized to the interactive setting, where parties engage in an interactive communication protocol? In this talk we will focus on the interactive analog of data compression in an attempt to answer the above question.

1 0

Talk: Arjun Guha, Monday Nov 30, 1:30pm
by Nicole E. Wagenblast 30 Nov '15

30 Nov '15

Talk Arjun Guha, University of Massachusetts, Amherst Monday, November 30, 1:30PM CITP Conference room, 3rd floor Sherrerd Hall A Fast Compiler for NetKAT In the past few years, high-level programming languages have played a key role in several networking platforms, by providing abstractions that streamline application development. Unfortunately, current compilers can take tens of minutes to generate forwarding state for even relatively small networks. This forces programmers to either work around performance issues or revert to using lower-level APIs. In this talk, we first present a new compiler for NetKAT (a network programming language) that is two orders of magnitude faster than existing systems. Our key insight is a new intermediate representation based on a variant of binary decision diagrams that can represent network programs compactly and supports fast, algebraic manipulation. We argue that our compiler scales to large networks using a diverse set of benchmarks. In addition to speed, our new intermediate representation lets us build a powerful new abstraction for network programming. Existing languages provide constructs for programming individual switches, which forces programmers to specify whole-network behavior on a switch-by-switch basis. For the first time, we can compile programs that syntactically represent sets of end-to-end paths through the network. To do so, our compiler automatically inserts stateful operations (e.g., VLAN tagging) to distinguish overlapping paths from each other. Finally, we present a very general implementation of network virtualization that leverages our ability to compile end-to-end paths. The key insight is to give packets two locations--physical and virtual--and synthesize a program that moves packets along physical paths to account for hops in the virtual network. We show that different synthesis strategies can be used to implement global requirements, such as shortest paths, load-balancing, and so on. Arjun Guha is an assistant professor of Computer Science at UMass Amherst. He enjoys tackling problems in systems using the tools and principles of programming languages. Apart from network programming, he has worked on Web security and system configuration languages. He received a PhD in Computer Science from Brown University in 2012 and a BA in Computer Science from Grinnell College in 2006.

1 1

Colloquium Speaker Ran Raz, Mon Nov 30, 12:30pm
by Nicole E. Wagenblast 30 Nov '15

30 Nov '15

Colloquium Speaker Ran Raz, The Weizmann Institute of Science Monday, November 30, 12:30pm Computer Science 105 Delegation of Computation, P-completeness of Linear Programming, and the many facets of the notion of a proof Suppose that Alice performs some computation for Bob, as he does not have sufficient computational power to run the computation himself. Can Bob be convinced that the computation was done correctly? Delegation of Computation is a central problem in modern cryptography. I will describe a recent one-round delegation protocol. The discussion will take us on a journey into the notion of a proof, through some of the most fascinating ideas in the history of theoretical computer science. I will conclude with a seemingly unrelated application to the P-completeness of Linear Programming with a fixed polytope.

1 1