|
|
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
|
|
|
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
|
|
|
The Paulsen problem is a basic open problem in operator theory. We define a continuous version of the operator scaling algorithm to solve this problem. A key step is to show that the continuous…
name
Lap Chi Lau Date
October 15th, 2018
|
|
|
List-decoding is an important primitive in the theory of error correcting codes, and it has long been a goal to obtain explicit constructions of capacity-achieving, efficiently list-decodable codes. …
name
Mary Wootters biography
Mary Wootters is an Assistant Professor of Computer Science and Electrical Engineering at Stanford University. Date
October 1st, 2018
|
|
|
The Graph Matching problem is a robust version of the Graph Isomorphism problem: given two not-necessarily-isomorphic graphs, the goal is to find a permutation of the vertices which maximizes the…
name
Tselil Schramm biography
Tselil Schramm is a postdoc in theoretical computer science at Harvard and MIT. Date
September 24th, 2018
|
|
|
Euclidean k-means clustering, a problem having numerous applications, is NP-hard in the worst case but often solved efficiently in practice using simple heuristics. A quest for understanding the…
name
Anand Louis Date
September 10th, 2018
|
|
|
We give a deterministic 2^O(rank) approximation algorithm to count the number of bases of a given matroid and the number of common bases of any two matroids. Based on a lower bound of Azar et al.,…
name
Nima Anari Date
May 30th, 2018
|
