Search for tag: "dom"

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 3 Weeks ago 12 views 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 2 Months ago 6 views 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 2 Months ago 8 views 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 2 Months ago 14 views 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 4 Months ago 8 views 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 4 Months ago 17 views 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 5 Months ago 12 views 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 5 Months ago 18 views 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 6 Months ago 16 views 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 6 Months ago 37 views 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 7 Months ago 31 views 0  

A Friendly Smoothed Analysis of the Simplex Method - Daniel Dadush

Explaining the excellent practical performance of the simplex method for linear programming has been a major topic of research for over 50 years. One of the most successful frameworks for…

From  Kathryn Gentilello 11 Months ago 28 views 0  

On the infection time of the Duarte model: the role of energy barriers - Fabio Martinelli

In the Duarte model each vertex of Z <Superscript> 2 can be either infected or healthy. In the bootstrap percolation model version, infected vertices stay infected while a healthy vertex…

From  Kathryn Gentilello 11 Months ago 7 views 0  

Cutoff with window for the random to random shuffle - Megan Bernstein

Cutoff is a remarkable property of many Markov chains in which they after number of steps abruptly transition in a smaller order window from an unmixed to a mixed distribution. Most random walks on…

From  Kathryn Gentilello 11 Months ago 10 views 0  

Sphere packings, codes, and kissing numbers via hard core models - Will Perkins

We prove a lower bound on the expected size of a spherical code drawn from a "hard cap" model and the expected density of a packing drawn from the hard sphere model in high dimensions.…

From  Kathryn Gentilello 11 Months ago 11 views 0  

Inapproximability of the Independent Set Polynomial in the Complex Plane - Daniel Stefankovic

Hard-core model (also known as independent set polynomial) is one of the simplest models in statistical physics. The complexity of approximating the value of the partition function of the model on…

From  Kathryn Gentilello 11 Months ago 11 views 0