Theory of Computation (TOC) Seminar

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
Vitaly Feldman: Lower bounds against convex relaxations via the statistical query complexity
Tuesday, February 14, 2017 - 4:00pm to 5:00pm


Silvio Micali: ALGORAND: The True Public Ledger
Tuesday, February 7, 2017 - 4:00pm to 5:00pm


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

Yuval Ishai: Succinct Secure Computation from DDH
Tuesday, November 8, 2016 - 4:00pm to 5:00pm



Ronitt Rubinfeld: Local Computation Algorithms
Tuesday, November 1, 2016 - 4:00pm to 5:00pm


Consider a setting in which inputs to and outputs from a computational
problem are so large, that there is not time to read them in their
entirety.   However, if one is only interested in small parts of the

Muthuramakrishnana Venkitasubramaniam: Composable Adaptive Secure Protocols without Setup Under Polytime Assumptions
Friday, October 28, 2016 - 10:30am to 12:00pm

Abstract: All previous constructions of general multiparty computation protocols that are secure against adaptive corruptions in the concurrent setting either require some form of setup or non-standard assumptions.


Subscribe to Theory of Computation (TOC) Seminar