Fast and Space Efficient Algorithms for Spectral Approximation
Event details
| Date | 11.06.2018 |
| Hour | 14:00 › 16:00 |
| Speaker | Navid Nouri |
| Location | |
| Category | Conferences - Seminars |
EDIC candidacy exam
Exam president: Prof. Emre Telatar
Thesis advisor: Prof. Michael Kapralov
Co-examiner: Prof. Ola Svensson
Abstract
Graphs and matrices are a common abstraction for representing real-world networks, and efficient algorithms for graph problems are at the core of large data analysis. The problem of designing compressed representations for graphs that preserve their structure has received a lot of attention in the literature recently, but many exciting directions remain open. This thesis will focus on designing such compressed representations that can be efficiently maintained and queried. Specific directions include efficient graph sketches that preserve spectral structure of graphs, lower bounds for graph sketches that preserve shortest path distances, as well spectral approximations to kernel matrices
Background papers
Localization of Electrical Flows, by A. Schild, S. Rao.
Optimal Data-Dependent Hashing for Approximate Near Neighbors, by A. Andoni, I. Razenshteyn.
Efficient \tilde{O}(n/\eps) Spectral Sketches for the Laplacian and its Pseudoinverse, by A. Jambulapati, A. Sidford
Exam president: Prof. Emre Telatar
Thesis advisor: Prof. Michael Kapralov
Co-examiner: Prof. Ola Svensson
Abstract
Graphs and matrices are a common abstraction for representing real-world networks, and efficient algorithms for graph problems are at the core of large data analysis. The problem of designing compressed representations for graphs that preserve their structure has received a lot of attention in the literature recently, but many exciting directions remain open. This thesis will focus on designing such compressed representations that can be efficiently maintained and queried. Specific directions include efficient graph sketches that preserve spectral structure of graphs, lower bounds for graph sketches that preserve shortest path distances, as well spectral approximations to kernel matrices
Background papers
Localization of Electrical Flows, by A. Schild, S. Rao.
Optimal Data-Dependent Hashing for Approximate Near Neighbors, by A. Andoni, I. Razenshteyn.
Efficient \tilde{O}(n/\eps) Spectral Sketches for the Laplacian and its Pseudoinverse, by A. Jambulapati, A. Sidford
Practical information
- General public
- Free
Contact
- EDIC - [email protected]