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 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.

Pages