Applying Randomized Methods for Zonotope Enumeration and...

on YouTube ↗29m

" summary

Two open problems are presented: empirical eigenvalue histograms for the triangle-weighted Laplacian of Erdős–Rényi graphs consistently defy semicircle and Marchenko–Pastur fits — what is the limiting distribution and why does triangle preprocessing improve stochastic block model cuts? and a practical randomized routine for zonotope vertex sampling (sign(G^T x) construction) yields vertices with frequency matching normal cone proportionality and gives excellent results for low-rank correlation clustering — can one prove approximation guarantees or design better sampling to target useful vertices?

AI-written summary · about

" chapters (11)

1. 0:00Intro
2. 3:30The eigenvalues of the normalized Laplacian of this weighted matrix do not follow a Marchenko-Pastur law Method.
3. 7:51Correlation clustering involves a weighted, signed graph
4. 11:14What happens for other low-rank matrices?
5. 13:29Vector partitioning formulation
6. 15:00A zonotope is the linear projection of a hypercube into a lower dimension
7. 15:56A really simple randomized algorithm to get a vertex of the zonotope
8. 19:11Prob.that a vertex is generated depends on normal cone
9. 20:36Vertices of the signing zonotope correspond to clusterings
10. 22:55For a rank-3 problem on clustering conferences
11. 24:39Summary. Here are my two questions!

" related talks

• 01h 04mRandomized Embeddings and Neural NetworksMert Pilanci · Sketching and Algorithm Design 2023
• 27mSampling Algorithms to Count Frequent Patterns in GraphsAli Pinar · Parallel and Distributed Algorithms for Inference and Optimization (Simons Institute, Oct. 21–24, 2013)
• 47mCrowdsourcing for Clustering: Algorithms and Information-Theoretic Lower BoundsBabak Hassibi · Real-Time Decision Making
• 01h 03mSampling for Linear Algebra, Statistics, and Optimization IMichael Mahoney · Foundations of Data Science Boot Camp 2018
• 35mLocal Statistics, Semidefinite Programming, and Community Detection IISidhanth Mohanty · Computational Phase Transitions (Simons Institute, 2020)
• 41mGeneral Network Models with Transitive StructuresSharmodeep Bhattacharyya · Statistics in the Big Data Era 2022
• 49mRecent Advances in Counting Sparse GraphsSourav Chatterjee · Random Instances and Phase Transitions (Simons Institute, 2016)
• 44mSomething for Almost Nothing: Advances in Sub-Linear Time AlgorithmsRonitt Rubinfeld · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)