|
|
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
|
|
|
I
will give two lectures introducing abstract polymer models and the cluster
expansion from statistical physics. I will describe some of the original
applications of these tools in statistical…
name
Will Perkins Date
May 6th, 2019
|
|
|
The traveling salesman problem is one of the most fundamental optimization problems. Given n cities and pairwise distances, it is the problem of finding a tour of minimum distance that visits each…
name
Ola Svensson Date
April 24th, 2019
|
|
|
The traveling salesman problem is one of the most fundamental optimization problems. Given n cities and pairwise distances, it is the problem of finding a tour of minimum distance that visits each…
name
Ola Svensson Date
April 25th, 2019
|
|
|
A rigorous foundational approach to private data analysis has emerged in theoretical computer science in the last decade, with differential privacy and its close variants playing a central role. We…
name
Kunal Talwar Date
April 1st, 2019
|
|
|
In this talk we construct a net around the unit sphere with good properties. We show that with exponentially high probability, the value of |Ax| on the sphere can be approximated well using this net,…
name
Galyna Livshyts Date
February 11th, 2019
|
|
|
Stochastic Gradient Descent-type (SGD) algorithms have been widely applied to many non-convex optimization problems in machine learning, e.g., training deep neural networks, variational Bayesian…
name
Tuo Zhao Date
February 11th, 2019
|
|
|
Selfish behavior can often lead to suboptimal outcome for all participants, a phenomenon illustrated by many classical examples in game theory. Over the last decade we have studied Nash equilibria…
name
Éva Tardos Date
February 11th, 2019
|
|
|
What underlying mathematical structure (or lack thereof) in a computational problem governs its efficient solvability (or dictates its hardness)? In the realm of constraint satisfaction problems…
name
Venkat Guruswami Date
December 3rd, 2018
|
|
|
I will go over some of my past and present work on hashing-based data structures. After presenting some background on Bloom filters and cuckoo hashing, we will describe cuckoo filters, an efficient…
name
Michael Mitzenmacher Date
November 26th, 2018
|
|
|
We develop efficient algorithms to approximate the partition function and sample from the hard-core and Potts models on lattices at sufficiently low temperatures in the phase coexistence regime. In…
name
Will Perkins Date
November 5th, 2018
|
|
|
In this talk we survey some formulations of fairness requirements for decision making under uncertainty. We then discuss results from 3 recent papers:1) Treating individuals fairly is not in conflict…
name
Sampath Kannan Date
October 29th, 2018
|
