Search for tag: "randomness"

92 Media

59:18 Yin Tat Lee - Solving Linear Programs in the… Yin Tat Lee - Solving Linear Programs in the Current Matrix Multiplication Time	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… arc colloquium algorithms and randomness center georgia tech recorded by gtlibrary spring 2019 From Kathryn Gentilello 2 Months ago 10 views 0 name Yin Tat Lee Date 05/20/2019
54:51 Will Perkins - Abstract polymer models, the… Will Perkins - Abstract polymer models, the cluster expansion, and applications	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… algorithms and randomness center arc colloquium georgia tech recorded by gtlibrary spring 2019 From Kathryn Gentilello 2 Months ago 1 views 0 name Will Perkins Date 05/06/2019
01:39:41 Ola Svensson - Lecture 2: Different approaches… Ola Svensson - Lecture 2: Different approaches for asymmetric TSP	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… algorithms and randomness center arc colloquium georgia tech recorded by gtlibrary spring 2019 From Kathryn Gentilello 3 Months ago 6 views 0 name Ola Svensson Date 04/24/2019
01:46:36 Ola Svensson - Lecture 3: A constant-factor… Ola Svensson - Lecture 3: A constant-factor approximation algorithm for asymmetric TSP	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… algorithms and randomness center arc colloquium georgia tech recorded by gtlibrary spring 2019 From Kathryn Gentilello 3 Months ago 13 views 0 name Ola Svensson Date 04/25/2019
59:16 Kunal Talwar - Amplification Theorems for… Kunal Talwar - Amplification Theorems for Differentially Private Machine Learning	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… algorithms and randomness center arc colloquium georgia tech recorded by gtlibrary spring 2019 From Kathryn Gentilello 4 Months ago 17 views 0 name Kunal Talwar Date 04/01/2019
28:03 Galyna Livshyts - A Tight Net with Respect to a… Galyna Livshyts - A Tight Net with Respect to a Random Matrix Norm and Applications to Estimating Singular Values	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,… arc12 distinguished lecture algorithms and randomness center college of computing georgia tech recorded by gtlibrary spring 2019 From Kathryn Gentilello 6 Months ago 7 views 0 name Galyna Livshyts Date 02/11/2019
25:25 Tuo Zhao - Towards Understanding First Order… Tuo Zhao - Towards Understanding First Order Algorithms for Nonconvex Optimization in Machine Learning	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… arc12 distinguished lecture algorithms and randomness center college of computing georgia tech recorded by gtlibrary spring 2019 From Kathryn Gentilello 6 Months ago 21 views 0 name Tuo Zhao Date 02/11/2019
51:59 Éva Tardos - Learning and Efficiency of… Éva Tardos - Learning and Efficiency of Outcomes in Games	É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… arc12 distinguished lecture algorithms and randomness center college of computing georgia tech recorded by gtlibrary spring 2019 From Kathryn Gentilello 6 Months ago 24 views 0 name Éva Tardos Date 02/11/2019
57:06 Venkat Guruswami - The polymorphic gateway… Venkat Guruswami - The polymorphic gateway between structure and algorithms: Beyond CSPs	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… georgia tech fall 2018 algorithms and randomness center recorded by gtlibrary From Kathryn Gentilello 8 Months ago 12 views 0 name Venkat Guruswami Date 12/03/2018
57:52 Michael Mitzenmacher - Bloom Filters, Cuckoo… Michael Mitzenmacher - Bloom Filters, Cuckoo Hashing, Cuckoo Filters, Adaptive Cuckoo Filters, and Learned Bloom Filters	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… algorithms and randomness center triad distinguished lecture series georgia tech recorded by gtlibrary fall 2018 From Kathryn Gentilello 8 Months ago 44 views 0 name Michael Mitzenmacher Date 11/26/2018
53:17 Will Perkins - Algorithmic Pirogov-Sinai theory Will Perkins - Algorithmic Pirogov-Sinai theory	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… arc colloquium algorithms and randomness center georgia tech recorded by gtlibrary fall 2018 From Kathryn Gentilello 9 Months ago 12 views 0 name Will Perkins Date 11/05/2018
01:00:03 Sampath Kannan - Fairness in Algorithmic Decision… Sampath Kannan - Fairness in Algorithmic Decision Making	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… arc colloquium algorithms and randomness center georgia tech recorded by gtlibrary fall 2018 From Kathryn Gentilello 9 Months ago 22 views 0 name Sampath Kannan Date 10/29/2018
01:00:19 Lap Chi Lau - The Paulsen problem, continuous… Lap Chi Lau - The Paulsen problem, continuous operator scaling, and smoothed analysis	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… arc colloquium algorithms and randomness center georgia tech recorded by gtlibrary fall 2018 From Kathryn Gentilello 10 Months ago 16 views 0 name Lap Chi Lau Date 10/15/2018
48:43 Tselil Schramm - (Nearly) Efficient Algorithms… Tselil Schramm - (Nearly) Efficient Algorithms for the Graph Matching Problem in Correlated Random Graphs	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… arc colloquium algorithms and randomness center georgia tech recorded by gtlibrary fall 2018 From Kathryn Gentilello 10 Months ago 46 views 0 name Tselil Schramm biography Tselil Schramm is a postdoc in theoretical computer science at Harvard and MIT. Date 09/24/2018
53:06 Anand Louis - On the complexity of clustering… Anand Louis - On the complexity of clustering problems	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… arc colloquium georgia tech algorithms and randomness center recorded by gtlibrary fall 2018 From Kathryn Gentilello 11 Months ago 42 views 0 name Anand Louis Date 09/10/2018
50:08 A Friendly Smoothed Analysis of the Simplex… A Friendly Smoothed Analysis of the Simplex Method - Daniel Dadush	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… workshop on algorithms and randomness algorithms and randomness center georgia tech recorded by gtlibrary spring 2018 From Kathryn Gentilello A year ago 29 views 0 name Daniel Dadush Date 05/17/2018