Algorithms and Complexity Seminar

 A&C Seminar: Rati Gelashvili: Time-Space Trade-Offs in Molecular ComputationWednesday, October 26, 2016 - 4:00pm to 5:00pm A&C Seminar: Optimality and sub-optimality of PCA for spiked random matrix modelsWednesday, October 19, 2016 - 4:00pm to 5:00pmClassical results from random matrix theory state that if a random (Wigner or Wishart) matrix is perturbed by a planted rank-1 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 LaplaciansWednesday, September 28, 2016 - 3:00pm to 4:00pmAbstract:We show how to perform sparse approximate Gaussian elimination for Laplacian matrices. A&C Seminar: Bipartite Perfect matching in Pseudo-deterministic NCWednesday, September 21, 2016 - 4:00pm to 5:00pmPseudo-deterministic 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 GraphsTuesday, August 23, 2016 - 4:00pm to 5:00pmIt 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 RegressionWednesday, August 24, 2016 - 4:00pm to 5:00pmWe 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 Brascamp-Lieb InequalitiesThursday, August 4, 2016 - 4:00pm to 5:00pmThe celebrated Brascamp-Lieb (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:00pmWe 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 sub-linear $\tldO(mn^{\delta})$ space and logarithmic approximation factor. TALK:Christopher Musco:Iterative Sampling Methods for Low-Rank Matrix and Kernel Approximation Wednesday, July 6, 2016 - 4:00pm to 5:00pmLow-rank 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 DistributionsWednesday, June 15, 2016 - 4:00pm to 4:30pmAbstract: We consider the problem of learning distributions in the presence of irrelevant features. This problem is formalized by introducing a new notion of k-junta distributions.