Theory of Computation (TOC) Seminar

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


Nir Bitansky: On the Cryptographic Hardness of Finding a Nash Equilibrium
Tuesday, April 14, 2015 - 4:15pm to 5:15pm


Antoine Joux: A Simplified Setting for Discrete Logarithms in Small Characteristics Fin
Tuesday, April 7, 2015 - 4:00pm to 5:15pm

Abstract:  The hardness of computing discrete logarithms in finite field has served as a foundation for many public key cryptosystems. In the last two years, tremendous progress have been made in the case of small characteristic finite fields.


Subscribe to Theory of Computation (TOC) Seminar