Search for tag: "search algorithms"

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 6 Days ago 2 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 6 Days ago 2 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 6 Days ago 4 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 2 Months ago 3 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 2 Months ago 10 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 3 Months ago 5 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 3 Months ago 16 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 4 Months ago 13 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 4 Months ago 22 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 5 Months ago 29 views 0