Theory of Computation (TOC) Seminar

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.

Ravi Kannan: Topic Modeling and NMF using Soft Clustering
Tuesday, September 22, 2015 - 4:15pm to 5:15pm
Abstract:  The model fitting problem in Topic Modeling is a special case
of Non-Negative Matrix Factorization and both are computationally
hard. Soft clustering, where, each datapoint can belong fractionally
Dana Moshkovitz: Amplification and Derandomization Without Slowdown
Tuesday, September 29, 2015 - 4:15pm to 5:15pm
Abstract: We show techniques for decreasing the error probability of randomized algorithms and for converting randomized algorithms to deterministic (non-uniform) algorithms.
David Steurer: Lower bounds on the size of semidefinite programming relaxations
Tuesday, May 19, 2015 - 4:15pm to 5:15pm


Shaddin Dughmi: Algorithmic Bayesian Persuasion
Wednesday, May 13, 2015 - 4:00pm to 5:00pm


Elad Hazan: Is Optimization Computationally Equivalent to Online Learning?
Tuesday, May 12, 2015 - 4:15pm to 5:15pm



Subscribe to Theory of Computation (TOC) Seminar