We typically have seminars on Wednesday at noon in Malone 228. All seminar announcements will be sent to the theory mailing list.

Speaker: Christopher Musco

Affiliation: NYU

Title: Structured Covariance Estimation

Abstract:

Given access to samples from a distribution D over d-dimensional vectors, how many samples are necessary to learn the distribution’s covariance matrix, T? Moreover, how can we leverage a priori knowledge about T’s structure to reduce this sample complexity?

I will discuss this fundamental statistical problem in the setting where T is known to have Toeplitz structure. Toeplitz covariance matrices arise in countless signal processing applications, from wireless communications, to medical imaging, to time series analysis. In many of these applications, we are interested in learning algorithms that only view a subset of entries in each d-dimensional vector sample from D. We care about minimizing two notions of sample complexity 1) the total number of vector samples taken and 2) the number of entries accessed in each vector sample. The later goal typically equates to minimizing equipment or hardware requirements.

I will present several new non-asymptotic bounds on these sample complexity measures. We will start by taking a fresh look at classical and widely used algorithms, including methods based on selecting entries from each sample according to a “sparse ruler”. Then, I will introduce a novel sampling and estimation strategy that improves on existing methods in many settings. Our new approach for learning Toeplitz structured covariance utilizes tools from random matrix sketching, leverage score sampling for continuous signals, and sparse Fourier transform algorithms. It fits into a broader line of work which seeks to address fundamental problems in signal processing using tools from theoretical computer science and randomized numerical linear algebra.

Bio:

Christopher Musco is an Assistant Professor in the Computer Science and Engineering department at NYU’s Tandon School of Engineering. His research focuses on the algorithmic foundations of data science and machine learning. Christopher received his Ph.D. in Computer Science from the Massachusetts Institute of Technology and B.S. degrees in Applied Mathematics and Computer Science from Yale University.

Speaker: Guy Kortsarz

Affiliation: Rutgers Universty – Camden

Title: A survey on the Directed Steiner tree problem

Abstract:

The directed Steiner problem is one of the most important problems in optimization, and in particular is more general than Group Steiner and other problems.

I will discuss the (by now classic) 1/\epsilon^3 n^epsilon approximation for the problem by Charikar et al (the algorithm was invented by Kortsarz and Peleg and is called recursive greedy. A technique who people in approximation should know). The running time is more than n^{1/epsilon}. One of the most important open questions in Approximation Algorithms is if there is a polynomial time polylog ratio for this problem. This is open from 1997.

I will discuss the Group Steiner problem ( a special case of the Directed Steiner problem) and the Directed Steiner Forest (a generalization of the Directed Steiner problem) and many more related problems.

Speaker: Jiapeng Zhang

Affiliation: Harvard University

Title:An improved sunflower bound

Abstract:

Speaker: Robert Krauthgamer

Affiliation: Weizmann Institute of Science

Title: On Solving Linear Systems in Sublinear Time

Abstract:

I will discuss sublinear algorithms that solve linear systems locally. In

the classical version of this problem, the input is a matrix S and a vector

b in the range of S, and the goal is to output a vector x satisfying Sx=b.

We focus on computing (approximating) one coordinate of x, which potentially

allows for sublinear algorithms. Our results show that there is a

qualitative gap between symmetric diagonally dominant (SDD) and the more

general class of positive semidefinite (PSD) matrices. For SDD matrices, we

develop an algorithm that runs in polylogarithmic time, provided that S is

sparse and has a small condition number (e.g., Laplacian of an expander

graph). In contrast, for certain PSD matrices with analgous assumptions, the

running time must be at least polynomial.

Joint work with Alexandr Andoni and Yosef Pogrow.

Speaker: Yasamin Nazari

Affiliation: Johns Hopkins University

Title: Sparse Hopsets in Congested Clique

Abstract:

Speaker: Richard Shea

Affiliation: Applied and Computational Math program, Johns Hopkins University

Title: Progress towards building a Dynamic Hawkes Graph

Abstract:

Speaker: Aditya Krishnan

Affiliation: Johns Hopkins University

Title: TBD

Abstract: TBD

Speaker: Arnold Filtser

Affiliation: Columbia University

Title: TBD

Abstract: TBD