Search for tag: "randomness"
Kamesh Munagala - Group Fairness in Combinatorial OptimizationConsider the following classical network design model. There are n clients in a multi-graph with a single sink node. Each edge has a cost to buy, and a length if bought; typically, costlier edges…
From Katie Gentilello
2 plays
0
|
|
Vidya Muthukumar - Surprises in overparameterized linear classificationSeemingly counter-intuitive phenomena in deep neural networks and kernel methods have prompted a recent re-investigation of classical machine learning methods, like linear models. Of particular focus…
From Katie Gentilello
10 plays
0
|
|
Anupam Gupta - Finding and Counting k-cuts in GraphsFor an undirected graph with edge weights, a k-cut is a set of edges whose deletion breaks the graph into at least k connected components. How fast can we find a minimum-weight k-cut? And how many…
From Katie Gentilello
17 plays
0
|
|
Aaron Sidford - Recent Advances on the Maximum Flow ProblemThe maximum flow problem is an incredibly well-studied problem in combinatorial optimization. The problem encompasses a range of cut, matching, and scheduling problems and is a key a proving ground…
From Katie Gentilello
20 plays
0
|
|
Maryam Aliakbarpour - Distribution testing: Classical and new paradigmsOne of the most fundamental problems in learning theory is to view input data as random samples from an unknown distribution and then to make statistical inferences about the underlying distribution.…
From Katie Gentilello
31 plays
0
|
|
Vedat Levi Alev - Improved Analysis of Higher Order Random Walks and ApplicationsLocal spectral expansion is a very useful method for arguing about the spectral properties of several random walk matrices over simplicial complexes. The motivation of this work is to extend this…
From Katie Gentilello
65 plays
0
|
|
Kuikui Liu - Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore ModelWe say a probability distribution µ is spectrally independent if an associated correlation matrix has a bounded largest eigenvalue for the distribution and all of its conditional distributions.…
From Katie Gentilello
28 plays
0
|
|
Samuel Hopkins - Robust Mean Estimation in Nearly-Linear TimeRobust mean estimation is the following basic estimation question: given i.i.d. copies of a random vector X in d-dimensional Euclidean space of which a small constant fraction are corrupted, how well…
From Katie Gentilello
17 plays
0
|
|
Jelani Nelson - Some new approaches to the heavy hitters problemIn the 'frequent items' problem one sees a sequence of items in a stream (e.g. a stream of words coming into a search query engine likeGoogle) and wants to report a small list of items…
From Katie Gentilello
22 plays
0
|
|
Yuhao Yi - Fast Approximation Algorithms and Complexity Analysis for Design of Networked SystemsThis talk focuses on network design algorithms for optimizing average consensus dynamics, dynamics that are widely used for information diffusion and distributed coordination in networked control…
From Katie Gentilello
15 plays
0
|
|
Nima Anari - Rapidly Mixing Random Walks via Log-Concave Polynomials (Part 2)(This is Part 2, continuation of Tuesday's lecture.)A fundamental tool used in sampling, counting, and inference problems is the Markov Chain Monte Carlo method, which uses random walks to solve…
From Katie Gentilello
38 plays
0
|
|
Nima Anari - Rapidly Mixing Random Walks via Log-Concave Polynomials (Part 1)A fundamental tool used in sampling, counting, and inference problems is the Markov Chain Monte Carlo method, which uses random walks to solve computational problems. The main parameter defining the…
From Katie Gentilello
55 plays
0
|
|
Ravi Kumar - Algorithmic Discrete ChoiceIn this talk we consider random utility models for discrete choice. In discrete choice, the task is to select exactly one element from a discrete set of alternatives. We focus on algorithmic…
From Katie Gentilello
16 plays
0
|
|
Rong Ge - What 2-layer neural nets can we optimize?Optimizing neural networks is a highly nonconvex problem, and even optimizing a 2-layer neural network can be challenging. In the recent years many different approaches were proposed to learn 2-layer…
From Katie Gentilello
31 plays
0
|
|
Umang Bhaskar - Partial Function Extension with Applications to Learning and Property TestingIn partial function extension, we are given a partial function consisting of points from a domain and a function value at each point.Our objective is to determine if this partial function can be…
From Katie Gentilello
2 plays
0
|
|
Thomas Rothvoss - Linear Size Sparsifier and the Geometry of the Operator Norm BallThe Matrix Spencer Conjecture asks whether given n symmetric matrices in ℝn×n with eigenvalues in [−1,1] one can always find signs so that their signed sum has singular values bounded by…
From Katie Gentilello
45 plays
0
|