The Power of Two Matrices in Spectral Algorithms

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,700
Published on ● Video Link: https://www.youtube.com/watch?v=9_zZDEvmRWk


Duration: 14:16
303 views
3

Souvik Dhara (University of California, Berkeley)
https://simons.berkeley.edu/talks/power-two-matrices-spectral-algorithms
Meet the Fellows Welcome Event Fall 2022

Spectral algorithms are some of the main tools in optimization and inference problems on graphs. Typically, the graph is encoded as a single matrix and eigenvectors and eigenvalues of the matrix are then used to solve the given graph problem. Spectral algorithms have been quite successful for graph partitioning problems among other applications. In this talk, I will present a scenario for graph partitioning with censored edges where spectral algorithms with a single encoding matrix is suboptimal. However, if we use multiple encoding matrices instead of one, that achieves optimality and leads to a much powerful and flexible class of algorithms. This is joint work with Julia Gaudio, Elchanan Mossel, Colin Sandon



Other Videos By Simons Institute for the Theory of Computing


2022-09-10Beyond Worst Case Analysis in ML
2022-09-09Pseudorandom Generators and Small-Space Derandomization
2022-09-09Competitive Control
2022-09-09Machine Learning on Large-Scale Graphs
2022-09-09Adaptive Online Learning without Prior Knowledge
2022-09-09Incentive-Aware Machine Learning
2022-09-09How Robust Is the Gittins Index? A Queueing Case Study
2022-09-09Quantum Scientific Computation
2022-09-09Quantum Algorithms for Hamiltonian Simulation with Unbounded Operators
2022-09-09Recent Trends in Minimum Cut Algorithms
2022-09-09The Power of Two Matrices in Spectral Algorithms
2022-09-09Approximately Efficient Bilateral Trade
2022-09-09Exploration for Algorithmic Fairness
2022-09-09On universal portfolios with continuous side information
2022-09-09Estimation of Games under No Regret
2022-09-09Misinformation, Persuasion, and News Media on Social Networks
2022-09-08Transmission Neural Networks: From Virus Spread Models to Neural Networks
2022-09-08Understanding the Geometry of Graph Neural Networks
2022-09-08Diversity and inequality in social networks
2022-09-08Birds of a Feather Flock Together: How Homophily Leads to Segregation, Inequality, and...
2022-09-03Graphons and Graph Limits 3


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing
Meet the Fellows Welcome Event Fall 2022
Souvik Dhara