Theory of Computation (TOC) Seminar

	Moni Naor: White-box vs. Black-box Search Problems: A Cryptographic Perspective Tuesday, March 21, 2017 - 4:00pm to 5:00pm Abstract: Ramsey theory assures us that in any graph there is a clique or independent set of a certain size, roughly logarithmic in the graph size. But how diﬃcult is it to ﬁnd the clique or independent set?
	Irit Dinur: Grassmann agreement testing and the 2:1 conjecture Tuesday, March 14, 2017 - 4:00pm to 5:00pm Abstract: I will describe the notion of agreement testing, which allows to deduce global structure from local agreement checks. In retrospect, agreement testing theorems are a key combinatorial component in nearly all PCPs.
	Vasilis Syrgkanis: Oracle efficient Learning and Auction Design Tuesday, February 28, 2017 - 4:00pm to 5:00pm Abstract. We consider the design of online no-regret algorithms that are computationally efficient, given access to an offline optimization oracle.
	Nikhil Bansal: A fast polynomial space algorithm for Subset Sum Tuesday, March 7, 2017 - 4:00pm to 5:00pm Abstract: I will describe an algorithm for the subset sum problem that runs in 2^{0.86n} time and uses polynomial space. Previously, all algorithms with running time less than 2^n used exponential space, and obtaining such a guarantee was open. Our algorithm is based on Floyd's
	Aaron Roth: Quantifying Tradeoffs Between Fairness and Accuracy in Online Learning Wednesday, February 22, 2017 - 4:00pm to 5:00pm Abstract:
	Vitaly Feldman: Lower bounds against convex relaxations via the statistical query complexity Tuesday, February 14, 2017 - 4:00pm to 5:00pm Abstract:
	Silvio Micali: ALGORAND: The True Public Ledger Tuesday, February 7, 2017 - 4:00pm to 5:00pm ABSTRACT
	Ola Svensson: Small Extended Formulations via Monotone Circuits of Small Depth Tuesday, December 13, 2016 - 4:00pm to 5:00pm Abstract: Extended formulations have received considerable amount of attention recently, mostly for proving impossibility results. These are results of the following
	Gil Cohen: Recent Advances in Randomness Extractors and Their Applications Tuesday, December 6, 2016 - 4:00pm to 5:00pm Abstract:
	Tim Roughgarden: How Computer Science Informs Modern Auction Design Tuesday, November 29, 2016 - 4:00pm to 5:00pm Abstract : Economists have studied the theory and practice of auctions for decades. How can computer science contribute? Using the ongoing U.S.

Pages