Theory of Computation (TOC) Seminar
 |
Nike Sun: The Exact k-SAT Threshold for Large k Tuesday, December 1, 2015 - 4:15pm to 5:15pm Abstract: |
 |
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 Abstract: |
 |
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 Abstract: |
 |
Shaddin Dughmi: Algorithmic Bayesian Persuasion Wednesday, May 13, 2015 - 4:00pm to 5:00pm Abstract: |
 |
Elad Hazan: Is Optimization Computationally Equivalent to Online Learning? Tuesday, May 12, 2015 - 4:15pm to 5:15pm Abstract: |
Pages
