Theory of Computation (TOC) Seminar

Andrea Montanari: The landscape of some statistical problems
Wednesday, April 19, 2017 - 4:30pm to 5:30pm

Abstract:  Most high-dimensional estimation and prediction methods propose to minimize a cost function
(empirical risk) that is written as a sum of losses associated to each data point (each example).

Virginia Vassilevska Williams: Fast distance product of bounded difference matrices with applications to Language Edit Distance and RNA-Folding
Tuesday, April 11, 2017 - 4:00pm to 5:00pm
Abstract:  The distance product of two matrices A and B is the matrix C defined as C[i,j]=min_k A[i,k]+B[k,j].
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 difficult is it to find 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
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


Subscribe to Theory of Computation (TOC) Seminar