- talks - lists.cs.princeton.edu

Sotirios Apostolakis will be presenting his general exam "Securing Commodity Systems with Containment: a Redis Server Case Study" on Monday, October 23, 2017 at 2:30pm in CS 402.
by Nicki Gotsis 18 Oct '17

18 Oct '17

Sotirios Apostolakis will be presenting his general exam " Securing Commodity Systems with Containment: a Redis Server Case Study" on Monday, October 23, 2017 at 2:30pm in CS 402. The members of his committee are David August (adviser), Nick Feamster, and Andrew Appel. Everyone is invited to attend his talk. Abstract: Modern computing systems are too complex to be vulnerability free. Current reactive approaches to security are not effective, and proposed "clean slate" approaches, requiring formal proofs of correctness for whole systems, are impractical. Prior work introduced TrustGuard, an approach that provides proactive protection against malicous and buggy hardware by allowing only the correct execution of signed software to produce output. This work expands TrustGuard’s containment guarantees to additionally protect against flawed software. To demonstrate TrustGuard's expanded capabilities, we implemented a system that secures a commodity Redis server against deviations from the Redis server specification. We show that 4K RTL LOC (one time cost on FPGA network card) and 3K software LOC can secure a modern Redis server consisting of hundreds of millions of LOC of hardware, OS, libraries and applications.

1 0

Raghuvansh Saxena will present his General Exam on Monday, October 16, 2017 in CS 233 at 11am
by Nicki Gotsis 13 Oct '17

13 Oct '17

Raghuvansh Saxena will present his General Exam on Monday, October 16, 2017 in CS 233 at 11am. The members of his committee are: Gillat Kol (adviser), Matt Weinberg, and Mark Braverman. Everyone is invited to attend his talk, and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. "Interactive Coding Over the Noisy Broadcast Channel" A set of n players, each holding a private input bit, communicate over a noisy broadcast channel. Their mutual goal is for all players to learn all inputs. At each round one of the players broadcasts a bit to all the other players, and the bit received by each player is flipped with a fixed constant probability (independently for each recipient). How many rounds are needed? This problem was first suggested by El Gamal in 1984. In 1988, Gallager gave an elegant noise-resistant protocol requiring only O(n log log n) rounds. The problem got resolved in 2005 by a seminal paper of Goyal, Kindler, and Saks, proving that Gallager’s protocol is essentially optimal. We revisit the above noisy broadcast problem and show that O(n) rounds suffice. This is possible due to a relaxation of the model assumed by the previous works. We no longer demand that exactly one player broadcasts in every round, but rather allow any number of players to broadcast. However, if it is not the case that exactly one player chooses to broadcast, each of the other players gets an adversely chosen bit. We generalized the above result and initiate the study of interactive coding over the noisy broadcast channel. We show that any interactive protocol that works over the noiseless broadcast channel can be simulated over our restrictive noisy broadcast model with constant blowup of the communication. Reading list: Textbook: Computational Complexity: A Modern Approach - By Sanjeev Arora and Boaz Barak. Survey: Coding for Interactive Communication: A Survey - By Ran Gelles. Papers: Finding parity in a simple broadcast network - Robert Gallager Deterministic coding for interactive communication - Leonard Schulman Communication on noisy channels: a coding theorem for computation - Leonard Schulman Lower Bounds for the Noisy Broadcast Problem - Navin Goyal, Guy Kindler, and Michael Saks Towards Coding for Maximum Errors in Interactive Communication - Mark Braverman and Anup Rao A coding theorem for distributed computation - Sridhar Rajagopalan and Leonard Schulman Information Equals Amortized Communication - Mark Braverman and Anup Rao Interactive channel capacity - Gillat Kol and Ran Raz Constant-rate coding for multiparty interactive communication is impossible - Mark Braverman, Klim Efremenko, Ran Gelles, and Bernhard Haeupler Optimal Error Rates for Interactive Coding I: Adaptivity and Other Settings - Mohsen Ghaffari, Bernhard Haeupler, and Madhu Sudan

1 0

Linpeng Tang will present his pre FPO, "Efficient processing and delivery of multimedia data" on Friday, October 20, 2017 at 2pm in CS 402.
by Nicki Gotsis 12 Oct '17

12 Oct '17

Linpeng Tang will present his pre FPO, " Efficient processing and delivery of multimedia data" on Friday, October 20, 2017 at 2pm in CS 402. The members of his committee are as follows: Readers: Prof. Mike Freedman, Prof. Wyatt Lloyd Non-readers: Prof. Jen Rexford, Prof. Kyle Jamieson Advisor: Prof. Kai Li Everyone is invited to attend his talk. The talk title and abstract follow below. Title: Efficient processing and delivery of multimedia data Abstract: With the rise of smart mobile devices and faster networks, multimedia data, such as photos and videos, are becoming a central part of people's digital lives in recent years. Meanwhile, new challenges have also emerged on how to process and delivery such data efficiently. This thesis I will investigate three challenging problems related to this area. The first part is about how to cache photo content in the large-scale content delivery network. We have designed and implemented RIPQ, an advanced photo caching framework on SSD. The Flash Translation Layer on SSD devices doesn't cope well with the random writes generated by advanced caching algorithms, causing lower througput and reduced device lifespan. To solve this issue, RIPQ aggregates small random writes, co-locates similarly prioritized content, and lazily moves updated content to reduce device overhead. Our evaluation on Facebook’s photo trace shows that two advanced caching algorithms running on RIPQ increase hit ratios up to ~20% over the current FIFO system, incur low overhead, and achieve high throughput. It has also since been deployed on the Facebook photo serving stack. The second part is on how to improve the streaming quality of social media video content. I will present CHESS, a scalable and accurate video popularity prediction algorithm. By accuratly predicting the popular videos, CHESS allows us to focus intensive processing on a small amount of videos, while improving user experience for most viewers. CHESS only requires constant space per video while delivering superior predictions using a combination of historical access patterns with social signals, in a unified online learning framework. In evaluation we find that re-encoding popular videos predicted by CHESS enables 80% Facebook user watch time to benefit from a computing intensive encoding, with only one-third computing overhead compared to a recent production heuristic. Finally, deep learning emerges as the most effective machine learning method for analyzing many types of content. Computing is a bottleneck for performing such analytics at scale, and I will present Graphi, a generic and high-performance execution engine for deep learning computation on many-core CPUs. We find that the key is finding the right balance between intra/inter operation parallelization, while minimizing resource interference across the weak cores. We therefore have designed and implemented Graphi using intelligent scheduling algorithms with feedback from a profiler, and a thread management system. Our experiments on show that the various training times with Graphi are 2.1× to 9.5× faster than those with TensorFlow on a 68-core Intel Xeon Phi processor.

1 0

Davit Buniatyan will present his general exam on Friday, October 13, 2017 at 4pm in CS 402.
by Nicki Gotsis 11 Oct '17

11 Oct '17

Davit Buniatyan will present his general exam on Friday, October 13, 2017 at 4pm in CS 402. The members of his committee are as follows: Sebastian Seung (adviser), Yoram Singer, and Szymon Rusinkiewicz. Everyone is invited to attend his talk, and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. Title: Deep Learning Improves Template Matching by Normalized Cross Correlation Abstract: Template matching by normalized cross correlation (NCC) is widely used for finding image correspondences. We improve the robustness of this algorithm by preprocessing images with "siamese" convolutional networks trained to maximize the contrast between NCC values of true and false matches. The improvement is quantified using patches of brain images from serial section electron microscopy. Relative to a parameter-tuned bandpass filter, siamese convolutional networks significantly reduce false matches. Furthermore, all false matches can be eliminated by removing a tiny fraction of all matches based on NCC values. The improved accuracy of our method could be essential for connectomics, because emerging petascale datasets may require billions of template matches to assemble 2D images of serial sections into a 3D image stack. Our method is also expected to generalize to many other computer vision applications that use NCC template matching to find image correspondences. Reading List * Ian Goodfellow and Yoshua Bengio and Aaron Courville, Deep Learning, * Brian Kulis et al. Metric learning: A survey. Foundations and TrendsR in Machine Learning, 5(4): 287–364, 2013 * Jane Bromley, James W. Bentz, Léon Bottou, Isabelle Guyon, Yann LeCun, Cliff Moore, Eduard Säckinger, and Roopak Shah. Signature verification using a "siamese" time delay neural network. IJPRAI, 7(4): 669–688, 1993. * Sumit Chopra, Raia Hadsell, and Yann LeCun. Learning a similarity metric discriminatively, with application to face verification. In Computer Vision and Pattern Recognition, 2005. CVPR 2005. IEEE Computer Society Conference on, volume 1, pages 539–546. IEEE, 2005. * Han, Xufeng, et al. "Matchnet: Unifying feature and metric learning for patch-based matching." Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition . 2015. * Arulkumar Subramaniam, Moitreya Chatterjee, and Anurag Mittal. Deep neural networks with inexact matching for person re-identification. In Advances in Neural Information Processing Systems, pages 2667–2675, 2016. * Stephan Saalfeld, Richard Fetter, Albert Cardona, and Pavel Tomancak. Elastic volume reconstruction from series of ultra-thin microscopy sections. Nature methods, 9(7):717–720, 2012. * Jonathan L Long, Ning Zhang, and Trevor Darrell. Do convnets learn correspondence? In Advances in Neural Information Processing Systems, pages 1601–1609, 2014.

1 0

Xinyi Fan will present her pre-FPO on Tuesday, October 10, 2017 at 2pm in CS 401.
by Nicki Gotsis 09 Oct '17

09 Oct '17

Xinyi Fan will present her pre-FPO on Tuesday (October 10) 2-4pm in CS 401. Advisor: Szymon Rusinkiewicz FPO examiners: Adam Finkelstein, Peter Ramadge (ELE) Thesis readers: Tom Funkhouser, Yuxin Chen (ELE) Title: View and Path Planning for Large-Scale 3D Acquisition Abstract: Demand for high-volume 3D scanning of real objects is rapidly growing in a wide range of applications, including online retailing, quality-control for manufacturing, stop motion capturing for 3D animation, as well as archaeological documentation and reconstruction. Although mature technologies exist for high-fidelity 3D model acquisition, deploying them at scale continues to require non-trivial manual labor. In this talk, I will present a system that allows non-expert users to scan large numbers of physical objects within a reasonable amount of time, and also with greater ease. I will describe the design of a structured-light scanner and positioning system, which are optimized for acquisition of relatively small objects, such as fragments of archaeological artifacts. I will also discuss novel view- and path-planning algorithms that enable automatic 3D acquisition, and demonstrate the ability of our prototype to safely, robustly, and automatically acquire 3D geometry and color models for large collections of small objects, such as toy soldiers and fragments of ancient artifacts.

1 0

Tengyu Ma will present his FPO, "Non-convex Optimization for Machine Learning: Design, Analysis, and Understanding" on Thursday, 10/12/2017 at 3pm, in CS 402.
by Nicki Gotsis 05 Oct '17

05 Oct '17

Tengyu Ma will present his FPO, "Non-convex Optimization for Machine Learning: Design, Analysis, and Understanding" on Thursday, 10/12/2017 at 3pm, in CS 402. The members of his committee are: Sanjeev Arora (adviser); Readers: Rong GE (Duke), Sanjeev Arora, and David Steurer (ETH Zurich); Nonreaders: Sanjeev Arora, Elad Hazan, and Mark Braverman. A copy of his thesis, is available in Room 310. Everyone is invited to attend his talk. The talk abstract follows below: Non-convex optimization is ubiquitous in modern machine learning: recent breakthroughs in deep learning require optimizing non-convex training objective functions; problems that admit accurate convex relaxation can often be solved more efficiently with non-convex formulations. However, the theoretical understanding of optimizing non-convex functions remained rather limited to the intractability result of optimizing worst case non-convex functions. Can we extend the algorithmic frontier by effi- ciently optimizing a family of interesting non-convex functions? Can we successfully apply non-convex optimization to machine learning problems with provable guarantees? How do we interpret the complicated models in machine learning that demand non-convex optimizers? Towards addressing these questions, in this thesis, we theoretically studied various machine learning models including sparse coding, topic models, and matrix completion, linear dynamical systems, and word embeddings. We first consider how to find a coarse solution to serve as a good starting point for local improvement algorithms such as stochastic gradient descent. We propose ef- ficient methods for sparse coding and topic inference with better provable guarantees. Second, we propose a framework for analyzing local improvement algorithms with a good starting point. We apply it successfully to the sparse coding problem and demonstrate its advantage over other related frameworks. Then, we consider minimizing a family of non-convex functions that local improvement algorithms can succeed efficiently from random or arbitrary initialization — the family of functions of which all local minima are also global. The challenge, in turn, becomes proving the objective function belongs to this class. We establish such type of results for the natural learning objectives for matrix completion and learning linear dynamical systems. iii Finally, we make steps towards interpreting the non-linear models that require non-convex training algorithms. We reflect on the principles of word embeddings in natural language processing. We give a generative model for the texts, using which we explain why different non-convex formulations such as word2vec and GloVe can learn similar word embeddings with the surprising performance — analogous words have embeddings with similar differences.

1 0

Rajesh Ranganath will present his FPO, "Black Box Variational Inference: Scalable, Generic Bayesian Computation and its Applications" on Friday, 10/6/2017 at 11am in CS 105.
by Nicki Gotsis 02 Oct '17

02 Oct '17

Rajesh Ranganath will present his FPO, "Black Box Variational Inference: Scalable, Generic Bayesian Computation and its Applications" on Friday, 10/6/2017 at 11:00 in CS 105. The members of his committee are as follows: David Blei (Adviser); Examiners: Sanjeev Arora, Barbara Engelhardt, and David Blei; Non Examiners: David Blei and Peter Orbanz (Columbia University, Department of Statistics) A copy of his thesis, is available in Room 310. Everyone is invited to attend his talk. The talk abstract follows below. Probabilistic generative models are robust to noise, uncover unseen patterns, and make predictions about the future. These models have been used successfully to solve problems in neuroscience, astrophysics, genetics, and medicine. The main computational challenge is computing the hidden structure given the data—posterior inference. For most models of interest, computing the posterior distribution requires approximations like variational inference. Variational inference transforms posterior inference into optimization. Classically, this optimization problem was feasible to deploy in only a small fraction of models. This thesis develops black box variational inference. Black box variational inference is a variational inference algorithm that is easy to deploy on a broad class of models and has already found use in models for neuroscience and health care. It makes new kinds of models possible, ones that were too unruly for previous inference methods. One set of models we develop is deep exponential families. Deep exponential families uncover new kinds of hidden pattens while being predictive of future data. Many existing models are deep exponential families. Black box variational inference makes it possible for us to quickly study a broad range of deep exponential families with minimal added eort for each new type of deep exponential family. The ideas around black box variational inference also facilitate new kinds of variational methods. First, we develop hierarchical variational models. Hierarchical variational models improve the approximation quality of variational inference by building higher-fidelity approximations from coarser ones. We show that they help with inference in deep exponential families. Second, we introduce operator variational inference. Operator variational inference delves into the possible distance measures that can be used for the variational optimization problem. We show that this formulation categorizes various variational inference methods and enables variational approximations without tractable densities. By developing black box variational inference, we have opened doors to new models, better posterior approximations, and new varieties of variational inference algorithms.

1 0

Katie Anna Wolf will present her FPO, "Methods for Personalized Design of Data Sonification" on Wednesday, 8/30/2017 at 10am in CS 402
by Nicki Gotsis 23 Aug '17

23 Aug '17

Katie Anna Wolf will present her FPO, "Methods for Personalized Design of Data Sonification" on Wednesday, 8/30/2017 at 10:00am in CS 402. The members of her committee are: Advisers: Adam Finkelstein and Rebecca Fiebrink (Goldsmiths, University of London); Readers: Michael Nees (Lafayette College), Adam Finkelstein, and Rebecca Fiebrink (Goldsmiths, University of London); Examiners: Adam Finkelstein, Marshini Chetty, and Daniel Trueman (Music). A copy of her thesis is available in Room 310. Everyone is invited to attend her talk. Attached is the talk abstract.

1 0

Stephen Beard will present his Pre FPO "Containment Architecture with Verified Output: A Model for Practical Trust in Real Systems" in CS 302 on Monday, August 14th at 1pm.
by Nicki Gotsis 08 Aug '17

08 Aug '17

Stephen Beard will present his Pre FPO "Containment Architecture with Verified Output: A Model for Practical Trust in Real Systems" in CS 302 on Monday, August 14th at 1pm. The members of his committee are as follows: David August (advisor) Andrew Appel (reader) Jothy Rosenberg (Dover Microsystems) (reader) Aarti Gupta (non-reader) Arvind Narayanan (non-reader) Everyone is invited to attend his talk. The talk abstract follows below: Abstract: All layers of today’s computing systems, from hardware to software, are vulnerable to attack. Market and economic pressure generally result in companies focusing on performance and features, leaving security and correctness as post deployment concerns. Thus, systems must frequently be patched or augmented after deployment to fix security vulnerabilities. While this non-virtuous exploit-patch-exploit cycle is not the most secure, it is practical enough for companies to use. Formal methods in both software and hardware can give true guarantees as to the security they provide. Ideally, modern systems would be comprised of entirely formally verified and secure components. Unfortunately, such methods have not seen widespread adoption for a number of reasons, such as difficulty in scaling, lack of tools, and high skill requirements. Additionally, the economics involved in securing and replacing every component in all systems, both new and currently deployed, are a major factor in clean slate solutions being unrealistic. Thus, a practical solution should rely on a few, simple components and should be adoptable incrementally. As the first implementation of the Containment Architecture with Verified Output (CAVO) model developed at Princeton, TrustGuard showed how a simple trusted Sentry could protect against malicious or buggy hardware components to ensure integrity of external communications. This was accomplished by ensuring the correct execution of signed software, with support from a modified CPU and system architecture. However, TrustGuard’s practicality was limited due to its reliance on modified host hardware and its requirement to trust entire application stacks, including the operating system. The work presented in this dissertation seeks to make the CAVO model a practical solution for ensuring the integrity of data communicated externally in an untrusted commodity system. This work extends CAVO in two ways. The first extension is to make the Sentry compatible with a wide range of devices without requiring hardware modifications to the host system, thus increasing its flexibility and ease of integration into existing environments. The second extension is to give developers the option to use trusted code to verify the execution of untrusted code, thus reducing the size of the trusted code base. This is similar to the way that the small, trusted Sentry can ensure correctness of execution of a large amount of complex, untrusted hardware.

1 0

Danny Huang on Cryptocurrencies, July 25 @ 12:30p
by Nick Feamster 25 Jul '17

25 Jul '17

All, Danny Huang will visit us from UCSD on July 25. He’ll give a talk on Cryptocurrencies (abstract below). If you’d like to chat with him, please sign up here: https://goo.gl/nhni3p -Nick ————— Date: July 25, 2017 Time: 12:30 p Place: Sherrerd Hall 306 (Conference Room) Title: Crypto-currencies: New opportunities for criminals, investors, and human-trafficking fighters. Abstract: When Satoshi Nakamoto designed Bitcoin, he had intended it as an “electronic cash system.” However, it is difficult to treat Bitcoin as a form of cash or currency, especially given its price volatility. Still, Bitcoin, as well as thousands of other similar crypto-currencies, allows for the exchange of value in a decentralized and partially anonymous manner. These properties have created opportunities for novel use cases, far beyond the original design goals of Satoshi Nakamoto. As I will discuss in the talk, these use cases span from being unethical to nobel, and from profit-driven to promoting social justice. In particular, three classes of users will be our focus today: (1) criminals who monetize stolen CPU cycles and files with Bitcoin; (2) investors who speculate in crypto-currencies; and (3) human-trafficking fighters who take advantage of a timing side channel in Bitcoin. ——— About the speaker: Danny Y. Huang is a PhD student at UC San Diego. He is generally interested in the economics of security/privacy. He is graduating in August. Details: https://sysnet.ucsd.edu/~dhuang

1 1