Theory of Computation (TOC) Seminar
 |
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 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 |
Pages
