Algorithms and Complexity Seminar

A&C Seminar: Optimality and sub-optimality 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 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 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 Pseudo-deterministic NC
Wednesday, September 21, 2016 - 4:00pm to 5:00pm
Pseudo-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 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 Brascamp-Lieb Inequalities
Thursday, August 4, 2016 - 4:00pm to 5:00pm

The 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: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 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:00pm

Low-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 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 k-junta distributions.

Deterministic Time-Space Tradeoffs for k-SUM
Wednesday, June 8, 2016 - 4:00pm to 5:00pm

Given a set of numbers, the k-SUM problem asks for a subset of k numbers that sums to zero.


Subscribe to Algorithms and Complexity Seminar