- talks - lists.cs.princeton.edu

Siyu Yang will present his Pre-FPO on March 3, 2015 at 3pm in Room 401.
by Nicki Gotsis 26 Feb '15

26 Feb '15

Siyu Yang will present his Pre-FPO on March 3, 2015 at 3pm in Room 401. His committee members are Professor Robert Tarjan (advisor), Prof Robert Sedgewick (reader), Dr. David Lee (non-Princeton reader), Prof Andrea LaPaugh (non-reader), Prof Bernard Chazelle (non-reader). Everyone is invited to attend his talk. The talk title and abstract follow below: Title: Eager and Lazy Deletion Rebalancing in Binary Search Trees The binary search tree is a fundamental data structure with many applications. Following the invention of AVL tree, many kinds of balanced search trees were developed, with the aim of obtaining simpler updating or improved efficiency or both. In most of such data structures, deletion rebalancing is more complicated than insertion rebalancing. This leads naturally to the question of how much rebalancing is necessary to guarantee a logarithmic height bound. We explore ways to make binary search trees more efficient by delaying rebalancing on deletion. This talk will focus on variants of AVL trees. We propose a variant of weak AVL trees with an even weaker balance condition. Our trees improved the amortized time bounds for rebalancing steps while keeping the same worst-case height guarantee as weak AVL trees. We also propose another variant with lazy rebalancing steps separated from deletion operations themselves. The algorithm's performance is guaranteed by running a background process that rebalances unbalanced parts of the tree. Unlike the similar work of relaxed AVL trees, in which the tree only eventually becomes balanced, our method guarantees that the tree remains balanced at all times, if the background process is run sufficiently often. Finally, I will summarize with some ongoing work.

1 1

Colloquium Speaker Joseph Gonzalez Today, 12:30pm
by Nicole E. Wagenblast 26 Feb '15

26 Feb '15

Colloquium Speaker Joseph Gonzalez, University of California Thursday, February 26, 12:30pm Computer Science 105 Learning Systems: Systems and Abstractions for Large-Scale Machine Learning The challenges of advanced analytics and big data cannot be address by developing new machine learning algorithms or new 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. Joseph Gonzalez is a postdoc in the UC Berkeley AMPLab and cofounder of GraphLab. Joseph received his PhD from the Machine Learning Department at Carnegie Mellon University where he worked with Carlos Guestrin on parallel algorithms and abstractions for scalable probabilistic machine learning. Joseph is a recipient of the AT&T Labs Graduate Fellowship and the NSF Graduate Research Fellowship.

1 0

Colloquium Speaker Joseph Gonzalez Thurs Feb 26, 12:30pm
by Nicole E. Wagenblast 25 Feb '15

25 Feb '15

Colloquium Speaker Joseph Gonzalez, University of California Thursday, February 26, 12:30pm Computer Science 105 Learning Systems: Systems and Abstractions for Large-Scale Machine Learning The challenges of advanced analytics and big data cannot be address by developing new machine learning algorithms or new 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. Joseph Gonzalez is a postdoc in the UC Berkeley AMPLab and cofounder of GraphLab. Joseph received his PhD from the Machine Learning Department at Carnegie Mellon University where he worked with Carlos Guestrin on parallel algorithms and abstractions for scalable probabilistic machine learning. Joseph is a recipient of the AT&T Labs Graduate Fellowship and the NSF Graduate Research Fellowship.

1 0

Colloquium Speaker Suman Jana today, 12:30pm
by Nicole E. Wagenblast 25 Feb '15

25 Feb '15

Colloquium Speaker Suman Jana, Stanford University Wednesday, February 25, 2015 - 12:30pm Computer Science 105 Rise of the Planet of the Apps: Security and Privacy in the Age of Bad Code 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. Suman Jana is a postdoctoral researcher at Stanford University. He earned his PhD in 2014 from the University of Texas, where he was supported by the Google PhD Fellowship. He is broadly interested in identifying fundamental flaws in existing systems and building new systems with strong security and privacy guarantees. Suman received the 2014 PET Award for Outstanding Research in Privacy-Enhancing Technologies, Best Practical Paper Award from the 2014 IEEE Symposium on Security and Privacy (Oakland), Best Student Paper Award from the 2012 IEEE Symposium on Security and Privacy, and the 2012 Best Applied Security Paper Award. Suman's research has been widely covered in popular media, and his code has been deployed at Google, Mozilla, and Apache.

1 0

Correction- Colloquium Speaker Joseph Gonzalez Thurs Feb 26, 12:30pm
by Nicole E. Wagenblast 24 Feb '15

24 Feb '15

Colloquium Speaker Joseph Gonzalez, University of California Thursday, February 26, 12:30pm Computer Science 105 Learning Systems: Systems and Abstractions for Large-Scale Machine Learning The challenges of advanced analytics and big data cannot be address by developing new machine learning algorithms or new 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. Joseph Gonzalez is a postdoc in the UC Berkeley AMPLab and cofounder of GraphLab. Joseph received his PhD from the Machine Learning Department at Carnegie Mellon University where he worked with Carlos Guestrin on parallel algorithms and abstractions for scalable probabilistic machine learning. Joseph is a recipient of the AT&T Labs Graduate Fellowship and the NSF Graduate Research Fellowship.

1 0

Colloquium Speaker Joseph Gonzalez Thurs Feb 24, 12:30pm
by Nicole E. Wagenblast 24 Feb '15

24 Feb '15

Colloquium Speaker Joseph Gonzalez, University of California Thursday, February 24, 12:30pm Computer Science 105 Learning Systems: Systems and Abstractions for Large-Scale Machine Learning The challenges of advanced analytics and big data cannot be address by developing new machine learning algorithms or new 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. Joseph Gonzalez is a postdoc in the UC Berkeley AMPLab and cofounder of GraphLab. Joseph received his PhD from the Machine Learning Department at Carnegie Mellon University where he worked with Carlos Guestrin on parallel algorithms and abstractions for scalable probabilistic machine learning. Joseph is a recipient of the AT&T Labs Graduate Fellowship and the NSF Graduate Research Fellowship.

1 0

Colloquium Speaker Suman Jana Wed Feb 25, 12:30pm
by Nicole E. Wagenblast 24 Feb '15

24 Feb '15

Colloquium Speaker Suman Jana, Stanford University Wednesday, February 25, 2015 - 12:30pm Computer Science 105 Rise of the Planet of the Apps: Security and Privacy in the Age of Bad Code 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. Suman Jana is a postdoctoral researcher at Stanford University. He earned his PhD in 2014 from the University of Texas, where he was supported by the Google PhD Fellowship. He is broadly interested in identifying fundamental flaws in existing systems and building new systems with strong security and privacy guarantees. Suman received the 2014 PET Award for Outstanding Research in Privacy-Enhancing Technologies, Best Practical Paper Award from the 2014 IEEE Symposium on Security and Privacy (Oakland), Best Student Paper Award from the 2012 IEEE Symposium on Security and Privacy, and the 2012 Best Applied Security Paper Award. Suman's research has been widely covered in popular media, and his code has been deployed at Google, Mozilla, and Apache.

1 0

Colloquium Speaker Matt Fredrikson, Today, February 24, 4:30pm
by Nicole E. Wagenblast 24 Feb '15

24 Feb '15

Colloquium Speaker Matt Fredrikson, University of Wisconsin, Madison Tuesday, February 24, 4:30pm Computer Science 105 Inference Attacks: Understanding Privacy in the Era of "Privacy is Dead" As data from far-reaching sources is collected, aggregated, and re-packaged to enable new and smarter applications, confidentiality and data security are at greater risk than ever before. Some of the most surprising and invasive threats to materialize in recent years are brought about by so-called inference attacks: successful attempts to learn sensitive information by leveraging public data such as social network updates, published research articles, and web APIs. In this talk, I will focus on two of my research efforts to better understand and defend against these attacks. First I will discuss work that examines the privacy risks that arise when machine learning models are used in a popular medical application, and illustrate the consequences of applying differential privacy as a defense. This work uncovered a new type of inference attack on machine learning models, and shows via an in-depth case study how to understand privacy "in situ" by balancing the attacker's chance of success against the likelihood of harmful medical outcomes. The second part of the talk will detail work that helps developers correctly write privacy-aware applications using verification tools. I will illustrate how a wide range of confidentiality guarantees can be framed in terms of a new logical primitive called Satisfiability Modulo Counting, and describe a tool that I have developed around this primitive that automatically finds privacy bugs in software (or proves that the software is bug-free). Through a better understanding of how proposed defenses impact real applications, and by providing tools that help developers implement the correct defense for their task, we can begin to proactively identify potential threats to privacy and take steps to ensure that they will not surface in practice. Matt Fredrikson is a Ph.D. candidate in the department of Computer Sciences at the University of Wisconsin-Madison. His research interests lie at the intersection of security, privacy, and formal methods, covering topics in software security, privacy issues associated with machine-learning models, and applied cryptography. His work has been profiled by Reuters, Technology Review, and New Scientist, and received the best paper award at USENIX Security 2014. He is a recipient of the Microsoft Research Graduate Fellowship Award.

1 0

Colloquium Speaker Matt Fredrikson, Tuesday, February 24, 4:30pm
by Nicole E. Wagenblast 23 Feb '15

23 Feb '15

Colloquium Speaker Matt Fredrikson, University of Wisconsin, Madison Tuesday, February 24, 4:30pm Computer Science 105 Inference Attacks: Understanding Privacy in the Era of "Privacy is Dead" As data from far-reaching sources is collected, aggregated, and re-packaged to enable new and smarter applications, confidentiality and data security are at greater risk than ever before. Some of the most surprising and invasive threats to materialize in recent years are brought about by so-called inference attacks: successful attempts to learn sensitive information by leveraging public data such as social network updates, published research articles, and web APIs. In this talk, I will focus on two of my research efforts to better understand and defend against these attacks. First I will discuss work that examines the privacy risks that arise when machine learning models are used in a popular medical application, and illustrate the consequences of applying differential privacy as a defense. This work uncovered a new type of inference attack on machine learning models, and shows via an in-depth case study how to understand privacy "in situ" by balancing the attacker's chance of success against the likelihood of harmful medical outcomes. The second part of the talk will detail work that helps developers correctly write privacy-aware applications using verification tools. I will illustrate how a wide range of confidentiality guarantees can be framed in terms of a new logical primitive called Satisfiability Modulo Counting, and describe a tool that I have developed around this primitive that automatically finds privacy bugs in software (or proves that the software is bug-free). Through a better understanding of how proposed defenses impact real applications, and by providing tools that help developers implement the correct defense for their task, we can begin to proactively identify potential threats to privacy and take steps to ensure that they will not surface in practice. Matt Fredrikson is a Ph.D. candidate in the department of Computer Sciences at the University of Wisconsin-Madison. His research interests lie at the intersection of security, privacy, and formal methods, covering topics in software security, privacy issues associated with machine-learning models, and applied cryptography. His work has been profiled by Reuters, Technology Review, and New Scientist, and received the best paper award at USENIX Security 2014. He is a recipient of the Microsoft Research Graduate Fellowship Award.

1 0

Colloquium Speaker Simon Peter, Today, 12:30pm
by Nicole E. Wagenblast 23 Feb '15

23 Feb '15

Colloquium Speaker Simon Peter, University of Washington Monday, February 23, 12:30pm Computer Science 105 Building an Operating System for the Data Center 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. Simon is a postdoctoral research associate at the University of Washington, where he leads research in operating systems and networks. His postdoctoral advisors are Tom Anderson and Arvind Krishnamurthy. Simon received a Ph.D. in Computer Science from ETH Zurich in 2012 and an MSc in Computer Science from the Carl-von-Ossietzky University Oldenburg, Germany in 2006. Simon's research focus is on data center performance issues. For his work on the Arrakis high I/O performance operating system, he received the Jay Lepreau best paper award (2014) and the Madrona prize (2014). Previously, Simon has worked on the Barrelfish multicore operating system and conducted further award-winning systems research at various locations, including MSR Silicon Valley, MSR Cambridge, Intel Labs Germany, UC Riverside, and the NSF.

1 0