Search for tag: "arc colloquium"

Nikhil Devanur - Lagrangian Duality in Mechanism Design

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…

From  Kathryn Gentilello on October 14th, 2019 1 plays 0  

Shipra Agrawal - Thompson Sampling for learning in online decision making

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…

From  Kathryn Gentilello on October 7th, 2019 13 plays 0  

Moses Charikar - Approximating Profile Maximum Likelihood Efficiently

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…

From  Kathryn Gentilello on September 30th, 2019 3 plays 0  

Aleksandar Nikolov - The Power of Factorization Mechanisms in Differential Privacy

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…

From  Kathryn Gentilello on August 28th, 2019 5 plays 0  

Yin Tat Lee - Solving Linear Programs in the Current Matrix Multiplication Time

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…

From  Kathryn Gentilello on May 23rd, 2019 11 plays 0  

Will Perkins - Abstract polymer models, the cluster expansion, and applications

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…

From  Kathryn Gentilello on May 22nd, 2019 2 plays 0  

Ola Svensson - Lecture 2: Different approaches for asymmetric TSP

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…

From  Kathryn Gentilello on May 3rd, 2019 7 plays 0  

Ola Svensson - Lecture 3: A constant-factor approximation algorithm for asymmetric TSP

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…

From  Kathryn Gentilello on May 3rd, 2019 13 plays 0  

Kunal Talwar - Amplification Theorems for Differentially Private Machine Learning

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…

From  Kathryn Gentilello on April 2nd, 2019 19 plays 0  

Will Perkins - Algorithmic Pirogov-Sinai theory

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…

From  Kathryn Gentilello on November 12th, 2018 12 plays 0  

Sampath Kannan - Fairness in Algorithmic Decision Making

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…

From  Kathryn Gentilello on November 7th, 2018 22 plays 0  

Lap Chi Lau - The Paulsen problem, continuous operator scaling, and smoothed analysis

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…

From  Kathryn Gentilello on October 18th, 2018 16 plays 0  

Mary Wootters - Improved Decoding of Folded Reed-Solomon and Multiplicity Codes

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. …

From  Kathryn Gentilello on October 9th, 2018 21 plays 0  

Tselil Schramm - (Nearly) Efficient Algorithms for the Graph Matching Problem in Correlated Random Graphs

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…

From  Kathryn Gentilello on October 1st, 2018 47 plays 0  

Anand Louis - On the complexity of clustering problems

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…

From  Kathryn Gentilello on September 12th, 2018 45 plays 0  

Entropy, Log-Concavity, and a Deterministic Approximation Algorithm for Counting Bases of Matroids - Nima Anari

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.,…

From  Kathryn Gentilello on May 16th, 2018 32 plays 0