Spectral Algorithms
Event details
| Date | 28.08.2019 |
| Hour | 15:00 › 17:00 |
| Speaker | Grzegorz Adam Gluch |
| Location | |
| Category | Conferences - Seminars |
EDIC candidacy exam
Exam president: Prof. Ola Svensson
Thesis advisor: Prof. Michael Kapralov
Thesis co-advisor: Prof. Rüdiger Urbanke
Co-examiner: Prof. Friedrich Eisenbrand
Abstract
Linear algebraic approaches to graph processing have played a crucial role in several recent developments in graph partitioning, solving linear systems and more. In this research proposal we discuss several recent results in spectral graph partitioning together with promising directions for improving them to optimality. We also discuss space lower bounds for numerical linear algebra in small space models, namely lower bounds for solving linear systems over reals from streams of i.i.d. samples in subquadratic space. We also discuss an exciting conjecture that the sample complexity of the problem becomes worse if the underlying matrix has poor spectral properties (large condition number).
Background papers
Multi-way spectral partitioning and higher-order Cheeger inequalities, by James R. Lee, et al.
Memory-Sample Tradeoffs for Linear Regression with Small Error, by Vatsal Sharan, et al.
Almost Optimal Local Graph Clustering Using Evolving Sets, by Reid Andersen
Exam president: Prof. Ola Svensson
Thesis advisor: Prof. Michael Kapralov
Thesis co-advisor: Prof. Rüdiger Urbanke
Co-examiner: Prof. Friedrich Eisenbrand
Abstract
Linear algebraic approaches to graph processing have played a crucial role in several recent developments in graph partitioning, solving linear systems and more. In this research proposal we discuss several recent results in spectral graph partitioning together with promising directions for improving them to optimality. We also discuss space lower bounds for numerical linear algebra in small space models, namely lower bounds for solving linear systems over reals from streams of i.i.d. samples in subquadratic space. We also discuss an exciting conjecture that the sample complexity of the problem becomes worse if the underlying matrix has poor spectral properties (large condition number).
Background papers
Multi-way spectral partitioning and higher-order Cheeger inequalities, by James R. Lee, et al.
Memory-Sample Tradeoffs for Linear Regression with Small Error, by Vatsal Sharan, et al.
Almost Optimal Local Graph Clustering Using Evolving Sets, by Reid Andersen
Practical information
- General public
- Free