A&C Seminar: Optimality and suboptimality of PCA for spiked random matrix models Wednesday, October 19, 2016  4:00pm to 5:00pm Classical results from random matrix theory state that if a random (Wigner or Wishart) matrix is perturbed by a planted rank1 signal (or "spike"), this spike affects the top eigenvalue if and only if the size of the spike exceeds a particular threshold. 

A&C Seminar: Approximate Gaussian Elimination for Laplacians Wednesday, September 28, 2016  3:00pm to 4:00pm Abstract:We show how to perform sparse approximate Gaussian elimination for Laplacian matrices. 

A&C Seminar: Bipartite Perfect matching in Pseudodeterministic NC Wednesday, September 21, 2016  4:00pm to 5:00pm Pseudodeterministic algorithms are randomized search algorithms that on different executions on the same input, output the same solution with high probability.


On the Rigidity of Sparse Random Graphs Tuesday, August 23, 2016  4:00pm to 5:00pm It is a truth universally acknowledged, that random objects are asymmetric. It was shown by Wright (1971) that for p slightly larger than logn / n a random G(n,p) graph has, whp, a trivial automorphism group. 

Talk: Brendan Juba: Conditional Sparse Linear Regression Wednesday, August 24, 2016  4:00pm to 5:00pm We consider the problem of jointly identifying a significant (but perhaps small) segment of a population in which there is a highly sparse linear regression fit, together with the coefficients for the linear fit. 

Talk: On Algorithmic Aspects of BrascampLieb Inequalities Thursday, August 4, 2016  4:00pm to 5:00pm The celebrated BrascampLieb (BL) inequalities (and their extensions) are an important mathematical tool, unifying and generalizing numerous inequalities in analysis, convex geometry and information theory. 

Ali Vakilian:Streaming Algorithms for Set Cover Problem Wednesday, July 20, 2016  4:00pm to 5:00pm We consider the classic Set Cover problem in the data stream model. For $n$ elements and $m$ sets we give a $O(1/\delta)$pass algorithm with a strongly sublinear $\tldO(mn^{\delta})$ space and logarithmic approximation factor. 

TALK:Christopher Musco:Iterative Sampling Methods for LowRank Matrix and Kernel Approximation Wednesday, July 6, 2016  4:00pm to 5:00pm Lowrank matrix approximation and its close relative, principal component analysis, are ubiquitous in statistics and machine learning. To address computational concerns as data size increases, recent years have a seen a flurry of work on fast approximation algorithms for these problems. 

Learning and Testing Junta Distributions Wednesday, June 15, 2016  4:00pm to 4:30pm Abstract: We consider the problem of learning distributions in the presence of irrelevant features. This problem is formalized by introducing a new notion of kjunta distributions. 

Deterministic TimeSpace Tradeoffs for kSUM Wednesday, June 8, 2016  4:00pm to 5:00pm Given a set of numbers, the kSUM problem asks for a subset of k numbers that sums to zero. 