Theory of Computation (TOC) Seminar

Alexandr Andoni: Optimal Hashing for High-Dimensional Spaces
Monday, October 3, 2016 - 4:00pm to 5:00pm
Abstract: 
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

Rocco Servedio: Two Circuit Lower Bounds
Tuesday, April 26, 2016 - 4:00pm to 5:00pm

Abstract:

 

Madhu Sudan: Communication Amid Uncertainty
Tuesday, May 10, 2016 - 4:00pm to 5:00pm

Abstract:  Computers and humans communicate in order to gain information about the state of the world around them, and to be able to determine how to act in the future.  Effective communication relies on large shared context between the communicating parties: Such shared context tells the communi

David Zuckerman: Explicit Two-Source Extractors and Resilient Functions
Tuesday, April 12, 2016 - 4:00pm to 5:00pm

Abstract: We explicitly construct an extractor for two independent sources on n bits,
each with min-entropy at least log^C n for a large enough constant C. Our
extractor outputs one bit and has error n^{-\Omega(1)}. The best previous

Omer Reingold: Constant-round Interactive-proofs for Delegating Computation
Tuesday, March 8, 2016 - 4:00pm to 5:00pm

Abstract: Interactive proofs, introduced by Goldwasser,

Pages

Subscribe to Theory of Computation (TOC) Seminar