Nov 13

Towards anonymous and metadata private communication at Internet scale

11:40 AM to 12:40 PM

CS Department 451

Srini Devadas, MIT

As the world becomes more connected, privacy is becoming harder to maintain. From social media services to Internet service providers to state-sponsored mass-surveillance programs, many outlets collect sensitive information about the users and the communication between them – often without the users ever knowing about it. In response, many Internet users have turned to end-to-end encryption, like Signal and TLS, to protect the content of the communication. Unfortunately, these works do little to hide the metadata of the communication, such as when and with whom a user is communicating. In scenarios where the metadata are sensitive, encryption alone is not sufficient to ensure users’ privacy.

Most prior systems that provide metadata private communication fall into one of two categories: systems that (1) provide formal privacy guarantees against global adversaries but do not scale to large numbers of users, or (2) scale easily to a large user base but do not provide strong guarantees against global adversaries. I will present two systems that aim to bridge the gap between the two categories to enable private communication with strong guarantees for many millions of users: Quark, a horizontally scalable anonymous broadcast system that defends against a global adversary who monitors the entire network and controls a significant fraction of the servers, and Crossroads, which provides metadata private communication between two honest users against the same adversary using a novel cryptographic primitive.

This talk is based on Albert Kwon's recently completed MIT PhD dissertation.

Host: Simha Sethumadhavan

Nov 21

Improved Massively Parallel Algorithms for Maximal Matching and Graph Connectivity

1:00 PM to 2:00 PM

CS conference room (CSB 453)

Soheil Behnezhad, University of Maryland

In this talk we will discuss the recent algorithmic progress made on the Massively Parallel Computations (MPC) model. The MPC model provides a clean theoretical abstraction of modern parallel computation frameworks such as MapReduce, Hadoop, Spark, etc., which have been extremely successful in processing large-scale data-sets.

Our main focus in the talk will be on the maximal matching problem. We provide a novel analysis of an extremely simple algorithm and show that it leads to exponentially faster MPC algorithms for maximal matching. Our analysis is based on a method of proving concentration bounds for algorithms satisfying a certain "locality" property, which we believe may find applications beyond parallel algorithms.

We will also briefly overview an algorithm for graph connectivity in the MPC model that takes O(log D) rounds for graphs with diameter D > log n and takes O(loglog n) rounds for all other graphs. This algorithm nearly matches an Ω(log D) (conditional) lower-bound for the problem.

Based on joint works with Mohammad Hajiaghayi and David Harris (FOCS 2019), and Laxman Dhulipala, Hossein Esfandiari, Jakub Łącki, and Vahab Mirrokni (FOCS 2019).

Nov 25

From Ethical Challenges of Intelligent Systems to Embedding Ethics in Computer Science Education

11:40 AM to 12:40 PM

CSB 451

Barbara Grosz, Harvard University

Computing technologies have become pervasive in daily life, sometimes bringing unintended but harmful consequences. For students to learn to think not only about what technology they could create, but also whether they should create that technology and to recognize the ethical considerations that should constrain their design, computer science curricula must expand to include ethical reasoning about the societal value and impact of these technologies. This talk will describe Harvard's Embedded EthiCS initiative, a novel approach to integrating ethics into computer science education that incorporates ethical reasoning throughout courses in the standard computer science curriculum. It changes existing courses rather than requiring wholly new courses. The talk will begin with a short description of my experiences teaching the course "Intelligent Systems: Design and Ethical Challenges" that inspired the design of Embedded EthiCS. It will then describe the goals behind the design, the way the program works, lessons learned and challenges to sustainable implementations of such a program across different types of academic institutions.
Host: Augustin Chaintreau

Dec 02

Distinguished Lecture - Bill Freeman

11:40 AM to 12:40 PM

CS Department 451

Bill Freeman, MIT

Dec 06

Theory Seminar - Anupam Gupta

12:00 PM to 1:00 PM

CS conference room (CSB 453)

Anupam Gupta, Carnegie Mellon University

Feb '20 14

Theory Seminar - Jiapeng Zhang

1:00 PM to 2:00 PM

CS conference room (CSB 453)

Jiapeng Zhang, Harvard University