|
|
Local spectral expansion is a very useful method for arguing about the spectral properties of several random walk matrices over simplicial complexes. The motivation of this work is to extend this…
name
Vedat Levi Alev Date
February 10th, 2020
|
|
|
We say a probability distribution µ is spectrally independent if an associated correlation matrix has a bounded largest eigenvalue for the distribution and all of its conditional distributions.…
name
Kuikui Liu Date
January 27th, 2020
|
|
|
Robust mean estimation is the following basic estimation question: given i.i.d. copies of a random vector X in d-dimensional Euclidean space of which a small constant fraction are corrupted, how well…
name
Samuel Hopkins Date
December 2nd, 2019
|
|
|
In the 'frequent items' problem one sees a sequence of items in a stream (e.g. a stream of words coming into a search query engine likeGoogle) and wants to report a small list of items…
name
Jelani Nelson Date
September 16th, 2019
|
|
|
This talk focuses on network design algorithms for optimizing average consensus dynamics, dynamics that are widely used for information diffusion and distributed coordination in networked control…
name
Yuhao Yi Date
November 18th, 2019
|
|
|
(This is Part 2, continuation of Tuesday's lecture.)A fundamental tool used in sampling, counting, and inference problems is the Markov Chain Monte Carlo method, which uses random walks to solve…
name
Nima Anari Date
November 6th, 2019
|
|
|
A fundamental tool used in sampling, counting, and inference problems is the Markov Chain Monte Carlo method, which uses random walks to solve computational problems. The main parameter defining the…
name
Nima Anari Date
November 5th, 2019
|
|
|
In this talk we consider random utility models for discrete choice. In discrete choice, the task is to select exactly one element from a discrete set of alternatives. We focus on algorithmic…
name
Ravi Kumar Date
November 4th, 2019
|
|
|
Optimizing neural networks is a highly nonconvex problem, and even optimizing a 2-layer neural network can be challenging. In the recent years many different approaches were proposed to learn 2-layer…
name
Rong Ge Date
October 28th, 2019
|
|
|
In partial function extension, we are given a partial function consisting of points from a domain and a function value at each point.Our objective is to determine if this partial function can be…
name
Umang Bhaskar Date
October 18th, 2019
|
|
|
The Matrix Spencer Conjecture asks whether given n symmetric matrices in ℝn×n with eigenvalues in [−1,1] one can always find signs so that their signed sum has singular values bounded by…
name
Thomas Rothvoss Date
October 7th, 2019
|
|
|
This talk surveys the usage of Lagrangian Duality in the design and analysis of auctions. Designing optimal (revenue maximizing) auctions in multi-parameter settings has been among the most active…
name
Nikhil Devanur Date
September 30th, 2019
|
|
|
Modern online marketplaces feed themselves. They rely on historical data to optimize content and user-interactions, but further, the data generated from these interactions is fed back into the system…
name
Shipra Agrawal Date
September 23rd, 2019
|
|
|
Symmetric properties of distributions arise in multiple settings. For each of these, separate estimators and analysis techniques have been developed. Recently, Orlitsky et al showed that a single…
name
Moses Charikar Date
September 9th, 2019
|
|
|
A central goal in private data analysis is to estimate statistics about an unknown distribution from a dataset possibly containing sensitive information, so that the privacy of any individual…
name
Aleksandar Nikolov Date
August 19th, 2019
|
|
|
We show how to solve linear programs with accuracy epsilon in time n^{omega+o(1)} log(1/epsilon) where omega~2.3728639 is the current matrix multiplication constant. This hits a natural barrier of…
name
Yin Tat Lee Date
May 20th, 2019
|
