Spring 2015

ABSTRACT: The speaker will talk about applying theory to practice, with a focus on two IBM case studies. In the first case study, the practitioner initiated the interaction. This interaction led to the following problem. Assume that there is a set of “voters” and a set of “candidates”, where each voter assigns a numerical score to each candidate. There is a scoring function (such as the mean or the median), and a consensus ranking is obtained by applying the scoring function to each candidate’s scores. The problem is to find the top k candidates, while minimizing the number of database accesses. The speaker will present an algorithm that is optimal in an extremely strong sense: not just in the worst case or the average case, but in every case! Even though the algorithm is only 10 lines long (!), the paper containing the algorithm won the 2014 Godel Prize, the top prize for a paper in theoretical computer science.

The interaction in the second case study was initiated by theoreticians, who wanted to lay the foundations for “data exchange”, in which data is converted from one format to another. Although this problem may sound mundane, the issues that arise are fascinating, and this work made data exchange a new subfield, with special sessions in every major database conference.

This talk will be completely self-contained, and the speaker will derive morals from the case studies. The talk is aimed at both theoreticians and practitioners, to show them the mutual benefits of working together.

ABSTRACT: Is “software engineering” really engineering? The term was coined in 1968 to call attention to problems with software production. Both theory and practice for software have evolved since then, but do we yet have a true engineering discipline? Classical engineering disciplines have emerged from craft practice and commercialization through the infusion of codified knowledge and science. Using this emergence pattern as a point of reference, I will sketch the evolution of software engineering, drawing on civil engineering and software architecture for examples that show the progressive codification of informal knowledge toward rigorous models and tools. This will provide the basis for assessing the maturity of the field and identifying our next challenges.

ABSTRACT: One of the challenges in big data analytics is to efficiently learn and reason collectively about extremely large, heterogeneous, incomplete, noisy interlinked data. Collective reasoning requires the ability to exploit both the logical and relational structure in the data and the probabilistic dependencies. In this talk I will overview our recent work on probabilistic soft logic (PSL), a framework for collective, probabilistic reasoning in relational domains. PSL is able to reason holistically about both entity attributes and relationships among the entities. The underlying mathematical framework, which we refer to as a hinge-loss Markov random field, supports extremely efficient, exact inference. This family of graphical models captures logic-like dependencies with convex hinge-loss potentials. I will survey applications of PSL to diverse problems ranging from information extraction to computational social science. Our recent results show that by building on state-of-the-art optimization methods in a distributed implementation, we can solve large-scale problems with millions of random variables orders of magnitude faster than existing approaches.

ABSTRACT: Inference for large-scale problems in machine learning and big data often requires imposition of additional structural assumptions via regularization. The resulting optimization problems are challenging both because of the scale of the data and the nature of regularization.

We present a general framework and efficient algorithms for denoising problems (where a functional is minimized subject to a constraint on fitting the observed data). This framework captures a wide range of structured inference problems, including sparse formulations, matrix completion, and robust principal component analysis.

We highlight the importance of efficient first-order solvers, and illustrate the practical impact of the approach with synthetic and real examples using Netflix datasets, geophysical data interpolation, and cloud removal applications.

ABSTRACT: Correctness is a fundamental tenet in computer systems. In many cases, however, perfect answers are unnecessary or even impossible: small errors can be acceptable in applications such as vision, machine learning, speech recognition, search, graphics, and physical simulation. Approximate computing is a new research direction that improves efficiency by carefully relaxing correctness constraints. My research seeks to get the most out of approximate computing using collaboration between software and hardware. In hardware, I have proposed CPU designs, accelerators, and storage systems that can gracefully trade off quality for efficiency. In software, I have designed type systems, debugging tools, compilers, and a language construct called a probabilistic assertion for controlling approximation’s impact. Together, software and hardware for approximate computing can exploit applications’ latent resiliency to yield new performance and energy benefits.

ABSTRACT: Information leaks are more and more prevalent. This should be no surprise: not only are users sharing more information, but there is a growing amount of code that handles sensitive data. Unless we make it easier to create secure programs, information leaks will only get worse.

I present a language, Jeeves, where programs preserve privacy and security properties by construction. In Jeeves, the programmer specifies expressive information flow policies separately from other functionality and relies on the language runtime to automatically differentiate behavior. Jeeves is the first language to factor out information flow, preventing information leaks by reducing the opportunity for programmer error. To help programmers reason about Jeeves programs, I defined what it means for Jeeves to enforce programmer-specified policies and proved that Jeeves correctly does so.

To demonstrate the feasibility of this programming model in practice, I implemented Jeeves in Scala and Python and created Jacqueline, a Jeeves-based web framework that enforces policies end-to-end. I describe how I used Jacqueline to implement a course manager, a health record manager, and a conference management system that has been used for an academic workshop.

ABSTRACT: Cloud computing promises flexibility, high performance, and low cost. However, despite its prevalence, most datacenters hosting cloud services still operate at very low utilization, posing serious scalability concerns.

The goal of my work is to improve the scalability of these systems, by increasing their utilization, while guaranteeing high performance for each submitted application. A crucial system component to achieve this goal is the cluster manager; the system that orchestrates where applications are placed and how many resources they receive. In this talk, I will describe a new approach in cluster management that relies on two main insights. First, it automates resource management by leveraging practical data mining techniques. Second, it provides the user with a high-level, declarative interface that centers around performance, not resource reservations. Using these insights, I designed and built a datacenter scheduler (Paragon), a cluster manager (Quasar), and scalable provisioning systems for public clouds. In settings with several hundred servers, I demonstrated that this approach achieves high application performance and improves system utilization. Several production systems, including Twitter and AT&T, have since adopted similar cluster management approaches.

ABSTRACT: Modern datasets are at scales that would be unthinkable just a decade ago. This demands rethinking the principles of algorithmic design used to handle such datasets. In this talk, I will describe how such principles emerge from the methods of efficient data representations.

The first illustration will be the Nearest Neighbor Search (NNS) problem — an ubiquitous massive datasets problem that is of key importance in machine learning and other areas. A central technique for tackling this problem is Locality Sensitive Hashing (LSH), a data representation method that has seen a lot of success in both theory and practice. I will present the best possible LSH-based algorithm for NNS under the Euclidean distance. Then, I will show a new method that, for the first time, provably outperforms the LSH-based algorithms.

Taking a broader perspective, I will also describe how the lens of “efficient data representation” leads to new fast algorithms for other longstanding questions. Specifically, I will discuss a classic dynamic programming problem (edit distance) and a Linear Programming problem (earth-mover distance). Finally, I will briefly mention how the above ideas enable an algorithmic framework for parallel computation systems such as MapReduce.

ABSTRACT: In cyber-physical systems (CPS), computation, communication and control are tightly combined with physical processes of different nature. Without a comprehensive modeling formalism and a rigorous, unifying design framework, CPS integration remains ad hoc. In this talk, we introduce a design methodology that addresses the complexity and heterogeneity of cyber-physical systems by using assume-guarantee contracts to formalize the design process and enable the realization of system architectures and control algorithms in a hierarchical and compositional way.

In our methodology, the design is carried out as a sequence of refinement steps from a high-level specification to an implementation built out of a library of components at the lower level. To enable formal requirement analysis and early detection of inconsistencies, we represent the top-level system requirements as contracts, by leveraging a front-end pattern-based specification language and a set of back-end languages, including mixed integer-linear constraints and temporal logic. We show how key analysis tasks, such as refinement checking, can indeed be made more efficient when a system is described based on a precharacterized library of components and contracts. We then illustrate how top-level contracts can be refined to achieve independent implementation of system architecture and control algorithm, by combining synthesis from requirements, optimization and simulation-based design space exploration methods. At the heart of our architecture design framework, we propose two optimization-based algorithms to tackle the complexity of exact reliability computation, and enable scalable co-design of large, safety-critical systems for cost and fault tolerance.

We demonstrate, for the first time, the effectiveness of a contract-based approach on a real-life example of industrial relevance, namely the design of aircraft electric power distribution systems (EPS). In our framework, optimal selection of large, industrial-scale EPS architectures can be performed in a few minutes, while design validation of EPS controllers based on linear temporal logic contracts shows up to two orders of magnitude improvement in terms of execution time with respect to conventional techniques.

ABSTRACT: Storage services form the platform on which widely-used cloud services, mobile applications, data analytics engines, and transactional databases are built. Such services are trusted with irreplaceable personal and commercial information by users, companies, and even governments.

The designers of storage services often have to choose between performance and reliability. If the developer makes the system reliable, performance is often significantly reduced. If the developer instead maximizes performance, a crash could lead to data loss and corruption.

In this talk, I describe how to build systems that achieve both strong reliability and high performance. In many systems, reliability is maintained by carefully ordering updates to storage. The key insight is that the low-level mechanism used to enforce ordering is overloaded: it provides durability as well as ordering. I introduce a new primitive, osync(), that decouples ordering from durability of writes. I present Optimistic Crash Consistency, a new crash-recovery protocol that builds on osync() to provide strong reliability guarantees and high performance. I implement these techniques in the Optimistic File System (OptFS) and show that it provides 10X increased performance for some workloads. With researchers in Microsoft, I employ the principles of Optimistic Crash Consistency in a distributed storage system, resulting in 2-5X performance improvements.

ABSTRACT: Computer Science instruction is most effective when interesting applications are presented together with the basic course material. Using connections to real-world systems and to research is critical for keeping students engaged and excited. In this talk, I present a variety of problems which have been used in my teaching of undergraduate classes. These problems allow students to create versions of existing real-world systems, to address particular parts of research questions, and to work with actual data obtained in the field. I also use examples from my doctoral and subsequent research to design projects for students at the introductory, intermediate, and advanced levels.

ABSTRACT: Many countries restrict the information their citizens can access on the Internet by using a sophisticated censorship infrastructure to block websites, keywords, or communication that the government deems inappropriate. Although proxies can occasionally be used to circumvent such blocks, these proxies can themselves be discovered and blocked by the censor, resulting in an arms race between censors and circumventors.

In this talk, I will describe a fundamentally new approach to anticensorship that leverages the unique network perspective of ISPs to create proxies that make censoring an all-or-nothing decision. These proxies are designed to resist a censor’s attempt to detect or prevent usage, even when all information for using the proxy is made public. Blocking access to such a system involves additionally blocking economically or politically desirable sites unrelated to the censorship system, a cost that most censors are unwilling to pay. I will also describe the challenges to deploying this type of system in practice, as well as ongoing work to overcome these obstacles. Ultimately, these efforts enable a state-level response to state-sponsored censorship, giving sympathetic governments the tools needed to encourage Internet freedom.

ABSTRACT: A remarkable feature of human and animal intelligence is the ability to autonomously acquire new behaviors. My work is concerned with designing algorithms that aim to bring this ability to robots and simulated characters. A central challenge in this field is to learn behaviors with representations that are sufficiently general and expressive to handle the wide range of motion skills that are necessary for real-world applications, such as general-purpose household robots. These representations must also be able to operate on raw, high-dimensional inputs and outputs, such as camera images, joint torques, and muscle activations. I will describe a class of guided policy search algorithms that tackle this challenge by transforming the task of learning control policies into a supervised learning problem, with supervision provided by simple, efficient trajectory-centric methods. I will show how this approach can be applied to a wide range of tasks, from locomotion and push recovery to robotic manipulation. I will also present new results on using deep convolutional neural networks to directly learn policies that combine visual perception and control, learning the entire mapping from rich visual stimuli to motor torques on a real robot. I will conclude by discussing future directions in deep sensorimotor learning and how advances in this emerging field can be applied to a range of other areas.

ABSTRACT: Many combinatorial optimization problems are much simpler in practice than in the worst-case. One of the challenges in the area of approximation algorithms is to explain this phenomena and to design algorithms that work well in real-life. In this talk, we will first discuss different ways of modelling “real-life” instances. Then, I will present a new semi-random semi-adversarial model for graph partitioning problems, a planted model with permutation-invariant random edges (PIE). This model is much more general than stochastic models considered previously. Finally, I will describe a “constant factor” approximation algorithm for finding the minimum balanced cut in graphs from this model.

ABSTRACT: Data Science is establishing itself as the groundbreaking field of the 21st century. A field in which BIG data plays the central role in re-shaping almost each and every aspect of life. A field that leverages the deluge of data being collected everywhere and that have the potential to be used for great benefit to society. Today, many problems that were so far considered insolvable can now be revisited with a data science perspective. At the core of the fields that will tremendously benefit from Data science are education and medicine.

Inspired by my ongoing “Introduction to Data Science” course, I will first give an overview of Data Science, success stories and process. I will then talk about three data science problems related to medicine and education, drawn from my research. I will share ongoing efforts in studying the topics of (1) understanding infant colic, (2) predicting preterm birth, and (3) optimizing online self-learning. I will also stress the interdisciplinary nature of Data Science and the importance of Computer Science as one of the main contributing disciplines. I will finally discuss integrating Data Science into the curriculum to train a data-aware next generation of computer scientists.

ABSTRACT: My research interests focus on security and privacy of cutting edge cyberphysical technologies. For such systems, my goals are to identify the possible security and privacy threats that can arise, evaluate their impact, and develop tools to prevent the identified attacks. More specifically, I focus on the question of how cyber-physical systems leverage human idiosyncrasies, and how that opens systems to exploitations and attacks. In doing so, I draw on systems and control theory, information theory, machine learning and experimental studies.

Two of the most interesting systems I have been working with are teleoperated robots and brain-computer interfaces (BCIs). While these systems appear to be different at first glance, in this talk I will discuss how in the security and privacy context they are duals of each other. The motivation for my work with teleoperated robots comes from the observation that everyone controls robots in a unique way. My collaborators and I introduce the Fitts’ law as a novel way of quantifying the impact of cyber security attacks, and we show that cyber attacks do not impact all components of a telerobotic procedure equally. Typically, there is a difference in impact between a “free movement” component and a “fine motor (homing)” component of a teleoperated procedure.

I will then show to what extent it is possible to misuse brain-computer interfaces to extract private information about users, such as their preferences, PINs and passwords. Our research focuses on identifying what people recognize, and one of our main contributions is the demonstration that, through the use of visual stimuli, people can recognize sensitive things in their life without even realizing it. This leads to privacy risks when such stimuli are a part of a legitimate BCI application. Finally, I will present our proposed approaches to mitigate the identified attacks. We observe that two types of approaches are needed. The first approach is technical in nature, such as our proposed BCI Anonymizer and operator signature validation system. The second approach, however, is policy-based, and it involves working closely with other fields, including law, policy, and ethics.

ABSTRACT: Data centers run a range of important applications with ever increasing performance demands, from cloud and server computing to Big Data and eScience. However, the scaling of CPU frequency has stalled in recent years, leading to hardware architectures that no longer transparently scale software performance. Two trends stand out: 1) Instead of frequency, hardware architectures increase the number of CPU cores, leaving complex memory system performance and CPU scheduling tradeoffs exposed to software. 2) Network and storage I/O performance continues to improve, but without matching improvements in CPU frequency. Software thus faces ever increasing I/O efficiency demands.

In my research, I address how operating systems (OSes) can handle these growing complexity and performance pressures to avoid becoming the limiting factor to performance. I first explain how current OS architecture is already inadequate to address these trends, limiting application performance. I then present how the OS can be redesigned to eliminate the performance limitations without compromising on existing features or application compatibility. I finish with an outlook on how these hardware trends affect software in the future and present ideas to address them.

ABSTRACT: Quantum computers potentially have a significant advantage over classical computers for a number of important problems. Shor’s algorithm for integer factorization and Grover’s search algorithms are two early examples demonstrating the potential benefits. We give an overview of quantum computing, briefly introducing the model of computation and its properties. We provide insights by discussing a number of its applications.

ABSTRACT: The challenges of advanced analytics and big data cannot be address by developing new machine learning algorithms or new large-scale computing systems in isolation. Some of the recent advances in machine learning have come from new systems that can apply complex models to big data problems. Likewise, some of the recent advances in systems have exploited fundamental properties in machine learning to reach new points in the system design space. By considering the design of scalable learning systems from both perspectives, we can address bigger problems, expose new opportunities in algorithm and system design, and define the new fundamental abstractions that will accelerate research in these complementary fields.

In this talk, I will present my research in learning systems spanning the design of efficient inference algorithms, the development of graph processing systems, and the unification of graphs and unstructured data. I will describe how the study of graphical model inference and power-law graph structure shaped the common abstractions in contemporary graph processing systems, and how new insights in system design enabled order-of-magnitude performance gains over general purpose data-processing systems. I will then discuss how lessons learned in the context of specialized graph-processing systems can be lifted to more general data-processing systems enabling users to view data as graph and tables interchangeably while preserving the performance gains of specialized systems. Finally, I will present a new direction for the design of learning systems that looks beyond traditional analytics and model fitting to the entire machine learning life-cycle spanning model training, serving, and management.

ABSTRACT: Computing is undergoing a major shift. Third-party applications hosted in online software markets have become ubiquitous on all kinds of platforms: mobile phones, Web browsers, gaming devices, even household robots. These applications often include yet more third-party code for advertising, analytics, etc. These trends have dramatically increased the amount of bad code throughout the software stack – buggy code, malicious code, code that overcollects private information intentionally or by accident, overprivileged code vulnerable to abuse – as well as the amount of sensitive data processed by bad code.

In this talk, I will demonstrate that existing application platforms are ill-suited to dealing with bad code, thus causing security and privacy problems. I will then show how to isolate bad code without affecting its useful functionality, by redesigning the interfaces across the software stack and controlling the information released to the applications by the platform. I will also show how automated testing can identify bad code and help developers improve their applications.