Search for tag: "algorithms"

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 A month ago 5 views 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 A month ago 1 views 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 A month ago 6 views 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 A month ago 10 views 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 2 Months ago 14 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 4 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 4 Months ago 18 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 4 Months ago 21 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 6 Months ago 11 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 6 Months ago 30 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 7 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 7 Months ago 21 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 8 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 8 Months ago 44 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 9 Months ago 37 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 A year ago 29 views 0