Theory of Computation (TOC) Seminar

Yuval Ishai: Succinct Secure Computation from DDH
Tuesday, November 8, 2016 - 4:00pm to 5:00pm



Ronitt Rubinfeld: Local Computation Algorithms
Tuesday, November 1, 2016 - 4:00pm to 5:00pm


Consider a setting in which inputs to and outputs from a computational
problem are so large, that there is not time to read them in their
entirety.   However, if one is only interested in small parts of the

Muthuramakrishnana Venkitasubramaniam: Composable Adaptive Secure Protocols without Setup Under Polytime Assumptions
Friday, October 28, 2016 - 10:30am to 12:00pm

Abstract: All previous constructions of general multiparty computation protocols that are secure against adaptive corruptions in the concurrent setting either require some form of setup or non-standard assumptions.

Jonathan Ullman: Algorithmic Stability for Adaptive Data Analysis
Tuesday, October 18, 2016 - 4:00pm to 5:00pm
Alexandr Andoni: Optimal Hashing for High-Dimensional Spaces
Monday, October 3, 2016 - 4:00pm to 5:00pm
We survey recent advances in the approximate nearest neighbor search
problem in high-dimensional Euclidean/Hamming spaces, which go beyond
the classic Locality Sensitive Hashing technique for the problem. The
Mohsen Ghaffari: Improved Local Distributed Graph Algorithms
Tuesday, September 27, 2016 - 4:00pm to 5:00pm

Abstract:  How can the computers in a network interact and communicate to solve the network's graph problems efficiently?

Alina Ene: From Minimum Cut to Submodular Minimization: Leveraging the Decomposable Structure
Monday, September 19, 2016 - 4:00pm to 5:00pm
Boaz Barak: Computational Bayesianism, Sums of Squares, and Unicorns
Tuesday, September 13, 2016 - 4:00pm to 5:00pm
ABSTRACT: Can we make sense of quantities such as "the probability that 2^81712357 - 1 is prime" or "the probability that statement X is a logical contradiction"?
Sebastien Bubeck: New Results at the Crossroads of Convexity, Learning and Information Theory
Tuesday, October 25, 2016 - 3:45pm to 5:15pm
Abstract: I will present three new results (no background in optimization will be assumed, all concepts will be defined and motivated): (i) the Cramer transform of the uniform measure on a convex body is a universal self-concordant barrier; (ii) projected gradient descent with Gaussian 
Ken Clarkson: More Near-Linear Linear Algebra, via Sketching
Tuesday, May 3, 2016 - 4:00pm to 5:00pm

Abstract:  In recent years there have been significant improvements in matrix
algorithms for data analysis, including several cases where the running
times are nearly linear: for an input matrix A, the running time is


Subscribe to Theory of Computation (TOC) Seminar