|
|
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
05/20/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
05/06/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
04/24/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
04/25/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
04/01/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
11/05/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
10/29/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
10/15/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
10/01/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
09/24/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
09/10/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
05/30/2018
|
|
|
We study the edge query complexity of graph isomorphism in the property testing model for dense graphs. We give an algorithm that makes n^{1+o(1)} queries, improving on the previous best bound of…
name
Xiaorui Sun Date
03/12/2018
|
|
|
We give an $m^{1+o(1)}\beta^{o(1)}$-time algorithm for generating uniformly random spanning trees in weighted graphs with max-to-min weight ratio $\beta$. In the process, we illustrate how…
name
Aaron Schild Date
02/12/2018
|
|
|
Quantum computers are proposed devices that would exploit quantum mechanics to solve certain specific problems dramatically faster than we know how to solve them with today's computers. In the…
name
Scott Aaronson Date
12/04/2017
|
|
|
There are several works characterizing the total-variation mixing time of a reversible Markov chain in term of natural probabilistic concepts such as stopping times and hitting times. In contrast,…
name
Jonathan Hermon Date
11/27/2017
|
