Search for tag: "randomness"

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  

Galyna Livshyts - A Tight Net with Respect to a Random Matrix Norm and Applications to Estimating Singular Values

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

From  Kathryn Gentilello on February 14th, 2019 9 plays 0  

Tuo Zhao - Towards Understanding First Order Algorithms for Nonconvex Optimization in Machine Learning

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…

From  Kathryn Gentilello on February 14th, 2019 23 plays 0  

Éva Tardos - Learning and Efficiency of Outcomes in Games

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…

From  Kathryn Gentilello on February 14th, 2019 26 plays 0  

Venkat Guruswami - The polymorphic gateway between structure and algorithms: Beyond CSPs

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…

From  Kathryn Gentilello on December 5th, 2018 14 plays 0  

Michael Mitzenmacher - Bloom Filters, Cuckoo Hashing, Cuckoo Filters, Adaptive Cuckoo Filters, and Learned Bloom Filters

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…

From  Kathryn Gentilello on December 3rd, 2018 55 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