April 2020 - talks - lists.cs.princeton.edu

Jennifer Lam will present her MSE talk "Towards Exploiting Skew in High Throughput Distributed Databases" on Wednesday, April 22, 2020 at 1:30pm via Zoom
by Nicki Mahler 20 Apr '20

20 Apr '20

Jennifer Lam will present her MSE talk "Towards Exploiting Skew in High Throughput Distributed Databases" on Wednesday, April 22, 2020 at 1:30pm via Zoom. Zoom link: [ https://princeton.zoom.us/j/93594446055 | https://princeton.zoom.us/j/93594446055 ] The members of her committee are Wyatt Lloyd (adviser) and Amit Levy (reader). Everyone is invited to attend her talk. Her abstract follows below. Abstract: When selecting a database, users are forced to trade off high throughput for scalable storage capacity. Specifically, a choice is made between performant single machine databases (DBs) or distributed DBs, whose throughput is several orders of magnitude worse. We work towards a novel distributed DB architecture that aims to scale while also sustaining the throughput of single machine systems. We exploit the skew common in real-world workloads and co-locate the most popular keys on a single “hot” node. Although conventional load balancing strategies maximize throughput by distributing hot keys across nodes, we instead choose to create a central point to which targeted, aggressive optimizations can now be applied. In particular, we plan to replace the hot node with a performant in-memory database and layer on a new commit protocol that utilizes its presence to increase throughput while preserving strict serializability by coordinating two distinct databases. In this talk, I will discuss our current progress towards implementing this architecture and our initial findings. We experimentally validate the viability of this approach, showing potential gains to be at least two orders of magnitude greater than that of existing strictly serializable distributed databases.

1 0

Reminder: CS and CITP Virtual Lunch Seminar: Seny Kamara, tomorrow at 12:30pm
by Emily C. Lawrence 20 Apr '20

20 Apr '20

CS and CITP Virtual Lunch Seminar Speaker: Seny Kamara, Brown University Date: Tuesday, April 21 Time: 12:30-1:30pm Location: Webinar Host: Arvind Narayanan Event page: [ https://www.cs.princeton.edu/events/25947 | https://www.cs.princeton.edu/events/25947 ] Please click here to register for this webinar: [ https://princeton.zoom.us/webinar/register/WN_3P3w-nJ5Td6RdHBeL4j_Kg | https://princeton.zoom.us/webinar/register/WN_3P3w-nJ5Td6RdHBeL4j_Kg ] After registering, you will receive a confirmation email containing information about joining the webinar. This virtual talk is being co-sponsored by CITP and the Department of Computer Science. It is open only to Princeton University faculty, staff, and students. Title: Cryptography for Privacy and Policy Abstract: As our lives become increasingly digital and we produce more and more data, we are witnessing several conflicting trends. On one hand, these massive datasets are becoming more intrusive and privacy-sensitive and on the other they are becoming harder to protect. This is illustrated by the constant occurrence of data breaches in almost every industry and sector. One of the best tools at our disposal for enforcing data privacy and security is end-to-end encryption where only the data owner hold the encryption key. While end-to-end encryption is already deployed in messaging and video calling apps, its widespread adoption is severely limited because it breaks the utility of critical technologies like databases, cloud computing and machine learning. In this talk, I will describe my work on designing, analyzing and cryptanalyzing efficient algorithms and systems that operate on end-to-end encrypted data. I will discuss the advances my collaborators and I have made on these problems over the last fifteen years based on ideas from a variety of fields including cryptography, algorithms, data structures, complexity theory, machine learning and databases. In addition to the technological impact of these advances, I will also discuss their societal implications which range from (potentially) expanding Law Enforcement's "Going Dark" problem to enabling new policy tradeoffs. Bio: Seny Kamara is an Associate Professor of Computer Science at Brown University, where he directs the Encrypted Systems Lab and is affiliated with the Center for Human Rights and Humanitarian Studies. Prior to joining Brown, he was a Research Scientist at Microsoft Research in the Cryptography Research group. At Brown, he conducts research in cryptography with a focus on problems motivated by social and policy issues. In 2016, he was appointed by the National Academies of Sciences to study the impact of end-to-end encryption on law enforcement and intelligence agencies and in 2019 he testified to the U.S. House of Representative about the privacy and fairness implications of Big Data. He has received a Google Faculty Award and was named a Leadership Fellow by the Boston Global Forum for his work and commitment to global peace.

1 0

CS and CITP Virtual Lunch Seminar: Seny Kamara, Tuesday April 21
by Emily C. Lawrence 15 Apr '20

15 Apr '20

CS and CITP Virtual Lunch Seminar Speaker: Seny Kamara, Brown University Date: Tuesday, April 21 Time: 12:30-1:30pm Location: Webinar Host: Arvind Narayanan Event page: [ https://www.cs.princeton.edu/events/25947 | https://www.cs.princeton.edu/events/25947 ] Please click here to register for this webinar: [ https://princeton.zoom.us/webinar/register/WN_3P3w-nJ5Td6RdHBeL4j_Kg | https://princeton.zoom.us/webinar/register/WN_3P3w-nJ5Td6RdHBeL4j_Kg ] After registering, you will receive a confirmation email containing information about joining the webinar. This virtual talk is being co-sponsored by CITP and the Department of Computer Science. It is open only to Princeton University faculty, staff, and students. Title: Cryptography for Privacy and Policy Abstract: As our lives become increasingly digital and we produce more and more data, we are witnessing several conflicting trends. On one hand, these massive datasets are becoming more intrusive and privacy-sensitive and on the other they are becoming harder to protect. This is illustrated by the constant occurrence of data breaches in almost every industry and sector. One of the best tools at our disposal for enforcing data privacy and security is end-to-end encryption where only the data owner hold the encryption key. While end-to-end encryption is already deployed in messaging and video calling apps, its widespread adoption is severely limited because it breaks the utility of critical technologies like databases, cloud computing and machine learning. In this talk, I will describe my work on designing, analyzing and cryptanalyzing efficient algorithms and systems that operate on end-to-end encrypted data. I will discuss the advances my collaborators and I have made on these problems over the last fifteen years based on ideas from a variety of fields including cryptography, algorithms, data structures, complexity theory, machine learning and databases. In addition to the technological impact of these advances, I will also discuss their societal implications which range from (potentially) expanding Law Enforcement's "Going Dark" problem to enabling new policy tradeoffs. Bio: Seny Kamara is an Associate Professor of Computer Science at Brown University, where he directs the Encrypted Systems Lab and is affiliated with the Center for Human Rights and Humanitarian Studies. Prior to joining Brown, he was a Research Scientist at Microsoft Research in the Cryptography Research group. At Brown, he conducts research in cryptography with a focus on problems motivated by social and policy issues. In 2016, he was appointed by the National Academies of Sciences to study the impact of end-to-end encryption on law enforcement and intelligence agencies and in 2019 he testified to the U.S. House of Representative about the privacy and fairness implications of Big Data. He has received a Google Faculty Award and was named a Leadership Fellow by the Boston Global Forum for his work and commitment to global peace.

1 0

CITP Webinar: Ed Felten – COVID-19, Technology, Privacy and Civil Liberties, Thursday, April 16
by Emily C. Lawrence 14 Apr '20

14 Apr '20

CITP Webinar: Ed Felten – COVID-19, Technology, Privacy and Civil Liberties Date: Thursday, April 16, 2020 Time: 3:00 pm - 4:30 pm Event page: [ https://citp.princeton.edu/event/webinar-felten-covid/ | https://citp.princeton.edu/event/webinar-felten-covid/ ] Please click here to register for the webinar: [ https://princeton.zoom.us/webinar/register/WN_bAmNsJQsSYKSveh2_ef2FA | https://princeton.zoom.us/webinar/register/WN_bAmNsJQsSYKSveh2_ef2FA ] This event is open to the public. Many systems have been proposed for using technology to help individuals and public health officials better respond to the COVID-19 pandemic. This talk will analyze the major proposed uses of information technology in the public health response to COVID-19, including aggregate reporting, contact tracing via direct proximity detection or location history matching, and creation of disease status passports. The public health value of these approaches will be considered along with their privacy and civil liberties implications. For several approaches, broad public acceptance is a prerequisite for success, making careful privacy and civil liberties protection an important contributor to public health goals. Bio: Edward W. Felten is the Robert E. Kahn Professor of Computer Science and Public Affairs at Princeton University and the founding director of Princeton’s Center for Information Technology Policy. In 2011-12 he served as the first chief technologist for the Federal Trade Commission. His research interests include computer security and privacy, especially relating to media and consumer products; and technology law and policy. He has published about 80 papers in the research literature and two books. His research on topics such as web security, copyright and copy protection, and electronic voting has been covered extensively in the popular press. His weblog, at freedom-to-tinker.com, is widely read for its commentary on technology, law and policy. Professor Felten is a member of the National Academy of Engineering and the American Academy of Arts and Sciences, and is a fellow of the ACM. He has testified at House and Senate committee hearings on privacy, electronic voting and digital television. In 2004, Scientific American magazine named him to its list of 50 worldwide science and technology leaders.

1 0

Yichen Chen will present his FPO "On the complexity of Markov decision problems" on Friday, 4/3/2020 at 10:45am in B327 EQuad
by Nicki Mahler 01 Apr '20

01 Apr '20

Yichen Chen will present his FPO "On the complexity of Markov decision problems" on Friday, 4/3/2020 at 10:45am in B327 EQuad. The members of his committee are as follows: Mengdi Wang (Adviser); Readers: Yuxin Chen and Karthik Narasimhan; Examiners: Sanjeev Arora, Robert Schapire, and Mengdi Wang. A copy of his thesis is available upon request (please email [ mailto:ngotsis@cs.princeton.edu | ngotsis(a)cs.princeton.edu ] ). All are welcome to attend. The talk abstract follows below. The Markov decision problem (MDP) is one of the most basic models for sequential decision-making problems in a dynamic environment where outcomes are partly random. It models a stochastic control process in which a planner makes a sequence of decisions as the system evolves. The Markov decision problem provides a mathematical framework for dynamic programming, stochastic control, and reinforcement learning. In this thesis, we study the complexity of solving MDPs. In the first part of the thesis, we propose a class of stochastic primal-dual methods for solving MDPs. We formulate the core policy optimization problem of the MDP as a stochastic saddle point problem. By utilizing the value-policy duality structure, the algorithm samples state-action transitions and makes alternative updates to value and policy estimates. We prove that our algorithm is able to find the approximate optimal policies to Markov decision problems with small space and computational complexity. Using linear models to represent the value functions and the policies, our algorithm is capable of scaling to problems with infinite and continuous state spaces. In the second part of the thesis, we establish the computational complexity lower bounds for solving MDPs. We prove our results by modeling the MDP algorithms using branching programs and then characterizing the properties of these programs by quantum arguments. The analysis is also extended to study the complexity of solving two-player turn-based Markov games. Our results show that if we have a simulator that can sample according to the transition probability function in O(1), the lower bounds have reduced dependence on the state number. These results suggest a fundamental di↵erence between Markov decision problems with and without a simulator. We believe that our results provide a new piece of theoretical evidence for the success of simulation-based methods in solving MDPs and Markov games.

1 1