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 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:
	Nir Bitansky: On the Cryptographic Hardness of Finding a Nash Equilibrium Tuesday, April 14, 2015 - 4:15pm to 5:15pm Abstract:
	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.

Pages