Theory of Computation (TOC) Seminar

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

Abstract: Interactive proofs, introduced by Goldwasser,

Ran Raz: Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning
Tuesday, March 15, 2016 - 4:00pm to 5:00pm
Abstract: We prove that any algorithm for learning parities requires either a memory of quadratic size or an exponential number of samples. This proves a recent conjecture of Steinhardt, Valiant and Wager and shows that for some learning problems a large storage space is crucial.
Avi Wigderson: Elementary Mathematical Problems Disguising Computational Hardness
Thursday, February 11, 2016 - 4:00pm to 5:00pm

Abstract:  The theory of computation has done (and is doing) incredibly well on upper bounds - finding ingenious efficient algorithms for important problems.

Laszlo Babai: Graph Isomorphism in Quasipolynomial Time
Tuesday, February 2, 2016 - 4:00pm to 5:00pm
Abstract:  The algorithm indicated in the title builds on Luks's classical framework and introduces new group theoretic and combinatorial tools.  

We outline the algorithm, with a focus on the core group theoretic routine ("Local Certificates").
Li-Yang Tan: Unconditional Lower Bounds in Complexity Theory
Tuesday, December 8, 2015 - 4:00pm to 5:00pm
Abstract: I will present three recent results, each establishing new unconditional lower bounds in fundamental and well-studied models of computation: 
Nike Sun: The Exact k-SAT Threshold for Large k
Tuesday, December 1, 2015 - 4:15pm to 5:15pm
Elchanan Mossel: Corruption Detection and Shotgun Assembly of Networks
Tuesday, November 3, 2015 - 4:00pm to 5:00pm

Abstract: I will discuss two algorithmic problems on networks. The first problem is the classical and well studied problem of identifying faulty nodes in a network given reports of their neighbors.

Nati Linial: High-Dimensional Permutations
Tuesday, November 24, 2015 - 4:00pm to 5:00pm

Abstract: This talk starts from the realization that many of the basic combinatorial constructs that we use all the time are inherently one dimensional. Permutations are a case in point.

Noga Ron-Zewi: High-rate locally-correctable and locally-testable codes with sub-polynomial query complexity
Tuesday, October 27, 2015 - 4:00pm to 5:00pm


Sanjeev Arora: The linear algebraic structure of word meanings
Tuesday, September 15, 2015 - 4:15pm to 5:15pm

Abstract:  In Natural Language Processing (NLP), semantic word embeddings are used to capture the meanings of words as vectors. They are  often constructed using nonlinear/nonconvex techniques such as deep nets and energy-based models.


Subscribe to Theory of Computation (TOC) Seminar